Meta Interview Question
HR: hash function search time, what is O(n)
Programming: write a function that get an int array, each int has category which can receive by a given function. category is one of (0,1,2).
eg Array[1]=20, get_category(20)=1
sort the int array by the int category.
following question, sort without addition array\space
Interview Answers
hash function = o(1), o(n) is a general running time speed of a signal program usually referring to sorting algo,
1) Would solve it with a 2nd array and placing in each cell a structure of the value and category, then placing going over it 3 times and placing all 0,1,2 in the right places , Guarntee O(3n) = O(n)
2) Would have used quick sort to sort the array - no aded array memory
Because there are only three categories, the sorting is made simple. Start with a pointer to the start and a current pointer, also at the start. scan the current pointer forward through the list. If current is a 1, swap it with the start and increment the start. Otherwise, just increment current. By the end, all the 1s will be at the start and the start pointer will point to the end of the 1s. Now do it again for the rest of the list and look for 2s. Each element is accessed a maximum of twice so linear time time and also no additional space.
#sort the array based get_category result
def sort_by_category(array):
return sorted(array, key=get_category)
how to do it without any additional memory?
I would iterate over the n elements, 3 times , in the first iteration any time I meet an int k from category 1 I'll swap
the n'th item with the n-1'th item and then swap int k with the last item.
next iteration would be done with all the 2's to the end and then 3's.
*Memory -one int var that is used for swapping two values in the array.
*Running time- O(3N)~O(N)