← WeRide Interview InsightsSoftware Engineer

WeRide·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Second round at Weride for a software engineering role, done remotely with someone on the US team. Split between talking through my resume and a coding problem, nothing too wild but the algo portion had some bite to it.

Questions Asked (1)

Q1

Given a grid where water rises over time, find the minimum time at which you can swim from the top-left to the bottom-right corner.

Algorithms & Data Structures
Author's notes

This is LeetCode 778.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding the minimum maximum elevation along a path from start to end. Use a priority queue (Dijkstra-like) to explore cells in order of the maximum elevation encountered so far, or binary search on time and check connectivity with BFS/DFS. The answer is the minimum such maximum elevation.

Pro tip: Clarify that the water level rises uniformly and you can wait at any cell, so the time to reach a cell is the maximum elevation along the path. Mention that both Dijkstra and binary search + BFS are acceptable, but Dijkstra is more efficient for a single query.

1. Understand the problem

Restate the problem: given a grid of elevations, find the minimum time t such that there is a path from (0,0) to (n-1,m-1) where all cells have elevation ≤ t. The water level rises uniformly, so you can swim through cells with elevation ≤ current time.

2. Choose an approach

Decide between Dijkstra-like search (minimax path) or binary search on time with BFS/DFS. Dijkstra is optimal for a single query; binary search is simpler if you prefer BFS.

3. Implement Dijkstra (minimax)

Use a min-heap prioritized by the maximum elevation along the path. Start with (0,0) and its elevation. For each neighbor, the new max is max(current_max, neighbor_elevation). Push if it improves the best known max for that cell. Return the max when reaching the target.

4. Implement binary search + BFS

Binary search over possible times (e.g., sorted unique elevations). For each mid, run BFS from start to end only through cells with elevation ≤ mid. If reachable, search lower; else search higher. Return the smallest feasible time.

5. Analyze complexity and edge cases

Dijkstra: O(NM log(NM)) time, O(NM) space. Binary search: O(NM log(max_elevation)) time. Handle edge cases: start or end elevation higher than all others, single cell grid, unreachable (should not happen if all cells eventually submerge).

Key Points to Mention

  • The problem reduces to finding a path that minimizes the maximum elevation along the path (minimax path).
  • Dijkstra's algorithm can be adapted by using the maximum elevation as the distance metric.
  • Binary search on the answer combined with BFS/DFS is a valid alternative, especially if the grid is small.
  • Time complexity: Dijkstra O(NM log(NM)) vs binary search O(NM log(max_elevation)).
  • Space complexity: O(NM) for visited/priority queue.
  • Edge cases: start or end cell may have high elevation, but you can wait for water to rise; if start and end are the same cell, time is its elevation.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.