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?

1. Find the Kth largest element in a number stream

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:

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.

2. Find k closest numbers

Given 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:

Solution

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).

• Scan the whole array once and store visited elements in a hash set. During scan, for every element e in the array, we check if val - e is present in the hash set i.e. val - e is already visited.
• If 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.
• If we have exhausted all elements in the array and didn’t find any such pair, the function will return false.

4. Delete node with a given key

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.

Example

Solution

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.

5. Copy linked list with arbitrary pointer

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.

Example

6. Mirror binary tree nodes

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.

Example

Solution

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.

7. Check if two binary trees are identical

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.

Example

Input:                                             1                              1

Solution

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:

• data on their roots is the same
• the left sub-tree of ‘A’ is identify to the left sub-tree of ‘B’
• the right sub-tree of ‘A’ is identical to the right sub-tree of ‘B’

Using recursion, we can solve this problem through a depth-first traversal on both trees simultaneously while comparing the data at each node.

Solution

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:

Solution

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.

Solution

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:

12. Print balanced brace combinations

Print all braces combinations for a given value n so that they are balanced. See the example below.

Solution

Runtime complexity: O(2N)

Space complexity: $O(N)$

The solution algorithm works by maintaining counts of left_braces and right_braces. The algorithm can be seen below.

13. LRU

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.

Example

Solution

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.

Solution

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.

15. Merge overlapping intervals

Given a collection of intervals, merge all overlapping intervals. See the example below.

.

16. Path sum

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.

Solution

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:

• List of input intervals is given, and we’ll keep merged intervals in the output list.

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.

17. Find the missing number

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.

Solution

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:

1. Find the sum ‘sum_of_elements’ of all the numbers in the array. This would require a linear scan, O(n).
2. Then find the sum ‘expected_sum’ of first ‘n’ numbers using the arithmetic series sum formula i.e. ( n * (n + 1) ) / 2.
3. The difference between these i.e. ‘expected_sum – sum_of_elements’, is the missing number in the array.

18. Reverse a linked list

Reverse a singly linked list. See the example below.

Solution

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.

More practice and preparation

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.