Google Interview Questions
- 0of 0 votes
AnswersYou are given a log of wood of length `n’. There are `m’ markings on the log. The log must be cut at each of the marking. The cost of cutting is equal to the length of the log that is being cut. Given such a log, determine the least cost of cutting.
- psuedo April 10, 2015 in India| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 2 votes
AnswersDesign an optimised algorithm to solve snakes and ladders with the least amount of roles possible under the assumption that you get whatever role you want when you role the dice.
- abc March 26, 2015 in United Kingdom for Graduate| Report Duplicate | Flag | PURGE
Google Software Engineer Dynamic Programming - 6of 8 votes
AnswersGiven an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter.
- dreamchaser1984 March 25, 2015 in United States
For Ex:
Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100]
n -> 2
Out put -> [100, 0] or [100, 2]
Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Algorithm - 0of 0 votes
AnswersThis is a two part question related to Markov string generation.
- Lively March 25, 2015 in United States
Part 1: Read a training set of strings. For each character in any of the strings, calculate the probability of seeing that character and store it for later use. (this part is about coming up with the right data structure and correct probability calculation).
Part 2: Based on the training set from Part 1, generate a random string of length N.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersGiven an API ReadFromDisk() which returns a block of 256 bytes from disk. Implement the API Read(SizeInBytes) which reads SizeInBytes bytes from the disk by calling only ReadFromDisk. Notice that every call to ReadFromDisk() will read the next 256 bytes from disk.
- Lively March 25, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven an API ReadFromDisk() which returns a block of 256 bytes from disk. Implement the API ReadEx(SizeInBytes) which reads SizeInBytes bytes from the disk by calling only ReadFromDisk. Notice that every call to ReadFromDisk() will read the next 256 bytes from disk.
- Lively March 25, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersYou are given printouts from an algorithm which ran over an unsorted binary tree. One printout is from an in-order run and another from a pre-order run. Can you reconstruct the tree? If so, then write an algorithm.
- tested.candidate March 22, 2015 in UK| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersYou are given printouts from an algorithm which ran over a sorted binary tree. One printout is from an in-order run and another from a pre-order run. Can you reconstruct the tree? If so, then write an algorithm.
- tested.candidate March 22, 2015 in UK| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersYou have N points on a 2D surface. List K points at a shortest distance to the point (0, 0).
- tested.candidate March 22, 2015 in UK| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 2 votes
AnswersThere is a company with 250 employees. Its records contain: EmployeeID, ManagerID (which is a reference to the EmployeeID of the manager).
- tested.candidate March 22, 2015 in UK
Part 1. List directly reporting employees for a given ID
Part 2. List all (also indirectly) reporting employees to a given ID| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersAssume we only take the least significant digit of each value in fibonacci sequence, and form the sequence of digits into pairs. In those pairs, the first value of one pair is the same as second value of its predecessor.
- evi March 22, 2015 in United States
As we know the fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21...
so the pair sequence is:
[1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 3], [3, 1] ...
Write a function to output the first n pairs of this sequence.
void Outputpairs(int n)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersPart 1: You are given a computer #1 with array Foo, a computer #2 with array Bar and a spare computer #3. You need to apply a function F to corresponding/matching elements of the two arrays. How would you do that?
- tested.candidate March 21, 2015 in UK
Part 2: Once you scale up, how would you balance the number of machines sorting with the machines applying the function?
Part 3: What if the master (which is distributing the work) dies and never recovers?| Report Duplicate | Flag | PURGE
Google Software Engineer Distributed Computing - 0of 2 votes
AnswersPrint all the different possible subsets suming the given number
- guysackman21 March 21, 2015 in India
Ex:
Input:4
Output:
1111
112
121
112
13
31| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 1of 1 vote
AnswersYou are given two strings. String T is a string where characters need to be reordered. String O contains characters (none of them repeated) which defines the order/precendence to be used while reordering the string T. Write an algorithm to do the reordering.
- tested.candidate March 21, 2015 in Switzerland
*** SPOILER ALERT ***
The question was pusposefully underspecified - upon questioning it was revealed that the string O might not necessarily include all characters used in string T - the characters not included in string O are supposed to be placed at the beginning of the resulting string (in no particular order).| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersYou are given two arrays - A & B. The length of the arrays is the same - N. The values in the arrays are integers from 0 to N - 1 in random order and no number is repeated. You need to list a sequence of two-element swaps required to reorder the array A into the order of the array B. Additionally, at each step of the sequence you are allowed to swap two elements only if one of them is 0.
- tested.candidate March 21, 2015 in UK| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGiven an array Of integers build a new array of integers such that every 2nd element of the array is greater than its left and right element.
- Gaurav Shah March 17, 2015 in United States for Chrome Team
eg:
[1,4,5,2,3]
o/p:
[1,4,2,5,3]
Soln proposed:
Step 1:Sort The array -> O(nlogn)
Step 2:Use 2 indices: one starting at leftmost index and other at rightmost index.
and populate the new array alterntely using the left pointer(index) first and then the right pointer and then increment the pointer used. till both the pointers meet/cross each other. -> O(n).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 5 votes
AnswersProblem Statement
- nirajkantsinha March 13, 2015 in United States
Diameter
The diameter of a graph is the maximum shortest path between any two nodes.
At the beginning, there is a simple grpah contains exactly 1 node. Then we add new nodes one by one to the graph. Each time when we add a new node to the graph, we also add exactly one edge to connect this node to another node which already exists.
We want to find the diameter of the graph each time we add a new node. Note that each edge cost 1.
Input Format:
First line of the input contains one integer N, indicating how many new nodes we will add.
Then following N lines. The ith line contains an integer X, which means we add the ith node and an edge connecting the Xth node and ith node.
The original node is the 0th node.
Output Format:
Output N lines. The ith line is an integer indicating the diameter of the graph after adding the ith node.
Constraints:
0 < N <= 100000
0 <= Xi < i
i is counting from 1
Sample Input:
5
0
0
1
1
1
Sample Output:
1
2
3
3
3
Explanation:
Firstly the graph contains only node 0. The first line of output is 1 because the diameter becomes 1 when node 1 is added and connected to node 0. Diameter becomes 2 after adding node 2 to node 0. Then adding node 3, 4, 5, all of them are connecting to node 1, caculate the shortest path of all pairs of nodes, the maximum shortest path is 3, so the last 3 lines of output are all 3.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 2 votes
AnswersWrite algorthim to determine the total time to make ice cream and when it leaves the store.
- google_me_honey March 12, 2015 in United States
Consist of an order time, order number, and ice cream type.
“ice cream Type” is an integer: 0 for combo, 1 for vanilla. Order numbers are increasing.
We have three machines for making ice creams.
It takes 45 seconds to make a combo ice cream and 15 for vanilla. Can only make one ice cream at a time.
Need to determine total time to make ice cream and time the ice cream leaves the store (delivered).
In: order_time,order_num,ice_cream_type
Out: order_num,depart_time,total_time| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 5of 5 votes
AnswersGiven a number "n", find the least number of perfect square numbers sum needed to get "n"
- tazo March 12, 2015 in United States
Example:
n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)
n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)| Report Duplicate | Flag | PURGE
Google Dynamic Programming - 3of 3 votes
AnswersFind longest substring with "m" unique characters in a given string.
- tazo March 12, 2015 in United States
input: aabacbeabbed
output:
4 (aaba) for 2 unique characters
6 (aabacb) for 3 unique characters| Report Duplicate | Flag | PURGE
Google Dynamic Programming Problem Solving - 0of 0 votes
AnswersYou are given heights of n candles .
- Rahul Sharma March 11, 2015 in India
First day you lit one candle
second day you need to lit two candles
Third day you need to lit three candles
..........
........
till possible.
After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day.
So you need to tell the maximum number number of days , you can carry on lighting the candles.
Example : there are three candles of heights {2 , 2 ,2 }
Answer : 3
1.You light first candle on day one. heights -> {1,2,2}
2.You light second and third and extinguish first one . heights ->{1, 1,1}
3.You light all the candles. heights -{0,0,0}| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 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 1 vote
AnswersConsider a social network graph like facebook. You are throwing a party and want to invite some of your friends. Design a algorithm to select top n friends from m friends using the social graph.
- mandardalvi8 March 09, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 1of 1 vote
AnswersHow would you optimize an elevator system for a building with 50 floors and 4 elevators ? Optimize in terms of lowest wait times for the users. Nothing related to power consumption.
- tbag March 08, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer System Design - 0of 0 votes
AnswersGiven the interface below, implement a task scheduler.
interface Task { void Run(); Set<Task> GetDependencies(); }
Additionally, the task scheduler should follow two rules.
- John March 07, 2015 in United States
1. Each task may only be executed once.
2. The dependencies of a task should be executed before the task itself.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersCreate a maze.
- marinalepi March 06, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Problem Solving - 0of 0 votes
AnswersPlay Scrabble. You have 7 letters to start from. Build the word with the highest score.
- marinalepi March 06, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer String Manipulation - 5of 5 votes
Answers
- Alex March 04, 2015 in United StatesQuestion: Given two strings, find number of discontinuous matches. Example: “cat”, “catapult” Output: 3 => “CATapult”, “CatApulT”, “CAtapulT”
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm