## Google Interview Questions

- 1of 1 vote
Given an integer array. Find out the equal sum partition with the smallest sum.

For example: a = [1, 3, 2, 2, 1, 3]. There are three equal sum partitions: [(1, 3), (2, 2), (1, 3)], [(1, 3, 2), (2, 1, 3)] and [(1, 3, 2, 2, 1, 3)]. First one has the smallest equal sum, so return 4

Notice you cannot reorder the input array.

- 0of 2 votes
Given a room with thief on left side of the room with finite number of sensors. He has to reach on right side missing the sensors. Each sensor is placed at any random point in the room and has its coverage in the radius r. Find out if the thief can reach to the right side without touching the range of any sensor.?

please discuss approach first & then code it..

- -1of 1 vote
1. Try to find whats wrong with this code

2. after fix it what is the out put

3 how to make this code more generic :D

Initial state of an array "a":

[[2, NULL, 2, NULL],

[2, NULL, 2, NULL],

[NULL, NULL, NULL, NULL],

[NULL, NULL, NULL, NULL]]

========

Main function:

FUNCTION foo()

FOR y := 0 to 3

FOR x := 0 to 3

IF a[x+1][y] != NULL

IF a[x+1][y] = a[x][y]

a[x][y] := a[x][y]*2

a[x+1][y] := NULL

END IF

IF a[x][y] = NULL

a[x][y] := a[x+1][y]

a[x+1][y] := NULL

END IF

END IF

END FOR

END FOR

END FUNCTION

- 0of 2 votes
Given a list L of video names and their watch rates, write a function that will return the videos with the top 10 watch rates. Video names may appear more than once.

- 0of 0 votes
You are given a campus map with the Google buildings, roads and Google

bikes. You have to help the employee find the nearest Google bike.

Campus map:`. - Free path/road # - Building B - Google bike Employee location - (x, y) - (1, 2) . . . . . # . . E . . # # # # # . # . B . . . . . . . . . B`

- -1of 1 vote
write a main program to take snapshots of VMs

Input: List of VMs(vmId: String), list of SLAs -> there is one-to-one mapping from VM to SLA

class SLA {

int freq_in_mins;

}

vm1 -> sla1{30 mins}

vm2 -> sla2{60 mins}

Constraints:

1) You can use takeSnapshot(vmId: String) -> Synchronous - I/O

2) If you start a snapshot of VM(with sla1) at time t0 and if it finishes at time t1, then the next snapshot should be scheduled at t1+sla1.freq_in_mins

vm1 at 00:00 and vm2 at 00:00

00:10 and 00:15

vm1 -> 00:10 + 30 = 00:40

- -1of 1 vote
Given two string check if they can be made equivalent by performing some operations on one or both string.

swapEven:swap a character at an even-numbered index with a character at another even-numbered index

swapOdd:swap a character at an odd-numbered index with a character at another odd-numbered index

Given : s="cdab" , x="abcd"

s -> cdab ->swap a and c ->adcb (swapEven)-> swap b and d (swapOdd) -> s="abcd" = x="abcd"

Given: s="dcba" , x="abcd"

no amount of operation will move character from an odd index to even index, so the two string will never be equals

Given: s="abcd" ,x="abcdcd"

x length to big so will never be equals

- 1of 1 vote
Find top 10 most frequent words in the past hour, day and month from twitter service. Given a streaming data such as tweets from twitter service, the objective is to find the top 10 frequent words in the past hour, day and past month at any instant of time.

- 6of 6 votes
Given two two integer arrays. Find the longest common subsequence.

eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]

- 1of 1 vote
Find all triplet that sum to a given value in an array of integers, given that the array is too big to fit into memory

- 5of 5 votes
Give an array A of n integers where 1 <= a[i] <= K.

Find out the length of the shortest sequence that can be constructed out of numbers 1, 2, .. k that is NOT a subsequence of A.

eg. A = [4, 2, 1, 2, 3, 3, 2, 4, 1], K = 4

All single digits appears. Each of the 16 double digit sequences, (1,1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2) ... appears. Because (1, 1, 2) doesn't appear, return 3.

- 1of 1 vote
Write a function that takes a magic number and a list of numbers. It returns true if it can insert add or subtract operations in the list of numbers to get the magic number. Otherwise, it returns false.

For example:

f(10, [1,2]) = false. There's no way to add or subtract 1 and 2 to get 10.

f(2, [1,2,3,4]) = true. 1 + 2 + 3 - 4 = 2.

f(0, []) = true

f(1, []) = false

f(1, [1]) = true

f(0, [1]) = false

- 0of 0 votes
Implement a rate-limiter-like iterator and how to improve the space complexity

Given a <Word, TimeStamp> pair data type iterator as input. Implement an iterator based on it which can ignore the item if the same word has occurred in the past 10 seconds.

My implementation is to use a HashMap to memorize the word and its latest timestamp + 10s. For each new item, it will be checked against the HashMap to see if it has duplicated word occurred in the past 10s.

The interviewer asked me how to improve the space complexity if the string value varieties are infinite. He mentioned some boundary stuff.

Could anyone share some thoughts?

- 0of 0 votes
Multi -level cache system design with different storage in each level.

Read Operation : – Minimum time to read a particular key from cache system. This should be followed by writing the key in all levels above it. Eg. if “key” is found at level ‘i’, add this key to cache present at 1 to i-1 level.

b. Write Operation: – Any write Operation should write in cache of all levels.

You can choose any algorithm for cache management like LRU, MRU.

- 0of 0 votes
Reverse a linked list

- 0of 0 votes
there is a 2d array and gbikes are located in that location. there is a person and he wants to know the nearest location of the bike which is available for him(there can be more than 1 nearest bike). person can only move left , right , up or down. output should be the distance in int.

- 0of 0 votes
Design a system like github.

- 0of 0 votes
A city represented by a rectangular matrix is divided into plot of lands, and the cost of each plot is known. Find the largest rectangular area of land we can buy, within a budget B.

4 6 7

3 5 2

2 4 5

B = 16

- 0of 0 votes
The wildcard regex can include the characters * and + .

‘+’ – matches any single character or empty character!

‘*’ – Matches any sequence of characters (including the empty sequence) For example,

Text = "baaabab":

regex = "ba*a++", output : true

regex = "ba*a+", output : true

regex = "a*ab", output : false

//empty string

Text=""

Regex= "+" , output : true

- 2of 2 votes
April Google Interview 1/4

A = a+b-c-a-b-c-a-b (Tree)

B = b+a+c+a+b-c+b (Tree)

is A equal to B

- 3of 3 votes
April Google Interview 4/4

Build HTML Reverser

Given

<A>(hello)(<P>ab</P>)(<S>hi</S>)</A>

Return

<A>(<S>ih</S>)(<P>ba</P>)(olleh)</A>

- 2of 2 votes
April Google Interview 3/4

Maze

N,M array

Level 1 0,0 to N-1,M-1 => Path exsits?

Level 2 if path exists then print path

Level 3 if path exists then print min cost path

Level 4 O(nm log mn) using Priority Queue.

- 2of 4 votes
April Google Interview 2/4

Count Number Given Array

Level1 Unsorted Array [1, 3, 2, 1, 2 ,3 , 4, 10]

Find occurrence of 1

Level 2 Sorted Array

Find occurrence of 1

- 0of 0 votes
Table: Customers

id | name

1|alice

2|bob

3|carol

Table: Orders

id | customer_id | content

1|1|House

2|2|car

3|2|dog

4|10|cow

please write a query which returns all of the invalid orders (where invalid means their customer_id does not have an associated customer)

4|10|cow

- 0of 0 votes
Suppose you have a list of tasks which need to be executed. Some of these tasks have dependencies which must be executed before they are. Please provide a method which, when given a list of tasks, will provide a valid ordering in return.

Example:

Input: [ A, B, C, D ]

A <- B, C

B <- C, D

D <- C

Return: [ C, D, B, A ]

- 0of 0 votes
Print (or return) the longest movie title found by successively matching the last and first words in each title, joining to form new titles, given a file containing a list of movie titles.

For example: 'OF MICE AND MEN' and 'MEN IN BLACK' join to form 'OF MICE AND MEN IN BLACK'.

You could further join 'OF MICE AND MEN IN BLACK' wth 'BLACK MASS' to form 'OF MICE AND MEN IN BLACK MASS'.

The longest title I found (at 143 characters is): WENT TO CONEY ISLAND ON A MISSION FROM GOD BE BACK BY FIVE WIVES THREE SECRETARIES AND ME WITHOUT YOU CANT TAKE IT WITH YOU WERE NEVER LOVELIER

- 0of 0 votes
You are given an array of strings. For example, ["AB", "BC", "FOO", "ZA", "BAZ"]

- Output strings where you can get from one to the other using any ROT transformation.

ROT_1(AB) = BC

ROT_1(BC) = CD

ROT_25(AB) = ZA

AB,BC you can go from one to the other using ROT_1

Input: list of strings

Output: strings where you can get from one to the other using any ROT transformation.

Example:

Input : ["AB", "BC", "FOO", "ZA", "BAZ"]

Output: [ [ab, bc] , [ab, za] ]

AB,BC because you can go from one to the other using ROT_1

AB,ZA because you can go from one to the other using ROT_25

Do not return FOO, BAZ you can’t get from one to the other.

- 0of 0 votes
How do you go about the phone interview for troubleshooting a problem, say "my computer has become slow 3 times from the last week.". Can someone please give the detailed explanation of how to go about this question. Also, "my internet is not working". How to go about these 2 troubleshooting problems in the phone interview?

- 0of 0 votes
Given list of schedules for different flights in a month, determine maximum number of flights that can be in the air anytime in that month.

Input : list of schedules for flights.- spread over a month.

output: a number - maximum flights that can be in the air

Assumptions: 1. All the given times are in a specific timezone( like GMT).

2. Given Schedules can be any time in the month

- 0of 0 votes
Given a list of N threads detect a deadlock in the system.