Google logo

Google Interview Questions

52 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
17
Coding
17
All
1
Easy
12
Medium
4
Hard
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 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 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.
coding Hard dynamic programming #8

8. [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 #9

9. [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.
system design Hard api design #10

10. [OA] Design a Google-like Search Autocomplete System

As Google’s search engine evolves, providing suggestions while users type is critical for enhancing search quality and user experience. Your task is to design an autocomplete system that suggests search terms based on previously entered queries.
Problem statement: Design a class AutocompleteSystem that supports the following operations:
  • input(char c: char) -> List[str]: Accepts a character and returns a list of the top 3 suggested terms that start with the current input string based on weighted frequency.

  • addSentence(sentence: str, times: int) -> None: Adds a new sentence with its corresponding frequency.


Example 1:
Input:
autocompleSystem = new AutocompleteSystem();
autocompleSystem.addSentence("i love you", 5);
autocompleSystem.addSentence("island", 5);
output = autocompleSystem.input('i');
// returns ["i love you", "island"]
Example 2:
Input:
autocompleSystem = new AutocompleteSystem();
autocompleSystem.addSentence("hi", 2);
output = autocompleSystem.input('h');
// returns ["hi"]
Constraints:
  • The input will only be lowercase English letters.

  • The total number of sentences will not exceed 1000.

  • Each sentence has at most 100 characters.
system design Hard cache #11

11. [OA] LRU Cache — Implement a caching layer for Google API responses

In optimizing the performance of Google’s services, managing frequently accessed data is key. Implement an LRU Cache for the API calls to minimize latency and server calls.
Problem statement: Implement an LRUCache class with the following methods:
  • get(key: int) -> int: Returns the value of the key if the key exists, otherwise return -1.

  • put(key: int, value: int) -> None: Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, the least recently used key should be removed.


Example 1:
Input:
lruCache = LRUCache(2);
lruCache.put(1, 1);
lruCache.put(2, 2);
output1 = lruCache.get(1); // returns 1
lruCache.put(3, 3); // evicts key 2
output2 = lruCache.get(2); // returns -1 (not found)
Example 2:
Input:
lruCache = LRUCache(1);
lruCache.put(2, 1);
output1 = lruCache.get(2); // returns 1
lruCache.put(3, 2); // evicts key 2
output2 = lruCache.get(2); // returns -1 (not found)
Constraints:
  • The capacity of the cache will be at most 10^4.

  • The keys are guaranteed to be unique within the cache.

Start practicing Google questions

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

Get Started Free
© 2026 Tryprepforge. All rights reserved.