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:
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, 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:
Design a class to efficiently find the Kth
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 containing initial numbers from the stream and an integer K
.
The class should expose a function add(int num) which will store the given number and return the Kth
largest number.
Example:
Input: [4, 1, 3, 12, 7, 14], K = 31. Calling add(6) should return '7'.2. Calling add(13) should return '12'.2. Calling add(4) should still return '12'.
Try solving this problem yourself:
class KthLargestNumberInStream:def __init__(self, nums, k):# TODO: Write your code hereself.k = kdef add(self, num):# TODO: Write your code herereturn -1def main():kthLargestNumber = KthLargestNumberInStream([3, 1, 5, 12, 2, 11], 4)print("4th largest number is: " + str(kthLargestNumber.add(6)))print("4th largest number is: " + str(kthLargestNumber.add(13)))print("4th largest number is: " + str(kthLargestNumber.add(4)))main()
from heapq import *class KthLargestNumberInStream:minHeap = []def __init__(self, nums, k):self.k = k# add the numbers in the min heapfor num in nums:self.add(num)def add(self, num):# add the new number in the min heapheappush(self.minHeap, num)# if heap has more than 'k' numbers, remove one numberif len(self.minHeap) > self.k:heappop(self.minHeap)# return the 'Kth largest numberreturn self.minHeap[0]def main():kthLargestNumber = KthLargestNumberInStream([3, 1, 5, 12, 2, 11], 4)print("4th largest number is: " + str(kthLargestNumber.add(6)))print("4th largest number is: " + str(kthLargestNumber.add(13)))print("4th largest number is: " + str(kthLargestNumber.add(4)))main()
Runtime complexity: $O(log(K))$
Space complexity: $O(K)$
To solve this problem, we will follow the common Top ‘K’ Elements pattern. So, we want to use a min-heap instead of a max-heap, which would be used for Kth smallest number. As we know, the root is the smallest element in the min heap. So, we can compare every number with root as we iterate through each number. If the number is bigger than root, we will swap the two. We will repeat this process until we have iterated through ever number.
k
closest numbersGiven a sorted number array and two integers ‘K’ and ‘X’, find ‘K’ closest numbers to ‘X’ in the array. Return the numbers in the sorted order. ‘X’ is not necessarily present in the array.
Example:
Input: arr = [1,2,3,4,5], k = 4, x = 3Output: [1,2,3,4]Input: [2, 4, 5, 6, 9], k = 3, x = 6Output: [4, 5, 6]
Try solving this problem yourself:
def find_closest_element(arr, K, X):result = []# TODO: Write your code herereturn result
Use the code widget above to see the solution to the coding question.
Runtime complexity: $O(K)$
Space complexity: $O(log(n-k))$
Once again this problem follows the Top ‘K’ Numbers pattern. Here is our approach to the problem:
X
through binary search. Let’s say that number is Y
.K
closest numbers to K
adjacent to Y
in the array. We can search both sides of Y
to find the closest numbers.K
numbers in both directions of Y
and push them in a min-heap sorted by their difference from X.K
numbers from the min-heap to find the required numbers.Given an array of integers and a value, determine if there are any two integers in the array whose sum is equal to the given value. Return true if the sum exists and return false if it does not.
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].
def find_sum_of_two(A, val):#TODO: Write - Your - Codereturn
Runtime complexity: $O(N)$
Space complexity: $O(N)$
In this solution, you can use the following algorithm to find a pair that add up to the target (say val
).
e
in the array, we check if val - e
is present in the hash set i.e. val - e
is already visited.val - e
is found in the hash set, it means there is a pair (e
, val
- e
) in array whose sum is equal to the given val
.false
.We are given the head of a linked list and a key. We have to delete the node that contains this given key. The following two examples elaborate on this problem further.
Input: head = [4,5,1,9], key = 5Output: [4,1,9]Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
def delete_node(head, key):#TODO: Write - Your - Codereturn
Runtime complexity: $O(n)$
Space complexity: $O(1)$
First, we have to find the key in the linked list. We’ll keep two pointers, current and previous, as we iterate the linked list.
If the key is found in the linked list, then the current pointer would be pointing to the node containing the key to be deleted. The previous should be pointing to the node before the key node.
This can be done in a linear scan and we can simply update current and previous pointers as we iterate through the linked list.
You are given a linked list where the node has two pointers. The first is the regular next
pointer. The second pointer is called arbitrary_pointer
and it can point to any node in the linked list. Your job is to write code to make a deep copy of the given linked list. Here, deep copy means that any operations on the original list (inserting, modifying and removing) should not affect the copied list.
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
def deep_copy_arbitrary_pointer(head):#TODO: Write - Your - Codereturn None
Runtime complexity: $O(N)$
Space complexity: $O(N)$
Here is how the solution algorithm works to find a paid that adds up to the target.
For this problem, we will use a map to track the arbitrary nodes pointed by the original list. Then, we create a deep copy of the original linked list in two passes.
For the first pass, we create a copy of the original linked list. When create the new copy, use the same values for data and arbitrary_pointer in the copied list. Furthermore, it’s important to keep updating the map with entries where the key is the address to the old node and the value is the address of the new node.
Once we’ve created the copy, again we’ll pass the copied linked list and update the arbitrary pointers to the new address created in the first pass.
Given the root node of a binary tree, swap the ‘left’ and ‘right’ children for each node. The below example shows how the mirrored binary tree should look like.
def mirror_tree(root):#TODO: Write - Your - Codereturn root
Runtime complexity: $O(N)$
Space complexity: $O(N)$
This problem is quite straightforward. For this algorithm, we will utilize a post order traversal of the binary tree. For each node, we will swap its left and right child.
Given the roots of two binary trees, determine if these trees are identical or not. Identical trees have the same layout and data at each node.
Input: 1 1/ \ / \2 3 2 3[1,2,3], [1,2,3]Output: trueInput: 1 1/ \ / \2 1 1 2[1,2,1], [1,1,2]Output: false
def are_identical(root1, root2):if root1 == None and root2 == None:return Trueif root1 != None and root2 != None:return (root1.data == root2.data andare_identical(root1.left, root2.left) andare_identical(root1.right, root2.right))return Falsearr1 = [100,50,200,25,125,350]arr2 = [1,2,10,50,180,199]root1 = create_BST(arr1)display_level_order(root1)root2 = create_BST(arr2)display_level_order(root2)if(are_identical(root1, root2)):print("The trees are identical")else:print("The trees are not identical")
Runtime complexity: $O(N)$
Space complexity: $O(N)$
This problem can be tackled using recursion. The base case of the recursive solution would be when both nodes being compared are null or one of them is null.
Two trees being compared are identical if:
Using recursion, we can solve this problem through a depth-first traversal on both trees simultaneously while comparing the data at each node.
You are given a dictionary of words and a large input string. You have to find out whether the input string can be completely segmented into the words of a given dictionary. The following two examples elaborate on the problem further.
Input: s = "applepenapple", wordDict = ["apple", "pen"]Output: trueExplanation: Return true because "applepenapple" can be segmented as "apple pen apple".Note that you are allowed to reuse a dictionary word.
def can_segment_string(s, dictionary):#TODO: Write - Your - Codereturn False
Runtime complexity: $O(2^N)$ (without memoization)
Space complexity: $O(N^2)$
This problem can be tackled by segmenting the input strign at every possible index to see if the string can be completely segmented into words in the dictionary. We can use an algorithm as follows:
n = length of input stringfor i = 0 to n - 1first_word = substring (input string from index [0, i] )second_word = substring (input string from index [i + 1, n - 1] )if dictionary has first_wordif second_word is in dictionary OR second_word is of zero length, then return truerecursively call this method with second_word as input and return true if it can be segmented
Given a string find all non-single letter substrings that are palindromes. For instance:
Input: "abc"Output: 3Explanation: Three palindromic strings: "a", "b", "c".
def find_all_palindrome_substrings(input):# TODO: Write - Your - Codereturn -1
Runtime complexity: $O(N^2)$ (without memoization)
Space complexity: $O(1)$
We will iterate through each letter in the input string. For each letter, we can find palindromes by expanding to the left and right will we check for even and odd length palindromes. If there are no palindromes, move to the next letter.
We find palindromes by checking if the left and right character are equal. If they are, we print out the palindrome substring.
In the array below, the largest sum subarray starts at index 3 and ends at 6, and with the largest sum being 12.
Input: [-2,1,-3,4,-1,2,1,-5,4],Output: 6Explanation: [4,-1,2,1] has the largest sum = 6.
def max_sub_array_of_size_k(k, arr):# TODO: Write your code herereturn -1
Runtime complexity: $O(N)$
Space complexity: $O(1)$
We will solve this problem by implementing Kadane’s algorithm. The algorithm works by scanning an entire array and at each position find the maximum sum of the subarray ending there. This is achieved by keeping a current_max for the current array index and a global_max. The algorithm is as follows:
current_max = A[0]global_max = A[0]for i = 1 -> size of Aif current_max is less than 0then current_max = A[i]otherwisecurrent_max = current_max + A[i]if global_max is less than current_maxthen global_max = current_max
Given an input string, determine if it makes a valid number or not. For simplicity, assume that white spaces are not present in the input.
4.325 is a valid number.
1.1.1 is NOT a valid number.
222 is a valid number.
0.1 is a valid number.
22.22. is NOT a valid number.
def is_number_valid(s):#TODO: Write - Your - Codereturn False
Runtime complexity: $O(N)$
Space complexity: $O(1)$
To check if a number is valid, we’ll use the state machine below. The initial state is start, and we’ll process each character to identify the next state. If the state ever ends up at unknown or in a decimal, the number is not valid.
add state machine visual
Print all braces combinations for a given value n
so that they are balanced. See the example below.
For example, given n = 3, a solution set is:["((()))","(()())","(())()","()(())","()()()"]
def print_all_braces(n):#TODO: Write - Your - Codereturn
Runtime complexity: $O(2^N)$
Space complexity: $O(N)$
The solution algorithm works by maintaining counts of left_braces
and right_braces
. The algorithm can be seen below.
left_braces count: 0right_braces count: 0if left_braces count is less than n:add left_braces and recurse furtherif right_braces count is less than left_braces count:add right_braces and recurse furtherstop recursing when left_braces and right_braces counts are both equal to n
Least Recently Used (LRU) is a common caching strategy. It defines the policy to evict elements from the cache to make room for new elements when the cache is full, meaning it discards the least recently used items first.
LRUCache cache = new LRUCache( 2 /* capacity */ );cache.put(1, 1);cache.put(2, 2);cache.get(1); // returns 1cache.put(3, 3); // evicts key 2cache.get(2); // returns -1 (not found)cache.put(4, 4); // evicts key 1cache.get(1); // returns -1 (not found)cache.get(3); // returns 3cache.get(4); // returns 4
# Linked list operations# insert_at_tail(self, key, data)# remove(self, data)# remove_node(self, node)# remove_head(self)# remove_tail(self)# get_head(self)# get_tail(self)class LRUCache:def __init__(self, capacity):self.capacity = capacityself.cache = {}self.cache_vals = LinkedList()def Set(self, key, value):# TODO: Write - Your - Codereturndef get(self, key):# TODO: Write - Your - Codereturn -1def get_cache(self):res = ""node = self.cache_vals.headwhile node:res += "(" + str(node.key) + "," + str(node.data) + ")"node = node.nextreturn res
Runtime complexity:
get (hashset): $O(N)$
set (hashset): $O(1)$
deletion at head when adding a new element (linked list): $O(1)$
search for deleting and adding to tail (linked list): $O(N)$
Complexity: $O(N)$
Space complexity: $O(N)$
To implement an LRU cache we use two data structures: a hashmap and a doubly linked list. A doubly linked list helps in maintaining the eviction order and a hashmap helps with O(1) lookup of cached keys. Here goes the algorithm for LRU cache.
If the element exists in hashmapmove the accessed element to the tail of the linked listOtherwise,if eviction is needed i.e. cache is already fullRemove the head element from doubly linked list and delete its hashmap entryAdd the new element at the tail of linked list and in hashmapGet from Cache and Return
Note that the doubly linked list is used to keep track of the most recently accessed elements. The element at the tail of the doubly linked list is the most recently accessed element. All newly inserted elements (in put) go the tail of the list. Similarly, any element accessed (in get operation) goes to the tail of the list.
Given an array of integers nums
sorted in ascending order, find the starting and ending position of a given target
value.
If the target is not found in the array, return [-1, -1]
. See the example below.
Input: nums = [5,7,7,8,8,10], target = 8Output: [3,4]
def find_low_high_index(arr, key):#TODO: Write - Your - Codereturn [-1, 1]
Runtime complexity: $O(LOG(N))$
Space complexity: $O(1)$
Scanning the array in a linear fashion would be highly inefficient because the array size could be in the millions. Instead, we will use binary search twice: once to find the low index and once to find the high index.
Here’s the algorithm to find the low index:
At each step, consider the array between low and high indices and calculate the mid index.
If the element at mid is greater or equal to the key, the high becomes mid - 1
. Index at low remains the same.
If the element at mid is less than the key, low becomes mid + 1
.
When low is greater than high, low would be pointing to the first occurrence of the key. If the element at low does not match the key, return -1.
For high index, we can use a similar algorithm with slight changes.
Switch the low index to mid + 1
when element at mid
index is less than or equal to the key.
Switch the high index to mid - 1
when the element at mid is greater than the key.
Given a collection of intervals, merge all overlapping intervals. See the example below.
Example 1:Input: [[1,3],[2,6],[8,10],[15,18]]Output: [[1,6],[8,10],[15,18]]Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].Example 2:Input: [[1,4],[4,5]]Output: [[1,5]]Explanation: Intervals [1,4] and [4,5] are considered overlapping.
def merge(intervals):merged = []# TODO: Write your code herereturn merged
Runtime complexity: $O(N)$
Space complexity: $O(N)$
This problem can be solved utilizing a simple linear search algorithm, since we already know that inputs are sorted by starting timestamps. Here’s the approach we will take:
For each interval,
If the input interval is overlapping with the last interval in the output list, we’ll merge the two intervals and update the last interval of the output list with the merged interval.
Otherwise, we’ll add an input interval to the output list.
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. See below for an example.
Given the below binary tree and sum = 22,5/ \4 8/ / \11 13 4/ \ \7 2 1return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
def has_path(root, sum):# TODO: Write your code herereturn False
Runtime complexity: $O(N)$
Space complexity: $O(N)$
This problem can be solved utilizing a simple linear search algorithm, since we already know that inputs are sorted by starting timestamps. Here’s the approach we will take:
For each interval,
If the input interval is overlapping with the last interval in the output list, we’ll merge the two intervals and update the last interval of the output list with the merged interval.
Otherwise, we’ll add an input interval to the output list.
We are given an array containing ‘n’ distinct numbers taken from the range 0 to ‘n’. Since the array has only ‘n’ numbers out of the total ‘n+1’ numbers, find the missing number. See the example below.
Example 1:Input: [4, 0, 3, 1]Output: 2Example 2:Input: [8, 3, 5, 2, 4, 6, 0, 1]Output: 7
def find_missing(input):#TODO: Write - Your - Codereturn
Runtime complexity: $O(N)$
Space complexity: $O(1)$ Let’s solve this problem with a linear, $O(N)$, solution using arithmetic series sum formula.
Here is the algorithm:
Find the sum ‘sum_of_elements’ of all the numbers in the array. This would require a linear scan, O(n).
Then find the sum ‘expected_sum’ of first ‘n’ numbers using the arithmetic series sum formula i.e. ( n * (n + 1) ) / 2.
The difference between these i.e. ‘expected_sum - sum_of_elements’, is the missing number in the array.
Reverse a singly linked list. See the example below.
Input: 1->2->3->4->5->NULLOutput: 5->4->3->2->1->NULL
def reverse(head):reversed_list = head#TODO: Write - Your - Codereturn reversed_list
Runtime complexity: $O(N)$
Space complexity: $O(1)$
Let’s take a look at the iterative approach.
If the linked list has 0 or 1 nodes, then the current list can be returned as is. If there are two or more nodes, then the iterative approach starts with two pointers:
reversed_list
: A pointer to already reversed linked list.
list_to_do
: A pointer to the remaining list.
Then, we set reversed_list->next
to NULL
. This becomes the last node of the reversed linked list.
For each iteration, the list_to_do
pointer moves forward. The current node becomes the new head of the reversed linked list. The loop terminates when we hit NULL
.
Congratulations on finishing these problems! To pass the coding interview, it’s important that you continue practice. To prepare for the Google Coding Interview, you should brush up on dynamic programming, backtracking, recursion, greedy algorithms, and divide & conquer. Here are some more common coding interview questions to practice.
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
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:
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!
Join a community of more than 1.4 million readers. A free, bi-monthly email with a roundup of Educative's top articles and coding tips.