|
What is the data structure which suits best for the Battleship game?.......
Microsoft Interview Questions and Answers
(Continued from previous question...)
112. What is the data structure which suits best for the Battleship game?.......
Question:
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
maybe an answer:
Things to consider here
1. How large is n?
2. How many ships should we accomidate?
3. Error checks. is the ship partially/fully outside the battleground
Assuming all normal cases
ships are numbered 1 to m
For efficiency I would assume/create a hash function which takes in i,j and returns the cell in constant time.
Use two data structures, one int 2D matrix, 0 indicates no ship a number indicates the ship number, the other data structure is a list/array of sets. Each list contains the hashed values of the ship locations.
attack(i,j) can result in three cases
1. there is no ship -
2. there is a ship, lets say 2, now go to the 2nd list and delete the hash corresponding to this cell. If the list is now empty return sunk
2a. if the list not empty continue
With this solution all operations are constant, including declaring that a ship is sunk.
(Continued on next question...)
Other Interview Questions
| 