- If you mess up the solution up from nerves or pressure. Then what can the interviewer do but mark you down for it.
- The best solution often takes time to consider and the interviewer is doing what in that time? While you sit around thinking what is the interview thinking about your performance?
- Often if things get to slow the interviewer will start to interfere with you to speed it along. He might offer tips to you, tips that you may of may not have needed, either way he is again likely to take marks off you for having to help you.
So here is an alternate approach, its inspired in part by the the old social engineering tricks made famous by hackers. Consider for a moment what the interviewer is doing, he has a problem and he knows the solution, he also probably knows some tips or key info about the solution that can help you. SO if he isnt talking to you there is no way he can tell you them by accident.
First of all start at brute force. Call it that so the interviewer knows you know better. Talk about it and its negative points and get the interviewer involved get him talking with you about it, make him think that your his fellow peer and you two are talking about a problem at work. Then propose a fix on one of the negative points and slowly change your answer into your ideal one. This gets the interviewer use to the idea that your solution isnt final and its just a discussion point.
Pay close attention to the interviewer, if you propose a fix and the interview was to say "yes but that cant insert with 0(1) complexity" then bingo he might want a data structure like a hash. So again point out a negative of your new solution and suggest a hash and do it gradually so he doesn't catch on that what he said was your key.
Sometimes the interviewer will stay tight lipped in the case of a tight lipped interviewer run down your list of ideas on how to optimize things. Here is mine generally one.
- Divide and Conquer:
- Look at each part of the solution and see if there is any dependence between the parts how is it dependent and can it be broken apart?
- Start looking at any abnormalities in the computation, if its is excluded does the computation become simpler, can the exception to the rule be added back in in the last moment?
- Take an array or LUT and divide it in half whats the logic to merge the parts back together after the division?
- For example take an array and sum all elements but the current element only, then cant you sum the left normally and then the right normally and then add the two sums on either side together of the current point together?
- Inductive repeating computations
- Examine the nature of computation especially ones that are repeated heavily or other pieces of data, reduce it to the induction formula and see if the partial results can be shared out some how.
- For example sums are an accumulation, and that reduces into a mathematics induction formula; ie Sum(x) = Sum(x-1) + f(x)
Some worked examples:
Here are posts in which i work out a solution to the question with the above rules;
WILL EDIT AND ADD THEM LATER