PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This multi-part question evaluates algorithmic problem-solving skills including efficient lookup/search, stable ordering and priority management, streaming algorithms under strict memory constraints, and expression parsing with variable substitution.

  • medium
  • Instacart
  • Coding & Algorithms
  • Software Engineer

Implement multiple coding round problems

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Solve the following **coding** problems. ## 1) Bus schedule (next departure) Given: - A sorted list `buses[]` of bus departure times (minutes since 00:00). - A list `arrivals[]` of passenger arrival times (minutes since 00:00). For each passenger, return the **earliest bus departure time** that is `>=` their arrival time, or `-1` if no such bus exists. **Constraints:** - `1 <= len(buses), len(arrivals) <= 2e5` - Times fit in 32-bit signed integers. ## 2) Priority boarding order You are given a list of passengers. Each passenger has: - `priority` (smaller number = higher priority, e.g. 0 is best) - `checkInTime` (integer) - `name` (string) Output the boarding order under these rules: 1. Higher priority boards first. 2. Within the same priority, earlier `checkInTime` boards first. 3. If still tied, preserve input order. **Follow-up:** If passengers arrive as a stream, how would you produce the next passenger to board efficiently? ## 3) Decode passwords from a stream with limited reads A file/stream contains multiple passwords encoded as `(index, char)` pairs in order of appearance. A password is defined by indices `0..L-1` appearing exactly once each, where `L` is the password length. Rules: - The **first password is guaranteed valid**. - When parsing the stream, encountering an `index` that has already appeared in the *current* password indicates the start of the **next** password (i.e., the pair you just read belongs to the next password). - You cannot load the full file into memory. You may only read in chunks whose size is at most the **length `L` of the first decoded password**. Return all decoded passwords in order. ## 4) Evaluate an arithmetic expression with up to two variables Given: - A string expression `expr` containing integers, `+` and `-`, parentheses `(` `)`, optional whitespace, and variable names consisting of letters. - The expression contains **at most two distinct variable names**. - A map of variable values (e.g., `{x: 3, y: 10}`), guaranteed to include any variables present. Compute and return the integer result. **Note:** You may not assume there are spaces between tokens.

Quick Answer: This multi-part question evaluates algorithmic problem-solving skills including efficient lookup/search, stable ordering and priority management, streaming algorithms under strict memory constraints, and expression parsing with variable substitution.

Part 1: Bus Schedule - Next Departure

You are given a sorted list `buses` of bus departure times and a list `arrivals` of passenger arrival times. For each passenger, return the earliest bus departure time that is greater than or equal to their arrival time. If no such bus exists, return `-1` for that passenger.

Constraints

  • 0 <= len(buses), len(arrivals) <= 2 * 10^5
  • `buses` is sorted in nondecreasing order
  • All times fit in 32-bit signed integers

Examples

Input: ([5, 10, 20], [0, 5, 6, 20, 21])

Expected Output: [5, 5, 10, 20, -1]

Explanation: Each arrival is matched to the first bus at or after that time.

Input: ([7], [1, 7, 8])

Expected Output: [7, 7, -1]

Explanation: A single bus can satisfy multiple passengers if its departure time is late enough.

Input: ([3, 9], [])

Expected Output: []

Explanation: Edge case: no passengers.

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

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

Explanation: Edge case: no buses are available.

Hints

  1. For one passenger, this is a search for the first bus time that is not smaller than the arrival time.
  2. A binary search per passenger is fast enough for the given limits.

Part 2: Priority Boarding Order

The i-th passenger has `priorities[i]`, `check_in_times[i]`, and `names[i]`. Smaller priority numbers mean higher priority. Output the boarding order using these rules: higher priority first, then earlier check-in time, and if still tied, preserve the original input order.

Constraints

  • 0 <= n <= 2 * 10^5, where n is the number of passengers
  • `len(priorities) == len(check_in_times) == len(names)`
  • `priorities[i]` and `check_in_times[i]` are integers
  • `names[i]` is a string

Examples

Input: ([1, 0, 1], [5, 10, 3], ["Ann", "Bob", "Cara"])

Expected Output: ["Bob", "Cara", "Ann"]

Explanation: Bob has the best priority. Between Cara and Ann, Cara checked in earlier.

Input: ([1, 1, 1], [5, 5, 5], ["A", "B", "C"])

Expected Output: ["A", "B", "C"]

Explanation: All keys tie, so input order is preserved.

Input: ([2, 1, 1, 0], [1, 9, 3, 8], ["D", "E", "F", "G"])

Expected Output: ["G", "F", "E", "D"]

Explanation: Priority 0 boards first, then priority 1 sorted by check-in time, then priority 2.

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

Expected Output: []

Explanation: Edge case: no passengers.

Hints

  1. If two passengers are completely tied on the first two rules, their original index decides the order.
  2. Sorting indices instead of modifying the original arrays can make tie-breaking easier.

Part 3: Streaming Priority Boarding

You must process boarding events as a stream. The i-th event is described by `op_types[i]`. If `op_types[i] == 'arrive'`, then a passenger with `priorities[i]`, `check_in_times[i]`, and `names[i]` is added to the waiting line. If `op_types[i] == 'board'`, output the name of the next passenger who should board according to the same rules as Part 2: smaller priority first, earlier check-in time second, and original arrival order as the final tie-breaker. If nobody is waiting at a `board` event, output an empty string `''` for that event.

Constraints

  • 0 <= q <= 2 * 10^5, where q is the number of events
  • `len(op_types) == len(priorities) == len(check_in_times) == len(names)`
  • `op_types[i]` is either `arrive` or `board`
  • Each `arrive` or `board` operation should be handled efficiently

Examples

Input: (["arrive", "arrive", "board", "board"], [1, 0, 0, 0], [5, 10, 0, 0], ["Ann", "Bob", "", ""])

Expected Output: ["Bob", "Ann"]

Explanation: Bob has higher priority than Ann, so he boards first.

Input: (["arrive", "arrive", "board", "board"], [1, 1, 0, 0], [5, 5, 0, 0], ["Ann", "Ben", "", ""])

Expected Output: ["Ann", "Ben"]

Explanation: The two passengers tie on priority and check-in time, so arrival order decides it.

Input: (["board", "arrive", "board", "board"], [0, 2, 0, 0], [0, 7, 0, 0], ["", "Cara", "", ""])

Expected Output: ["", "Cara", ""]

Explanation: Edge case: boarding from an empty waiting line returns an empty string.

Input: (["arrive", "arrive", "board", "arrive", "board", "board"], [2, 1, 0, 1, 0, 0], [4, 9, 0, 3, 0, 0], ["Dan", "Eve", "", "Finn", "", ""])

Expected Output: ["Eve", "Finn", "Dan"]

Explanation: After Eve boards, Finn arrives with the same priority level but an earlier check-in time than Eve had.

Hints

  1. You need a data structure that can always give you the smallest item by `(priority, check_in_time, arrival_sequence)`.
  2. A min-heap is a natural fit for repeatedly taking the next passenger to board.

Part 4: Decode Passwords from a Stream

A stream encodes passwords as `(index, char)` pairs. Every password has the same length `L`, which is not given in advance. Within one password, each index from `0` to `L-1` appears exactly once. The first password is guaranteed valid. While scanning left to right, the first time you see an index that already appeared in the current password, that pair actually belongs to the next password. For testing, the stream is provided as two parallel lists `indices` and `chars`, but your algorithm should process them sequentially and use only O(L) extra memory.

Constraints

  • 0 <= n <= 2 * 10^5, where n is the number of pairs
  • `len(indices) == len(chars)`
  • The first password is valid and determines the common length `L`
  • All later pairs follow the same password format

Examples

Input: ([0, 1, 2, 2, 0, 1], ["a", "b", "c", "x", "y", "z"])

Expected Output: ["abc", "yzx"]

Explanation: The repeated index `2` starts the second password.

Input: ([2, 0, 1], ["c", "a", "b"])

Expected Output: ["abc"]

Explanation: Only one password appears in the stream.

Input: ([0, 0, 0], ["a", "b", "c"])

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

Explanation: Edge case: password length is 1, so every pair starts a new password after the first.

Input: ([], [])

Expected Output: []

Explanation: Edge case: empty stream.

Hints

  1. The first repeated index tells you that the first password is complete and also reveals its length.
  2. Once `L` is known, a fixed-size buffer and a seen-array are enough to decode the rest.

Part 5: Evaluate an Arithmetic Expression with Variables

Given an arithmetic expression `expr` containing integers, `+`, `-`, parentheses, optional whitespace, and variable names made of letters, compute its integer value. A map `values` gives the integer value for every variable used in the expression. The expression contains at most two distinct variable names, but your solution may handle more.

Constraints

  • 1 <= len(expr) <= 2 * 10^5
  • The expression is valid
  • Tokens may appear without spaces between them
  • `values` contains every variable used in `expr`

Examples

Input: ("1 + x - (y - 2)", {"x": 3, "y": 10})

Expected Output: -4

Explanation: This evaluates to `1 + 3 - (10 - 2) = -4`.

Input: ("(a-(b-5))+10", {"a": 7, "b": 2})

Expected Output: 20

Explanation: Nested parentheses and variables are both used.

Input: ("-x+5", {"x": 8})

Expected Output: -3

Explanation: Edge case: the expression starts with a unary minus.

Input: (" 42 ", {})

Expected Output: 42

Explanation: Edge case: a single number with whitespace.

Input: ("x-(y-(x-1))", {"x": 2, "y": 5})

Expected Output: -2

Explanation: No spaces are required between tokens.

Hints

  1. This is a parentheses parsing problem; a stack can remember the result and sign before each `(`.
  2. Parse multi-digit numbers and multi-letter variable names as whole tokens, not one character at a time.
Last updated: May 29, 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

  • Fix the Broken Search Filter in a Book Catalog API - Instacart (medium)
  • Find Largest Adjacent Stock Price Change - Instacart (medium)
  • Implement an In-Memory File Storage System - Instacart (medium)
  • Decode an encoded string - Instacart (medium)
  • Evaluate an arithmetic expression - Instacart (medium)