Google logo

Google Software Engineer Coding Questions

54 practice questions for Google Software Engineer interviews

Google software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.

Software Engineer Backend Engineer Frontend Engineer Full Stack Engineer Mobile Engineer Data Engineer Data Scientist ML Engineer DevOps Engineer DevOps Engineer Product Manager SRE Security Engineer Engineering Manager Data Analyst UX/UI Designer QA Engineer
coding Medium Verified Question #1

1. Dictionary of Sorted Letters


Category: Array coding problem

Question Given a string where letters are sorted in alphabetical order, identify all letters that appear more than twice and record their first and...

Input: Array
Output: Computed result
Want to practise this one?
Create a free account to open the full question and practise Google questions with AI.
Sign up free
coding Medium Verified Question #2

2. GPS Error Tracking


Category: Algorithm coding problem

Question You are tracking GPS location errors by comparing measured GPS locations against a set of "golden" (reference) locations. Each location...

Input: List
Output: Computed result
coding Hard Verified Question #3

3. Minimum Boxing Area


Category: Binary search coding problem

Question Design a data structure to maintain a dynamic set of points on a 2D coordinate plane. Support operations to insert points, remove points,...

Input: List
Output: Integer
coding Medium Verified Question #4

4. Reverse Segment of Linked List


Category: Linked list coding problem

Question Given a singly linked list, reverse the second half of the list and then interleave the nodes from the first half and the reversed second...

Input: Linked list
Output: Computed result
coding Medium Verified Question #5

5. Unpainted Segments


Category: Binary search coding problem

Question You are given a range [A, B] and a sequence of painting operations. For each operation [L, R], calculate the total length of unpainted...

Input: Array of intervals
Output: Computed result
coding Medium Verified Question #6

6. Running Tests With Failing Pairs


Category: Algorithm coding problem

Question You are given a set of test cases and a black-box function runTests() that accepts a subset of these test cases and returns whether...

Input: List
Output: Integer
coding Medium Verified Question #7

7. Connected Crop Allocation


Category: Grid/matrix coding problem

Question You are given an M x N garden grid and a list of crops, each requiring a specific number of plots. The total number of plots required by...

Input: 2D grid
Output: Computed result
coding Medium Verified Question #8

8. [CodeSignal] Maximum Zero-Sum Triplets


Category: Array coding problem

Question You are given an array A of integers. A triplet is a sequence of three consecutive elements. A triplet is called zero-sum if the...

Input: Array
Output: Computed result
coding Easy Verified Question #9

9. [CodeSignal] Coin Table Game


Category: String coding problem

Question A player is playing a game in which coins are placed on and removed from a table. The game consists of multiple rounds. At the beginning...

Input: String
Output: Computed result
coding Medium Verified Question #10

10. Longest Match Tokenizer


Category: Array coding problem
You are given a text string text and a dictionary array where each element is in the format "<key>:<id>". Here key is a token string and id...
Input: Array
Output: Computed result
coding Hard Verified Question #11

11. Dual Extremes Queue


Category: Queue-based coding problem
Design a StreamBuffer class that buffers a stream of integer latency samples in FIFO order and supports O(1) access to both the minimum and maximum...
Input: Integer(s)
Output: Integer
coding Medium Verified Question #12

12. Daily Branch Pruning


Category: Tree coding problem
A file system manages a directory tree. Each day, all leaf directories (those with no child directories) are simultaneously removed. Directories that...
Input: Array
Output: Array
coding Medium Verified Question #13

13. Path Router


Category: Algorithm coding problem

Question Design a PathRouter class that maps URL-like path patterns to handler names. Patterns may contain wildcard segments (*) that match any...

Input: Number(s)
Output: Computed result
coding Medium Verified Question #14

14. Frequency Merge Tree


Category: Tree coding problem

Question Given a string, build a Frequency Merge Tree as follows: 1. Count the frequency of each character in the string. 2. Create a leaf node...

Input: String
Output: Computed result
coding Hard Verified Question #15

15. Expression Simplifier


Category: String coding problem
Given an algebraic expression string containing single lowercase-letter variables, the operators + and -, and parentheses ( and ), simplify...
Input: String
Output: Computed result
coding Medium Verified Question #16

16. Largest Island Perimeter


Category: Grid/matrix coding problem
You are given an m x n binary grid where each cell is either '1' (land) or '0' (water). A group of connected land cells (connected horizontally...
Input: 2D grid
Output: Computed result
coding Hard Verified Question #17

17. Interval Coverage Counter


Category: Interval-based coding problem
Given a list of closed intervals on the integer number line, build a data structure that efficiently answers point-coverage queries. A closed...
Input: List
Output: Computed result
coding Hard dynamic programming #1

1. [AI Enabled Coding] BigQuery Reservation Savings Planner


Scenario
A Google Cloud team is prototyping a planner that moves flexible BigQuery queries into a dedicated reservation to reduce on-demand charges. In this simplified model, the reservation runs at most one query at a time, and each query has a fixed execution window and an estimated dollar saving. Operators need an optimal schedule and an auditable explanation of policy rejections; you may use an AI assistant while implementing it.
Part 1 — Select the best reservation schedule
  • Each input record contains string fields id, project, start, end, slots, and savings. Times are integer minutes relative to a common epoch; execution occupies [start, end).

  • Apply both eligibility rules independently: BASE_MIN_SAVINGS rejects savings below 5.00; SLOT_CAP rejects requests above 100 slots. Report every violated rule.

  • Among eligible queries, select a non-overlapping schedule maximizing total savings. A query may start exactly when the preceding query ends.

  • Break ties by selecting fewer queries, then by the lexicographically smallest sequence of query IDs in execution order. IDs use ordinary, case-sensitive lexicographic ordering.

  • Return selected IDs in execution order, total savings formatted with exactly two decimal places, and rejected records sorted by ID with rule names sorted lexicographically. Eligible but unselected queries are not rejected.

  • The return type is up to the candidate. The JSON examples specify its required observable information.


Function signature: plan_queries(jobs: list[dict[str, str]]) -> candidate_defined_type
Example 1:
Input:
{
  "jobs": [
    {"id":"a","project":"analytics","start":"0","end":"30","slots":"80","savings":"8.00"},
    {"id":"b","project":"analytics","start":"20","end":"50","slots":"100","savings":"12.00"},
    {"id":"c","project":"reporting","start":"30","end":"60","slots":"60","savings":"9.00"},
    {"id":"d","project":"reporting","start":"60","end":"70","slots":"20","savings":"4.00"},
    {"id":"e","project":"analytics","start":"60","end":"80","slots":"120","savings":"15.00"}
  ]
}

Output:
{
  "selected_ids": ["a", "c"],
  "total_savings": "17.00",
  "rejected": [
    {"id":"d","rules":["BASE_MIN_SAVINGS"]},
    {"id":"e","rules":["SLOT_CAP"]}
  ]
}

Explanation: a and c touch without overlapping and save 8.00 + 9.00 = 17.00, exceeding b alone at 12.00. Query d fails the 5.00 savings floor; e exceeds the 100-slot cap.
Part 2 — Project policies and a launch budget
Project administrators now supply additional policy records, each containing string fields project, min_savings, max_duration, and cooldown. The planner also receives an integer max_jobs, limiting the number of selected queries.
  • Preserve all Part 1 rules and tie-breaks. For a query with an explicit project policy, PROJECT_MIN_SAVINGS rejects savings below min_savings, and PROJECT_MAX_DURATION rejects execution duration end - start above max_duration.

  • A selected query with a project policy occupies the entire reservation until end + cooldown, even if the next query belongs to another project. Its effective occupied interval is [start, end + cooldown). The duration rule still measures only end - start.

  • Projects without a policy have no additional eligibility rules and a cooldown of zero. Report all violated rules, including overlapping base and project violations.

  • Select at most max_jobs queries. A limit of zero is valid and produces an empty schedule, but eligibility checks must still run.

  • Extend the result with reservations, in execution order, containing each selected query's id and string-valued available_at, equal to end + cooldown.

  • Discuss how your return type changes before implementing this extension. The design must support future named eligibility rules and additional per-project policy checks without rewriting the scheduling algorithm.


Extended function signature: plan_with_policies(jobs: list[dict[str, str]], policies: list[dict[str, str]], max_jobs: int) -> candidate_defined_type
Example 2:
Input:
{
  "jobs": [
    {"id":"a","project":"alpha","start":"0","end":"20","slots":"80","savings":"8.00"},
    {"id":"b","project":"beta","start":"20","end":"40","slots":"90","savings":"11.00"},
    {"id":"c","project":"alpha","start":"30","end":"50","slots":"70","savings":"10.00"},
    {"id":"d","project":"beta","start":"50","end":"70","slots":"100","savings":"13.00"},
    {"id":"e","project":"beta","start":"70","end":"90","slots":"60","savings":"9.00"}
  ],
  "policies": [
    {"project":"alpha","min_savings":"10.00","max_duration":"30","cooldown":"10"},
    {"project":"beta","min_savings":"5.00","max_duration":"25","cooldown":"0"}
  ],
  "max_jobs": 2
}

Output:
{
  "selected_ids": ["b", "d"],
  "total_savings": "24.00",
  "rejected": [
    {"id":"a","rules":["PROJECT_MIN_SAVINGS"]}
  ],
  "reservations": [
    {"id":"b","available_at":"40"},
    {"id":"d","available_at":"70"}
  ]
}

Explanation: a passes the base floor but fails alpha's 10.00 floor. All execution durations are 20, within the respective limits. Query c would occupy [30, 60), conflicting with both b and d. The cap prevents selecting b, d, and e together, which would save 33.00. The best allowed pair is b + d = 11.00 + 13.00 = 24.00, versus d + e = 22.00, b + e = 20.00, and c + e = 19.00.
Example 3:
Input:
{
  "jobs": [
    {"id":"u","project":"alpha","start":"0","end":"20","slots":"101","savings":"4.00"},
    {"id":"v","project":"alpha","start":"0","end":"10","slots":"100","savings":"10.00"},
    {"id":"w","project":"beta","start":"10","end":"20","slots":"100","savings":"10.00"},
    {"id":"x","project":"beta","start":"15","end":"25","slots":"100","savings":"10.00"},
    {"id":"y","project":"beta","start":"25","end":"35","slots":"100","savings":"10.00"}
  ],
  "policies": [
    {"project":"alpha","min_savings":"10.00","max_duration":"15","cooldown":"5"}
  ],
  "max_jobs": 2
}

Output:
{
  "selected_ids": ["v", "x"],
  "total_savings": "20.00",
  "rejected": [
    {"id":"u","rules":["BASE_MIN_SAVINGS","PROJECT_MAX_DURATION","PROJECT_MIN_SAVINGS","SLOT_CAP"]}
  ],
  "reservations": [
    {"id":"v","available_at":"15"},
    {"id":"x","available_at":"25"}
  ]
}

Explanation: u violates four rules: 4.00 < 5.00, duration 20 > 15, 4.00 < 10.00, and 101 > 100 slots. Query v releases the reservation at 10 + 5 = 15, so it conflicts with w but can precede x. Several two-query schedules save 10.00 + 10.00 = 20.00; ["v", "x"] is lexicographically smallest. The launch cap prevents the otherwise compatible three-query schedule ["v", "x", "y"].
Notes:
  • There are at most 2,000 jobs, IDs are unique nonempty ASCII strings of length at most 64, and each project has at most one policy; in Part 2, 0 <= max_jobs <= 30.

  • Inputs are well-formed: 0 <= start < end <= 10^9, slots are positive integers, savings are nonnegative decimal strings with exactly two fractional digits, and monetary values fit in signed 64-bit cents when summed. Policies have min_savings >= 5.00, positive max_duration, and nonnegative cooldown, each time quantity at most 10^9.

  • Use exact monetary arithmetic and a polynomial-time scheduling algorithm; the reservation model is an interview simplification, not a claim about BigQuery's actual query scheduling implementation.
Want to practise this one?
Create a free account to open the full question and practise Google questions with AI.
Sign up free
coding Hard graph #2

2. [Graph] — Earliest arrival with bounded flight connections


Background
Google Flights needs to reason about schedules rather than ordinary, static routes: reaching an airport does not guarantee that a usable connection exists. This exercise models itinerary validation with both minimum transfer time and a maximum permitted layover, extending a reported Google interview question about time-constrained flight reachability.
Problem statement
You are given an unsorted list of scheduled flights. Each flight is a tuple (origin, destination, departure, arrival), where airport names are strings and times are integer minutes measured from a common epoch. Each flight can be used only at its listed departure time.
A traveler is at airport source at time ready_time and wants to reach target as early as possible. The following rules apply:
  • The first flight must depart from source at a time in the inclusive interval [ready_time, ready_time + max_layover]. The minimum connection time does not apply before the first flight.

  • After arriving at any airport at time t, the next flight must depart from that airport in the inclusive interval [t + min_connection, t + max_layover].

  • Flights always arrive strictly after they depart. Airports may be revisited, and duplicate flight records are allowed.

  • There are no capacity restrictions, cancellations, or other travel restrictions.


Return the earliest arrival time at target among all valid itineraries, or -1 if none exists. If source == target, return ready_time without taking a flight.
A single earliest-arrival label per airport is not necessarily sufficient: arriving too early can make a later departure violate the maximum layover.
Function signature
  • earliest_arrival(flights: list[tuple[str, str, int, int]], source: str, target: str, ready_time: int, min_connection: int, max_layover: int) -> int


Example 1:
Input:
{
  "flights": [["S", "A", 0, 2], ["S", "A", 1, 6], ["A", "T", 8, 10]],
  "source": "S",
  "target": "T",
  "ready_time": 0,
  "min_connection": 1,
  "max_layover": 3
}

Output:
10

Explanation: Both flights from S are initially available because their departures lie in [0, 3]. Arriving at A at time 2 permits departures only in [3, 5], so that arrival cannot connect. Arriving at time 6 permits departures in [7, 9], allowing the flight departing at 8 and arriving at T at 10.
Example 2:
Input:
{
  "flights": [["S", "A", 0, 2], ["A", "T", 6, 8]],
  "source": "S",
  "target": "T",
  "ready_time": 0,
  "min_connection": 1,
  "max_layover": 3
}

Output:
-1

Explanation: The traveler reaches A at time 2, but the permitted connection window is [3, 5]. The departure at 6 is too late.
Constraints:
  • 0 <= len(flights) <= 200000.

  • Each airport name is a case-sensitive string containing 1–10 uppercase English letters.

  • At most 200000 distinct airports occur across the flights, source, and target.

  • For every flight, 0 <= departure < arrival <= 10^12.

  • 0 <= ready_time <= 10^12.

  • 0 <= min_connection <= max_layover <= 10^12.

  • Arithmetic must support values up to 2 * 10^12.

  • Aim for O(m log(m + 1)) time and O(m + 1) auxiliary space, where m is the number of flights; do not explicitly construct all possible flight-to-flight connections.


Follow-up:
Return an actual optimal itinerary as a list of original flight indices. Among itineraries with the earliest arrival time, return one using the fewest flights. Preserve the same asymptotic time and space bounds.
coding Medium graph #3

3. Depth First Search (DFS) — traversing a graph to find a path

Background: Google often deals with complex data structures like graphs in products like Google Maps or for web crawling. Understanding how to efficiently traverse these structures is crucial for optimizing search and routing algorithms.
Problem statement: You are given a graph represented as an adjacency list and two nodes, start and end. Your task is to determine if there exists a path from start to end using DFS. The graph is undirected and can contain cycles. Return true if a path exists; otherwise, return false.
Function/class signature:
  • def has_path(graph: List[List[int]], start: int, end: int) -> bool:

Example 1:
Input: graph = [[1, 2], [2, 3], [3], []], start = 0, end = 3
Output: True
Explanation: There's a path 0 -> 1 -> 2 -> 3.
Example 2:
Input: graph = [[1], [2], [3], []], start = 0, end = 3
Output: True
Constraints:
  • 1 <= len(graph) <= 1000

  • Each node has at most N neighbors.

  • Nodes are represented by integer indices.
coding Medium graph #4

4. Graph — Finding the Shortest Path in a Graph

Background: Google Maps relies on efficient algorithms to find the shortest routes between locations. This involves evaluating the shortest paths in a graph representation of roads and intersections.
Problem statement: Given a graph represented as an adjacency list where each edge has a weight representing distance, implement a function that finds the shortest path from a start node to a target node. You must return the total distance and the path taken as a list of node identifiers. Use Dijkstra's algorithm for this task.
Function/class signature:
  • def dijkstra(graph: Dict[str, List[Tuple[str, int]]], start: str, target: str) -> Tuple[int, List[str]]:

Example 1:
  • Input: graph = { 'A': [('B', 1), ('C', 4)], 'B': [('C', 2), ('D', 5)], 'C': [('D', 1)], 'D': [] }, start = 'A', target = 'D'

  • Output: (4, ['A', 'B', 'C', 'D'])

  • Explanation: The shortest path from A to D is A -> B -> C -> D with a total distance of 4.

Example 2:
  • Input: graph = { 'A': [('B', 2)], 'B': [('C', 2), ('D', 1)], 'C': [], 'D': [] }, start = 'A', target = 'C'

  • Output: (4, ['A', 'B', 'C'])

Constraints:
  • The graph can have at most 1000 nodes.

  • Each node is represented by a single alphabetical character.

  • Weights of the edges (distances) are positive integers.

  • All nodes are reachable from the start node.
coding Medium graph #5

5. Graph — Shortest Path in Google's Maps

Background: Google Maps requires efficient algorithms to determine the shortest path between locations to provide optimal routing for users.
Problem statement: Given a directed graph where nodes represent locations and edges represent distances, implement a function to find the shortest path from a source node to a target node using Dijkstra's algorithm. Your function should return the total distance as well as the path taken.
Function/class signature:
  • def shortest_path(graph: Dict[int, List[Tuple[int, int]]], src: int, target: int) -> Tuple[int, List[int]]:

Example 1:
  • Input: graph = {0: [(1, 5), (2, 10)], 1: [(3, 3)], 2: [(3, 1)], 3: []}, src = 0, target = 3

  • Output: (8, [0, 1, 3])

  • Explanation: The shortest path is 0 -> 1 -> 3 with a total distance of 8.

Example 2:
  • Input: graph = {0: [(1, 2), (2, 4)], 1: [(2, 1), (3, 7)], 2: [(3, 3)], 3: []}, src = 0, target = 3

  • Output: (6, [0, 1, 2, 3])

  • Explanation: The shortest path is 0 -> 1 -> 2 -> 3 with a total distance of 6.

Constraints:
  • The graph will have no more than 10^4 nodes.

  • Each node will have edges with positive weights.

  • The source and target nodes will always be valid nodes in the graph.
coding Medium graph #6

6. Graph — Find the shortest path in a grid

Background: Google Maps needs to provide users with the most efficient route to their destination. This involves evaluating various paths on a grid representing the terrain.
Problem statement: You are given a 2D grid of size m x n, where each cell represents either a road (0) or an obstacle (1). You need to find the shortest path from the top-left corner (0,0) to the bottom-right corner (m-1,n-1). Return the length of the shortest path, or -1 if there is no path available.
Function/class signature:
  • def shortestPath(grid: List[List[int]]) -> int:

Example 1:
Input: [[0,0,0],[0,1,0],[0,0,0]]
Output: 4
Explanation: The path (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) has length 4.
Example 2:
Input: [[0,1,0],[1,1,0],[0,0,0]]
Output: -1
Constraints:
  • 1 <= m, n <= 100

  • The grid only contains 0s and 1s.
coding Medium graph #7

7. Graph — Detect a Cycle in a Directed Graph


Background: Google infrastructure relies heavily on the use of directed graphs for representing dependencies in various systems, such as service dependencies in its cloud services. Detecting cycles is crucial to ensure stability and reliability in these systems.
Problem statement: Given a directed graph represented as an adjacency list, you need to determine if there is a cycle in the graph. A directed graph is cyclic if there exists at least one path that leads back to a node already visited.
Implement the function has_cycle(graph: List[List[int]]) -> bool that returns True if the given graph contains a cycle, and False otherwise.
Function/class signature:
  • def has_cycle(graph: List[List[int]]) -> bool:


Example 1:
  • Input: graph = [[1], [2], [0,3], [3]]

  • Output: True

  • Explanation: There is a cycle (0 -> 1 -> 2 -> 0).


Example 2:
  • Input: graph = [[1, 2], [2], [], [0]]

  • Output: False

  • Explanation: There are no cycles in this graph.


Constraints:
  • 1 <= len(graph) <= 10^4

  • 1 <= len(graph[i]) <= 10^4

  • Each node is a unique integer value between 0 and len(graph) - 1 inclusive.
coding Medium graph #8

8. Graph — Finding the shortest path in a directed acyclic graph (DAG)

Background: Google's Search infrastructure relies on efficient algorithms for crawling and indexing web pages. The ability to find the shortest path in a web graph is essential for optimizing the crawling process and improving user search experiences.
Problem statement: Given a directed acyclic graph represented as an adjacency list, your task is to find the shortest path from a start node to a target node. If there is no path, return -1. The graph's nodes are represented as integers from 0 to N-1 and edges are represented by pairs of integers (a, b) denoting an edge from a to b.
Function/class signature:
  • def shortest_path_dag(edges: List[Tuple[int, int]], start: int, target: int, N: int) -> int:

Example 1:
Input: edges = [(0, 1), (1, 2), (2, 3)], start = 0, target = 3
Output: 3
Explanation: The path is 0 -> 1 -> 2 -> 3, which has a length of 3.
Example 2:
Input: edges = [(0, 1), (0, 2), (2, 3)], start = 1, target = 3
Output: -1
Explanation: There is no path from node 1 to node 3.
Constraints:
  • 1 <= N <= 1000

  • 0 <= edges.length <= 10000

  • 0 <= start, target < N

  • All edges are unique and valid.

coding Medium graph #9

9. Graph Traversal — Finding the Shortest Path in a Modified Graph

Background: Google Maps needs to efficiently find the shortest path in complex road systems to provide users with optimal routes. This problem involves handling variable road conditions that affect travel time.
Problem statement: Given a directed graph represented through a list of edges with weights that represent travel times, implement a function that finds the shortest path from a starting node to a destination node, considering the possibility of temporary road closures (represented as infinite weights). Implement this using Dijkstra's algorithm.
Function/class signature:
  • def shortest_path(edges: List[Tuple[int, int, int]], start: int, destination: int) -> Optional[int]:

Example 1:
  • Input: edges = [(0, 1, 2), (1, 2, 3), (0, 2, 7), (2, 3, 1)], start = 0, destination = 3

  • Output: 6

  • Explanation: The shortest path is 0 -> 1 -> 2 -> 3, which costs 2 + 3 + 1 = 6.

Example 2:
  • Input: edges = [(0, 1, 2), (1, 2, 3), (0, 2, float('inf')), (2, 3, 1)], start = 0, destination = 3

  • Output: 6

  • Explanation: Despite the infinite weight representing a closed road, the path 0 -> 1 -> 2 -> 3 is still valid and optimal.

Constraints:
  • 1 <= len(edges) <= 10^4

  • 0 <= start < max_node

  • 0 <= destination < max_node

  • Edge weights are non-negative integers or float('inf') to denote closed roads.
coding Hard dynamic programming #10

10. [OA] Dynamic Programming — Maximal Rectangle in Google Cloud’s BigQuery

In managing large datasets, Google Cloud’s BigQuery requires efficient computations to determine the largest rectangular area defined by 1s in a binary matrix.
Problem statement: Given a m x n binary matrix filled with 0s and 1s, your task is to return the area of the largest rectangle containing only 1s. You must implement maximalRectangle(matrix: List[List[int]]) -> int.
Example 1:
Input: matrix = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
Output: 6
Explanation: The largest rectangle has an area of 6.
Example 2:
Input: matrix = [[0,0,0],[0,0,0]]
Output: 0
Explanation: There are no 1s in the matrix.
Constraints:
  • m == matrix.length

  • n == matrix[i].length

  • Area must be computed in O(m*n) time.
coding Senior graph #11

11. [OA] A* Search Algorithm — Implement the routing algorithm used for real-time traffic updates

In Google's Maps, real-time navigation requires efficient pathfinding over large graphs representing cities and road networks. Your task is to implement the A* search algorithm to find the shortest path between two points.
Problem statement: You need to implement the method findShortestPath(start: Point, end: Point) -> List[Point], which returns the shortest path as a list of Points from the start to the end. Assumptions include that the environment is represented as a 2D grid where passable and non-passable terrains are indicated.
  • Point: A representation of a coordinate with x and y attributes.


Example 1:
Input: start = (0, 0), end = (3, 3)
Output: [(0, 0), (1, 1), (2, 2), (3, 3)]
Explanation: The algorithm finds an optimal path through the grid.
Example 2:
Input: start = (1, 1), end = (4, 4)
Output: [(1, 1), (2, 2), (3, 3), (4, 4)]
Explanation: Another optimal path is provided based on proximity.
Constraints:
  • The grid size will be at most N x N with N ≤ 1000.

  • Points coordinates will be between 0 and N-1.

Related Google Software Engineer interview prep

Start practicing Google questions

Sign up for free to access walkthroughs, AI-generated questions, and more.

Get Started Free