c++ interview questions on sort, qsort, merge sort, binary search
Sort the list of input characters that need to be deleted. and then binary search each char in the input string.
m = length of the list of characters to be deleted.
n = number of characters in original list.
Step 1) O( nlog(m) ) for sorting
Step 2) O ( n * log(m) ) for search
Overall : O( n log (m) )
1) Store the Input string characters in a Linked List.
2) Loop through the array of deletion chars and for those chars remove the corresponding nodes from the linked list.
3) Store the resultant linked list into another array.
4) Reverse the resultant array using swapping algorithm
Given 2 unsorted, of variable length, arrays, determine the elements not in common.
ways to solve:
linear search of each item in 1 array with the other
sort 1 then do binary search
1.Question: Suppose that data is an array of 1000 integers. Write a single function call that will sort the 100 elements data  through data .
Answer: quicksort ((data + 222), 100);
2.Question: Which recursive sorting technique always makes recursive calls to sort subarrays that are about half size of the original array?
Answer: Mergesort always makes recursive calls to sort subarrays that are about half size of the original array, resulting in O(n log n) time.
I chose Mergesort because it has good performance and the algorithm is easy to remember.
quick sort function in C (qsort)