## Google Interview Questions

- 0of 0 votes

AnswersGiven a large that consists of millions of lines, retrieve only the first and last lines.

- adelabarra24 November 05, 2015 in United States| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm - 5of 5 votes

AnswersGiven a prime set, we call "prime expressible" if a number can be factorized only using given prime numbers. Find n-th big expressible number.

- pandacoder October 30, 2015 in United States

E.g., prime set = {2, 3}

expressible number = {1,2,3,4,6,8, 9, 12...}

non-expressible number = {5, 10... }

The primes in the prime set are ordered in an increasing order, and can include a prime < 10^4 (don't remember the exact range), and n can also be as large as 1-10^6.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersSuppose we have two CPUs, each has an L1 cache associated with it. An L2 cache is shared by the two CPUs, and it requests data from DRAM:

- lou October 27, 2015 in United States

|CPU0| |CPU1|

|L1Cache0| |L1Cache1|

|Shared L2C|

|DRAM|

Let's say CPU0 and CPU1 send out a write signal at the same time:

- At timestamp 0, CPU0 sends a wr request - write address A to 0;

- Also at timestamp 0, CPU1 sends a wr request - write address A to 1;

- At timestamp 0, all of the L1/L2 caches are empty, i.e. write req will result in a miss in the cache;

- At timestamp 0, data in address A in DRAM is 100;

- Cache coherency protocol is MOESI.

What will the values be after these two writes complete? In L1, L2 and DRAM? and what are the states in each cache?| Report Duplicate | Flag | PURGE

Google Systems Design Engineer Computer Architecture & Low Level - 6of 6 votes

AnswersGiven an array of elements, return an array of values pertaining to how many elements are greater than that element remaining in the array.

- PradeepN October 27, 2015 in United States

Brute force is obvious, but must be done faster than O(n^2)

Ex. [3,4,5,9,2,1, 3]

Return [3, 2, 1, 0, 1, 1, 0]

First element is 3 because 3<4,5,9. Second element is 2 because 4< 5,9 etc| Report Duplicate | Flag | PURGE

Google Algorithm - 1of 1 vote

AnswersGiven a set of values 0-9, return all permutations of that set of length n. Example: n=2, set ={2,3,4} Return: {2,2}, {3,3}, {4,4}, {2,3}, {3,2}, {3,4}, {4,3}, {2,4}, {4,2}

- PradeepN October 27, 2015 in United States| Report Duplicate | Flag | PURGE

Google Algorithm - 1of 1 vote

AnswersFind a counter example proving that the following substring algorithm is incorrect:

- awayes October 20, 2015 in United States`const char* findSubstr(const char* str, const char* substr) { int len = strlen(str); int substrlen = strlen(substr); int j = 0; const char* result = NULL; for (int i = 0; i < len; ++i) { if (str[i] != substr[j]) { j = 0; result = NULL; } else { if (j==0) result = &str[i]; ++j; if (j >= substrlen) break; } } return result; }`

| Report Duplicate | Flag | PURGE

Google Algorithm - 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 - 3of 3 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++ - 7of 7 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

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

Open Chat in New Window