Top Google interview questions

Trapping rain water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after rain. For example, Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Basic thought We know water stays at the highest level it is able to, and it always maintains the ...
Read More

Number of islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Input: 11110 11010 11000 ...
Read More

Critical Connections in a Network

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network. A critical connection is a connection that, if removed, ...
Read More

Super Egg drop problem

Egg dropping problem goes like given n eggs and f floors, our task is to find the minimum number of trials required to find the highest floor from which it is safe to drop eggs (i.e. the eggs don’t break) considering worst-case scenario and a few conditions: An egg can ...
Read More

Arrays With Elements In The Range 1 to N

When an array has all its elements in the range of 1 to N ( where N is the length of the array ) we can use the indices to store the ordered state of the elements in the array. This ordered-state can in-turn be used to solve a variety ...
Read More

Maximum area rectangle in a histogram

A histogram is a diagram consisting of rectangles whose area is proportional to the frequency of a variable and whose width is equal to the class interval. Below is an example of a histogram. Given a histogram, whose class interval is 1, find maximum area rectangle in it. Let me ...
Read More

Minimizing maximum lateness

Minimizing maximum lateness : Greedy algorithm Since we have chosen the greed, let continue with it for one more post at least. Today’s problem is to minimize maximum lateness of a task. Let me clarify the problem: given a processor which processes one process at a time and as always ...
Read More

Coin change problem : Greedy algorithm

Coin change problem : Greedy algorithm Today, we will learn a very common problem which can be solved using the greedy algorithm. If you are not very familiar with a greedy algorithm, here is the gist: At every step of the algorithm, you take the best available option and hope ...
Read More

Range minimum query (RMQ)

Range minimum query RMQ Given an array A[0..n], find the index of the element with the minimum value in a given range. This problem is known as Range Minimum Query or RMQ. For example, if given array below, find the index of minimum value between index 2 and 7, RMQ ...
Read More

Prune nodes not on paths with given sum

Prune nodes not on paths with given sum Prune nodes not on paths with given sum is a very commonly asked question in Amazon interviews. It involves two concepts in one problem. First, how to find a path with a given sum and then second, how to prune nodes from ...
Read More