|
What is the data structure which suits best for the Battleship game?
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
What is the data structure which suits best for the Battleship game?
Q:
Microsoft Interview Question for SDE in tests
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
(Continued on next question...)
Other Interview Questions
| 