Answer common graph, grid, and array tasks
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: nan
Interview Round: Technical Screen
### Problem 1: Largest continuous island after filling sea (1D)
Humans can convert ocean cells into land by filling them.
**Input**
- `islands`: a 1D array of length `n` with values `0` (ocean) and `1` (land)
- `material`: an integer `k` indicating how many `0` cells you may flip to `1`
**Task**
Return the **maximum length of a contiguous segment of 1s** achievable after flipping **at most** `k` zeros to ones.
**Example**
- `islands = [0, 1, 0, 1, 1, 1]`, `material = 1` → `5`
**Constraints (assume)**
- `1 ≤ n ≤ 2e5`
- `0 ≤ k ≤ n`
---
### Problem 2: Resolve software package dependencies
You need to compute a valid installation order given package dependencies.
**Input**
- `packages: List[str]` — packages the user wants installed
- `dependencies: Dict[str, List[str]]` — `dependencies[p]` is the list of packages that **must be installed before** `p`
- A package may have multiple dependencies.
- A package with no dependencies might not appear as a key in `dependencies`.
**Task**
Return an installation order `List[str]` such that:
1. Every requested package in `packages` appears in the output.
2. All **transitive dependencies** required by the requested packages also appear in the output.
3. For every dependency edge `p -> d` (meaning `p` depends on `d`), `d` appears **before** `p` in the output.
**Error handling**
- If there is a **cycle** among required packages/dependencies, raise `ValueError`.
**Clarifications (assume)**
- If a dependency name is mentioned but not present as a key in `dependencies`, it is still a valid package and has no further dependencies.
---
### Problem 3: Count clouds in a heat-index grid (2D)
A satellite observes a 2D grid of heat radiation indices `0..9`. Cells with value `<= 4` are considered "cloud".
**Input**
- `sky`: an `R x C` integer grid with values in `[0, 9]`
**Cloud definition**
- A cloud is a **connected component** of cells with value `<= 4`.
- Connectivity is **4-directional** (up/down/left/right). Diagonals do not connect.
**Task A**
Return the **number of clouds** in the grid.
**Follow-up 1**
Return the **maximum cloud size** (maximum number of cells in any single cloud).
**Follow-up 2 (Thunderstorm clouds)**
A cloud is a **thunderstorm** if at least **50%** of its cells have value `<= 1`.
- For a cloud of size `S`, let `T` be the count of cells with value `<= 1`. It is thunderstorm if `T >= S/2`.
Return either:
- the **number of thunderstorm clouds**, or
- the list of cloud IDs/positions that are thunderstorms (specify your choice during implementation).
---
### Problem 4: Find an influencer (celebrity) in a following matrix
There are `N` users labeled `0..N-1`.
**Input**
- `followingMatrix: bool[N][N]`
- `followingMatrix[i][j] == true` means user `i` follows user `j`
- `followingMatrix[i][i] == false` for all `i`
**Influencer definition** (must satisfy both)
1. The influencer follows nobody: row `i` is all `false`.
2. Everyone else follows the influencer: column `i` is all `true` except `followingMatrix[i][i]`.
**Task**
Return the influencer’s user ID, or `-1` if none exists.
**Follow-up**
Return the user with the **maximum number of followers** (i.e., the column with the most `true` values, excluding diagonal).
Quick Answer: This set of problems evaluates algorithmic skills across arrays, graph theory, and grid/matrix traversal—covering sliding-window and contiguous-segment reasoning, dependency resolution and topological ordering with cycle detection, connected-component analysis and attribute aggregation in 2D grids, and influencer identification in adjacency matrices. They are commonly asked in the Coding & Algorithms domain to measure understanding of fundamental data structures and graph concepts, reasoning about connectivity and ordering under constraints, and the ability to design efficient, practical solutions that require both conceptual understanding and practical application.