Interview Questions

Over the past 12 months, I have done several face-to-face as well as phone interviews for industry based internships. As someone who loves interviews and interesting problems, most of the interviews were quite enjoyable. Admittedly I feel more relaxed during non-technical interviews but technical ones are still fun because they present an opportunity to be exposed to possibly challenging problems that you may not have encountered before. Or they may even be the same problem but in an entirely different context.

Anyway, in no way eluding to which companies interviewed me, the following were a few of the fun mind challenges I was faced with:

Battleships:

• If you were implementing a battle ship game, what data structures would you use to store information about the grid, information about the ships, information on the scoring?
• Initially think about a grid that's 20x20 with 12 ships of different sizes. How would implementation change if the grid is 1000x1000 or 100000x100000 with 12 ships of different sizes? Now consider the larger grids with 100 ships or more of different sizes?
  
• How do you determine when a player has won the game? How should you keep track of the scoring? Make sure the other player can't cheat! For example, if a player hits a particular position that contained a part of a ship, continuously hitting (spamming) that position causes him to win. This could happen if you had a counter for the number of hits and didn't keep track of distinct battleship hits.
  

Reverse:

• Given a string, reverse it.
  
• Given a number, reverse it.
  
• Given a byte, reverse it.
  
• Can you do it in place?
• Can you make it more efficient?
• How can you test your functionality?

Latex:

• My interviewer noticed I used latex to generate my resume. He asked how I felt about latex and what I found annoying. I mentioned that I noticed " and " did not turn out if I just typed " and ". To have quotations at the correct angles, `` and '' needed to be written. This problems comes from this. Given a tex file, go through and replace all the '' and '' with `` and '', assuming the text was well formed. That is, there are an even number of " in the text.
  
• Can you do it in place and in O(n) where n is the number of characters in the text?
  

Division:

• Do some division without the division operator.
• Why is recursion suboptimal?
• What would be more efficient?