Wish you a very happy new year!
This is an attempt to discuss a problem I’ve come across. Some common things that I would like to suggest people going for computer science interviews are –
- listen to the question with full concentration on every word; avoid wandering for the similar questions that your friend discussed this morning
- do not assume anything (even if this means asking the dumbest questions, don’t hesistate)
- if you know the problem and the solution (or you’ve been asked the same or similar question in a previous round of interview), tell them. don’t waste your and their time.
- break the problem into small tangible subsets; things that you are more comfortable working with (say a problem with million users telephone directory, think of a 50 or 10 users telephone directory or say a problem on a variation of tower of hanoi, think of the implementation of simple tower of hanoi and then move towards the special treatment) or things that are more do-able.
- think aloud; most interviewers love loud thinking
- think out of box when you cannot remember (or you do not know) a standard solution (which you are sure exists although). Everyone loves innovative ideas and believe me, they do come.
- do not make an obvious mistake while writing code. code defensively. check success of every memory allocation or file read.
- make sure you understand the Big-O notation for algorithmic time-space metric. I’ve seen that computer scientists’ are happy when you come up with more accurate O-notation understanding.
- think of design issues like portability of code, reentrancy of the code, bottleneck portions of the code (and any trade offs) etc. and discuss these with the interviewer
- if you can think of more than one solution for a problem, tell them.
Write a program to implement a binary search for generic array whose elements are sorted.
Problem is to write n implementation of binary search algorithm and twist is “generic”. The term generic itself is enough for giving you a clue into the direction of thoughts. Without the “generic” requirement, suppose a binary search algorithm is to be implemented for an array of integers, then signature is:
int binsearch(int a, int x, int n)
If you are going to implement the algorithm in C, think “void *” and if you are going to implement the algorithm in C++, think templates. Now I discuss here an implementation in C. Well my function should have an array (which will be a ‘void *’ to accommodate an array of any data type), the item to search for (again a void *), the number of elements in the array. What else?
- We do not have an idea of how to dereference the pointer available to us.
- we do not have a way to base our comparison on (e.g. this may be an array of structures sorted on an element of the structure (which obviously our algorithm is blind to)).
So we require two more arguments, size of the data structure so that we can do a typecast of ‘void * arr’ to ‘char *’ and for an index ‘i’, jump using the expression ((char*)arr + i*size) to get to the item of interest and a pointer to a function, compare, which will take two ‘void *’ and return -1, 0, 1 just like any compare function. so signature is:
int binsearch(void *arr, void *x, int n, size_t size, int (*func)(void *, void*));
Algorithm itself is not much a problem I think. It works like calculating the “mid” (for 0 to n), and then comparing the mid value with x by:
int p = compare(((char *)arr + mid*size), x);
If p == 1, search in [mid+1, n], if p == -1, search in [0, mid-1] and if p == 0, you happy, go lucky got it!
You can actually edo away with the argument “size” if you make the function signature a bit uglier by pushing the responsibility of dereferencing the arr (void *) to the user. so now your function signature code will be –
int compare(void * /* arr */, int index /* index */, void * /* tosearch */);
But this is dirtier since humans normally are in habit of a ‘compare’ with two parameters. In this new avatar your binsearch becomes –
int binsearch(void *arr, void *x, int n, int (*func)(void *, int i, void*) );