20 Most Frequently Asked Google Interview Questions

Getting a job at Google is a dream of many. We all are aware of the perks that you get as a Google employee, and that excites us. But before that, there is something that we need to clear, and we are afraid of, “The Google Interviews”. Here are some most frequently asked Google interview questions that might help you get an idea of the Google interviews.

1) Tell me everything you know about hash tables.

Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects. In hashing, large keys are converted into small keys by using hash functions. The values are then stored in a data structure called the hash table. The idea of hashing is to distribute entries (key/value pairs) uniformly across an array. Each element is assigned a key (converted key). By using that key you can access the element in O(1) time. Using the key, the algorithm (hash function) computes an index that suggests where an entry can be found or inserted.

Get the full answer here: https://tinyurl.com/y88r4jgp

2) Imagine you were creating a search engine for events; how would you go about it?

The browser could select a location and then look for an event by a category (music, networking, food, art, etc.) and/or event type (conference, etc). The user can also initiate a keyword-based search. The engine should be capable of a keyword initiated search and apply any filter (category, event type, etc.) on top of that. A search should bring back a list of results, having key information about the events, name, location, ticket information, etc. The location when hovered over should show a map.

Get the full answer here: https://tinyurl.com/ybgvmsh3

3) Can you count the strings that can be formed using a, b, and c under given constraints?

Given a length n, count the number of strings of length n that can be made using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.
A simple solution is to recursively count all possible combinations of string that can be mode up to the letter ‘a’, ‘b’, and ‘c’.

Get the full answer here: https://tinyurl.com/ydxjgu4e

4) Check if a Binary Tree contains duplicate subtrees of size 2 or more.

Given a Binary Tree, check whether the Binary tree contains a duplicate sub-tree of size 2 or more.
An Efficient solution based on tree serialization and hashing. The idea is to serialize subtrees as strings and store the strings in the hash table. Once we find a serialized tree (which is not a leaf) already existing in a hash-table, we return true.

Get the full answer here: https://tinyurl.com/yausbjvv

5) Length of the longest valid substring.

A Simple Approach is to find all the substrings of a given string. For every string, check if it is a valid string or not. If valid and length is more than maximum length so far, then update maximum length. We can check whether a substring is valid or not in linear time using a stack. The time complexity of this solution is O(n2)

Get the full answer here: https://tinyurl.com/y7v44y89

6) Write a function to find the 2nd largest element in a binary search tree

We start with a function for getting the largest value. The largest value is simply the "rightmost" one, so we can get it in one walk down the tree by traversing rightward until we don't have the right child anymore.
With this in mind, we can also find the second largest in one walk down the tree.

Get the full answer here: https://tinyurl.com/y8c5swlm

7) Write a function to reverse a linked list

Our first thought might be to build our reversed list "from the beginning," starting with the head of the final reversed linked list. The head of the reversed list will be the tail of the input list. To get to that node we'll have to walk through the whole list once( O(n) time). And that's just to get started. That seems inefficient.

Get the full answer here: https://tinyurl.com/y8of5hl6

8) The Gas station problem

There are N gas stations along a circular route, where the amount of gas at station i is A[i].You have a car with an unlimited gas tank and it costs B[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the minimum starting gas station’s index if you can travel around the circuit once, otherwise return -1. You can only travel in one direction. i to i+1, i+2, … n-1, 0, 1, 2.. Completing the circuit means starting at i and ending up at i again.

Get the full answer here: https://tinyurl.com/yb7uq43f

9) Given a non-negative number represented as an array of digits, add 1 to the number

Certain things are intentionally left unclear in this question which you should practice asking the interviewer.
For example, for this problem, the following are some good questions to ask :

• Q: Can the input have 0’s before the most significant digit. Or in other words, is 0 1 2 3 a valid input?
• A: For the purpose of this question, YES
• Q: Can the output have 0’s before the most significant digit? Or in other words, is 0 1 2 4 a valid output?
• A: For the purpose of this question, NO. Even if the input has zeroes before the most significant digit.

Get the full answer here: https://tinyurl.com/ybxs3pk4

10) The Travelling Salesman Problem

1. Consider city 1 as the starting and ending point.
2. Generate all (n-1)! Permutations of cities.
3. Calculate the cost of every permutation and keep track of the minimum cost permutation.
4. Return the permutation with minimum cost.

Get the full answer here: https://tinyurl.com/y6nqmzc6

11) Can you find the median of two sorted arrays?

IF the number of elements in the merged array is even, then the median is the average of n / 2 th and n/2 + 1th elements. For example, if the array is [1 2 3 4], the median is (2 + 3) / 2.0 = 2.5

Get the full answer here: https://tinyurl.com/y9odyqh6

12) Find the two non-repeating elements in an array of repeating elements

First, sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements. The time complexity of this method is O(nLogn)

Get the full answer here: https://tinyurl.com/y8hzeauv

13) Find the largest word in the dictionary by deleting some characters of a given string.

This problem reduces to finding if a string is a subsequence of another string or not. We traverse all dictionary words and for every word, we check if it is a subsequence of the given string and is the largest of all such words. We finally return the longest word with the given string as a subsequence.

Get the full answer here: https://tinyurl.com/y2jy94mo

14) Can you find the longest substring with k unique characters in a given string?

The problem can be solved in O(n). Idea is to maintain a window and add elements to the window till it contains less or equal k, update our result if required while doing so. If unique elements exceed than required in the window, start removing the elements from the left side.

Get the full answer here: https://tinyurl.com/yckam84k

15) Find the lowest common ancestor in an unordered binary tree

Following is a simple O(n) algorithm to find LCA of n1 and n2.

• Find a path from the root to n1 and store it in a vector or array.
• Find a path from the root to n2 and store it in another vector or array.
• Traverse both paths until the values in arrays are the same. Return the common element just before the mismatch.

Get the full answer here: https://tinyurl.com/yc334bhh

16) Describe how Dijkstra’s algorithm works.

Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate an SPT (shortest path tree) with a given source as root. We maintain two sets, one set contains vertices included in the shortest-path tree, another set includes vertices not yet included in the shortest-path tree. At every step of the algorithm, we find a vertex that is in the other set (set of not yet included) and has a minimum distance from the source.

Get the full answer here: https://tinyurl.com/y7l2e23a

17) How would you create an algorithm to verify whether a number is prime or not?

A naive solution is to iterate through all numbers from 2 to n-1 and for every number check if it divides n. If we find any number that divides, we return false.

Get the full answer here: https://tinyurl.com/yb8js7z5

18) Given a string containing ‘0’, ‘1’, and ‘?’ wildcard characters, generate all binary strings that can be formed by replacing each wildcard character by ‘0’ or ‘1’.

We pass the index of the next character to the recursive function. If the current character is a wildcard character ‘?’, we replace it by ‘0’ or ‘1’ and recurse for the remaining characters. We print the string if we reach its end.

Get the full answer here: https://tinyurl.com/y9dgfdcz

19) Given an array of integers, A of length N, find out the maximum sum sub-array of non-negative numbers from A.

Max Non-Negative SubArray. Given an array of integers, A of length N, find out the maximum sum sub-array of non-negative numbers from A. The sub-array should be contiguous i.e., a sub-array created by choosing the second and fourth element and skipping the third element is invalid.

Get the full answer here: https://tinyurl.com/ycmlumot

20) How would you implement a thread-safe LRU cache?

We use two data structures to implement an LRU Cache.

• The queue which is implemented using a doubly-linked list. The maximum size of the queue will be equal to the total number of frames available (cache size). The most recently used pages will be near the front end and the least recent pages will be near the rear end.
• A Hash with page number as key and address of the corresponding queue node as value.

Get the full answer here: https://tinyurl.com/y3fy5xdc

That’s it for this one! I hope these will take you a few steps closer to your Google Job dream! Let me know below in the comments what do you think about the Google Interviews?