Google logo

Google Hard Interview Questions

9 hard-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
coding Hard Verified Question #1

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

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

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

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

3. [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.
system design Hard api design #4

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

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