Google Interview Questions
- DSA
- LLD
- HLD
Q1: Longest Consecutive Sequence
Given an array of integers, find the length of the longest consecutive elements sequence running in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is[1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9
Example 3:
Input: nums = [1,0,1,2] Output: 3
Q2: Sort Colors
Sort an array containing 0, 1, and 2 to group colors in-place.
Example 1:
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1] Output: [0,1,2]
Q3: House Robber III
Maximize sum of values in nodes of a binary tree without robbing two directly connected nodes.
Example 1:
Input: root = [3,2,3,null,3,null,1] Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: root = [3,4,5,1,3,null,1] Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
Q4: Minimum Operations to Reduce X to Zero
Minimum number of operations removing elements from ends of array to reduce sum by x.
Example 1:
Input: nums = [1,1,4,2,3], x = 5 Output: 2 Explanation: The optimal solution is to remove the last two elements to reduce x to zero.
Example 2:
Input: nums = [5,6,7,8,9], x = 4 Output: -1
Example 3:
Input: nums = [3,2,20,1,1,3], x = 10 Output: 5 Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.
Q5: Detect Cycle in an Undirected Graph (using DFS)
Given an undirected graph with V vertices and E edges, check whether it contains any cycle or not.
Example 1:
Input: V = 8, E = 7 Output: No
Explanation: No cycle in the given graph.
Example 2: Input: V = 8, E = 6
Output: Yes Explanation: 4->5->6->4 is a cycle.
Q6: Find the Celebrity
Find a celebrity who is known by everyone but knows no one.
Example 1:
Input: N = 4, M = [[0,1,1,1], [0,0,1,1], [0,0,0,0], [0,1,1,0]]
Output: 2
Explanation: Person 2 is known by everyone (0, 1, and 3) but does not know anyone in return. Hence, person 2 is the celebrity.
Example 2:
Input: N = 3, M = [[0,1,0], [0,0,0], [1,1,0]]
Output: 1
Explanation: Everyone knows person 1, and person 1 knows no one. Therefore, person 1 is the celebrity.
Example 3:
Input: N = 3, M = [[0,1,0], [0,0,1], [1,0,0]]
Output: No Celebrity
Explanation: No single person is known by everyone while knowing no one. Hence, no celebrity exists in this graph.
Q7: Minimum Cost to Connect Sticks
Connect sticks in minimum total cost where cost is sum of sticks connected.
Example 1:
Input: Sticks = [2, 4, 3]
Output: 14
Explanation:
Combine sticks of length 2 and 3 → cost = 5
Sticks become [4, 5]
Combine 4 and 5 → cost = 9
Total cost = 5 + 9 = 14
Example 2:
Input: Sticks = [1, 8, 3, 5]
Output: 30
Explanation:
Combine 1 and 3 → cost = 4, new sticks = [4, 5, 8]
Combine 4 and 5 → cost = 9, new sticks = [8, 9]
Combine 8 and 9 → cost = 17
Total cost = 4 + 9 + 17 = 30
Example 3:
Input: Sticks = [5]
Output: 0
Explanation: Only one stick, no cost required for any connection.
Q8: Rotting Oranges
Time taken to rot all oranges in grid spreading rot to adjacent cells.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten because rotting only happens in the four directions (up, down, left, right).
Example 3:
Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Q9: Word Search
Search if a word exists in a 2D grid of letters, moving adjacent cells.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Q10: 3Sum
Find all triplets in array which sum to zero.
Example 1:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
The distinct triplets are [-1, 0, 1] and [-1, -1, 2].
Note that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0, 1, 1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
Explanation: The only possible triplet sums up to 0.
Q11: LRU Cache
Implement Least Recently Used cache with get and put in O(1).
Example 1:
Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"][[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation:
Q12: Next Permutation
Rearrange array to next lexicographically greater permutation.
Example 1:
Input: nums = [1, 2, 3]
Output: [1, 3, 2]
Example 2:
Input: nums = [3, 2, 1]
Output: [1, 2, 3]
Example 3:
Input: nums = [1, 1, 5]
Output: [1, 5, 1]
Q13: Stack using Queue
Implement stack operations using queue.
Example 1:
Input: ["MyStack", "push", "push", "top", "pop", "empty"][[], [1], [2], [], [], []]
Output: [null, null, null, 2, 2, false]
Explanation:
Q14: Zigzag Conversion
Convert string into zigzag pattern based on given rows.
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Zigzag pattern:
Q1. Car Rental System
Design a car rental system supporting search, reservation, cancellation, billing with multiple vehicle types, stores, and notifications.
Use Factory, Strategy, Observer, Singleton patterns for extensibility and modularity.
Q2. Peer-to-Peer Parcel Delivery System
Parcel delivery between customers and drivers handling states, concurrency, auto assignment, and notifications.
Q3. Spring Boot API Development with Pagination & Exception Handling
- Develop REST APIs supporting request pagination, robust global exception handling, security, and unit testing.
Q4. Todo List Machine Coding
CRUD and search operations on todo tasks.
Q5. Student / Teacher OOP Class Design
Implement classes with inheritance for shared and unique attributes.
Q6. Producer-Consumer Problem with Java BlockingQueue
Thread-safe synchronization between producers and consumers.
Q1. Car Pooling System Design
Design scalable ride sharing matching system, with database choices, API design, CAP considerations, and real-time notifications.
Q2. Online Bidding System Design
Scalable system for auction and bidding processes.
Q3. Spotify-like Music Streaming System
Q4. Notification Service System Design
Design microservice for efficient notifications delivery.
Q5. API Design with Pagination, Rate Limiting, and Error Handling
Design APIs to handle massive load with proper error codes and scalable pagination.
