Microsoft Interview Question Software Engineer in Tests
yeah a 2-D array would be an ideal solution. The array can contain boolean 0s and 1s...0 to indicate absence of ship and 1 to indicate the presence of a ship...Runtime complexity in this is concerned with how fast we can acess the 2-D array elements and check for the status of the coordinates
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.
I would 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 - we ignore (unless we don't duplicate hits)
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. We can also improve this to know if the game is over
The hash function which takes (i, j) and return the cell, is actually just a call of "board[i][j]", right?
If the board dimension is fixed, what is the different between the hash solution and 2D array solution? Aren't they identical?
@Z yeah you are right, if its a constant size memory might as well go for an array, but every time the size increases resizing the array could be an issue.
1, how is the hash function designed?
2, you mean increase the size at run time?
can you give a bit more detail about how the program can be benefited from hash table?
@ProlificCoder, thanks for the image! but why use a hashmap? cant we just set matrix[i,j] to 0 when the ship is shot/attacked? and when a ship is hit, wont HIT and SUNK both be true, so what should function return in that case?ideally when the ship is hit, when we change the value to zero, its sunk right?
@witty not sure if I understood your comment correctly. But each ship in a battleship game occupies more than one square. A ship is not sunk until all the cells/blocks of it are hit. en.wikipedia.org/wiki/Battleship_(game)
In my case when the ship is hit, I am just remove the hash/set value from the array. In code, I will have a check to see if there are no remaining values and return SUNK if true.
Can a 2D array be a good choice for these kind of board games, one more example is Tic Tac Toe..
- WittyWoman March 23, 2011