PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This multi-part question evaluates algorithmic problem-solving and data structure design skills across ordered-array search with dynamic updates, expected O(1) randomized set operations, nesting-depth string parsing, Manhattan-range counting on grids, and constrained shortest-path search.

  • medium
  • Bloomberg
  • Coding & Algorithms
  • Software Engineer

Answer multi-round grid and data-structure questions

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given several independent interview-style coding questions. ## 1) Find first/last occurrence in sorted array (+ dynamic updates follow-ups) Given an integer array `nums` sorted in **non-decreasing** order and an integer `target`, return a 2-element array `[firstIndex, lastIndex]` where: - `firstIndex` is the smallest index `i` such that `nums[i] == target` - `lastIndex` is the largest index `j` such that `nums[j] == target` - if `target` does not appear, return `[-1, -1]` **Constraints (typical):** `0 <= n <= 2e5`, values fit in 32-bit signed int. **Follow-ups (discuss approach):** 1. If the array keeps receiving insertions only at the end, and every inserted number is **greater than the current last element** (so the array stays sorted), how would you update/answer range queries efficiently? 2. If insertions can happen **anywhere** (while keeping the overall order non-decreasing), how would you support both insertions and `[first,last]` range queries efficiently? --- ## 2) Implement an O(1) lottery participant store Design a data structure `LotterySystem` supporting the following operations with **expected O(1)** time: - `LotterySystem()` – initialize the structure - `boolean addParticipant(int id)` – add a participant with **unique** `id`; return `true` if added, `false` if already present - `boolean removeParticipant(int id)` – remove a participant by `id`; return `true` if removed, `false` if not present - `int randomPick()` – return a uniformly random participant id among current participants; return `-1` if empty --- ## 3) Extract the string(s) at maximum parenthesis depth Given a string `s` consisting of lowercase letters and parentheses `'('`, `')'`, assume parentheses are **balanced**. Define the **nesting depth** as the number of currently open parentheses. Return a string consisting of **all characters whose depth equals the maximum depth** anywhere in the string, in their original order. **Examples** - `s = "a(b(c)d)e"` → max depth is 2 → output `"c"` - `s = "((ab)(cd))"` → max depth is 2 → output `"abcd"` **Constraints (typical):** `|s| <= 2e5`. --- ## 4) Place one turret to protect the most houses (Manhattan radius) You are given an `m x n` 2D grid where each cell is either a house (`1`) or empty (`0`). You may place **one** turret on any cell. A turret protects a house if the Manhattan distance from the turret to that house is `<= k`: \[ |r_1-r_2| + |c_1-c_2| \le k \] Return the **maximum** number of houses that can be protected. **Constraints (typical):** `1 <= m,n <= 2000` (or discuss scalable approaches), `0 <= k <= 2000`. --- ## 5) Shortest path in grid with up to k wall breaks Given an `m x n` grid where: - `0` = empty cell - `1` = wall Starting at `(0,0)`, you want to reach `(m-1,n-1)` with 4-directional moves. You may traverse through at most `k` wall cells total (i.e., “break” up to `k` walls). Return the length of the shortest path (number of steps), or `-1` if impossible. **Constraints (typical):** `1 <= m,n <= 100`, `0 <= k <= m*n`.

Quick Answer: This multi-part question evaluates algorithmic problem-solving and data structure design skills across ordered-array search with dynamic updates, expected O(1) randomized set operations, nesting-depth string parsing, Manhattan-range counting on grids, and constrained shortest-path search.

Find First and Last Position in Sorted Array

Given an integer array `nums` sorted in non-decreasing order and an integer `target`, return a 2-element array `[firstIndex, lastIndex]` where `firstIndex` is the smallest index `i` with `nums[i] == target` and `lastIndex` is the largest index `j` with `nums[j] == target`. If `target` does not appear, return `[-1, -1]`. Aim for O(log n) using two binary searches. Follow-ups to discuss: (1) If numbers are only appended at the end and each is strictly greater than the current last element, the array stays sorted and binary search still answers range queries in O(log n) per query with O(1) amortized append. (2) If insertions can happen anywhere while keeping non-decreasing order, use a balanced BST / order-statistics structure (or a B-tree) to support O(log n) insert and O(log n) first/last-occurrence (lower_bound / upper_bound) queries.

Constraints

  • 0 <= n <= 2 * 10^5
  • Values fit in a 32-bit signed integer
  • nums is sorted in non-decreasing order

Examples

Input: ([5,7,7,8,8,10], 8)

Expected Output: [3, 4]

Explanation: 8 first appears at index 3 and last at index 4.

Input: ([5,7,7,8,8,10], 6)

Expected Output: [-1, -1]

Explanation: 6 does not appear in the array.

Input: ([], 0)

Expected Output: [-1, -1]

Explanation: Empty array: target cannot be found.

Input: ([1], 1)

Expected Output: [0, 0]

Explanation: Single element equal to target.

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

Expected Output: [0, 4]

Explanation: All elements equal target; range spans the whole array.

Input: ([-3,-1,-1,0,4], -1)

Expected Output: [1, 2]

Explanation: Handles negative values and duplicates.

Hints

  1. Run one binary search for the leftmost index where target could be inserted (lower_bound).
  2. If that index is out of range or the value there is not target, the target is absent.
  3. Run a second binary search for the rightmost position (upper_bound) and subtract 1 to get the last index.

O(1) Lottery Participant Store

Design `LotterySystem` supporting expected O(1) `addParticipant(id)`, `removeParticipant(id)`, and `randomPick()`. - `addParticipant(id)` returns true if the unique id was added, false if it was already present. - `removeParticipant(id)` returns true if removed, false if not present. - `randomPick()` returns a uniformly random current participant id, or -1 if empty. Use a dynamic array of ids plus a hash map from id to its array index. To remove, swap the target with the last element, pop, and fix the moved element's index — all O(1). Pick a uniform random array index. For grading, this is modeled as a function `solution(operations)` that replays a list of operations and returns the list of return values. Operations are `['add', id]`, `['remove', id]`, or `['pick']`. The random generator is seeded so picks are reproducible.

Constraints

  • ids are unique integers
  • Each operation is O(1) expected
  • randomPick returns -1 when there are no participants

Examples

Input: ([['add', 1], ['add', 2], ['add', 1], ['remove', 1], ['remove', 5]],)

Expected Output: [True, True, False, True, False]

Explanation: Adding 1 again fails; removing 1 succeeds; removing absent 5 fails.

Input: ([['pick']],)

Expected Output: [-1]

Explanation: Picking from an empty store returns -1.

Input: ([['add', 7], ['pick'], ['remove', 7], ['pick']],)

Expected Output: [True, 7, True, -1]

Explanation: With one participant the pick is deterministically 7; after removal the store is empty.

Input: ([['add', 3], ['add', 4], ['remove', 3], ['add', 3], ['remove', 4]],)

Expected Output: [True, True, True, True, True]

Explanation: Remove then re-add 3 works because the index map is kept consistent via swap-with-last.

Input: ([['remove', 99], ['add', 99], ['remove', 99], ['remove', 99]],)

Expected Output: [False, True, True, False]

Explanation: Remove before add fails; the second removal of 99 fails since it is gone.

Hints

  1. Keep a dynamic array of ids and a hash map from id to its index in that array.
  2. To remove in O(1), swap the target with the last element, pop the last, and update the moved element's stored index.
  3. randomPick is just a uniform random array index; return -1 when the array is empty.

Characters at Maximum Parenthesis Depth

Given a string `s` of lowercase letters and balanced parentheses, define nesting depth as the number of currently open parentheses. Return, in original order, all letters whose depth equals the maximum depth reached anywhere in the string. Examples: `"a(b(c)d)e"` has max depth 2, output `"c"`. `"((ab)(cd))"` has max depth 2, output `"abcd"`. If the maximum depth is 0 (no parentheses), every letter qualifies. Do two passes (or track on the fly): first find the max depth, then collect letters at that depth.

Constraints

  • |s| <= 2 * 10^5
  • s contains only lowercase letters and '(' ')'
  • Parentheses are balanced

Examples

Input: ('a(b(c)d)e',)

Expected Output: c

Explanation: Max depth 2 is reached only around 'c'.

Input: ('((ab)(cd))',)

Expected Output: abcd

Explanation: Both 'ab' and 'cd' sit at depth 2, the maximum.

Input: ('abc',)

Expected Output: abc

Explanation: No parentheses: max depth is 0, so every letter qualifies.

Input: ('',)

Expected Output:

Explanation: Empty string yields empty output.

Input: ('(())',)

Expected Output:

Explanation: Max depth 2 but no letters anywhere, so output is empty.

Input: ('x(y)(z(w))',)

Expected Output: w

Explanation: Max depth 2 is only reached at 'w'.

Hints

  1. Track a running depth: +1 on '(', -1 on ')'.
  2. First pass: record the maximum depth ever reached.
  3. Second pass: append a letter only when the current depth equals that maximum. With no parentheses the max depth is 0, so all letters qualify.

Place One Turret to Protect the Most Houses

Given an `m x n` grid where each cell is a house (`1`) or empty (`0`), you may place one turret on any cell. A turret protects a house if the Manhattan distance `|r1-r2| + |c1-c2| <= k`. Return the maximum number of houses that can be protected by a single optimally placed turret. A direct approach scans every candidate cell and counts houses within radius k; for large grids you would discuss a diamond-shaped (rotated-coordinate) 2D prefix-sum so each candidate is O(1).

Constraints

  • 1 <= m, n <= 2000 (discuss scalable approaches)
  • 0 <= k <= 2000
  • Each cell is 0 or 1
  • The turret may sit on a house or an empty cell

Examples

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

Expected Output: 2

Explanation: Placing the turret on the middle of the top edge (0,1) covers the two top-corner houses at distance 1.

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

Expected Output: 4

Explanation: The center (1,1) is distance 2 from all four corner houses.

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

Expected Output: 0

Explanation: No houses to protect.

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

Expected Output: 1

Explanation: With k=0 a turret protects only the house on its own cell.

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

Expected Output: 4

Explanation: A large radius covers every house from any cell.

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

Expected Output: 2

Explanation: Placing at index 1 covers the house at index 0 (dist 1) and index 3 (dist 2).

Hints

  1. Collect the coordinates of all houses once.
  2. For each candidate turret cell, count houses with Manhattan distance <= k.
  3. To scale, rotate coordinates to (r+c, r-c); a Manhattan ball becomes an axis-aligned square, enabling an O(1) 2D prefix-sum query per candidate.

Shortest Path in a Grid with Up to k Wall Breaks

Given an `m x n` grid where `0` is empty and `1` is a wall, start at `(0,0)` and reach `(m-1, n-1)` using 4-directional moves. You may pass through at most `k` wall cells total. Return the length of the shortest path (number of steps), or `-1` if it is impossible. Use BFS over the state `(row, col, walls_used)`. Track, for each cell, the minimum walls used to reach it, and only enqueue a neighbor when entering it uses fewer walls than any previous arrival (and still within k). The first time you pop the destination, the distance is shortest.

Constraints

  • 1 <= m, n <= 100
  • 0 <= k <= m * n
  • Cells are 0 (empty) or 1 (wall)
  • Movement is 4-directional

Examples

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

Expected Output: 4

Explanation: A clear path of length 4 exists without breaking any wall.

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

Expected Output: -1

Explanation: Two walls block the single row; only 1 break is allowed.

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

Expected Output: 4

Explanation: Breaking both walls gives a straight path of length 4.

Input: ([[0]], 0)

Expected Output: 0

Explanation: Start equals destination; zero steps.

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

Expected Output: 2

Explanation: Go right then down avoiding the wall, length 2.

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

Expected Output: 2

Explanation: Either route breaks exactly one wall; with k=5 the shortest is length 2.

Hints

  1. BFS guarantees the shortest path in an unweighted grid; augment the state with the number of walls already broken.
  2. For each cell store the minimum walls used to reach it; skip a neighbor if you cannot improve on it (and never exceed k).
  3. Return the distance the moment you first reach the bottom-right cell; return -1 if BFS drains without reaching it.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ 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

  • Minimize Travel Assignment Cost - Bloomberg (medium)
  • Determine Balloon Popping Time - Bloomberg (medium)
  • Solve meeting and tree problems - Bloomberg (easy)
  • Minimize travel cost with two cities - Bloomberg (easy)
  • Check connectivity between two subway stations - Bloomberg (easy)