## Google Interview Questions

- 2of 2 votes

AnswersGiven a binary tree, implement an iterator that will iterate through its elements.

- carlosgsouza July 07, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 10of 10 votes

AnswersYou are given four integers 'a', 'b', 'y' and 'x', where 'x' can only be either zero or one. Your task is as follows:

- autoboli June 30, 2015 in United States

If 'x' is zero assign value 'a' to the variable 'y', if 'x' is one assign value 'b' to the variable 'y'.

You are not allowed to use any conditional operator (including ternary operator).

Follow up: Solve the problem without utilizing arithmetic operators '+ - * /'.| Report Duplicate | Flag | PURGE

Google - 0of 2 votes

AnswersGiven a List of Strings, return the number of sets of anagrams.

- SK June 30, 2015 in United States

For instance, given:

<abc,cab,dac,beed,deb,few,acd>

return 5| Report Duplicate | Flag | PURGE

Google Algorithm - 1of 1 vote

AnswersDesign a cache module for an image server. The server accepts image requests from users and sends them back the images. The cache should always hold in-memory the 10 most recently requested images. The cache should also support multiple requests simultaneously

- assaf.keret1 June 28, 2015 in Switzerland| Report Duplicate | Flag | PURGE

Google Software Engineer in Test Coding - 2of 2 votes

AnswersDesign an application which sends the user the 10 closest hotels based on his geo location.

- assaf.keret1 June 21, 2015

When i asked roughly how many hotels in total are we talking about, i was asked to estimate how many hotels are there in the world...| Report Duplicate | Flag | PURGE

Google Software Engineer in Test - 4of 4 votes

AnswersYou are given 2 documents. We want to know how similar they are through N-Grams.

- um01 June 20, 2015 in United States

Given an input n (n = number of word in the Ngram) and two documents(strings) find the intersection of the NGrams of two document.

E.g doc1 = 'This is a dog'

doc2 = 'This is a cat'

n = 3

Ngrams for doc1 = 'This is a', 'is a dog'

Ngrams for doc2 = 'This is a', 'is a cat'

Output 'This is a'

Find a efficient way and give its complexity.| Report Duplicate | Flag | PURGE

Google Software Engineer - 2of 2 votes

Answersstd C library has pow(x, n) function - implement that function

- kumarr.arvind June 20, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersGiven a sorted array and n, find the count of sum of 2 numbers greater than or equal to n

- Killbill June 17, 2015 in United States| Report Duplicate | Flag | PURGE

Google - 10of 12 votes

AnswersGiven a max-heap represented as an array, return the kth largest element without modifying the heap. I was asked to do it in linear time, but was told it can be done in log time.

- lilzh4ng June 10, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 2 votes

AnswersGiven a sorted array, find a way to find the # of occurrence of a number

- aj June 09, 2015 in United States

for eg: [1, 1, 2, 3, 3, 3, 4, 5]

find # of occurrence of 3 in time better than O(n)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 4 votes

AnswersGiven a range of floats, find the range of size 1 with max num of elements

- aj June 09, 2015 in United States

for eg: [-13.7, -14.5, -12.3, -12.5, -12.9]

one possible answer: [-12.3, -13.3]| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 2of 4 votes

AnswersDescription

- programming.kingdom June 07, 2015 in United States

A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate.

Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall.

For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall.

In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue.

Input

There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 <= n <= 12, which is the number of courses in this data set and m, 2 <= m <= 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered ('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 <= p <= 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above.

Output

The output contains one line for each data set, formatted as shown in the sample output.

Sample Input

4 6

cs123 mt42 cs456 cs789

mt42 F 0

cs123 S 0

cs456 S 2 cs123 mt42

cs789 B 1 cs456

3 6

math1 comp2 comp3

comp3 S 1 comp2

math1 S 0

comp2 F 1 math1

4 3

m10 m20 c33 c44

m10 B 0

m20 B 0

c33 B 0

c44 B 0

-1 -1

Sample Output

The minimum number of semesters required to graduate is 5.

The minimum number of semesters required to graduate is 4.

The minimum number of semesters required to graduate is 2.| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 2of 2 votes

AnswersGiven an array and is rotated n number of times find the number where the peak happens. The array is sorted in increasing order. Follow up question: how will you rearrange them in normal sorted order.

- madhur.eng June 03, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 2 votes

AnswersYou are given two streams 's_a' and 's_b' of digits. Each stream represents an integer 'a' and 'b' from its less significant digit to the most significant digit. For example, integer 2048 is represented in the stream as 8, 4, 0, 2.

- autoboli May 30, 2015 in United States

Write a function that subtract two integers 'a - b' and returns the result as a string. You are not allowed to buffer entire 'a' or 'b' into a single string, i.e. you may access only a single digit per stream at time (imagine that 'a' and 'b' are stored in huge files). You may assume that 'a>=b'.

Example:

s_a: 8 4 0 2

s_b: 4 2 0 1

result: '1024'| Report Duplicate | Flag | PURGE

Google - 0of 4 votes

Answersi18n (where 18 stands for the number of letters between the first i and the last n in the word “internationalization,”) Wiki it.

- Gcrack May 22, 2015 in United States

Generate all such possible i18n strings for any given string. for eg. "careercup"=>"c7p","ca6p","c6up","car5p","ca5up","care4p","car4up","caree3p","care3up"..till the count is 0 which means its the complete string again.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm Arrays - 2of 2 votes

AnswersGiven an bunch of airline tickets with [from, to], for example [MUC, LHR], [CDG, MUC], [SFO, SJC], [LHR, SFO], please reconstruct the itinerary in order,

- blah_blah May 18, 2015 in United States

for example: [ CDG, MUC, LHR, SFO, SJC ].

//tickets can be represented as nodes| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 9of 9 votes

AnswersIf a canoe can hold 2 kids and a max weight of 150 lbs, write a function that returns the minimum number of canoes needed, given a list of kids and their weights.

- Rando May 17, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer - 3of 3 votes

AnswersGiven a list of queries and their counts, write a function that returns one of the queries at random such that over time it returns an equal distribution based on the counts provided in the input.

- Rando May 17, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 6of 6 votes

AnswersYou are given a list of word. Find if two words can be joined to-gather to form a palindrome. eg Consider a list {bat, tab, cat} Then bat and tab can be joined to gather to form a palindrome.

- um01 May 14, 2015 in United States

Expecting a O(nk) solution where n = number of works and k is length

There can be multiple pairs| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm - 1of 1 vote

AnswersWrite a function which, given two integers (a numerator and a denominator), print the first N digits of a rational number. For example, for 5 / 3 with N=5, the result should be "1.66666". N=2: 1.66

- Dan Shah May 13, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 4 votes

Answersyou have a stream of bytes (1010101101011110100010......)to send over the net. but if you compress it. you will be charged less for less data usage. please try to compress it in a way that you can decompress at other end ahd you dont loss data

- coinsofakshay May 11, 2015 in United States| Report Duplicate | Flag | PURGE

Google Developer Program Engineer Algorithm - 2of 2 votes

Answers0 1 ?

- .netDecoder May 08, 2015 in United States

? wildcard for 0 or 1

"01?"

010 011

Example:

01?0?

Will produce

01000

01100

01001

01101| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersIn a Formula-1 challenge, there are n teams numbered 1 to n. Each team has a car and a driver. Car’s specification are as follows:

- Nitin Gupta May 06, 2015 in India

– Top speed: (150 + 10 * i) km per hour

– Acceleration: (2 * i) meter per second square.

– Handling factor (hf) = 0.8

– Nitro : Increases the speed to double or top speed, whichever is less. Can be used only once.

Here i is the team number.

The cars line up for the race. The start line for (i + 1)th car is 200 * i meters behind the ith car.

All of them start at the same time and try to attain their top speed. A re-assessment of the positions is done every 2 seconds(So even if the car has crossed the finish line in between, you’ll get to know after 2 seconds). During this assessment, each driver checks if there is any car within 10 meters of his car, his speed reduces to: hf * (speed at that moment). Also, if the driver notices that he is the last one on the race, he uses ‘nitro’.

Taking the number of teams and length of track as the input, Calculate the final speeds and the corresponding completion times.| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm Arrays Data Structures Java Object Oriented Design - 3of 5 votes

AnswersLook at the sequence below:

- amirtar May 05, 2015 in United States

1, 11, 21, 1211, 111221, 312211, ...

Write a code that receives n and returns the nth element of the sequence. If it gets 4 as input of the method it should return 1211.| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 2 votes

AnswersThe text of question below is exactly given by Google interviewer. So they are owner of the text and I am just quoting them. I am not the author of the text below:

- amirtar May 05, 2015 in United States

"

Imagine a museum floor that looks like this:

.#.G.

..#..

G....

..#..

G == Museum Guard

# == obstruction/impassable obstacle

. == empty space

Write a piece of code that will find the nearest guard for each open floor space. Diagonal moves are not allowed. The output should convey this information:

2#1G1

12#12

G1223

12#34

You may choose how you want to receive the input and output. For example, you may use a 2-d array, as depicted here, or you may use a list of points with features, if you deem that easier to work with, as long as the same information is conveyed.

"| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm Ideas Math & Computation - 1of 1 vote

AnswersGiven two binary trees ( not BST) , return true if both of them have same inorder else return false.

Eg.`B / \ A C`

`A \ B \ C`

Both of the trees have same inorder ( A-B-C) hence function will return true

- Anonymous April 25, 2015 in United States

P.S.

Please note, we can write inorder method call it once for first tree and then second tree, and finally compare both inorder.

We want to parallely do inorder on both tree, if there is mismatch between inorder nodes of both trees, we can stop the traversal and return false| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Trees and Graphs - 0of 0 votes

AnswersGiven a Binary search tree of integer values. return the count of nodes where all the nodes under that sub-tree lies between a given range [x, y]. assume there are more than 100,000 nodes

- solxget April 24, 2015 in United States| Report Duplicate | Flag | PURGE

Google SDET - 0of 0 votes

AnswersBring up as many approaches: Your goal is to make faster web browser for phones. You can change the phones, the data center etc. There's a limited network bandwidth and the browsers from the companies can't be altered.

- ghirlwhocodes April 23, 2015 in Switzerland| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Brain Storming - 0of 0 votes

AnswersWe've got Quad-trees making up a screen. Every box of the Quad-tree has either color white or black. How would you design the data structure of this Quad-tree?

And how would you count the number of pixels in a screen of a given color, given a Quad-tree?`int numberOfPixelsGivenColor(QuadTree* t, bool col)`

i used bool to specify white/black.

- ghirlwhocodes April 23, 2015 in Switzerland| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 3of 3 votes

Answerswrite a function:

`int median(int a, int b, int c)`

and then write another function:

- ghirlwhocodes April 23, 2015 in Switzerland`int median(int a, int b, int c, int min, int max)`

| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window