Searching_and_Sorting

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