Google Interview Questions
- 2of 2 votes
AnswersWe have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get
- neer.1304 July 03, 2019 in United States
this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
Input : k = 2, A = {10, 10, 10, 10}
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter
gets 20 units of board and the total
time taken is 20.
Input : k = 2, A = {10, 20, 30, 40}
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for
second painter.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersCreate an iterator class that stores a list of the built-in Iterators.
- acoding167 March 15, 2019 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 - 2of 2 votes
AnswersApril Google Interview 1/4
- aonecoding May 06, 2018 in Korea
A = a+b-c-a-b-c-a-b (Tree)
B = b+a+c+a+b-c+b (Tree)
is A equal to B| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersApril Google Interview 3/4
- aonecoding May 06, 2018 in Korea
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.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven a equation in the form of "3x+4y+2=-5y+2x+10", simplify the equation to be in form "y=Ax+B", and return A,B. Also allow parenthesis to be in the equation. Ex. "3y-4x+(3-(2x-3y))=10y", result is "y =0.75 - 1.5x"
- anony-mites April 16, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswerWas asked at GHCI Bangalore at their booth for a prize and perhaps hiring interns or experienced software developers.
- jaryya@hawk.iit.edu November 10, 2019 in India
Find the return value for N=100
int returnAns(int N){
int ans=0;
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
ans +=((i & -i) == (j & -j)?1:0); //the question missed the condition and was returning a boolean, so I added it myself
}
}
return ans;
}
My answer: 0 ; their answer: 1610, hence got it wrong.
My explanation: I assumed negative of i in binary to be
simply represented by setting the MSB to 1 e.g. for 8 bit representation of 3: +3 is 0000 0011 and -3 is 1000 0011. In the inner loop the value of ans will always evaluate to 0 since Bitwise & of these i and -i or j and -j will always result into i and j respectively. (undergrad computer organization concept.)
Negative numbers can also be represented as 1s and 2's complement and in all modern machines by architecture its 2s complement.
Now if we assume 1's complement, +3: 0000 0011 and -3: 1111 1100. so bitwise & of these two is 0 and so the value of ans will always be incremented by 1. By two loops 100+99+98+97+...+1 = 100*101/2 (i.e. n*(n+1)/2)
Then 2's complement, which is the most relevant representation of signed binary numbers.
Odd numbers:
+3: 0000 0011 -3: 1111 1101 Binary & is 0000 0001.
For all even numbers:
+4: 0000 0100 and -4: 1111 1011+0000 0001 = 1111 1100 and Bitwise & of 4 and -4 is 0000 0100 which is 4.
So, in the innermost loop ans is incremented by 1 when i is odd and j is also odd. ie. when i is 1, 3, 5, 7... 97 and j is 3, 5, 7, 9,...,99 ans is added 1(return value of true ==) when calculated it comes to 1610.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswerSelect a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid).
- acoding167 June 19, 2019 in United States
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 - 2of 2 votes
AnswerGoogle
- aonecoding January 20, 2018 in United States
1st round
Given a box with N balls in it, each ball having a weight, randomly choose pick one out base on the weight.
Input ball1-> 5kg, ball2 -> 10kg and ball3 -> 35kg,
then Prob(ball1 chosen) = 10%, Prob(ball2) = 20%,
Prob(ball3) = 70% ;
Follow-up:
Select a ball randomly based on weights. Once a ball is chosen, remove it. Next time select from the remaining balls. Go on until there is nothing left in the box.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven matrix in which each cell is either filled with 'C' (Computer) or empty.
- igeek April 13, 2019
Computers can communicate if they are in the same row or in the same column.
Computers can also communicate through middleware computers.
Given index of a computer, find all computers it can communicate with.
How many communication paths are there?
Find the order of turning computers off, in which every computer will manage to communicate with another computer in order to pass the data it stores before it is turned off, keeping minimum computers on in the end.| Report Duplicate | Flag | PURGE
Google - 2of 0 votes
AnswersThere are hundred prisoners each standing in a column. Each one is given a hat and there are two possible colors of hat which are red and white. The 100th person can see the hats of 99 people in front of him and the 99th person can see 98 people in front of him but can't see his own and the previous hat. The number of hats aren't known and the hats are placed in random order. Starting with the 100th person, each person is asked what color hat they have. If they guess wrong, they die. Come up with a strategy such that maximum people are alive. How many people are alive? (Do not use probability constraint given)
- preethi natarajan October 31, 2008| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Brain Teasers - 2of 0 votes
AnswersVirtual functions and vtable...
- Anonymous November 06, 2008
What happens when a Constructor gives a call to a virtual functions
What if it is a pure virtual function| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer C - 1of 7 votes
AnswersWrite a method to determine if two strings are anagrams of each other.
- nsvbry August 14, 2013 in United States
e.g. isAnagram(“secure”, “rescue”) → false
e.g. isAnagram(“conifers”, “fir cones”) → true
e.g. isAnagram(“google”, “facebook”) → false| Report Duplicate | Flag | PURGE
Google Software Engineer in Test - 1of 5 votes
AnswersWrite a function that takes an integer as input and produces an output string.
- tbag March 11, 2015 in United States
Some sample Input/outputs are as follows
i/p o/p
1 - A
2 - B
3 - AA
4 - AB
5 - BA
6 - BB
7 - AAA
8 - AAB
9 - ABA
10 - ABB
11 - BAA
12 - BAB
13 - BBA
14 - BBB
15 - AAAA| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 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 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 - 1of 3 votes
AnswersGiven an inorder traversal only for a binary tree (not necessarily a
- Bugaboo December 27, 2011 in United States
BST), give a pseudo code to generate all possible binary trees for
this traversal sequence.
Firstly, how many binary trees can be generated given an in-order
traversal? I know that given 'n' nodes, number of BTs possible is
(2^n)-n. But if we are given a specific in-order sequence, can we cut
down on this number?| Report Duplicate | Flag | PURGE
Google - 1of 3 votes
AnswersYou are given a string which has numbers and letters. Numbers occupy all odd positions and letters even positions. You need to transform this string such that all letters move to front of array, and all numbers at the end.
- andy March 09, 2014 in United States for Google Search
The relative order of the letters and numbers needs to be preserved
I need to do this in O(n) time and O(1) space.
eg: a1b2c3d4 -> abcd1234 , x3y4z6 -> xyz346
Please don't submit your answers if it is not fulfilling the time-space complexity requirements.| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 3 votes
AnswersFirst greater number in an array. Given a large array of positive
- nim January 24, 2012 in United States
integers, for an arbitrary integer A, we want to know the first integer in
the array which is greater than or equal A . O(logn) solution required
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 3 votes
AnswersHow can you efficiently implement three stacks in a single array, such that no stack overflows until there is no space left in the entire array space.
- alex December 13, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 1of 3 votes
Answersdesign and implement a calculater that can calculate expressions like:
- srcnaks February 02, 2015 in -
+ 2 4
* 8 ( + 7 12)
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 )
(PS:all items are space delimetered.)
Example answers
+ 2 4 => 2 + 4 = 6
* 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Problem Solving Stacks String Manipulation Trees and Graphs - 1of 3 votes
AnswersDoes a given file name match a single-star pattern? (can't use regex I assume)
- Guy January 18, 2014 in United States
index.html matches *.html
foo.txt does not match *.html
matches(“index.html”, “*html”) returns true
matches(“foo.txt”, “*html”) returns false
matches(“cat”, “c*t”) returns true| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 3 votes
AnswersGive efficient implementation of the following problem.
- sigkill July 08, 2014 in India
An item consist of different keys say k1, k2, k3. User can insert any number of items in database, search for item using any key, delete it using any key and iterate through all the items in sorted order using any key. Give the most efficient way such that it supports insertion, search based on a key, iteration and deletion.| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 1of 3 votes
AnswersHow to find medium of 1 billion numbers across N distributed machines efficiently?
- seanren7 August 09, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 1of 3 votes
AnswersHow would you synchronize a linked list across multiple computers. If nodes are added/removed to a linked list on one computer, all others must reflect this change. Concurrancy must be accounted for. (java)
- Guy January 22, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - 1of 3 votes
AnswersFind the shortest path in a maze (from origin to destination). I believe we are supposed to use Dijkstra or BFS. But what I am confused with is that Dijkstra computes the shortest path based on the distance of each edge. But a maze doesn't have weighted edges, and its shortest path should be 'minimum number of cells'. How can we make use of Dijkstra, or BFS?
- Guy January 21, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 3 votes
AnswersCreate a function to calculate the height of an n-ary tree.
- theNightsKing16 November 03, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Trees and Graphs - 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 - 1of 3 votes
AnswersA graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted vertices given in K. If it creates a path, we have to discard the edge.
- setu April 01, 2019 in India
Example: N = 4; K = {(1,4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 3 votes
Answershow would you store and find the top 10 queries in google from some day (when you begin to count) till a certain date?
- adam2008 February 11, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer