There were two rounds of phone interviews.

Round 1: "Given a linked list such that one node points to some random node, write the clone method of a linked list."

I was able to provide an approximate solution in C# using a dictionary. The interviewer was helpful and encouraging, which helped me arrive at the exact solution.

A couple of days later, I received a call back from the recruiter stating that I would be interviewed for a second round of phone interviews.

2nd round:

"What is the data structure that suits best for the Battleship game? The board will be of size n x n, with m different ships, each having k1, ..., km lengths. Each ship can be placed either horizontally or vertically on the board.

The structures should be designed to support basic operations for playing the game. For example, the board and a particular (i, j) coordinate representing a position on the board may be passed into a function attack(). The function should return 'hit' if a ship was hit at that position, 'sunk' if a ship has sunk after being attacked at that position, and 'miss' if no ship is at that position.

Describe your design of the structures, what kind of data they store, and the runtime complexity of typical operations for playing the game (like the attack() function) as a result of your design decisions."

I was considering an O(n) solution during attack(), which was my first attempt, and then I was thinking about optimization. But by then, time was over, and the interviewer seemed unhappy with my solution or my attempt.