Google Interview Questions
- 0of 0 votes
AnswersYou've escaped Commander Lambda's exploding space station along with numerous escape pods full of bunnies. But - oh no! - one of the escape pods has flown into a nearby nebula, causing you to lose track of it. You start monitoring the nebula, but unfortunately, just a moment too late to find where the pod went. However, you do find that the gas of the steadily expanding nebula follows a simple pattern, meaning that you should be able to determine the previous state of the gas and narrow down where you might find the pod.
- Anon April 11, 2017 in United States
From the scans of the nebula, you have found that it is very flat and distributed in distinct patches, so you can model it as a 2D grid. You find that the current existence of gas in a cell of the grid is determined exactly by its 4 nearby cells, specifically, (1) that cell, (2) the cell below it, (3) the cell to the right of it, and (4) the cell below and to the right of it. If, in the current state, exactly 1 of those 4 cells in the 2x2 block has gas, then it will also have gas in the next state. Otherwise, the cell will be empty in the next state.
For example, let's say the previous state of the grid (p) was:
.O..
..O.
...O
O...
To see how this grid will change to become the current grid (c) over the next time step, consider the 2x2 blocks of cells around each cell. Of the 2x2 block of [p[0][0], p[0][1], p[1][0], p[1][1]], only p[0][1] has gas in it, which means this 2x2 block would become cell c[0][0] with gas in the next time step:
.O -> O
..
Likewise, in the next 2x2 block to the right consisting of [p[0][1], p[0][2], p[1][1], p[1][2]], two of the containing cells have gas, so in the next state of the grid, c[0][1] will NOT have gas:
O. -> .
.O
Following this pattern to its conclusion, from the previous state p, the current state of the grid c will be:
O.O
.O.
O.O
Note that the resulting output will have 1 fewer row and column, since the bottom and rightmost cells do not have a cell below and to the right of them, respectively.
Write a function answer(g) where g is an array of array of bools saying whether there is gas in each cell (the current scan of the nebula), and return an int with the number of possible previous states that could have resulted in that grid after 1 time step. For instance, if the function were given the current state c above, it would deduce that the possible previous states were p (given above) as well as its horizontal and vertical reflections, and would return 4. The width of the grid will be between 3 and 50 inclusive, and the height of the grid will be between 3 and 9 inclusive. The answer will always be less than one billion (10^9).| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
Answerswrite a function that randomly return only odd number in range [min, max)
- ajay.raj April 11, 2017 in United States
public int getRandomOdd(int min, int max){}| Report Duplicate | Flag | PURGE
Google Software Developer - 0of 0 votes
AnswersFor a string chemical formula like “C6H2(NO2)3CH3”, and output a map with key as element and value as its count.
- ajay.raj April 11, 2017 in United States
element can have two chars, for example Fe2(SO4)3
public HashMap<Character, Integer> getCount(String chemicals){
}| Report Duplicate | Flag | PURGE
Google SDE1 - -4of 4 votes
AnswersFind the coordinates of the rectangle which is parallel to axis and has minimum area.
- Ray April 08, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersSuppose you have a stream of (timestamp, tag) events. You need to filter this stream (online), leaving only events with tags that haven't been already encountered in the last X seconds.
- Ray April 08, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersPeople enter and leave a room over the course of a day. Each person has a badge with a unique integer id, which is logged by the security system on enter/exit. Each log entry is an enter record (“E <id>”) or and leave record (“L <id>”) for the given badge id.
- gqian3 April 07, 2017 in United States
The room is empty at the beginning and ending of the day, and there are no other ways into or out of the room.
E: Enters the room
L: Leaves the room
Well formed log:
E 111
E 222
L 111
E 111
L 222
L 111
Question: You have a log and write a function to check is it the well formed log or not.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
Answers* Definition for a binary tree node.
- ajay.raj March 27, 2017 in United States
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
Given an array of Binary Tree Node, check if all of these nodes can form a binary tree?
Public boolean canForm(TreeNode[] nodes){
}| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 2of 2 votes
AnswersPhone Interview, New Grad - Software Developer
Imagine you are given 10,000 files each containing 1 Million integers. I would you sum all of them and give the final result?
---> Interviewer wanted to test scalability, distributed concepts.
He has written the basic code and wanted to improve upon that.
Here's the basic code.public getSum(String[] file_names) { int sum = 0; for(String f: file_names) { sum = sum + sumOfFile(f); } return sum; }
Questions:
- confides123 March 25, 2017 in United States for Developer Tools
What's wrong with above code? Ans: Integer overflow
How would you implement sumOfFile?
What if 'sumOfFile' takes lot of time to finish computing?
How do you fasten the program?
Overall scalability etc| Report Duplicate | Flag | PURGE
Google Software Developer Distributed Computing - 3of 3 votes
AnswersGiven a sorted array, find all the numbers that occur more than n/4 times.
- alisonlee659 March 24, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGive a Runable interface, and then give a scheduler post method. This post is parallel, for example:
- ajay.raj March 23, 2017 in United States
Method header:
public void post (Runable r) {};
Call 5 times:
Scheduler.post (r1);
Scheduler.post (r2);
Scheduler.post (r3);
Scheduler.post (r4);
Scheduler.post (r5);
The five runables are allocated to five threads and run at the same time. And then asked: how to achieve these five tasks one by one run,| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 5 votes
AnswersIn school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
- aonecoding March 22, 2017 in United States
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Follow-up:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersIn school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
- aonecoding March 22, 2017 in United States
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time), check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Follow-up:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure the student gets the reward.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGiven an non-negative int array and target number, check if the target can be equal to the sum of non-negative multiples of the numbers in the array.
- ajay.raj March 17, 2017 in United States
For example, I have three numbers 6,9,20. Ex: n = 47 then it can be determined that 47 = 9*3 + 20
n=23 then there are no combinations.
public boolean combinationSum(int[] nums, int target) {
}| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersCheck if two given binary trees(expression trees with two characters 'a' and 'b' and obviously operators like +,-,*) are mathematically equivalent?
- AlgoBaba March 16, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersFind three non-overlap windows of size k in an int array, that together has a maximum sum
- ajay.raj March 14, 2017 in United States
of the 3k entries.
example
int[] nums = [1,2,1,2,6,7,5,1]
k = 2
output
[1,2],[2,6],[7,5]| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersGiven a list of words with lower and upper cases. Implement a function to find all Words that have the same unique character set .
- marium27 March 14, 2017 in United States
For example:
May student students dog studentssess
god Cat act tab bat flow wolf lambs Amy Yam balms looped poodle john alice
output:
may amy
student students studentssess
dog god
cat act
tab bat
flow wolf
lambs balms
looped, poodle| Report Duplicate | Flag | PURGE
Google - 2of 2 votes
AnswersGiven an int array without repeated elements and a target, count the total number of subset that can be generated from the array such that min (subset) + max (subset) < target
- ajay.raj March 13, 2017 in United States
public int countSubSet(int[] nums, int target){
}| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersData structure design, N horse races, there are 10 checkpoints, whenever a horse through a check point will produce a (horse number, check point number) message, then design a data structure and algorithm to update the messages and then get the top 3 horse efficiently.
- ajay.raj March 13, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersInput friend’s relation {{1,2}, {2,3}, {3,4}}, could you split all the users into two groups and for the user in each group, all the users do not know each other. So the expected output should be group1 {1,3}, group2 {2,4}. If it is cannot be spitted into two group, just return “impossible”
- ajay.raj March 12, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersGiven an array that contains both positive and negative integers, find the start and end index of the subarray that achieves the maximum subarray product using one pass
- ajay.raj March 12, 2017 in United States| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
Answershow to find leaf node value from preorder sequence of BST without rebuilding the tree
- ajay.raj March 11, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - -2of 2 votes
Answersdeleted
- ajay.raj March 10, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersSay you have an array for which the ith element is the price of a given stock on day i.
- ajay.raj March 10, 2017 in United States
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
, but each time you sell you need to pay transaction fee, please calculate the maximum profit you can take.
public int maxProfit(int[] prices, int fee) {
}| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
Answersfor a binary tree, print the root to the leaf path, but add "_" to indicate the relative position.
example:
- ajay.raj March 10, 2017 in United StatesA / \ B C / \ / \ D E F G output _ _ A _ B D _A B _E A _C F A _ C _ _ G
| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
Answers/**
- ajay.raj March 10, 2017 in United States
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
Given a list of intervals, and a target interval
Our goal is to merge these intervals, so that the results of the merge can cover the target interval, return the minimum number of the original interval required for this merge
For example
IntervalList: [-1, 9] [1, 10] [0, 3] [9,10] [3, 14] [2, 9] [10, 16]
Target interval: [2, 15]
we find that there are several ways to cover [2,15], such as:
[-1, 9] + [9,10] + [10, 16] or [1, 10] + [10, 16].
We want to merge the least number of ways, so here should return 2| Report Duplicate | Flag | PURGE
Google SDE1 - 4of 4 votes
Answers/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
Find if a given binary tree has duplicate sub trees.
followup:
Find all duplicate subtrees in a binary tree
- ajay.raj March 03, 2017 in United StatesFor example, 1 / \ 2 3 / / \ 4 2 4 / 4 The following are two duplicate subtrees: 2 / 4 and 4 Therefore, return [ [2,4], [4] ].
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 6of 6 votes
AnswersPaper Cut into Minimum Number of Squares
- ajay.raj March 02, 2017 in United States
Given a paper of size A x B. Task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.
Examples:
Input : 13 x 29
Output : 9
Explanation :
2 (squares of size 13x13) +
4 (squares of size 3x3) +
3 (squares of size 1x1)=9
Input : 4 x 5
Output : 5
Explanation :
1 (squares of size 4x4) +
4 (squares of size 1x1)
geeksforgeeks provides a solution, but it is not right
http://www.geeksforgeeks.org/paper-cut-minimum-number-squares/| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersGiven the weekly vacation numbers for various cities for an year (ie 12 * 4 = 48 weeks ) , design a tour which will maximize the number of vacations for a salesman. The salesman can choose to work in any city for the week , and can weekly change the city unlimited number of times , but has to remain in the city for the week . It's not necessary for the salesman to go to all cities , goal is to find the schedule which maximize the vacation for whole year. Input will be HashMap<string , int[48] vacation> where string is the city name and int[48] is city's vacation numbers for an year.
- yuvithomas February 27, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 6 votes
AnswersCreate an iterator class that stores a list of the built-in Iterators.
- aonecoding February 27, 2017 in United States
Implement the next() and hasNext() methods in a Round Robin pattern (pops next element in a circle).
Example:
Given a list [iterator1,iterator2, iterator3...]
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next() if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
until there is no more element in any of the iterators| Report Duplicate | Flag | PURGE
Google Algorithm