PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • nan
  • Microsoft
  • Coding & Algorithms
  • Software Engineer

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.

Part 1: Largest continuous island after filling sea (1D)

You are given a binary array where 1 means land and 0 means ocean. You may flip at most material ocean cells into land. Return the maximum possible length of a contiguous segment containing only 1s after the flips.

Constraints

  • 1 <= len(islands) <= 2e5
  • 0 <= material <= len(islands)
  • Each islands[i] is either 0 or 1

Examples

Input: ([0, 1, 0, 1, 1, 1], 1)

Expected Output: 5

Explanation: Flip the zero at index 2 to get a longest contiguous segment of length 5.

Input: ([1, 1, 1, 1], 2)

Expected Output: 4

Explanation: The array is already all land, so the answer is the full length.

Input: ([0, 0, 0], 2)

Expected Output: 2

Explanation: At most two ocean cells can be flipped, so the best contiguous land segment has length 2.

Input: ([0], 0)

Expected Output: 0

Explanation: Single-cell edge case with no material.

Hints

  1. Think about maintaining a window that contains at most material zeros.
  2. If the window becomes invalid, move its left side forward until the number of zeros is small enough again.

Part 2: Resolve software package dependencies

You are given a list of requested packages and a dependency mapping. Return an installation order that includes every requested package and all of their transitive dependencies, with every dependency appearing before the package that needs it. If multiple valid orders exist, return the deterministic order produced by running depth-first search over packages in the given input order and visiting each dependency list in the listed order. If a cycle exists in the required dependency graph, raise ValueError.

Constraints

  • 0 <= len(packages) <= 2e5
  • The total number of required packages plus dependency edges is assumed to be manageable in memory
  • Package names are strings
  • Dependencies may mention packages not present as keys

Examples

Input: (['app'], {'app': ['lib', 'core'], 'lib': ['util'], 'core': []})

Expected Output: ['util', 'lib', 'core', 'app']

Explanation: util is implied even though it is not a key. Each dependency appears before the package that needs it.

Input: (['a', 'b'], {'a': ['c'], 'b': ['c']})

Expected Output: ['c', 'a', 'b']

Explanation: Shared dependency c appears only once, before both requested packages.

Input: (['pkg'], {})

Expected Output: ['pkg']

Explanation: A package with no dependencies is installed by itself.

Input: ([], {'a': ['b']})

Expected Output: []

Explanation: No requested packages means nothing needs to be installed.

Input: (['a'], {'a': ['b'], 'b': ['a']})

Expected Output: 'ValueError'

Explanation: The required dependency graph contains a cycle, so the function should raise ValueError.

Hints

  1. This is a topological ordering problem on the required subgraph.
  2. Use three states for DFS nodes: unseen, visiting, and done. Encountering a visiting node means there is a cycle.

Part 3: Count the number of clouds in a heat-index grid

A cell in the grid is considered cloud if its value is at most 4. A cloud is a 4-directionally connected component of cloud cells. Return the number of distinct clouds in the grid.

Constraints

  • 0 <= number of rows, columns <= 500
  • 0 <= sky[r][c] <= 9
  • Connectivity is 4-directional

Examples

Input: [[5, 2, 2], [6, 5, 2], [1, 7, 8]]

Expected Output: 2

Explanation: There is one cloud of size 3 in the top-right area and one single-cell cloud at the bottom-left.

Input: [[9, 9], [9, 9]]

Expected Output: 0

Explanation: No cell has value at most 4.

Input: [[0]]

Expected Output: 1

Explanation: A single cloud cell forms one cloud.

Input: []

Expected Output: 0

Explanation: Empty grid edge case.

Hints

  1. Whenever you find an unvisited cloud cell, start a flood fill from it.
  2. Mark all cells in that component so they are not counted again.

Part 4: Find the maximum cloud size

A cell in the grid is considered cloud if its value is at most 4. A cloud is a 4-directionally connected component of cloud cells. Return the size of the largest cloud, measured as the number of cells in that component.

Constraints

  • 0 <= number of rows, columns <= 500
  • 0 <= sky[r][c] <= 9
  • Connectivity is 4-directional

Examples

Input: [[5, 2, 2], [6, 5, 2], [1, 7, 8]]

Expected Output: 3

Explanation: The largest cloud contains the three connected cells in the top-right area.

Input: [[0, 0], [0, 0]]

Expected Output: 4

Explanation: All four cells are cloud and all are connected.

Input: [[9, 9], [9, 9]]

Expected Output: 0

Explanation: There are no clouds.

Input: []

Expected Output: 0

Explanation: Empty grid edge case.

Hints

  1. Use the same flood-fill idea as cloud counting, but track the number of cells visited in each component.
  2. Update the best answer after finishing each component.

Part 5: Identify and count thunderstorm clouds

A cell is cloud if its value is at most 4, and clouds are 4-directionally connected components of cloud cells. A cloud is a thunderstorm cloud if at least half of its cells have value at most 1. Return the number of thunderstorm clouds in the grid.

Constraints

  • 0 <= number of rows, columns <= 500
  • 0 <= sky[r][c] <= 9
  • A thunderstorm cloud satisfies thunder_cells * 2 >= cloud_size

Examples

Input: [[1, 4, 5], [0, 3, 9], [6, 9, 1]]

Expected Output: 2

Explanation: There are two clouds. The 2x2 cloud has 2 of 4 cells at most 1, and the single-cell cloud also qualifies.

Input: [[2, 4], [4, 2]]

Expected Output: 0

Explanation: All four cells form one cloud, but none are at most 1.

Input: [[1, 9, 1]]

Expected Output: 2

Explanation: Two isolated one-cell clouds both qualify as thunderstorm clouds.

Input: []

Expected Output: 0

Explanation: Empty grid edge case.

Hints

  1. During each flood fill, track both the total component size and how many cells have value at most 1.
  2. To avoid floating-point math, compare 2 * thunder_cells with cloud_size.

Part 6: Find an influencer (celebrity) in a following matrix

There are N users labeled 0 to N-1. User i is an influencer if they follow nobody and every other user follows them. Return that user's ID, or -1 if no influencer exists.

Constraints

  • 0 <= N <= 5000
  • followingMatrix is an N x N boolean matrix
  • followingMatrix[i][i] == False for all i

Examples

Input: [[False, True, True], [False, False, True], [False, False, False]]

Expected Output: 2

Explanation: User 2 follows nobody, and users 0 and 1 both follow user 2.

Input: [[False, True], [True, False]]

Expected Output: -1

Explanation: Both users follow someone, so there is no influencer.

Input: [[False]]

Expected Output: 0

Explanation: With one user, the conditions hold vacuously.

Input: []

Expected Output: -1

Explanation: Empty network edge case.

Hints

  1. If user a follows user b, then a cannot be the influencer.
  2. After narrowing down to one candidate, you still must verify both the candidate's row and column.

Part 7: Find the user with the maximum number of followers

There are N users labeled 0 to N-1. The number of followers of user j is the count of users i != j such that followingMatrix[i][j] is True. Return the user with the maximum number of followers. If multiple users tie for the maximum, return the smallest user ID. Return -1 for an empty matrix.

Constraints

  • 0 <= N <= 5000
  • followingMatrix is an N x N boolean matrix
  • followingMatrix[i][i] == False for all i

Examples

Input: [[False, True, True], [False, False, True], [True, False, False]]

Expected Output: 2

Explanation: User 2 is followed by users 0 and 1, which is the highest count.

Input: [[False, True], [True, False]]

Expected Output: 0

Explanation: Both users have one follower, so the smaller ID is returned.

Input: [[False, False, False], [False, False, False], [False, False, False]]

Expected Output: 0

Explanation: Everyone has zero followers, so tie-breaking returns user 0.

Input: []

Expected Output: -1

Explanation: Empty network edge case.

Hints

  1. The answer depends on column counts, not row counts.
  2. A simple way is to count how many True values appear in each column, excluding the diagonal.
Last updated: Jun 4, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Return Top K Open Businesses - Microsoft (hard)
  • Implement Memory Allocation and In-Memory Records - Microsoft (medium)
  • Implement K-Means and Detect Divisible Subarrays - Microsoft (medium)
  • Sort Three Categories In Place - Microsoft (medium)
  • Retain Top K Elements - Microsoft (medium)