Google Coding Interview Questions: OA, Phone Screen & Onsite | New Grad · L3 · L4 · Intern
Google is the most searched tech company for interview prep and for good reason. Making it through a Google SDE interview means surviving 4–5 rounds of challenging DSA problems, each evaluated not just on correctness but on how you think, communicate, and handle follow-ups.
This guide is organized by interview stage OA, Phone Screen, and Onsite based on questions actually reported by candidates across 2024–2026, including fresh reports from the Google 2026 New Grad batch. Every problem includes the exact question, a worked example, the right approach, and time/space complexity.
Whether you are targeting an L3 (new grad), L4 (experienced SDE), or an internship through STEP or the SWE Intern program, this is the most complete Google PYQ resource you will find.
Google's Hiring Process for SDE Roles (2026)
1. Online Application
- Submit via careers.google.com. Referrals significantly improve your OA invite rate.
- Tip: Quantify impact. Replace "built microservices" with "designed microservices that reduced p99 latency from 800ms to 120ms for 2M daily users."
2. Online Assessment (OA) 60–90 minutes
- 2 coding problems, easy-medium difficulty, auto-graded on HackerRank or an internal platform.
- Both questions are visible from the start. Read both before starting.
- Tip: Partial credit matters get all visible test cases passing first, then handle edge cases.
3. Recruiter Call 15–30 minutes
- Non-technical. Aligns on level (L3/L4), location, and timeline. Recruiter shares a DSA prep list.
4. Technical Phone Screen 45–60 minutes (Elimination Round)
- 1–2 medium/hard DSA problems in a shared Google Doc (no IDE, no autocomplete, no syntax highlighting).
- The single biggest filter in the process.
- Tip: Think out loud. State your approach before writing code. State time and space complexity unprompted at the end.
5. Virtual Onsite Loop 4–5 Rounds (45 min each)
- Coding Rounds (2–3): 1–2 medium/hard problems per round with 2–3 follow-ups.
- System Design (L4+): Design scalable distributed systems.
- Googleyness Round: Behavioural collaboration, ownership, learning from failure, handling ambiguity.
6. Hiring Committee → Team Matching → Offer
- HC reviews all scorecards independently. Team matching takes 2–6 weeks after HC approval.
Preparation Resources
Part 1 Google Online Assessment (OA) Questions
The OA is your first real filter. 2 problems, 60–90 minutes, both visible from the start. Problems lean Easy–Medium. Speed and correctness on all test cases both matter.
1. Build the Longest Palindrome Easy
Given a string s of lowercase and uppercase letters, find the length of the longest palindrome you can build using those characters. Note: 'A' and 'a' are treated as different characters.
Input: s = "abccccdd"
Output: 7
Why: "dccaccd" uses 4 c's, 2 d's, 1 a placed in the center
Approach: Count the frequency of each character. Sum all even-count characters fully. For each odd-count character, take count − 1. If any character had an odd count, add 1 (center slot).
Complexity: Time O(n) · Space O(1)
Follow-up: What if the string contains Unicode characters beyond ASCII?
2. Compare Strings Word Universality Check Medium
Given two string arrays words1 and words2, return all strings in words1 that are universal: for every word b in words2, each character's frequency in b is ≤ its frequency in the candidate word from words1.
Input: words1 = ["amazon","apple","facebook","google","leetcode"]
words2 = ["e","o"]
Output: ["facebook","google","leetcode"]
Why: Each must contain at least 1 'e' and 1 'o'
Approach: Precompute the max frequency needed for each character across all words in words2. For each word in words1, check if it satisfies every requirement in a single pass.
Complexity: Time O(A + B) where A, B are total characters · Space O(1)
3. Largest Subarray of Length K Easy
Given an integer array nums and integer k, the largest subarray of length k is the one starting from the maximum element (the array has exactly one maximum). Return it.
Input: nums = [1,4,5,2,3], k = 3
Output: [5,2,3]
Why: Maximum element is 5 at index 2. Take k=3 elements from there.
Approach: Find the index of the maximum element using a single scan. Slice nums[maxIdx : maxIdx + k].
Complexity: Time O(n) · Space O(k)
4. Count Distinct Strings via Non-Adjacent Swaps Medium
Given string s of length n, you may perform any number of operations: pick index i and swap s[i] with s[i+1]. Constraint: if you swap at index i, you cannot also swap at i+1 in the same round. Count the number of distinct strings that can be formed.
Input: s = "abc"
Output: 4
Why: "", swap(1), swap(2), swap(1)+swap(3) → "abc","bac","acb","bca"
(positions 1 and 3 are non-adjacent so both can be swapped)
Approach: DP on the string. At each index, either skip (keep char) or swap with next (if s[i] != s[i+1] for a new string). Use memoization on (index, current string state) to count distinct outcomes.
Complexity: Time O(n²) · Space O(n)
5. Maximum Score from Removing Substrings Medium
Given string s and integers x and y, you can remove "ab" for x points or "ba" for y points any number of times. Maximize total points.
Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Why: Remove "ba"×3 (15 pts) then "ab"×1 (4 pts)
Approach: Greedily remove the higher-value pair first (stack pass), then do a second pass for the lower-value pair on the remaining string.
Complexity: Time O(n) · Space O(n)
6. Minimum Operations to Make Array Alternating Medium
Given a 0-indexed even-length array nums, make it alternating: all even-indexed elements equal, all odd-indexed elements equal, and the two values differ. Return minimum operations (each operation changes one element to any value).
Input: nums = [3,1,3,2,4,3]
Output: 3
Approach: Find the top-2 most frequent elements at even positions and odd positions. Answer = n − (best_even + best_odd), handling the edge case where the most frequent element is the same at both positions (use the second-best for one side).
Complexity: Time O(n) · Space O(n)
7. Sum of Beauty of All Substrings Medium
The beauty of a string = (max frequency char) − (min frequency char). Given string s, return the sum of beauty of all its substrings.
Input: s = "aabcb"
Output: 5
Approach: For each starting index i, expand the window rightward maintaining a frequency array. At each step, compute max − min frequency in O(26). Sum all values.
Complexity: Time O(n² × 26) · Space O(26)
8. Student Lines Minimum New Lines Created Medium
Students arrive one at a time. Each student joins an existing line if all students in it are taller than them, or starts a new line. Given an array of heights in arrival order, return the minimum number of lines formed.
Input: heights = [5, 3, 6, 2, 4]
Output: 3
Why: Line1:[5,3,2], Line2:[6,4], Line3:[] greedy assigns each
student to a valid line with the smallest tail > student height
Approach: Maintain a list of current line "tail" heights (smallest student so far in each line). For each new student, binary search for the smallest tail that is strictly greater than the student. If found, replace it. Otherwise, open a new line. (Analogous to Longest Increasing Subsequence / patience sorting.)
Complexity: Time O(n log n) · Space O(n)
Part 2 Phone Screen Questions
The phone screen is a 45–60 minute session in a plain Google Doc. Expect 1–2 medium problems with follow-ups. These are the most commonly reported problems from 2024–2026 phone screens.
9. Router Broadcast BFS with Distance Limit Medium
A source router broadcasts to all routers within d hops. Given the network as an undirected graph, return true if the destination router dest receives the broadcast.
Input: edges = [[0,1],[1,2],[2,3]], source = 0, dest = 2, d = 2
Output: true (0→1→2 is 2 hops, within limit)
Input: edges = [[0,1],[1,2],[2,3]], source = 0, dest = 3, d = 2
Output: false (0→1→2→3 needs 3 hops)
Approach: BFS from source tracking hop count. If dest is reached within d levels, return true.
Complexity: Time O(V+E) · Space O(V)
Follow-up: What if edges have weights and distance = sum of weights? → Use Dijkstra with dist[dest] ≤ d check.
10. Remove All "AB" and "CD" Pairs from a String Medium
Given a string of 'A', 'B', 'C', 'D', repeatedly remove the first occurrence of "AB" or "CD" until none remain. Return the final string.
Input: s = "ACDCBD"
Steps: "ACDCBD" → remove CD → "ACBD" → remove AB → "CD" → remove CD → ""
Output: ""
Approach: Use a stack. Push each character. After every push, check if the top two chars form "AB" or "CD" if so, pop both. This is O(n) and avoids repeated rescanning.
Complexity: Time O(n) · Space O(n)
11. Minimum Jumps to Reach End Medium
nums[i] is the max jump length from index i. Return the minimum number of jumps to reach the last index. You can always reach the end.
Input: nums = [2,3,1,1,4]
Output: 2
Why: Jump index 0→1 (jump len 2, land on 3), then 1→4 (jump len 3)
Approach: Greedy with curEnd (boundary of current jump) and farthest (max reachable so far). When index == curEnd, increment jumps and extend to farthest.
Complexity: Time O(n) · Space O(1)
12. Subarray Sum Closest to Target Medium
Given an array (may contain negatives) and integer k, find the contiguous subarray whose sum is closest to k. Return that sum.
Input: nums = [1,3,-2,5,4], k = 6
Output: 6 (subarray [3,-2,5] sums to 6)
Approach: Build prefix sums, store sorted. For each P[j], binary search for P[j] − k in the sorted prefix array. Track minimum absolute difference found.
Complexity: Time O(n log n) · Space O(n)
13. Binary Search with Hidden Array + Trie Follow-up Hard
You have a hidden sorted-descending binary array of length n (all 1s before all 0s). You can only access it via query(i) which returns the value at index i. Find the count of 1s using minimum queries.
n = 10, hidden = [1,1,1,1,0,0,0,0,0,0]
Output: 4 (4 ones found via binary search in O(log n) queries)
Approach: Binary search. If query(mid) == 1, search right half. If 0, search left half. The boundary gives the count.
Complexity: Time O(log n) queries · Space O(1)
Follow-up (actual): Solve prefix-based queries on strings using a Trie. Build a Trie from a dictionary; countWithPrefix(prefix) returns how many words start with prefix.
14. Minimum Cost to Connect All Ropes Medium
Connect n ropes into one. Cost of connecting two ropes = sum of their lengths. Find minimum total cost.
Input: ropes = [4,3,2,6]
Output: 29
Why: (2+3)=5 cost 5, (4+5)=9 cost 9, (9+6)=15 cost 15 → total 29
Approach: Min-heap. Always merge the two smallest ropes first (greedy, same as Huffman coding). Push the merged rope back.
Complexity: Time O(n log n) · Space O(n)
Part 3 Onsite Interview Questions
Google onsite rounds go deep. One medium problem + 2–3 follow-ups is the norm, or two medium problems back-to-back. Focus on thinking out loud and handling edge cases gracefully.
Arrays & Two Pointers
15. 3Sum All Unique Triplets Summing to Zero Medium
Return all unique triplets [a,b,c] from nums such that a + b + c == 0.
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Approach: Sort the array. Fix the first element, use two pointers for the rest. Skip duplicates at each pointer after a match.
Complexity: Time O(n²) · Space O(1) excluding output
16. Trapping Rain Water Hard
Given an elevation map height[], compute how much water can be trapped between bars.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Approach: Two pointers. Track leftMax and rightMax. Water at each position = min(leftMax, rightMax) − height[i]. Move the smaller-max pointer inward.
Complexity: Time O(n) · Space O(1)
17. Container With Most Water Medium
Find two lines forming a container that holds the most water.
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Approach: Two pointers at ends. Area = min(h[l], h[r]) × (r − l). Always move the pointer with smaller height.
Complexity: Time O(n) · Space O(1)
Strings
18. Minimum Window Substring Hard
Return the minimum window in s that contains all characters of t.
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Approach: Sliding window. Expand right until all chars of t are covered, then shrink from the left. Track the shortest valid window seen.
Complexity: Time O(n) · Space O(t)
19. Group Strings by Shifting Sequence Medium
Group strings that belong to the same shifting sequence (e.g. "abc"→"bcd"→"xyz").
Input: ["abc","bcd","acef","xyz","az","ba","a","z"]
Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]
Approach: Normalize each string to a canonical form by computing differences between consecutive chars (mod 26). Use this as hash map key.
Complexity: Time O(n×L) · Space O(n×L)
20. Minimum Cuts for Palindrome Partitioning Hard
Find the minimum cuts to partition string s so every part is a palindrome.
Input: s = "aab"
Output: 1 (cut between "aa" and "b")
Approach: Precompute isPalin[i][j] (expand around center, O(n²)). Then DP: dp[i] = min cuts for s[0..i]. For each i, try all j ≤ i where s[j..i] is a palindrome.
Complexity: Time O(n²) · Space O(n²)
Trees
21. Lowest Common Ancestor of a Binary Tree Medium
Find the deepest node that is an ancestor of both p and q.
Input: root=[3,5,1,6,2,0,8,null,null,7,4], p=5, q=4
Output: 5 (5 is an ancestor of 4)
Approach: Post-order DFS. Return the node if it equals p or q. If both left and right return non-null, current node is the LCA.
Complexity: Time O(n) · Space O(h)
Follow-up: What if the tree is a BST? What if nodes don't necessarily exist in the tree?
22. Binary Tree Maximum Path Sum Hard
Find the path (start/end at any nodes) in a binary tree with the maximum sum.
Input: root = [-10,9,20,null,null,15,7]
Output: 42 (path 15→20→7)
Approach: At each node, compute max gain from left and right (clamp to 0 if negative). Update global max with left + node.val + right. Return node.val + max(left, right) to parent.
Complexity: Time O(n) · Space O(h)
23. Serialize and Deserialize Binary Tree Hard
Design an algorithm to encode a tree as a string and decode it back losslessly.
Input: [1,2,3,null,null,4,5]
Encode: "1,2,null,null,3,4,null,null,5,null,null"
Decode: same tree restored
Approach: Preorder DFS for serialization using # for nulls and , as delimiter. Deserialize by consuming tokens from a queue, recursively building.
Complexity: Time O(n) · Space O(n)
24. Minimum Weight to Disconnect All Leaf Nodes Hard
Given a weighted binary tree, find the minimum total edge weight to remove so every leaf becomes unreachable from the root.
Input: tree with edges: root→A (weight 5), A→leaf1 (weight 2), root→leaf2 (weight 7)
Output: 9 (remove A→leaf1 costs 2, remove root→leaf2 costs 7)
Approach: DFS on each root-to-leaf path, tracking the minimum-weight edge on the path. Removing that minimum edge disconnects the leaf at lowest cost. Greedily collect these minimum edges.
Complexity: Time O(n) · Space O(h)
Graphs
25. Word Ladder Minimum Transformation Steps Hard
Find the shortest transformation from beginWord to endWord, changing one letter at a time, using only dictionary words.
Input: beginWord="hit", endWord="cog"
wordList=["hot","dot","dog","lot","log","cog"]
Output: 5 (hit→hot→dot→dog→cog)
Approach: BFS. For each word, try every single-character mutation and check the dictionary. Add valid unvisited words to the queue. Return the level at which endWord is reached.
Complexity: Time O(M²×N) where M = word length, N = dict size · Space O(M×N)
26. Boolean Constraint Satisfaction (Union-Find) Medium
Given equations like a==b, b==c, a!=c, determine if all constraints can be satisfied simultaneously.
Input: ["a==b","b==c","a!=c"]
Output: false (a==b==c contradicts a!=c)
Approach: Two-pass Union-Find. First, union all == pairs. Then verify no != pair shares the same component.
Complexity: Time O(n × α(n)) · Space O(1) (26 chars)
27. Course Schedule II Topological Sort Medium
Return a valid order to finish all courses given prerequisites, or [] if impossible.
Input: n=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3] (or any valid topological order)
Approach: Kahn's algorithm maintain in-degree counts, process zero in-degree nodes via BFS. If all n nodes are processed, a valid order exists.
Complexity: Time O(V+E) · Space O(V+E)
Dynamic Programming
28. Edit Distance Hard
Minimum insert / delete / replace operations to convert word1 into word2.
Input: word1 = "horse", word2 = "ros"
Output: 3 (horse→rorse→rose→ros)
Approach: 2D DP. dp[i][j] = min operations for first i chars of word1 to first j chars of word2. If chars match: dp[i-1][j-1], else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
Complexity: Time O(m×n) · Space O(m×n) (optimizable to O(n))
29. Decode Ways Medium
'A'→1 through 'Z'→26. Count total ways to decode a digit string.
Input: s = "226"
Output: 3 ("BZ","VF","BBF")
Approach: DP where dp[i] = ways to decode s[0..i-1]. Add dp[i-1] if s[i-1] != '0'; add dp[i-2] if s[i-2..i-1] is 10–26.
Complexity: Time O(n) · Space O(n)
30. Maximal Square Medium
Find the largest square of all '1's in a binary matrix. Return its area.
Input: [["1","0","1"],["1","1","1"],["1","1","1"]]
Output: 4 (2×2 square in bottom-right)
Approach: dp[i][j] = side of largest square with bottom-right at (i,j). If matrix[i][j]=='1': dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.
Complexity: Time O(m×n) · Space O(m×n)
31. String Grouping with Distinct Char Constraint Hard
Given string s and integer k, divide into groups of size ≤ k. All occurrences of each distinct character must land in the same group. Return minimum number of groups, or -1 if any single character's total count exceeds k.
Input: s = "aabbcc", k = 4
Output: 2 (groups: all a's+b's = 4, all c's = 2)
Approach: Count occurrences of each character. If any count > k, return -1. Sort character blocks by count. Greedily fill bins of size k.
Complexity: Time O(n + C log C) where C = distinct chars · Space O(C)
Design Problems
32. LRU Cache Medium
Design get(key) and put(key, value) both in O(1) time, with LRU eviction at capacity.
LRUCache(2) → put(1,1) → put(2,2) → get(1)=1
→ put(3,3) [evicts key 2] → get(2)=-1
Approach: Doubly linked list + hash map. Hash map gives O(1) lookup; linked list maintains usage order. Move accessed node to head; evict from tail.
Complexity: Time O(1) per operation · Space O(capacity)
33. Find Median from Data Stream Hard
Support addNum(n) and findMedian() dynamically.
addNum(1) → addNum(2) → findMedian()=1.5 → addNum(3) → findMedian()=2.0
Approach: Max-heap for lower half, min-heap for upper half. Keep sizes balanced (diff ≤ 1). Median = top of larger heap or average of both tops.
Complexity: Time O(log n) add · O(1) median · Space O(n)
34. Design Hit Counter Medium
Count hits in the past 300 seconds. Support hit(timestamp) and getHits(timestamp).
hit(1) → hit(2) → hit(300) → getHits(300)=3 → hit(301) → getHits(301)=2
Approach: Circular array of 300 slots. Each slot stores (timestamp, count). On hit, overwrite slot if timestamp differs. On getHits, sum only slots whose timestamp is within the window.
Complexity: Time O(1) per operation · Space O(300)
Follow-up: Handle distributed hits across multiple machines.
35. Robot Room Cleaner Hard
A robot with move(), turnLeft(), turnRight(), clean() APIs must clean the entire reachable room. Grid layout and obstacles are unknown.
Approach: DFS with backtracking. Track visited cells by relative (row, col, direction). After exploring each direction, backtrack by rotating 180°, stepping forward, rotating back. Clean the current cell before exploring.
Complexity: Time O(N−M) cells visited · Space O(N−M) for visited set
Additional High-Frequency Questions
36. Longest Consecutive Sequence Medium
Find the length of the longest consecutive sequence in an unsorted array. Must run in O(n).
Input: [100,4,200,1,3,2] → Output: 4 (1,2,3,4)
Approach: Hash set. For each number that has no n−1 in set (sequence start), expand forward. Time O(n) · Space O(n).
37. Word Break Medium
Can s be segmented into dictionary words?
Input: s="applepenapple", dict=["apple","pen"] → Output: true
Approach: DP. dp[i] = true if s[0..i-1] segments cleanly. Time O(n²) · Space O(n).
38. Generate Parentheses Medium
Generate all valid combinations of n pairs of parentheses.
n=3 → ["((()))","(()())","(())()","()(())","()()()"]
Approach: Backtracking. Add ( if open < n, add ) if close < open. Time O(4^n/√n).
39. Clone Graph Medium
Deep copy a connected undirected graph given a node reference.
Approach: DFS/BFS + hash map (original → clone). Time O(V+E) · Space O(V).
40. Pacific Atlantic Water Flow Medium
Find cells from which water can flow to both oceans.
Approach: Reverse BFS from both borders. Answer = intersection of both reachable sets. Time O(m×n).
41. Longest Increasing Subsequence Medium
Input: [10,9,2,5,3,7,101,18] → Output: 4 ([2,3,7,101])
Approach: Binary search on tails[] array (patience sorting). Time O(n log n) · Space O(n).
42. Alien Dictionary Hard
Derive character ordering from a sorted word list in an alien language.
["wrt","wrf","er","ett","rftt"] → "wertf"
Approach: Build directed graph from adjacent word comparisons. Topological sort + cycle detection. Time O(C).
43. Implement Trie (Prefix Tree) Medium
Implement insert, search, startsWith.
Approach: Each node = children map + isEnd flag. Time O(m) per operation.
44. Number of Islands Medium
Count connected groups of '1's in a grid.
Approach: DFS from each unvisited '1', mark connected cells. Increment count per DFS call. Time O(m×n).
45. Minimum Spanning Tree Connect Cities Medium
Minimum cost to connect all n cities.
Approach: Kruskal's sort edges by weight, Union-Find to avoid cycles. Time O(E log E).
46. Copy List with Random Pointer Medium
Deep copy a linked list where each node has next and random pointers.
Approach: Two-pass with hash map (original → clone). Time O(n) · Space O(n).
47. Random Pick with Weight Medium
Pick index i with probability proportional to w[i].
Approach: Prefix sum + binary search on a random number in [1, totalSum]. Time O(log n) per pick.
48. Merge K Sorted Lists Hard
Merge k sorted linked lists into one.
[1→4→5, 1→3→4, 2→6] → 1→1→2→3→4→4→5→6
Approach: Min-heap of size k. Extract min, push next node from that list. Time O(n log k).
49. Next Permutation Medium
Rearrange to the lexicographically next greater permutation in-place.
[1,2,3] → [1,3,2]
[3,2,1] → [1,2,3] (wrap-around)
Approach: Find rightmost element smaller than its successor. Swap with smallest larger element to its right. Reverse the suffix. Time O(n) · Space O(1).
50. Burst Balloons Hard
Burst balloons to maximize coins. Bursting balloon i earns nums[i-1] × nums[i] × nums[i+1].
Input: [3,1,5,8] → Output: 167
Approach: Interval DP. Think in reverse choose the last balloon to burst in each interval. dp[i][j] = max coins from bursting all balloons in (i,j). Time O(n³) · Space O(n²).
Preparation Tips
- Practice in a plain text editor: Google interviews happen in a Google Doc no autocomplete, no syntax highlighting. Simulate this.
- Medium is the baseline: Easy questions only appear in the OA. Phone screen and onsite expect medium-to-hard. Solve at least 150 LeetCode mediums before your phone screen.
- State complexity unprompted: Google interviewers expect time and space complexity at the end of every solution without being asked.
- Strong areas for Google: Trees (LCA, construction, path problems), Graphs (BFS/DFS, Union-Find, topological sort), and DP (2D DP, interval DP, string DP).
- Handle follow-ups: Google interviewers always have follow-ups. Be ready to optimize further, handle larger inputs, or adapt to a distributed setting.
- Googleyness Round: Prepare 5–6 genuine STAR stories collaboration, learning from failure, decisions under ambiguity, disagreeing respectfully.
- System Design (L4+): Study consistent hashing, sharding, replication, CAP theorem. Read the Google Spanner and Bigtable papers if time permits.
Join Telegram group for any doubts & discussions!