Is LeetCode enough for Google?

While LeetCode can be a useful tool to prepare candidates for interview prep, more is needed to ace the interview. Candidates must focus on logical thinking, in-depth knowledge of foundational concepts, and communication skills.

Home/Blog/Interview Prep/Google coding interview questions: Top 18 questions explained

Google coding interview questions: Top 18 questions explained

Aaron Xie

Jun 26, 2024

23 min read

content

Landing a tech job at Google is no easy feat. Like other large tech giants, Google’s software engineering interview process is comprehensive and difficult, requiring weeks of preparation and practice. So, how can you prepare for the coding interview? What interview questions should prepare for?

Today we’ll revisit our Google Coding interview series and breakdown 18 common interview questions asked by Google recruiters.

Today we’ll cover the following:

Google coding interview recap
Top 18 Google coding interview questions with explanations
More practice and preparation
Wrapping up and resources

Google coding interview recap#

The entire Google interview process takes around two months to complete and consists of five interviews in total. For the interviews, there will primarily be three question formats: system design interview, general analysis, and technical skills.

Prescreen: The first interview consists of a prescreening with a Google employee, which will last 45 - 60 minutes. In this interview, the interviewer will test you on your knowledge of data structures and algorithms.

On-site interviews: If you past the prescreen, you will be invited to an on-site interview, in which you will be interviewed by 4-6 employees for 45 minutes each. These interviews will more rigorously test your knowledge of data structures and algorithms. Typically, you will be writing code on a Google Doc or whiteboard.

Decision: Based on your performance, you will be scored on a scale between 1 and 4, with 3 being the minimum threshold to hire.

Overall, Google wants to test your technical and logical application of computer science. Here are some popular topics to review before your interview:

1. Find the kth largest element in a number stream#

Design a class to efficiently find the $k^{th}$ largest element in a stream of numbers. The class should have the following two things:

The constructor of the class should accept an integer array (nums) containing initial numbers from the stream and an integer $k$ .
The class should expose a function add(int value) which will add the number value to the stream of numbers, and will return the $k^{th}$ largest number in the stream seen so far.

Time complexity of __init__: $O((n-k) \log n) = O(n \log n)$

Time complexity of add: $O(\log k)$ , where $k$ represents the size of the heap.

Space complexity of __init__: $O(k)$

Space complexity of add: $O(k)$ , where $k$ represents the size of the heap.

Solution summary#

The KthLargest class is designed to efficiently maintain the $k$ largest elements within a given list using a min heap. Here’s a breakdown of the solution:

Initialization: Upon initialization, the constructor sets the instance variables k and nums, where k denotes the $k^{th}$ largest element to be tracked, and nums represents the input list of numbers. The constructor heapifies the list and prunes elements from the heap until its length is reduced to k, ensuring only the $k$ largest elements remain.
Adding elements: The add method is responsible for adding a new element val into the heap. If the length of nums exceeds k after adding the new element, the method heappop is used to remove the smallest element from the heap. Subsequently, it returns the smallest element in the heap, which corresponds to the $k^{th}$ largest element.

2. Find k closest numbers#

You are given a sorted array of integers, nums, and two integers, target and k. Your task is to return k number of integers that are closest to the target value, target. The integers in the output array should be in sorted order.

An integer, nums[i], is considered to be closer to target, as compared to nums[j] when |nums[i] - target| < |nums[j] - target|. However, when |nums[i] - target| == |nums[j] - target|, the smaller of the two values nums[i] and nums[j] is selected.

Time complexity: $O(\log n + k)$

Space complexity: $O(1)$

Solution summary#

The find_closest_elements function efficiently identifies the $k$ closest elements to a given target value within a sorted list of numbers. Here’s an overview of the solution:

Edge cases handling: If the length of nums is equal to the value in the variable k, the function returns the entire list since all elements are closest to the target. Similarly, if the target is less than or equal to the first element of nums, it returns the first $k$ elements. Likewise, if the target is greater than or equal to the last element of nums, it returns the last $k$ elements.
Binary search for closest element: The function utilizes the binary_search function to find the index of the closest element to the target in the sorted list nums.
Window expansion: After finding the index of the closest element, the function expands a window around this element to capture the $k$ closest elements. It iteratively adjusts the window boundaries based on the proximity of elements to the target until the window contains exactly $k$ elements.
Result extraction: Finally, the function returns the elements within the determined window, representing the $k$ closest numbers to the target.

Time complexity: $O(n)$

Note: In the worst case, the time complexity for operations like accessing and inserting elements in a dictionary can degrade to $O(n)$ , which could potentially result in an overall time complexity of $O(n^2)$ if there are many collisions. However, such scenarios are uncommon.

Space complexity: $O(n)$

Solution summary#

The two_sum function efficiently finds the indices of two numbers in an array that sum up to a given target value t. Here’s an overview of the solution:

Dictionary for indices storage: The function initializes an empty dictionary indices to store the indices of array elements.
Iterative search for complement: It iterates through the array using the enumerate function to access both the elements and their indices. For each element num, it calculates its complement (t - num) and checks if this complement exists in the indices dictionary.
Return indices if complement found: If the complement is found in the dictionary, it means that the current element, along with its complement, sums up to the target value. The function returns the indices of these two elements.
Update indices dictionary: If the complement is not found, the current element’s index is stored in the indices dictionary with the element itself as the key.
Handling no solution: If no solution is found after iterating through the entire array, the function returns an empty list.

main.py

linked_list.py

from linked_list import ListNode
def delete_node(head, key):
    
    # Write your code here
    return head
if __name__ == "__main__":
    # Test the LinkedList
    linked_list = ListNode()
    linked_list.append('A')
    linked_list.append('B')
    linked_list.append('C')
    linked_list.append('D')
    linked_list.print_list()
    print("Deleting the A node")
    linked_list = delete_node(linked_list, 'A')
    linked_list.print_list()
    print("Deleting the C node")
    linked_list = delete_node(linked_list, 'C')
    linked_list.print_list()
    print("Deleting the D node")
    linked_list = delete_node(linked_list, 'D')
    linked_list.print_list()

Time complexity: $O(n)$

Space complexity: $O(1)$

Solution summary#

The delete_node function aims to remove a node with a specified key from a singly linked list. Here’s a summary of the solution:

Check if the head node contains the value passed in the variable key.
Otherwise, traverse the linked list using the pointers prev_node and curr_node to point to two consecutive nodes.
While traversing, compare the value of each node with the given key. If a node with the key value is found, update the next pointer of the previous node (prev_node) to bypass the current node (curr_node), effectively removing curr_node from the linked list.
Return the head of the modified linked list.

class LinkedListNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.arbitrary = None
def deep_copy_with_arbitrary_pointer(head):
    
    # Write your code here
    return None
def print_linked_list(head):
    current = head
    while current:
        arbitrary_data = current.arbitrary.data if current.arbitrary else None
        print(f"Data: {current.data}, Arbitrary data: {arbitrary_data}, Memory address: {id(current)}")
        current = current.next
# Example usage with provided input and output
if __name__ == "__main__":
    # Create the original linked list with arbitrary pointers
    head = LinkedListNode(7)
    node1 = LinkedListNode(13)
    node2 = LinkedListNode(11)
    node3 = LinkedListNode(10)
    node4 = LinkedListNode(1)
    head.next = node1
    node1.next = node2
    node2.next = node3
    node3.next = node4
    head.arbitrary = None
    node1.arbitrary = head
    node2.arbitrary = node4
    node3.arbitrary = node2
    node4.arbitrary = head
    print("Original linked list: ") 
    print_linked_list(head)
    
    # Perform deep copy with arbitrary pointer
    copied_head = deep_copy_with_arbitrary_pointer(head)
    print("\nCopied linked list for verification: ")
    print_linked_list(copied_head)

Time complexity: $O(n)$

Space complexity: $O(n)$

Solution summary#

To perform a deep copy of a linked list with arbitrary pointers, the algorithm follows these steps:

Create a mapping: Iterates through the original linked list (head) and creates a mapping (mapping) between each original node and its corresponding new node. Each new node is initialized with the same data as the original node.
Set pointers: While iterating through the original list again, it updates the next pointers of the new nodes based on the mapping of original next pointers. Simultaneously, it sets the arbitrary pointers of the new nodes using the mapping to find corresponding new nodes for the arbitrary pointers of the original nodes.
Return the head of the new list: Finally, it returns the head of the new list (mapping[head]), which now represents a deep copy of the original linked list with correct next and arbitrary pointers.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def print_tree(self, level=0):
        if self.right:
            self.right.print_tree(level + 1)
        print(' ' * 6 * level+ '  ', self.val)
        if self.left:
            self.left.print_tree(level + 1)
def mirror_tree(root):
    
    # Write your code here
    return root
# Test the function with the provided example
if __name__ == "__main__":
    # Define the tree according to the provided example
    root = TreeNode(40)
    root.left = TreeNode(100)
    root.right = TreeNode(400)
    root.left.left = TreeNode(150)
    root.left.right = TreeNode(50)
    root.right.left = TreeNode(300)
    root.right.right = TreeNode(600)
    # Print the original tree
    print("Original Tree:")
    root.print_tree()
    # Perform mirror operation
    mirrored_root = mirror_tree(root)
    # Print the mirrored tree
    print("\nMirrored Tree:")
    mirrored_root.print_tree()

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def print_tree(self):
        self._print_tree(self, 0)
    def _print_tree(self, root, depth):
        if root:
            self._print_tree(root.right, depth + 1)
            print("  " * depth + str(root.val))
            self._print_tree(root.left, depth + 1)
def identical(root1, root2):
    
    # Write your code here
    return None
if __name__ == "__main__":
    # Example 1
    root1 = TreeNode(1)
    root1.left = TreeNode(2)
    root1.right = TreeNode(3)
    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.right = TreeNode(3)
    print("Tree 1:")
    root1.print_tree()
    print("Tree 2:")
    root2.print_tree()
    print("Are trees identical?", identical(root1, root2))  # Output: True
    # Example 2
    root1 = TreeNode(1)
    root1.left = TreeNode(2)
    root1.right = TreeNode(1)
    root2 = TreeNode(1)
    root2.left = TreeNode(1)
    root2.right = TreeNode(2)
    print("\nTree 1:")
    root1.print_tree()
    print("Tree 2:")
    root2.print_tree()
    print("Are trees identical?", identical(root1, root2))  # Output: False

If both roots contain identical values and their left and right subtrees are also identical, return True. Otherwise return False.

Time complexity: $O(n)$

Space complexity: $O(n)$

Solution summary#

The identical function checks if two binary trees are identical. It follows these steps:

Base case: If both roots are None, they are identical, so return True.
Recursive case:
- If one of the roots is None while the other is not, they are not identical, so return False.
- If both roots contain identical values and their left and right subtrees are also identical, return True. Otherwise return False.

Time complexity: $O(n^{2}m)$ (where $m$ is the size of the dictionary)

Space complexity: $O(n)$

Solution summary#

The can_segment_string function efficiently checks if a string can be segmented into words from a given list using dynamic programming. Here’s how it works:

Initialization: Determine the length of the input string s (n = len(s)). Initialize a boolean array dp (dp = [False] * (n + 1)) where dp[i] indicates if the substring s[0:i] can be segmented into words from word_dict. Set dp[0] = True to indicate that an empty string can always be segmented.
Dynamic programming approach: Iterate over each value of i from $0$ to n representing the length of the string being considered for segmentation. Iterate over j from $0$ to i-1, representing potential end points of the first segment. Check if dp[j] is True (indicating s[0:j] can be segmented) and s[j:i] exists in word_dict. If true, set dp[i] = True. Break out of the inner loop once a segmentation is found to avoid unnecessary checks.
Result: Return dp[n], where dp[n] is True if the entire string s can be segmented into words from word_dict, otherwise False.

Time complexity: $O(n^3)$

Space complexity: $O(n^3)$

Solution summary#

Let’s break down the solution step by step:

Iterating through substrings: The code starts by iterating through all possible substrings of the input string s. It does this with two nested loops:
- The outer loop iterates over each character of the string s, denoted by the variable i.
- The inner loop iterates over each character starting from i+2 to the end of the string s, denoted by the variable j. This ensures that the length of the substring being considered is greater than $1$ , indicating a non-trivial palindrome.
Extracting substrings: For each combination of i and j, the code extracts the substring using slicing: substring = s[i:j].
Checking for palindromes: For each extracted substring, the code checks if it’s a palindrome:
- It does this by comparing the substring with its reverse using substring == substring[::-1].
Storing palindromes: If the substring is a palindrome, it’s appended to the list palindromes.
Returning palindromes: Finally, the list of palindromes is returned.

Time complexity: $O(n)$

Space complexity: $O(1)$

Solution summary#

To determine the largest sum subarray in an array, the algorithm follows these steps:

Initialize max_sum and current_sum variables to the first element of the array.
Iterate through each element in the input array. At each iteration, update current_sum by taking the maximum between the current element and the sum of the current element and the previous current_sum.
Update max_sum by taking the maximum between the current max_sum and the updated current_sum.
Finally, return max_sum as the result.

Time complexity: $O(n)$

Space complexity: $O(1)$

Solution summary#

To determine if a given string represents a valid number, the algorithm follows these steps:

If the input string is empty, return False.
Initialize an index variable i to track the position in the string.
If the first character is a positive or negative sign (’+’ or ‘-’), increment i to skip it.
Define a state variable current_state to track the state of parsing the string.
Iterate through the characters of the string using index i.
Update current_state based on the current character using the get_next_state function.
If current_state becomes UNKNOWN at any point, return False, indicating an invalid number.
If the final state is DECIMAL, return False, as the number cannot end with a decimal point.
If all characters are successfully parsed and no invalid states are encountered, return True, indicating a valid number.

Time complexity: $O(2^{2n})$

Space complexity: $O(n)$

Solution summary#

To generate all balanced brace combinations for a given value in variable n, the algorithm follows these steps:

Start with an empty result list.
Initialize a stack with a tuple containing a string '{', and counters left and right, both initially set to 1 and 0 respectively.
While the stack is not empty:
- Pop the top tuple from the stack, and store its three elements in the variables s, left, and right.
- If the length of s reaches 2*n and left equals right, append s to the result list.
- Otherwise, if left is less than n, push a tuple onto the stack with s appended with a left brace, and the left variable incremented by $1$ .
- Also, if right is less than left, push a tuple onto the stack with s appended with a right brace, and right incremented by $1$ .
Return the result list containing all balanced brace combinations.

# Initialize the cache with capacity 2
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))  # returns 1
cache.put(3, 3)      # evicts key 2
print(cache.get(2))  # returns -1 (not found)
cache.put(4, 4)      # evicts key 1
print(cache.get(1))  # returns -1 (not found)
print(cache.get(3))  # returns 3
print(cache.get(4))  # returns 4
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       # returns 1
cache.put(3, 3);    # evicts key 2
cache.get(2);       # returns -1 (not found)
cache.put(4, 4);    # evicts key 1
cache.get(1);       # returns -1 (not found)
cache.get(3);       # returns 3
cache.get(4);       # returns 4

class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    def _add_node(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    def _remove_node(self, node):
        prev = node.prev
        next_node = node.next
        prev.next = next_node
        next_node.prev = prev
    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_node(node)
    def get(self, key):
        
        # Write your code here
        return -1
    def set(self, key, value):
        
        # Write your code here
        pass

Time complexity: $O(1)$

Space complexity: $O(1)$

Solution summary#

To implement the LRU cache, we utilize a combination of a doubly linked list and a dictionary:

We define a ListNode class to represent individual nodes in a doubly linked list. Each node contains key-value pairs and pointers to the previous and next nodes.
We implement the LRUCache class, which is initialized with a given capacity. It also maintains a dictionary (cache) to store key-node mappings and doubly linked list nodes to maintain the order of recently used items.
The _add_node method adds a node to the head of the linked list.
The _remove_node method removes a given node from the linked list.
The _move_to_head method moves a given node to the head of the linked list, indicating it as the most recently used.
The get method retrieves the value associated with a given key. If the key exists in the cache, it moves the corresponding node to the head of the linked list and returns the value stored in it; otherwise, it returns -1.
The set method sets the value associated with a given key. If the key exists in the cache, it updates the value and moves the corresponding node to the head of the linked list. If the key does not exist in the cache and the cache is at full capacity, it removes the least recently used node from the tail of the linked list and the cache dictionary. Then, it adds a new node with the given key and value to the head of the linked list and the cache dictionary.

Time complexity: $O(\log n)$

Space complexity: $O(1)$

Solution summary#

The solution consists of two primary functions: find_low_index and find_high_index. These functions utilize a binary search algorithm to determine the starting and ending positions of a given target value in a sorted array.

find_low_index(arr, key): This function identifies the lowest index of the target value key in the sorted array arr. It employs binary search to locate the leftmost occurrence of the target value.
find_high_index(arr, key): Similar to find_low_index, this function determines the highest index of the target value key in the sorted array arr. It utilizes binary search to find the rightmost occurrence of the target value.
find_low_high_index(arr, key): This function integrates the results from find_low_index and find_high_index to return a list containing the low and high indices of the target value key in the sorted array arr.

Time complexity: $O(n \log n)$

Space complexity: $O(n)$

Solution summary#

To merge overlapping intervals, the algorithm follows these steps:

Sort the intervals based on their start time.
Initialize an empty list to store merged intervals and add the first interval from the sorted list.
Iterate through the sorted intervals starting from the second interval.
If the current interval overlaps with the previous one, merge them by updating the end time of the previous interval to the maximum of both end times.
If there’s no overlap, add the current interval to the merged list.
Return the merged list of intervals as the result.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    
    def print_tree(self, level=0):
        if self.right:
            self.right.print_tree(level + 1)
        print("    " * level + str(self.val))
        if self.left:
            self.left.print_tree(level + 1)
def has_path_sum(root, target):
    
    # Write your code here
    return None
if __name__ == "__main__":
    # Create the binary tree
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(1)
    target = 22
    # Check if there exists a root-to-leaf path with the given sum
    result = has_path_sum(root, target)
    
    # Output the result
    print("Does there exist a root-to-leaf path with sum {}?".format(target))
    print("Result:", result)
    root.print_tree()

Time complexity: $O(n)$

Space complexity: $O(n)$

Solution summary#

To determine if there exists a path from the root to a leaf node in a binary tree such that the sum of values along the path equals a given target, the algorithm follows these steps:

Define a recursive function has_path_sum(root, target_sum) to traverse the binary tree.
If the root is None there is no path that sums to the given target. So, return False.
If the root is a leaf node (i.e., it has no left or right child) and if its value equals the target sum, return True.
Recursively call the function on the left and right subtrees, subtracting the value of the current node from the target.
If either recursive call returns True, indicating a path with the target exists in either subtree, return True.
If neither subtree contains a path with the target, return False.

Time complexity: $O(n)$

Space complexity: $O(1)$

Solution summary#

To find the missing number in an array, the algorithm follows these steps:

Calculate the expected sum of the numbers from $0$ to $n$ using the formula $\frac{n \times (n + 1)}{2}$ , where $n$ is the length of the input array.
Calculate the actual sum of the numbers in the input array using the sum function.
The missing number is the difference between the expected sum and the actual sum.
Return the missing number as the result.

main.py

linked_list.py

from linked_list import ListNode, create_linked_list, print_linked_list
def reverse_linked_list(head):
    
    # Write your code here
    return head
if __name__ == "__main__":
    # Create a linked list
    values = [1, 2, 3, 4, 5]
    head = create_linked_list(values)
    # Print the original linked list
    print("Original linked list:")
    print_linked_list(head)
    # Reverse the linked list
    reversed_head = reverse_linked_list(head)
    # Print the reversed linked list
    print("\nReversed linked list:")
    print_linked_list(reversed_head)

Time complexity: $O(n)$

Space complexity: $O(1)$

Solution summary#

To reverse a linked list, the algorithm follows these steps:

Initialize two pointers, prev and current, to None and the head of the linked list, respectively.
Iterate through the linked list, and at each step, store the next node of the current node in a temporary variable next_node.
Update the next pointer of the current node to point to the previous node (prev).
To prepare for the next round, update prev to be the current node and current to be the node stored in the temporary variable next_node.
After the last iteration, the prev pointer points to the new head of the reversed linked list.
Return the head of the reversed linked list (prev).

Determine if the sum of three integers is equal to the given value
Intersection point of two linked lists
Move zeros to the left
Add two integers
Merge two sorted linked lists
Convert binary tree to doubly linked list
Level order traversal of binary tree
Reverse words in a sentence
Find maximum single sell profit
Calculate the power of a number

Find all possible subsets
Clone a directed graph
Serialize / deserialize binary tree
Search rotated array
Set columns and rows as zeros
Connect all siblings
Find all sum combinations
Clone a directed graph
Closest meeting point
Search for the given key in a 2D matrix

Wrapping up and resources#

Cracking the Google coding interview simply comes down to repetition and practice. It’s important that you continue practice more interview questions after reading this article.

To help you prepare for Google interviews, Educative has created these unique language-specific courses:

Grokking Coding Interview Patterns in Python

Grokking Coding Interview Patterns in JavaScript

Grokking Coding Interview Patterns in Java

Grokking Coding Interview Patterns in Go

Grokking Coding Interview Patterns in C++

Available in multiple languages, these courses will give you a hands-on mastery of the underlying patterns to help you solve any coding interview problem.

This is coding interview prep reimagined, with your needs in mind.

Happy learning!

Continue reading about coding interview prep#

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Google coding interview questions: Top 18 questions explained

Google Coding Interview Series#

The definitive prep guide to the interview process#

Top Google coding questions explained#

Crack coding interviews by building these 5 real-world features#

Answer any interview problem by learning the patterns behind common questions.#

Google coding interview recap#

18 common Google coding interview questions#

1. Find the kth largest element in a number stream#

Examples#

Try it yourself#

Solution summary#

2. Find k closest numbers#

Examples#

Try it yourself#

Solution summary#

3. Sum of two values#

Examples#

Try it yourself#

Solution summary#

4. Delete node with a given key#

Examples#

Try it yourself#

Solution summary#

5. Copy linked list with arbitrary pointer#

Example#

Try it yourself#

Solution summary#

6. Mirror binary tree nodes#

Example#

Try it yourself#

Solution summary#

7. Check if two binary trees are identical#

Examples#

Try it yourself#

Solution summary#

8. String segmentation#

Example#

Try it yourself#

Solution summary#

9. Find all palindrome substrings#

Example#

Try it yourself#

Solution summary#

Answer any interview problem by learning the patterns behind common questions.#

10. Largest sum subarray#

Example#

Try it yourself#

Solution summary#

11. Determine if the number is valid#

Examples#

Try it yourself#

Solution summary#

12. Print balanced brace combinations#

Example#

Try it yourself#

Solution summary#

13. LRU#

Example#

Try it yourself#

Solution summary#

14. Find Low/High Index#

Example#

Try it yourself#

Solution summary#

15. Merge overlapping intervals#

Examples#

Try it yourself#

Solution summary#

16. Path sum#

Example#

Try it yourself#

Solution summary#

17. Find the missing number#

Examples#

Try it yourself#

Solution summary#

18. Reverse a linked list#

Example#

Try it yourself#