Google Interview Questions
- 0of 2 votes
AnswersThe text of question below is exactly given by Google interviewer. So they are owner of the text and I am just quoting them. I am not the author of the text below:
- amirtar May 05, 2015 in United States
"
Imagine a museum floor that looks like this:
.#.G.
..#..
G....
..#..
G == Museum Guard
# == obstruction/impassable obstacle
. == empty space
Write a piece of code that will find the nearest guard for each open floor space. Diagonal moves are not allowed. The output should convey this information:
2#1G1
12#12
G1223
12#34
You may choose how you want to receive the input and output. For example, you may use a 2-d array, as depicted here, or you may use a list of points with features, if you deem that easier to work with, as long as the same information is conveyed.
"| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Ideas Math & Computation - 0of 0 votes
AnswersWrite a function
- psuedo April 10, 2015 in India
bool fancy_shuffle(char* s);
which rearranges characters in the string given as input, in such a way that no same character occurs twice in a row (that is, next to each other).
If such rearrangement is not possible, the function should return false.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven an array of numbers, find a pair whose sum is closest to zero.
- psuedo April 10, 2015 in India| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 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 - 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 - 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 - 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 - 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
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 - 2of 2 votes
AnswersConsider the 52 cards of a deck. You generated a random sequence for these cards and want to send that sequence to a receiver. You want to minimize the communication between you and the receiver, i.e., minimize the number of bits required to send the sequence.
- eng.ahmed.moustafa February 23, 2015 in United States
What is the minimum number of bits required to send the sequence?
Hint: It is not 6 x 52| Report Duplicate | Flag | PURGE
Google Software Engineer Arrays - 0of 0 votes
AnswersOn a table there are four papers, one with the letter X written on top, one with the letter Y written on top, one with the number 1 written on top, and one with the number 2 written on top. Every paper has one of those letters on one side and one of those numbers on the other side. To prove that a paper with the letter x contains even number on the other side, what is the minimum number of conditions we have to check?
- LeetJile February 23, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Brain Teasers - 0of 0 votes
AnswersHow would you get all of the unique IDs out of a single file? What if it was a very large file?
- LeetJile February 23, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Knowledge Based - 0of 0 votes
AnswersWrite a function that takes an array of numbers and returns the maximum and minimum values.
- trophygeek February 21, 2015 in United States
Give BigO for runtime.
(This is a basic coding question. There are no real tricks or shortcuts.)| Report Duplicate | Flag | PURGE
Google Software Engineer Coding - 0of 0 votes
AnswersSuppose you are in the middle of Africa, each machine is on an Edge network, and each packet between the machines costs $1.00. Write a solution that minimizes the cost.
- shing.zhao February 03, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Network - 0of 0 votes
Answersdesign a video thumb up/down system at youtube scale. how to concurrent read/write, persistence, store, update....etc.
- rjrush January 30, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer System Design