Google Interview Questions

There are two sorts of interviews, phone/hangout interviews and on-site interviews, according to Google's official career page. An excerpt from their official page is provided below.

For candidates for software engineering positions, we are interested in your coding abilities, technical specialties, knowledge of tools or programming languages, and broad understanding of concepts like data structures and algorithms. We prefer to challenge one other's thinking and discover new perspectives, so there is usually some back and forth in these discussions, just like there is on the job. So be ready to thoroughly discuss your solutions. Find the greatest solution by pushing your own limits—that's probably how you think anyway.

Google Questions from Medium to Hard level are as follows:

Easy Level

1. Find all triplets with zero sum
2. Generate all binary strings from given pattern
3. Count of strings that can be formed using a, b and c under given constraints
4. Find largest word in dictionary by deleting some characters of given string
5. Find subarray with given sum | Set 1 (Nonnegative Numbers)
6. Find the longest substring with k unique characters in a given string
7. Find the two non-repeating elements in an array of repeating elements
8. Flood fill Algorithm – how to implement fill() in paint?
9. Meta Strings (Check if two strings can become same after a swap in one string)
10. Print all Jumping Numbers smaller than or equal to a given value
11. Sum of all the numbers that are formed from root to leaf paths
12. The Celebrity Problem
13. Unbounded Knapsack (Repetition of items allowed)

Medium Level

1. Backtracking | Set 7 (Sudoku)
2. Boggle | Set 2 (Using Trie)
3. Check if a Binary Tree contains duplicate subtrees of size 2 or more
4. Dynamic Programming | Set 33 (Find if a string is interleaved of two other stri
5. Connect nodes at same level
6. Count BST nodes that lie in a given range
7. Dynamic Programming | Set 11 (Egg Dropping Puzzle)
8. Dynamic Programming | Set 28 (Minimum insertions to form a palindrome)
9. Dynamic Programming | Set 31 (Optimal Strategy for a Game)
10. Dynamic Programming | Set 32 (Word Break Problem)
11. Find four elements that sum to a given value | Set 2 ( O(n^2Logn) Solution)
12. Given a matrix of ‘O’ and ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’
13. How to print maximum number of A’s using given four keys
14. Inplace rotate square matrix by 90 degrees | Set 1
15. Maximum absolute difference between sum of two contiguous sub-arrays
16. Merge two BSTs with limited extra space
17. Merge Overlapping Intervals
18. Modular Exponentiation (Power in Modular Arithmetic)
19. Paper Cut into Minimum Number of Squares | Set 2
20. Sum of bit differences among all pairs

Hard Level

1. Allocate minimum number of pages
2. Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
3. Given a sorted dictionary of an alien language, find order of characters
4. Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)
5. Implement LRU Cache
6. Length of the longest valid substring
7. Median in a stream of integers (running integers)
8. Sum of bit differences among all pairs
9. Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming)
10. Word Break Problem using Backtracking