How to approach the question?
NOTE - This is just my way of approaching the question. You can always have a different and better way.
- Ask clarifying questions. For ex, if array is defined then what kind of data it has, wether it's Integers or Strings. If Integers, then wether all are positive, or a mix of both positive and negative. Don't jump on the question as of now. Think through it for atleast 30 seconds. Think about kind of input you have at hand and output expected.
- Draw diagram of data structure if that helps, confirm this is what is expected. This may include drawing a linked list or a tree.
- Explain the approach to Interviewer. If you know multiple, explain all of them and why you are choosing one over the other. Explain in terms of time and space complexity.
- Once Interviewer agrees with the approach, define some basic test cases i.e validation etc.
- Check with him, if we are good to start on the code.
- Try to make your solution generic, for ex, in case of Linked List, don’t just make your solution for Integer or just String. Better to have it generic, though it comes with extra overhead of custom comparator, but that’s ok. This will for sure mark a better impression.
- You can check with Interviewer that you are thinking of a generic solution, and if that would be ok to implement.
- Keep talking aloud in whole process. Keep interviewer engaged.
- Once you are done with the solution, run through it once again using the example you defined in #2 and place appropriate comments. That way you will have a better commented code and you will revise the approach as well. Keep interviewer engaged here. Go step by step and talk aloud what is happening.
- Run through multiple test cases including edge cases (if any) you defined initially.
- If everything looks good, and you have covered all the test cases, step back and look at the code again. Don’t just say you are done.
- Double check on method signature, input params, return type etc.
- If that looks good too, we are done.