#### most common Google coding interview questions

#### the 15 most asked questions in a Google interview

For detailed solutions to each question, you can visit

Grokking the Coding Interview: Patterns for Coding Questions

# Arrays

#### Find the kth largest element in a number stream

Problem Statement

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.

#### Find 'k' closest points to the origin

# Problem Statement

#

Given an array of points in a 2D plane, find ‘K’ closest points to the origin.

# linked lists

#### Delete node with given key

# Problem statement

#

You are given the head of a linked list and a key. You have to delete the node that contains this given key.

#### Copy linked list with arbitrary pointer

# Problem statement

#

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.

# trees

#### Mirror binary trees

# Problem statement

#

Given the root node of a binary tree, swap the 'left' and 'right' children for each node.

#### Find all paths for a sum

# Problem statement

#

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

# strings

#### Longest substring with no more than 'k' distinct characters

# Problem statement

#

Given a string, find the length of the longest substring in it with no more than K distinct characters.

#### Longest substring with no repeating characters

# Problem statement

#

Given a string, find if its letters can be rearranged in such a way that no two same characters come next to each other.

# dynamic programming

#### Equal subset sum partition

# Problem statement

#

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.

# Math and stats

#### Determine if the number is valid

# Problem statement

#

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.

# backtracking

#### Print balanced brace combinations

# Problem statement

#

Print all braces combinations for a given value 'N' so that they are balanced.

# Graphs

#### Given a number of tasks, determine if they can all be scheduled

# Problem statement

#

There are ‘N’ tasks, labeled 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.

# design

#### Implement a LRU cache

# Problem statement

#

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.

# sorting and searching

#### Find the high and low index

# Problem statement

#

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.

#### Merge overlapping intervals

# Problem statement

#

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

For detailed solutions to each question, you can visit

Grokking the Coding Interview: Patterns for Coding Questions

have you been asked a question that is not included here in your google interview?

please share with us:

Need help preparing for the interview?

Check out the Definitive Interview Prep Roadmap,

written and reviewed by real hiring managers.