0%
100%

# Top 29 Google Interview Questions to Crack the Coding Interview

Posted on
June 23, 2020
|
by
Team Interview Kickstart Google’s technical interview process is considered to be one of the most in-depth and comprehensive tests of a candidate’s technical knowledge and skills. Of the many rounds of interviews that Google conducts, the coding interviews are undoubtedly the most challenging.

Google’s coding interview questions test your conceptual knowledge and your approach to solving real-world problems. During the interview, you will be expected to write code on a whiteboard or Google docs and communicate your thought process as you develop solutions. This includes expressing your understanding of the problem given as well as asking clarifying questions to arrive at an optimal solution.

Getting through Google’s coding interviews requires immense practice on key topics such as

• Data structures – Graphs, Arrays, Linked Lists, Hash maps, Trees, Stacks, Queues etc.
• Algorithms – Searches, Sorting, A*, Dynamic programming etc.

Practice simple and complex coding problems until you develop the ability to recognize different patterns and the right approach to solving them quickly and cleanly. Interviewers are more interested in how you solve problems than if you solve them correctly.

While technical interviews are fairly similar across companies, FAANG companies like Google have a more structured and focused process, with unique questions developed over the years to filter out the best from among thousands of applicants.  Before attending a coding interview, get an insight into the type of questions asked at a company and how you will be expected to solve them.

1. Design a class to efficiently find the Kth largest element in a stream of numbers. The class should have the following two things:
a. The constructor of the class should accept an integer array containing initial numbers from the stream and an integer ‘K’.
b. The class should expose a function add(int num) which will store the given number and return the Kth largest number.
1. 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.
1. Find the Kth row of Pascal’s triangle, given an index k; Pascal’s triangle: To generate A[C] in row R, sum up A’[C] and A’[C-1] from previous row R - 1
1. Delete the node containing a given key, given the head of a linked list.
1. Crete a deep copy of a given linked list with a node that has a regular and an arbitrary pointer.
1. Mirror binary trees: Given the root node of a binary tree, swap the ‘left’ and ‘right’ children for each node.
1. Find all paths for a sum: Given a binary tree and a number ‘S’, find all paths from root-to-leaf such that the sum of all the node values of each path equals ‘S’.
1. Given a string, find the length of the longest substring in it with no more than K distinct characters.
1. Given a string, find if its letters can be rearranged in such a way that no two same characters come next to each other.
1. Given a set of positive numbers, find if we can partition it into two subsets such that the sum of elements in both subsets is equal.
1. 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.
1. Print all braces combinations for a given value ‘N’ so that they are balanced.
1. There are ‘N’ tasks, labelled from ‘0’ to ‘N-1’. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, find out if it is possible to schedule all the tasks.
1. You are given the following: A positive number N, a list of heights of N persons standing in a queue, a list of numbers corresponding to each person (P) that gives the number of persons who are taller than P and standing in front of P. Return a list of the actual order of persons’ heights.
1. Given a sorted array of integers, return the low and high index of the given key. Return -1 if not found. The array length can be in the millions with many duplicates.
1. You are given an array (list) of interval pairs as input where each interval has a start and end timestamp. The input array is sorted by starting timestamps. You are required to merge overlapping intervals and return output array (list).
1. Given two integer arrays A and B of size N. 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.
1. Given two sequences A, B, count the number of unique ways in sequence A, to form a subsequence that is identical to the sequence B. Subsequence: A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e. “ACE” is a subsequence of “ABCDE” while “AEC” is not).
1. Given an array of non-negative integers, A, of length N, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Return the minimum number of jumps required to reach the last index. If it is not possible to reach the last index, return -1.
1. Given two strings A and B, find the minimum number of steps required to convert A to B. (each operation is counted as 1 step). You have the following 3 operations permitted on a word: Insert a character, delete a character, replace a character
1. Sort a linked list in O(n log n) time using constant space complexity.
1. Evaluate the value of an arithmetic expression in reverse polish notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression.
1. Given a string S and a string T, find the minimum window in S which will contain all the characters in T in linear time complexity. Note that when the count of a character C in T is N, then the count of C in minimum window in S should be at least N.
1. Implement regular expression matching with support for '.' and '*'.
1. '.' Matches any single character.
2. '*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
1. Decompress and compressed string: Your input is a compressed string of the format number[string] and the decompressed output form should be the string written number times. For example: The input 3[abc]4[ab]c would be output as abcabcabcababababc. Other rules:
1. Number can have more than one digit. for example, 10[a] is allowed, and just means aaaaaaaaaa;
2. One repetition can occur inside another. For example, 2[3[a]b] decompresses into aaabaaab
3. Characters allowed as input include digits, small English letters and brackets [ ]
4. Digits are only to represent amount of repetitions.
5. Letters are just letters.
6. Brackets are only part of syntax of writing repeated substring.
7. Input is always valid, so no need to check its validity.
1. Implement Minesweeper: Minesweeper is a game where the objective is to correctly identify the location of all mines in a given grid. You are given a uniform grid of grey squares in the beginning of the game. Each square contains either a mine (indicated by a value of 9), or an empty square. Empty squares have a number indicating the count of mines in the adjacent squares. Empty squares can have counts from zero (no adjacent mines) up to 8 (all adjacent squares are mines). Gameplay starts with a user un-hiding a square at random. If the square contains a mine, the game ends. If it is a blank, the number of adjacent mines is revealed. Exposing a zero means that there are no adjacent mines, so exposing all adjacent squares is guaranteed safe. As a convenience to the player, the game continues to expose adjacent squares until a non-zero square is reached. Please write functions to construct the playing field given the size and number of mines. The goal is to expose safe squares correctly, not demonstrate facility with matrix classes or arrays
1. Given an iterator of iterators, implement an interleaving iterator that takes in an iterator of iterators, and emits elements from the nested iterators in interleaved order. That is, if we had the iterators i and j iterating over the elements [ia, ib, ic] and [ja, jb] respectively, the order in which your interleaving iterator should emit the elements would be [ia, ja, ib, jb, ic]. Your interleaving iterator should implement the Iterator interface, take in the iterator of iterators in its constructor, and provide the next methods. Assume that there are no additional methods offered by the iterator.
1. Given a string S and a set of words D, find the longest word in D that is a subsequence of S. Word W is a subsequence of S if some number of characters, possibly zero, can be deleted from S to form W, without reordering the remaining characters. Note: D can appear in any format (list, hash table, prefix tree, etc.)
1. Create a way to find word squares. First, design a way to return true if a given sequence of words is a word square. Second, given an arbitrary list of words, return all the possible word squares it contains. Reordering is allowed. For example, the input list [AREA, BALL, DEAR, LADY, LEAD, YARD] should output [(BALL, AREA, LEAD, LADY), (LADY, AREA, DEAR, YARD)]. Finishing the first task should help you accomplish the second task.

If you wish to begin your interview prep and bag exciting offers from top tech companies, start by signing up for our free webinar today.