Sort And Searching Interview Preparation Guide
Download PDF

Sort and Searching job test questions and answers guide. The one who provides the best answers with a perfect presentation is the one who wins the job hunting race. Learn Sort And Searching and get preparation for the new job

27 Sort And Searching Questions and Answers:

1 :: Tell me what is quick sort?

Quick sort is one the fastest sorting algorithm used for sorting a list. A pivot point is chosen. Remaining elements are portioned or divided such that elements less than the pivot point are in left and those greater than the pivot are on the right. Now, the elements on the left and right can be recursively sorted by repeating the algorithm.

2 :: What is bubble sort algorithm?

Bubble sort algorithm is used for sorting a list. It makes use of a temporary variable for swapping. It compares two numbers at a time and swaps them if they are in wrong order. This process is repeated until no swapping is needed. The algorithm is very inefficient if the list is long.

E.g. List: - 7 4 5 3
1. 7 and 4 are compared

2. Since 4 < 7, 4 is stored in a temporary variable.

3. the content of 7 is now stored in the variable which was holding 4

4. Now, the content of temporary variable and the variable previously holding 7 are swapped.

3 :: Explain binary search?

Binary search is most useful when the list is sorted. In binary search, element present in the middle of the list is determined. If the key (number to search) is smaller than the middle element, the binary search is done on the first half. If the key (number to search) is greater than the middle element, the binary search is done on the second half (right). The first and the last half are again divided into two by determining the middle element.

4 :: Do you know what is linear search?

Linear search is the simplest form of search. It searches for the element sequentially starting from the first element. This search has a disadvantage if the element is located at the end. Advantage lies in the simplicity of the search. Also it is most useful when the elements are arranged in a random order.

5 :: What is Mergesort and Hashtable?

In short:
Mergesort is a sorting algorithm that follows the paradigm of: divide and conquer:

1) recursivly split the array in 2
2) until the array length is 1 ( or the pointers start and end are equal)
3) merge the sorted array an return the array sorted

6 :: What is Binary Search Tree and explain its time complexity?

Traverse: O(n). Coz it would be visiting all the nodes once.
Search : O(log n)
Insert : O(log n)
Delete : O(log n)

Binary Search is a searching algorithm that is used on a certain data structure (ordered array) to find a if an element is within the array through a divide a conquer technique that takes the middle value of the array and compares it to the value in question. If the value is less, then compare the value in question to the lower mid-value and if greater, vice versa until you find the value or determine that it is none of the elements within the array. All a Binary Search Tree is a visual concept that allows one to see this divide a conquer technique in an easier way. For example, given : Array A = {1,2,4,6,10,20,35} we ask if the number 35 is there. First you would compare 20 to 6. 20<,>,= 6? Greater than, so compare the mid value of upper range. 35>,<,=20? greater than, compare next greater mid value. 35>,<, = 35 ? Equal. So it has been search with only three comparisons, with the worst time complexity of O(log(n)).

7 :: How to sort 1 million floating point numbers?

Radix Sort.. easily can be done.. user bitwise operations to bucket the numbers.. same algorithm can be used for negative and positive mix of fp numbers with some minor modification to the initial list

8 :: Explain which of the following is true about asort?
• Sorts highest to lowest by value maintaining key association.
• Sorts lowest to highest by key maintaining key association.
• Sorts highest to lowest by key, re-indexing the array.
• Sorts lowest to highest by value, re-indexing the array.

Sorts lowest to highest by key maintaining key association.

asort()
This function sorts an array such that array indices
maintain their correlation with the array elements they are
associated with. This is used mainly when sorting
associative arrays where the actual element order is
significant.

9 :: Tell me which of the following maintain index associations?

• ksort
• asort
• sort

These are php sorting methods.

ksort and asort maintain index associations and sort from lowest to highest. ksort sorts keys.
sort doesnt maintain index associations.

10 :: Tell me why might quick sort might be better than merge sort

Quick sort also preserves order. Merge sort has undefined behavior wrt order.