PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches

Quick Overview

This multi-part problem evaluates core competencies in data structures and algorithm design (LRU cache, grid pathfinding and earliest-feasible-time analysis), randomized algorithms and probability (rand7→rand10 and reservoir sampling), and computational geometry with counting and hashing for axis-aligned square detection.

  • medium
  • WeRide
  • Coding & Algorithms
  • Software Engineer

Implement Several Core Algorithmic Components

Company: WeRide

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Solve the following independent coding tasks. 1. **Implement an LRU cache.** Design a class `LRUCache` with: - `LRUCache(int capacity)`: initializes the cache with a positive capacity. - `int get(int key)`: returns the value for `key` if it exists; otherwise returns `-1`. Accessing a key makes it the most recently used item. - `void put(int key, int value)`: inserts or updates the value. If the cache exceeds capacity, evict the least recently used key. Both `get` and `put` should run in `O(1)` average time. 2. **Find the earliest feasible time to cross a grid.** You are given an `n x n` grid of nonnegative integers. `grid[r][c]` is the earliest time at which cell `(r, c)` becomes passable. You start at `(0, 0)` and want to reach `(n - 1, n - 1)`. At time `t`, you may stand on or move into only cells with value `<= t`. Each move goes one step up, down, left, or right. Return the minimum time `t` such that a path from the start to the destination exists. 3. **Generate a uniform random integer from 1 to 10 using a 1-to-7 generator.** You are given an API `rand7()` that returns each integer from `1` to `7` with equal probability. Implement `rand10()` so that it returns each integer from `1` to `10` with equal probability. Minimize the expected number of calls to `rand7()`. 4. **Design a point data structure for counting axis-aligned squares.** Design a data structure supporting: - `add(int x, int y)`: adds a point. Duplicate points are allowed and should be counted with multiplicity. - `count(int x, int y)`: given a query point `(x, y)`, returns the number of ways to choose three previously added points that, together with `(x, y)`, form an axis-aligned square with positive side length. 5. **Explain and implement reservoir sampling.** Given a stream of items of unknown length, design an algorithm that returns one item chosen uniformly at random from all items seen in the stream while using `O(1)` extra space. Be prepared to explain why every item has equal probability of being selected.

Quick Answer: This multi-part problem evaluates core competencies in data structures and algorithm design (LRU cache, grid pathfinding and earliest-feasible-time analysis), randomized algorithms and probability (rand7→rand10 and reservoir sampling), and computational geometry with counting and hashing for axis-aligned square detection.

Part 1: Implement an LRU Cache

Design and simulate an LRU (Least Recently Used) cache. For testability, implement a function that receives a cache capacity, a list of operation names, and a parallel list of arguments. Each operation is either 'put' with arguments [key, value] or 'get' with arguments [key]. A 'get' should return the stored value or -1 if the key is absent, and it must mark that key as most recently used. A 'put' should insert or update the key, and if the cache exceeds capacity, it must evict the least recently used key. Return the results of all 'get' operations in order.

Constraints

  • 1 <= capacity <= 10^5
  • 1 <= len(op_types) == len(args) <= 2 * 10^5
  • 0 <= key, value <= 10^9
  • Both 'get' and 'put' should be handled in O(1) average time per operation

Examples

Input: (2, ['put', 'put', 'get', 'put', 'get', 'put', 'get', 'get', 'get'], [[1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]])

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

Explanation: After inserting 1 and 2, getting 1 makes it most recent. Putting 3 evicts 2, and putting 4 later evicts 1.

Input: (1, ['put', 'put', 'get', 'get'], [[1, 10], [2, 20], [1], [2]])

Expected Output: [-1, 20]

Explanation: With capacity 1, inserting key 2 evicts key 1.

Input: (2, ['put', 'put', 'put', 'get', 'put', 'get', 'get'], [[2, 1], [2, 2], [1, 1], [2], [4, 1], [1], [2]])

Expected Output: [2, -1, 2]

Explanation: Updating an existing key should not increase cache size and should refresh its recency.

Hints

  1. A hash map can find a key in O(1), but you also need O(1) updates to recency order.
  2. A doubly linked list is a good way to remove and insert nodes in O(1) when combined with a hash map.

Part 2: Find the Earliest Feasible Time to Cross a Grid

You are given a grid of nonnegative integers where grid[r][c] is the earliest time when cell (r, c) becomes passable. Starting at the top-left cell, you may move up, down, left, or right, but at time t you may only stand on cells whose value is at most t. Return the minimum time needed to reach the bottom-right cell.

Constraints

  • 1 <= len(grid) <= 200
  • 1 <= len(grid[0]) <= 200
  • 0 <= grid[r][c] <= 10^9

Examples

Input: [[0, 2], [1, 3]]

Expected Output: 3

Explanation: You must wait until time 3 before a complete path exists.

Input: [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]

Expected Output: 16

Explanation: The optimal route keeps the maximum required cell value at 16.

Input: [[7]]

Expected Output: 7

Explanation: The start is also the destination, so the answer is the cell's own availability time.

Input: [[0, 100], [1, 2]]

Expected Output: 2

Explanation: Going down first avoids waiting for the cell with value 100.

Hints

  1. Think of the cost of a path as the maximum grid value seen along that path.
  2. Dijkstra's algorithm works if the distance to a cell is defined as the minimum possible maximum value needed to reach it.

Part 3: Generate rand10() Using rand7()

To make this random-generation task deterministic for testing, you are given a list called rolls representing consecutive outputs of rand7(), where each value is between 1 and 7. Implement the standard rejection-sampling version of rand10(): repeatedly consume two rand7() results to form a number in 1..49 using (a - 1) * 7 + b. If that number is at most 40, convert it to a value in 1..10 using 1 + (num - 1) % 10; otherwise reject it and try again with the next two rolls. Return the first k generated rand10() values. If the rolls run out early, return whatever values were generated.

Constraints

  • 0 <= k <= 10^5
  • 0 <= len(rolls) <= 2 * 10^5
  • Each value in rolls is between 1 and 7

Examples

Input: ([1, 1, 2, 7, 6, 6, 1, 5], 3)

Expected Output: [1, 4, 5]

Explanation: Pairs (1,1) and (2,7) are accepted immediately. Pair (6,6) gives 41 and is rejected, so the next pair (1,5) produces 5.

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

Expected Output: []

Explanation: Requesting zero outputs should return an empty list.

Input: ([7, 7, 7, 6, 7, 5, 3, 4], 1)

Expected Output: [8]

Explanation: 49, 48, and 47 are rejected. The next accepted value is 18, which maps to 8.

Input: ([6, 5, 1, 1, 1, 7], 2)

Expected Output: [10, 1]

Explanation: 40 maps to 10, and then 1 maps to 1.

Hints

  1. Two independent rand7() calls give 49 equally likely outcomes.
  2. Only the first 40 outcomes can be evenly mapped onto 10 results.

Part 4: Design a Data Structure for Counting Axis-Aligned Squares

Design and simulate a point data structure that supports adding points and counting axis-aligned squares. For testability, implement a function that receives a list of operation names and a parallel list of points. Each operation is either 'add' with point [x, y] or 'count' with query point [x, y]. Duplicate points are allowed and count with multiplicity. For each 'count' query, return the number of ways to choose three previously added points that, together with the query point, form an axis-aligned square with positive side length.

Constraints

  • 1 <= len(op_types) == len(points) <= 5000
  • -10^4 <= x, y <= 10^4
  • Duplicate points may be added multiple times

Examples

Input: (['add', 'add', 'add', 'count', 'count', 'add', 'count'], [[3, 10], [11, 2], [3, 2], [11, 10], [14, 8], [11, 2], [11, 10]])

Expected Output: [1, 0, 2]

Explanation: The first query forms one square. After adding a duplicate point at (11,2), the same square can be formed in two distinct ways.

Input: (['count'], [[0, 0]])

Expected Output: [0]

Explanation: With no added points, there are no squares.

Input: (['add', 'add', 'add', 'add', 'add', 'count', 'count'], [[0, 0], [1, 0], [0, 1], [1, 1], [1, 1], [0, 0], [1, 0]])

Expected Output: [2, 2]

Explanation: The duplicate point (1,1) doubles the number of valid squares for both queries.

Hints

  1. For a query point, any square partner on the same horizontal line determines the side length.
  2. Store point multiplicities so duplicates contribute multiple valid squares.

Part 5: Explain and Implement Reservoir Sampling

Reservoir sampling chooses one item uniformly at random from a stream of unknown length using O(1) extra space. To make the task deterministic for testing, you are given a stream of nonnegative integers and a parallel array draws, where draws[i] is the random integer that would have been generated uniformly from 1 to i + 1 when processing stream[i]. Simulate the standard algorithm: when the i-th item (1-indexed) arrives, replace the current sample if the drawn number equals 1. Return the final selected item. If the stream is empty, return -1.

Constraints

  • 0 <= len(stream) == len(draws) <= 2 * 10^5
  • 0 <= stream[i] <= 10^9
  • For each i, draws[i] is an integer in the range [1, i + 1]

Examples

Input: ([10, 20, 30, 40], [1, 2, 1, 3])

Expected Output: 30

Explanation: 10 is chosen first, 20 is ignored, 30 replaces it, and 40 is ignored.

Input: ([], [])

Expected Output: -1

Explanation: An empty stream has no selectable item.

Input: ([7], [1])

Expected Output: 7

Explanation: With one item, that item must be selected.

Input: ([5, 6, 7, 8, 9], [1, 1, 3, 1, 5])

Expected Output: 8

Explanation: 5 is chosen, then replaced by 6, kept through 7, replaced by 8, and kept through 9.

Hints

  1. At step i, the new item should become the sample with probability 1 / i.
  2. To prove uniformity, show that after processing i items, every item has probability 1 / i of being stored.
Last updated: May 23, 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

  • Validate Bracket Sequence - WeRide (medium)
  • Implement matrix multiplication and fast exponentiation - WeRide (medium)
  • Implement expression expansion to plus-only form - WeRide (Medium)
  • Expand algebraic expression with distribution - WeRide (Medium)