Google Interview Questions
- 0of 0 votes
Answerstransactions = [
- Pedro September 01, 2017 in United States
{"payee": "BoA", "amount": 132, "payer": "Chase"},
{"payee": "BoA", "amount": 827, "payer": "Chase"},
{"payee": "Well Fargo", "amount": 751, "payer": "BoA"},
{"payee": "BoA", "amount": 585, "payer": "Chase"},
{"payee": "Chase", "amount": 877, "payer": "Well Fargo"},
{"payee": "Well Fargo", "amount": 157, "payer": "Chase"},
{"payee": "Well Fargo", "amount": 904, "payer": "Chase"},
{"payee": "Chase", "amount": 976, "payer": "BoA"},
{"payee": "Chase", "amount": 548, "payer": "Well Fargo"},
{"payee": "BoA", "amount": 872, "payer": "Well Fargo"},
There are multiple transactions from payee to payer. Consolidate all these transactions to minimum number of possible transactions.
HINT: Consolidate transitive transactions along with similar transactions| Report Duplicate | Flag | PURGE
Google Software Developer - 2of 2 votes
AnswersGenerate a random binary tree, with equal probability.
- pb August 30, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersYour input is a double array, and you can use *, +, -, and () parenthesis anywhere to create and output the maximum possible value.
- talal.nabulsi5 August 27, 2017 in United States
Ex:
input is {3,4,5,1} --> output: 72
input is {1,1,1,5} --> output: 15
Follow up, if there are numbers <0| Report Duplicate | Flag | PURGE
Google SDE-3 Algorithm - 0of 0 votes
AnswersToday Google phone interview I was asked to code multithreading solution to return union of two sorted arrays in java for given number of processors. Does anybody can provide a short neat code sample om that?
- marcin.jolkowsky August 26, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE-3 - 1of 1 vote
AnswersGiven an array of objects with a known set of properties , implement a function that finds all possible partial matches (one object's property value matches the same property on another object), and produce a results object that describes those matches in any format you want.
- ad09 August 23, 2017 in United States| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 1of 1 vote
AnswersImplement multithreaded rm -r <folder>, i.e recursively delete files/folder under <folder> by walking through it and assume there can be billions of files under folder and you can only delete folder if all contents in it are first deleted
- Erik August 17, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -2of 2 votes
AnswersMedian of Stream of Running Integers
- anaghakr89 August 16, 2017 in United States
Note: The integers are in particular range from 1..n
The time complexity of the code should be o(n)| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersDesign a space shooter program .
- anaghakr89 August 16, 2017 in United States for Nest Labs
Note: The game includes spaceship , bullets and asteroids. Spaceship rotates in 180 degree generating bullets. The position of the bullets gets updated after certain time period every time . No Need to write the code for collision detection
Basic code in expected . Not the entire working code.| Report Duplicate | Flag | PURGE
Google Software Developer - 0of 0 votes
AnswersYou are in charge of a classroom which has n seats in a single row, numbered 0 through n-1.
- ad09 August 12, 2017 in United States
During the day students enter and leave the classroom for the exam.
In order to minimize the cheating, your task is to efficiently seat all incoming students.
You're given 2 types of queries: add_student(student_id) -> seat index, and remove_student(student_id) -> void.
The rules for seating the student is the following:
1) The seat must be unoccupied
2) The closest student must be as far away as possible
3) Ties can be resolved by choosing the lowest-numbered seat.| Report Duplicate | Flag | PURGE
Google Intern - 3of 3 votes
AnswersRound4
- aonecoding August 09, 2017 in United States
Starting from num = 0, add 2^i (where i can be any non-negative integer) to num until num == N. Print all paths of how num turns from 0 to N.
For example if N = 4,
Paths printed are [0,1,2,3,4], [0,1,2,4], [0,1,3,4], [0,2,4], [0,2,3,4], [0,4].
[0,2,4] is made from 0 + 2^1 + 2^1. [0,1,3,4] from 0 + 2^0 + 2^1 + 2^0| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersRound3
- aonecoding August 09, 2017 in United States
For N light bulbs, implement two methods
I. isOn(int i) - find if the ith bulb is on or off.
II. toggle(int start, int end)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersRound1
- aonecoding August 09, 2017 in United States
Find if two people in a family tree are blood-related.
Round2
Given some nodes in a singly linked list, how many groups of consecutively connected nodes there is.
For linked list
0->1->2->3->4->5->6,
given nodes 1, 3, 5, 6
there are 3 groups [1], [3], and [5, 6].| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersExplain the linear piecewise function.
- anaghakr89 August 09, 2017 in United States for Nest Labs| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 3 votes
AnswersThe array of integers in given . The array indicates nothing but the heights of the cylinders. The robotic arm has two ends-> left and right.
- anaghakr89 August 07, 2017 in United States
The left end points to the left end of the cylinder array and right end searched for the cylinder with least height.
ex:
array = {4,5,6,7,1,2}
left end => index 0
right end =>index 0->n giving index 4 with min height
Now the entire block is rotated by 180 degree.
now the array = { 1, 7, 6, 5, 4, 2}
now the left end moves forward.
and right end will search from left index onwards till the end of the array
so left index = 1
right index => 1-> n giving index 5 as min. height
again do the block rotate .
Write the code for this particular algorithm.
However, there is one condition
1. If there are duplicates in the array then the final order of those duplicates should remain the same.
ex. If the cylinder with height 4 is appearing at index 3 and 5 in the initial array then the cylinder at index 3 should always appear before the one at index 5 in the final array.| Report Duplicate | Flag | PURGE
Google Software Developer - 2of 2 votes
AnswersWe have N gas stations, and we are given all the distances between each pair of station. So we have nC2 distances provided to us. For example if I have 3 stations namely A, B, C the distances provided will be AB, AC, BC. We have to find the exact position of each gas station provided with these nC2 distances.
- logan9 August 05, 2017 in United States
eg. we have 5 stations so 5C2 distances are given in random order - 10, 20, 70, 80, 30, 20, 100, 70, 50, 90
Output the exact positions of gas stations A, B, C, D, E
i.e
A - 0
B - 10
C - 30
D - 80
E - 100
refer this image for more clarity
https://drive.google.com/open?id=0BxPkptdH01OBZzEwX29iRGI4cEU| Report Duplicate | Flag | PURGE
Google Software Engineer Problem Solving - 0of 2 votes
Answerscount number of combinations which are not possible.
- bit32413 August 05, 2017 in United States
There are 'n' empty slots.
A slot can be filled with 'O', 'E', or 'X'
A combination is possible if
1. 'O' s are placed in odd slot , 'E' a are placed in even slots.
2. 'O' and 'E' alternate among them,
i.e (OXOE) not allowed because between O s there is no 'E'; but (OEXXO) is allowed.
some allowed combinations
OEXXX, XXOEO, OXXEX
For 3 slots, not allowed combinations are
OXX
XXO
XEX
XXX
OXO
Only those combinations are considered in which O s and E s are in their respective odd and even slots.
i.e EEXXX will never be considered because a 'E' is in odd slot
A combination isn't allowed if 'O' is not followed by 'E' or vice versa| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 3of 3 votes
AnswersGiven two sorted arrays A and B. Find the first K pairs (a, b) from A and B which have the smallest sum of a & b. Supposed K is small compared to |A| x |B|
- anonymous August 05, 2017 in United States
For example:
A = [1, 2, 3, 6, 10]
B = [1, 4, 5, 7]
K = 5
Result [(1,1), (1,4), (1,5), (2,1), (3,1)]| Report Duplicate | Flag | PURGE
Google Intern - 1of 1 vote
AnswersGiven a sorted distinct array of integers and a key K. C closest elements to K are in range [L,R] inclusive, L<=R. Return L as the left index of C closest elements to K.
- anonymous August 04, 2017 in United States
For example:
A = [1, 2, 5, 8, 9, 13]. K = 8 and C = 4. The result L = 3 because 4 closest elements to 8 are [5, 8, 9, 13]| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 1of 1 vote
AnswersRound 5:
- aonecoding August 03, 2017 in United States
Given a set of synonyms such as (fast, quick), (fast, speedy), (learn, study), decides if two sentences were synonymous.
(The sentences were structurally the same and has the same number of words in them.
The synonymous relation [fast ~ quick] and [fast ~ speedy] does not necessarily mean [quick ~ speedy].)
Follow-up:
If the synonymous relation passes down so that [fast ~ quick] and [fast ~ speedy] implies [quick ~ speedy], decide if two sentences were synonymous.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersRound 4:
- aonecoding August 03, 2017 in United States
Implement a class Employment with these 3 methods: assignManager(p1, p2): assign p1 as p2's manager. beColleague(p1, p2): make p1 and p2 peer colleagues. isManager((p1, p2): decide if p1 is the manager of p2.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersRound 3
- aonecoding August 03, 2017 in United States
Given a matrix of 0s and 1s where 0 is wall and 1 is pathway, print the shortest path from the first row to the last row.
Can walk to the left, top, right, bottom at any given spot.
Follow-up:
If every pathway takes a cost (positive integer) to get through, print the minimum cost path from the first row to the last row.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGoogle on-site June
- aonecoding August 03, 2017 in United States
Round 1
Leetcode 10
Round 2
Select a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid).
Follow-up: Given multiple non-overlapped rectangles on the 2D grid, uniformly select a random point from the rectangles.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - -1of 1 vote
AnswersThe array of integers in given . The array indicates nothing but the heights of the cylinders. The robotic arm has two ends-> left and right.
- anaghakr89 July 31, 2017 in United States
The left end points to the left end of the cylinder array and right end searched for the cylinder with least height.
ex:
array = {4,5,6,7,1,2}
left end => index 0
right end =>index 0->n giving index 4 with min height
Now the entire block is rotated by 180 degree.
now the array = { 1, 7, 6, 5, 4, 2}
now the left end moves forward.
and right end will search from left index onwards till the end of the array
so left index = 1
right index => 1-> n giving index 5 as min. height
again do the block rotate .
Write the code for this particular algorithm.
However, there is one condition
1. If there are duplicates in the array then the final order of those duplicates should remain the same.
ex. If the cylinder with height 4 is appearing at index 3 and 5 in the initial array then the cylinder at index 3 should always appear before the one at index 5 in the final array.| Report Duplicate | Flag | PURGE
Google Software Developer - 1of 1 vote
AnswersGenerate a random number with UNIFORM DISTRIBUTION between [0,n) where n is given and excluded list is given. The randomly generated number should belong to the range [0, n) but should be excluded from the given excluded list. For example, n = 10 and excluded list ={2,3,0} then the random number should be from {1,4,5,6,7,8,9} such that any number from the list {1,4,5,6,7,8,9} has UNIFORM probablility of occuring
- xyz July 31, 2017 in United States for NEST| Report Duplicate | Flag | PURGE
Google Software Developer - 0of 0 votes
AnswersImplement Ring Buffer with read and write pointers.
- anaghakr89 July 26, 2017 in United States
For example if the Ring buffer is implemented in the form of array of integers , one should be able to read / write more than one integer at a time. In short the data read / written should be in a chunk .| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersPhone interview question from January.
We have a maze with three types of spaces:
1. Walls
2. Offices
3. Hallway space
Given a maze, determine which non-wall space would minimize the sum of all distances between that space and every office. You can only move up, down, left, and right.
(Edit: ChrisK described the problem more clearly than I did: "find the field that minimizes the sum of the shortest path[s] from this field to each office space.")
Example:WWWWWWWW WWW O WW WWW OW WWW WWWW WO WWWW WWW WWWW WO W WWWWWWWW
O = office, W = wall, spaces are hallway spaces
- mbs729 July 13, 2017 in United States
You can represent the maze however you want. That is, you can use any data structures you want, and you don't necessarily have to use O for office, W for Wall, and spaces for hallways.
(I'm not sure if you can actually start from an office space, but that should be a trivial issue because you can always just start a position adjacent to an office.)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
Answers1 year exp. Interviewed at Cambridge, MA
- aonecoding July 11, 2017 in United States
Round1
LC304. Follow-up: given a char stream instead a string as the input, get the longest substring with at most K distinct characters.
Round2
Find out the area of a number of squares on a plane, an advanced version of LC223.
Had no clue on that problem at all so the interviewer kindly gave another one LC305.
Round3
Similar to LC393 but the interviewer made a slightly different rule for encoding.
Follow-up: decode with utf-16. It took quite a while for me to understand the rules.
Round4
Card game rule: the hand is drawn from a pack of cards (no jokers).
Play cards ONLY when they are
1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).
2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).
Find out whether the player is able to play the whole hand given.
e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.
[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 3 votes
Answers - missing July 07, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Arrays - 0of 0 votes
AnswersAutomation Testing Question:
- sambenison66 July 04, 2017 in United States
How do you verify a search result list which changes consistently based on each search word and filters?
For example, how do you make sure that the list is sorted based on price or rating or etc without any identical list to compare with? Since providing an identical list as Test Input for each word is not the best approach.| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Testing - 0of 0 votes
AnswersHow do you reverse the words in a linked list?
For ex, Convert " H-e-l-l-o- -W-o-r-l-d " (There is a space between the word), into " o-l-l-e-H- -d-l-r-o-W "
Write a Java code to use as less Space Complexity as possible. (So not too many spaces should be used)
Linked List Structure:
- sambenison66 July 04, 2017 in United Statesclass Node { char val; Node next; }
| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Java