Implement a Battleship Game Engine: Ship Placement, Shots and Sunk Detection
Company: Citadel
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: hard
Interview Round: Technical Screen
Implement a Battleship game. The report gives only the problem's name and notes that the expected amount of code was large enough that the candidate did not finish, so plan to get a working core running first. Use the standard game as the default and confirm the details with the interviewer: ships are straight horizontal or vertical segments placed on a square grid without overlapping; a player fires at one cell at a time; each shot is reported as a miss, a hit, or a hit that sinks a ship (every cell of that ship has now been hit); and a player loses when all of their ships are sunk.
### Clarifying Questions
- What is the board size, and are the ship lengths fixed (a standard fleet) or given as input?
- How are ships and shots given: `(row, column)` pairs, or labels such as a row number and a column letter? Is a ship described by its two end cells?
- May ships touch each other? Is an invalid placement (off the board, overlapping, diagonal) rejected for the whole setup or ship by ship?
- What does a shot at an already-shot cell return: an error, an "already shot" result that does not use the turn, or a miss that ends the turn?
- One player firing at a fixed board, or two players taking turns? Is a computer opponent required?
- Besides each shot's result, which status queries are needed: ships sunk, ships hit but not sunk, whether the game is over?
### Part 1 — Model the board and place ships
Define the classes and implement ship placement with validation.
```hint From a cell to its ship
Think about what a shot at one cell must find out immediately, and which lookup answers that without scanning every ship.
```
#### What This Part Should Cover
- Classes for the ship, the board and the game, and what each one owns
- Placement validation: bounds, straight lines, overlaps, required ship lengths
- What happens to the board when one ship in a setup is invalid
### Part 2 — Fire shots
Implement firing at a cell, the turn order and the end of the game.
```hint Knowing when a ship sinks
Ask what you need to store for each ship so that the shot that sinks it is recognized without re-checking all of its cells.
```
#### What This Part Should Cover
- Results for a miss, a hit, a sinking hit, a repeated shot and an off-board shot
- Turn handling and detecting the winner
- Cost per shot
### Part 3 — Report the status
Report how many ships are sunk, how many are hit but not yet sunk, and whether the game is over.
```hint Counting both kinds
Decide which per-ship numbers already tell you both counts.
```
#### What This Part Should Cover
- Correct counts, including a ship of length one
- Consistency between the status and the shot results
- Tests that check the status after each kind of shot
### What a Strong Answer Covers
- Rules and input format agreed quickly, then the smallest end-to-end working version built before any extras
- Clear classes with a cell-to-ship lookup instead of repeated scans
- Placement validation that leaves no partial state behind
- Constant-time shot handling, correct sunk detection and a defined rule for repeated shots
- Tests for the edge cases, and code organized so the remaining features are easy to add if time runs out
### Follow-up Questions
- Add a computer opponent that fires sensibly after it scores a hit. How would you structure it?
- The board becomes enormous (a billion cells per side) with only a few ships. What changes in your data structures?
- How would two remote players play over a network, and which side validates the shots?
- How would you place a fleet at random so that every valid arrangement can occur?
Overview: Implement a Battleship game: place ships on a grid, process shots as a miss, a hit or a sinking hit, and report how many ships are sunk or only hit. It tests object modeling, placement validation, constant-time shot handling, clear rules for repeated shots, and delivering a working core under time pressure.