Skip to content

Latest commit

 

History

History

Searching_and_Sorting

README.md

Searching

Questions for practice

S. No Date Question Solution Difficulty
01. 27/09/2021 Searching in a number Java Basic
02. 27/09/2021 Searching in a sorted array Java Basic
03. 27/09/2021 Minimum Difference Pair Java   CPP Basic
04. 28/09/2021 Peak Element Java Easy
05. 30/09/2021 Search in row-column Sorted Matrix Will be uploaded Soon Easy
06. 06/10/2021 Searching in an array where adjacent differ by at most k Will be uploaded soon Easy
07. 08/10/2021 The optimal Solution Will be uploaded soon Easy
08. 11/10/2021 Check if the array is sorted or not Will be uploaded soon Easy
09. 11/10/2021 Race in fooland Will be uploaded soon

Sorting

Questions for practice

S. No Date Question Solution Difficulty
01. 28/09/2021 Sort the array Java Basic
02. 28/09/2021 Wave array Java Easy
03. 29/09/2021 Minimum difference pair Java Basic
04. 29/09/2021 Sort an array of 0s, 1s and 2s Java Easy
05. 29/09/2021 Toppers Of Class Will be uploaded soon Easy
06. 30/09/2021 Alternative Sorting Will be uploaded Soon Basic
07. 30/09/2021 Geek and his Marks Will be uploaded Soon Easy
08. 01/10/2021 Sort by set bit count Will be uploaded Soon Easy
09. 01/10/2021 kth Smallest element Will be uploaded Soon Medium
10. 03/10/2021 Insertion Sort Will be uploaded Soon Easy
11. 03/10/2021 Largest Even Number Will be uploaded Soon Easy
12. 04/10/2021 Selection sort Will be uploaded Soon Easy
13. 04/10/2021 Counting Sort Will be uploaded Soon Easy
14. 04/10/2021 Insertion Sort Will be uploaded Soon Easy
15. 05/10/2021 Bubbe sort Will be uploaded soon Easy
16. 05/10/2021 Minimum Swaps Will be uploaded soom Medium
17. 07/10/2021 Rope Cutting Will be uploaded soon Easy
18. 07/10/2021 K larger values Will be uploaded soon Easy
19. 07/10/2021 Punish the students Will be uploaded soon Easy
20. 08/10/2021 Merging two unsorted array in sorted order Will be uploaded soon Easy
21. 08/10/2021 Sorting all array elements except one Will be uploaded soon Easy

Theoritical Questions

Question 1

Which of the following is not a stable sorting algorithm in its typical implementation.

  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Bubble Sort

Question 2

Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).

  • Quick Sort
  • Heap Sort
  • Merge Sort
  • Insertion Sort

Question 3

Consider a sorted array of n numbers and a number x. What would be the time complexity of the best known algorithm to find a triplet with sum equal to x. For example, arr[] = {1, 5, 10, 15, 20, 30}, x = 40. Then there is a triplet {5, 15, 20} with sum 40.

  • O(n)
  • O(n^2)
  • O(n Log n)
  • O(n^3)

Question 4

Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

  • Insertion Sort with time complexity O(kn)
  • Heap Sort with time complexity O(nLogk)
  • Quick Sort with time complexity O(kLogk)
  • Merge Sort with time complexity O(kLogk)

Question 5

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is( GATE CS 2008)

  • Θ(n)
  • Θ(logn)
  • Θ(log*n)
  • Θ(1)

Question 6

A program P reads in 500 integers in the range [0..100] exepresenting the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies? (GATE CS 2005)

  • An array of 50 numbers
  • An array of 100 numbers
  • An array of 500 number- A dynamically allocated array of 550 numbers