# 20 of Google's hardest interview questions for software engineers

ADVERTISEMENT

## Introduction

Google is notorious for asking hard interview questions. Many Software Engineers find their coding challenges extremely difficult, taking many months to prepare their skills. Programmers stay up all night solving problems on whiteboards, training to get the chance to work at Google. Writing production code that scales to billions of users can be difficult, so they look for the brightest of minds. Here are the hardest interview questions reported by Software Engineers inside their Google Interview.

## 20 of Google's hardest interview questions

### 1. Prove P=NP

### 2. Find the deepest node of a binary tree. If multiple nodes are at the deepest level, then return the rightmost node

### 3. In Python, what is a generator?

### 4. Implement an LRU Cache

### 5. Given a graph as input, write a java method returning boolean true if the graph is bipartite, else false

### 6. Given an 8x8 chessboard, write a function to determine how many moves it would take for a bishop to go from a start location to an end location. Then write a function to determine how spaces it would move

### 7. Find the minimum number required to insert into a word to make it a palindrome

### 8. Find the n-th digit of a number which is constructed by concatenation of all natural numbers

### 9. A square matrix of size n^2 and random entries from 0 ... n^2, find the longest sequence of consecutive neighbors (i.e. top, left, bottom, right entries)

### 10. Write an API to start Google Now, when saying "Ok Google"

### 11. Explain the details of MapReduce

### 12. Given a binary tree and inorder traversal, construct a new binary tree with additional pointers such that the inorder traversal is reflected in the new tree

### 13. Given a collection of intervals, merge all overlapping intervals

### 14. Reverse a linked list without using temporary variables

### 15. Randomize an array, ensuring no items are in the same position they were in originally

### 16. Implement a circular buffer and make it thread-safe

### 17. Rotate an m*n image that is stored in an array

### 18. Describe memory fragmentation and how it relates to the garbage collector

### 19. How would I implement the autocomplete function on an iPhone or Google search?

### 20. Design a cache with O(1) search time and delete time.

## Conclusion

Preparing for a Coding Interview? We suggest Cracking the Coding Interview, written by an ex-Googler, giving you the best chance at passing your interview.