Microsoft Software Development Engineer - II interview questions

2nd round: "What is the data structure which 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 either by place horizontally or vertically on the board. The structures should be designed such that they can support basic operations for playing a 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 coming with an O(n) solution during attack, which was my first attempt and then I was thinking about optimization. But by then the time was over and interviewer seemed unhappy with my solution or the attempt.

Solve: M is a 2D matrix of integers (nXm) they are sorted in both row and column Write a function search(int s) that return the exact location of the number or Null using lgn