## Google Interview Questions

- 1of 1 vote

AnswersGiven an array of "array range", return an optimized array by deleting subarrays.

- dark_knight October 19, 2015 in United States

NOTE: Array range (2,6) represents (2,3,4,5,6)

INPUT: [(2,6),(3,5),(7,21),(20,21)]

OUTPUT: [(2,6),(7,21)]

Reason: (3,5) is a subarray of (2,6) and (20,21) is a subarray of (7,21)| Report Duplicate | Flag | PURGE

Google Software Engineer Intern Algorithm - 0of 0 votes

Answers2. VeryLongInt

- siva.sai.2020 October 18, 2015 in India

Design a class which can add and subtract integers up to 1000 digits. You can make the following assumptions

No need to handle overflow or underflow (extra credit if you do)

Copy constructor is available

“+” and “-” are binary operators| Report Duplicate | Flag | PURGE

Google SDE-2 Algorithm - 2of 2 votes

Answers1. Balanced Parentheses

- siva.sai.2020 October 18, 2015 in India

Given a string s of parentheses (ex: “(()”), return the minimum number of parentheses that need to be inserted to make it into a well formed string

A well formed (balanced) string of parentheses is defined by the following rules: ● The empty string is well formed. ● If s is a well formed string, (s) is a well formed string. ● If s1 and s2 are well formed strings, their concatenation s1s2 is a well formed string.

Implement

int MinNumInsersertionsForBalancing(const string& s)| Report Duplicate | Flag | PURGE

Google SDE-2 Algorithm - 0of 0 votes

AnswersHow would you go about testing a distributed system such as Gmail, before releasing it to the public. How would you simulate realistic server load?

- Ray October 17, 2015 in United States| Report Duplicate | Flag | PURGE

Google Intern Distributed Computing - 0of 0 votes

AnswersYou have some money in your bank account, the only function to withdraw money is uint16 Withdraw(uint16 value), if the value is greater than the money you have it returns 0, otherwise it withdraws the requested amount and returns the "value"

- mike.radula October 13, 2015 in United States

Write a function that withdraws all your money.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 4of 4 votes

AnswersRearrange characters in a string so that no character repeats twice.

- pcinterview October 10, 2015 in United States

Input: aaabc

Output: abaca

Input: aa

Output: No valid output

Input: aaaabc

Output: No valid output| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 3of 5 votes

AnswersThere are several people sitting in the cinema, some of them are couples, some are not, they decide to swap their seats so that the couples can seat together, please calculate the minimal swap numbers.

- xblwyc October 07, 2015 in United States

1. the swap can happen between any two position.

2. E.g. AABCCDB -> AADCCBB, ans is 1| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven a string and array of strings, find whether the array contains a string with one character difference from the given string. Array may contain string of different lengths.

Ex: Given string`banana`

and array is

`[bana, apple, banaba, bonanza, banamf]`

and the outpost should be true as banana and banaba are one character difference.

- kpraveen420 October 03, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Arrays String Manipulation - 8of 8 votes

AnswersGiven an array int32 arr[] of size n, return the number of non-empty contigious subarrays whose sum lies in range [a, b]

That is, implement the following naive algorithm faster than O(n^2)`def naive_algorithm(lst, a, b): result = 0 for i in xrange(len(lst)): for j in xrange(i, len(lst)): if a <= sum(lst[i:j + 1]) <= b: result += 1 return result`

Examples:

`count([1,2,3], 0, 3) = 3 # [1], [2], [3], [1, 2], [3] count([-2,5,-1], -2, 2) = 3 # [-2], [-1], [-2, 5, -1]`

You may assume that there are no overflows, that is sum(|x_i|) <= MAX_INT - 1

- emb September 26, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer - 1of 5 votes

AnswersYou are given an array of n unique integer numbers 0 <= x_i < 2 * n

- emb September 23, 2015 in United States

Print all integers 0 <= x < 2 * n that are not present in this array.

Example:

find_missing([0]) = [1]

find_missing([0, 2, 4]) = [1, 3, 5] # because all numbers are [0, 1, 2, 3, 4, 5]

find_missing([]) = []

find_missing([0, 1, 4, 5]) = [2, 3, 6, 7] # because all numbers are [0, 1, 2, 3, 4, 5, 6, 7]

Quirks are about requirements:

Time complexity O(n) - BUT there should be some fixed constant C independent of size of input such that every element of array is written/read < C times, so radix sorting the array is a no go.

Space complexity O(1) - you may modify the initial array, BUT sorted(initial_array) must equal sorted(array_after_executing_program) AND you can't store integers outside range [0, 2n) in this array (imagine that it's an array of uint32_t).| Report Duplicate | Flag | PURGE

Google Software Engineer Brain Teasers - 1of 1 vote

AnswersYou are given large numbers of logs, each one of which contains a start time (long), end time (long) and memory usage (int). The time is recorded as MMDDHH (100317 means October 3rd 5PM) Write an algorithm that returns a specific time (hour) when the memory usage is the highest. If there are multiple answers, return the first hour.

- aijackmoore September 21, 2015 in United States

e.g. 100207 100208 2

100305 100307 5

100207 100209 4

111515 121212 1

Answer: 100207

(Need to consider different scenarios like the time slots could be very sparse)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersCounting the islands.

- byPaco September 15, 2015 in United States

Given a map N x N, 2-D array

0 - sea

X - land

Land is connected by 4-Neighbor connections, i.e.: above, down, left and right.

00000000000000000000000000000000000

00000000000000000000000000000000000

00000000000000000000000000000000000

0000000000000000000X000000000000000

000000000000000000XXX00000000000000

000XX000000000000000000000000000000

000XXXX0000000000000000000000000000

0000000X000000000000000000000000000

00000000000000000000000000000000000

000000000000000000000X0000000000000

00000000000000000000000000000000000

00000000000000000000000000000000000

00000000000000000000000000000000000

00000000000000000000000000000000000

00000000000000000000000000000000000

00000000000000000000000000000000000

00000000000000000000000000000000000

00000000000000000000000000000000000

Output of this map: 4 (totally 4 islands on the map)| Report Duplicate | Flag | PURGE

Google iOS Developer - 2of 2 votes

AnswersNumber list compressing.

- byPaco September 15, 2015 in United States

Given an sorted array. Input: sorted number list

1, 2, 3,10, 25, 26, 30, 31, 32, 33

Output: find consecutive segments

print: 1-3, 10, 25-26, 30-33| Report Duplicate | Flag | PURGE

Google iOS Developer - 6of 6 votes

AnswersPost order traversal for an N-ary tree iterative way.

- hm September 14, 2015 in United States

Given,

struct Node {

int val;

vector<Node*> children;

};

Without modifying original structure.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm C++ Trees and Graphs - 0of 0 votes

AnswersPost order traversal for an N-ary tree iterative way.

- hm September 14, 2015 in United States

Given,

struct Node {

int val;

vector<Node*> children;

};

To simplify you can modify the structure.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm C++ Trees and Graphs - 11of 11 votes

AnswersGiven a string which only contains lowercase. You need delete the repeated letters only leave one, and try to make the lexicographical order of new string is smallest.

- lxfuhuo September 09, 2015 in -

i.e:

bcabc

You need delete 1 'b' and 1 'c', so you delete the first 'b' and first 'c', the new string will be abc which is smallest.

ps: If you try to use greedy algorithm to solve this problem, you must sure that you could pass this case:

cbacdcbc. answer is acdb not adcb

I can't solve this problem well and the interviewer said that you can scan the string twice. First scan is do some preprocess, and the second is to get the answer, but I really can't come up this idea.| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 2of 4 votes

AnswersYou are given a matrix n rows, m columns where each row is sorted in increasing order. Find median of the overall elements. What is the time complexity?

- emb September 07, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 0 votes

Answersyou are on a biz trip and travelling from one city to another. you have a stack of unsorted flight boarding passes. only departure city and destination city are on the boarding pass. how do you find the first departure city and your final destination city, write the solution in javascript.

- codebind September 06, 2015 in United States| Report Duplicate | Flag | PURGE

Google Front-end Software Engineer JavaScript - 1of 1 vote

AnswersYou are given a flat room 1x1 metres, a position of victim in it (v_x, v_y) and a position of a killer (k_x, k_y) both inside this room (in range [0, 1]).

- emb September 06, 2015 in United States

Then the killer shoots once at some direction. The bullet reflects of the walls as if it was a light ray - if it falls under angle X degrees, it will reflect at angle X degrees, if it gets into the corner it just reflects back. If the bullet hits guardian (see below) it stops and killer fails.

Write a function that will be given coordinates of victim and a killer and will return a list of coordinates of guardians such that it's impossible for a killer to kill victim.

That is, whichever direction the killer will shoot, the bullet will never reach victim, or will be stopped by a guardian.

Here is an example for the case when we assume the walls don't reflect bullet (for simplicity):

killer: (0, 0), victim: (1, 1). The solution to this simplified problem is to place 1 guardian between killer and victim e.g. on (0.1, 0.1).

Your task is to do this with accounting bullet reflection. E.g. in the previous case the killer can shoot at (1/3, 1), the bullet will reflect to (2/3, 0) and finally get to the victim at (1, 1).| Report Duplicate | Flag | PURGE

Google Software Engineer Brain Teasers - 0of 0 votes

AnswersImplement a method for the following signature:

`void * alignedAllocate(size_t sizeInBytes, size_t alignment) { }`

The method should allocate memory for the given size and the pointer should be aligned.

For example if`p = alignedAllocate(1000,64);`

p%8 should be 0.

- thewhatwhat September 05, 2015 in United States

Implement a second method that deleted the pointer give p.

Extend the delete method to handle multiple p's.| Report Duplicate | Flag | PURGE

Google Software Engineer C C++ - 8of 8 votes

AnswersYou are given a list of n float numbers x_1, x_2, x_3, ... x_n, where x_i > 0.

- emb September 04, 2015 in United States

A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise)

Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it's self-intersecting)

e.g.

2 1 1 2 -> crosses

1 2 3 4 -> doesn't cross| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 1of 1 vote

AnswersInteger Array Ques:

- cdude September 01, 2015 in United States

Given an integer array of variable length like so [9, 8, 8, 3] where each item in array could be 0 to 9, write a function that would take would interpret the array [9, 8, 8, 3] as a number 9883 and increment it by 1. The return of the function would be an integer array containing the addition like so [9,8,8,4]. No zeros in the first position like [0,1,2,3]. I initially suggested a possible solution of process to convert the integer array to String then convert to Integer or Long and then do the addition of 1 and then convert it back to integer array. That is not allowed when the interviewer change the ques. to not allow that.| Report Duplicate | Flag | PURGE

Google Android Engineer Arrays - 0of 0 votes

AnswersGiven unsigned integer 'x', write an algorithm thet returns unsigned integer 'y' such that it has the same number of bits set as 'x' and is not equal to 'x' and the distance |x-y| is minimized.

- autoboli August 31, 2015 in United States

Example:

x: 01

y: 10

Note that one bit is set and 'x' is not equal 'y'. You may assume that x is positive integer between zero and 2^32-2;| Report Duplicate | Flag | PURGE

Google - 1of 1 vote

AnswersWrite function to determine if given unsigned 32-bit number is a power of 3

`int is_power_of_3(uint32_t n)`

return 1 if yes, 0 otherwise.

e.g.`is_power_of_3(27) = 1 is_power_of_3(9) = 1 is_power_of_3(42) = 0 is_power_of_3(0) = 0`

Expected the answer not to be straightforward loop, but something faster.

- emb August 28, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Math & Computation - 0of 0 votes

AnswersThere is a graph which has 1 source and 1 sink(destination node)

- student1234 August 28, 2015 in United States

In between those 2 nodes there are n levels of nodes. At each level there are exactly m nodes.

Every node of level i is connected to every node of level i+1 (All edges go in forward direction)

Find total no. of paths between source and sink.

This was basic question. Then he tweaked it by adding few more edges.

Now there were some additional edges. Now sdges can go from any lower level to any higher level. That is not just from i to i+1..

can be from i to i+2 or i +3 so on...

(such bouncing edges were added only in the n levels not from or to (to src or sink)

Now find number of paths?| Report Duplicate | Flag | PURGE

Google Algorithm - 3of 3 votes

AnswersSuppose you have a incoming stream of numbers and a method like T* readNextNumber() to read them, and each time there is only limited amont of them coming in and readNextNumber would return null if no more available. implement a method to calculate the median of all numbers you have read.

- lucifer1986 August 28, 2015 in United States

The key point to the question is figure out the data structure to store those numbers you have read and I stopped at a balance tree, the interviewer told me it should be 2 heaps, one ascending and one descending, plus a median value between them. The final algorithm I figure out based on it is each time compare the new number with median, if bigger than it insert to the descending heap at the right side of the median else to the left, recalculate the median by checking heap sizes, the new median would be either current median, max of the left heap or min of the right heap.| Report Duplicate | Flag | PURGE

Google Data Structures - 1of 1 vote

AnswersGiven an array consisting of N Numbers.

- smarthbehl August 25, 2015 in United States

Divide it into two Equal(it is important) partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum.

If number of elements are odd difference in partition size can be at most 1.| Report Duplicate | Flag | PURGE

Google Software Engineer - 1of 1 vote

AnswersWrite all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5] in at least O(n^2) complexity

- dev123 August 24, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersDesign a data structure which should have following operation. Insert, Delete, Random access

- hm August 21, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Data Structures - 1of 1 vote

AnswersGiven 2 large number A and B, create a new number C using the digits from A which needs to be grater than B.

- hm August 21, 2015 in United States

e.g. A = 5281, B = 7443

C = 8125.| Report Duplicate | Flag | PURGE

Google Software Engineer Math & Computation

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

Open Chat in New Window