Google logo

Google Medium Interview Questions

19 medium-level practice questions for Google technical 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
12
Coding
12
All
12
Medium
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
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 Medium Verified Question #3

3. 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 #4

4. 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 #5

5. 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 #6

6. 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 #7

7. [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 Medium Verified Question #8

8. 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 Medium Verified Question #9

9. 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 #10

10. 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 #11

11. 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 Medium Verified Question #12

12. 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 Medium graph #1

1. 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 #2

2. 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 #3

3. 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 #4

4. 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 #5

5. 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 #6

6. 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 #7

7. 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.

Start practicing Google questions

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

Get Started Free
© 2026 Tryprepforge. All rights reserved.