Answer common graph, grid, and array tasks

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).