Google Interview Questions
- 0of 0 votes
AnswersCombination of these two leetcode question.
- nauld November 22, 2016 in United States
Given a digital strings, find all the sentence it can represent.
Digital to letter mapping is same as telephone keypad.
Separating the letters according to a dictionary to form sentences.
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
https://leetcode.com/problems/word-break-ii/| Report Duplicate | Flag | PURGE
Google SDE-3 Algorithm - 0of 2 votes
Answers// TokenBucket
- nauld November 22, 2016 in United States
// Goal: regulate a resource of some kind (1 token = 1 unit of a resource)
//
// init(start_tokens, max_tokens, fill_rate)
// get_tokens(int tokens)
// - block until those tokens are available in the token bucket
// - if number of tokens in the bucket is less than requested number of tokens, wait
// put_tokens(int tokens)
// - block until there is space in the token bucket for those tokens.
// fill_rate: x tokens per sec are added to the token bucket
Thread communication methods allowed are listed below. No thread safe collections are allowed.
// Lock()
// - lock()
// - unlock()
// ConditionVariable()
// - wait(lock, max_time_to_wait_in_secs)
// - releases lock before sleep and then reacquires lock upon waking
// - notify(): This wakes up 1 waiter on this condition variable
// - notifyAll(): Wakes up all waiters on this condition variable| Report Duplicate | Flag | PURGE
Google SDE-3 Algorithm - 2of 2 votes
AnswersYou are the main character in a game where you have to defeat a number of enemies in order. The player has a strength value and an initial amount of money. Each enemy also has a strength value, plus a price.
- camiloni42 November 19, 2016 in United States
When facing each enemy you can either:
1) Fight him (if your strength is enough). You keep your money.
2) Bribe him (if you have the necessary money). You subtract the enemy's price from your money, and it joins you and adds its strength to yours.
Given a starting strength and amount of money, calculate the optimal strategy and the amount of money you end with (-1 if impossible).
This can be easily solved recursively in O(2^n) basically trying out each option at every enemy. But is there a polynomial solution, maybe involving DP?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven a list of coin values, and quantity of each type of coin. Write a
- snakeonbasket November 18, 2016 in United States
program to return the set of all possible sums which can be made using those
coins.
ex. coins = [10, 50, 100, 500]
quantity = [5, 3, 2, 2]
sum could be 400 , 300 ,200 , 100| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
Answersn points on a 2D space. You observe the points from (0,0) with viewing direction and viewing angle.
- Casper November 17, 2016 in United States
Given an array (xn,yn), and a viewing angle v (45 degree), find the direction that can observe max number of points.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer C++ - 0of 0 votes
AnswerWrite a function that compares Spanish strings, how would you handle special cases like 'ch' ?
- Gear November 17, 2016 in United States
c < ch < d, ch will be represented as 2 ASCII characters| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven a function getRandom that returns a random double in [0,1). Write a function getRandomPermutation(int n) that takes a positive integer n as argument and returns a random permutation of first n natural numbers.
- AlgoBaba November 15, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou are given a sorted list of distinct integers from 0 to 99, for instance [0, 1, 2, 50, 52, 75]. Your task is to produce a string that describes numbers missing from the list; in this case "3-49,51,53-74,76-99".
- Casper November 14, 2016 in United States
Examples:
[] “0-99”
[0] “1-99”
[3, 5] “0-2,4,6-99”| Report Duplicate | Flag | PURGE
Google Software Engineer Intern C++ - 0of 2 votes
AnswerAssume (n+1) points on a 2D space. You observe the points from (0,0) with viewing direction and viewing angle.
- Casper November 14, 2016 in United States
Given an array (xn,yn), and a viewing angle v (45 degree), find the direction that can observe max number of points.| Report Duplicate | Flag | PURGE
Google Software Engineer Intern C++ - 3of 3 votes
AnswersGiven 'n' circles (each defined by center and radius)
- sheva November 12, 2016 in United States
Write an algorithm to detect if circles intersect with any other circle in the same plane
Better than O(n^2) complexity| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersReturn the pivot index of the given array of numbers. The pivot index is the index where the sum of the numbers on the left is equal to the sum of the numbers on the right. Input Array {1,2,3,4,0,6}
- umesh.shaw November 11, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Arrays - 1of 1 vote
AnswersGiven the village of a map represented as a 2D grid containing houses,bushes and open-spaces, write a program to find a point for conducting a meeting in the map. Such point should be minimum from all the houses in the village.
Eg.# # # # # # # A # # B # # # # # # # C # # # # # #
# -> represents the bushes
- angry_scorpion November 10, 2016 in United States
A, B, C -> position of houses
I provided a O(n*a*b) approach, where n-> no. of houses , a,b->dimensions of the grid.
The interviewer asked me for some special cases. Can it be done more efficiently?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersWrite an algorithm that returns any duplicate in an array of integers. The algorithm must run in O(n) time and O(1) space. (hint: the integers in the array are not greater than the size of the array).
- davidgbadebo6 November 08, 2016 in United States| Report Duplicate | Flag | PURGE
Google Intern - 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 - 0of 0 votes
AnswersGiven a binary tree & the following TreeNode definition, return all root-to-leaf paths.
Definition of TreeNode:public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val) { this.val = val; this.left = this.right = null; } }
EXAMPLE
Given the following binary tree: 1 / \ 2 3 \ 5 All root-to-leaf paths are: [ "1->2->5", "1->3" ]
From Lint Code - http://www.lintcode.com/en/problem/binary-tree-paths/
- johndifini October 29, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersYou are given a scrambled input sentence. Each word is scrambled independently, and the results are concatenated. So:
- merlinme October 25, 2016
'hello to the world'
might become:
'elhloothtedrowl'
You have a dictionary with all words in it. Unscramble the sentence.| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer String Manipulation - 2of 2 votes
AnswersGiven a string "2-4a0r7-4k", there are two dashes which we can split into 3 groups of length 1, 5, 2.
- J@sper October 20, 2016 in United States
If we want each group to be length 4, then we get "24A0-R74k"
Given a String A and an int K, return a correctly formatted string.
IF A is "2-4A0r7-4k" and B is 4, string is "24A0-R74K"
IF K is 3, string is "24-A0R-74K" as the first grp could be shorter.| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersGiven an n-ary tree, find the longest sequence in it. The sequence doesn't end to start at the root. It can go from leaf to leaf.
- ul October 16, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Trees and Graphs - 1of 1 vote
AnswersGiven an NxN grid with an array of lamp coordinates. Each lamp provides illumination to every square on their x axis, every square on their y axis, and every square that lies in their diagonal (think of a Queen in chess). Given an array of query coordinates, determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on,…
- ad09 October 16, 2016 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersFind the shortest path between a start node and end node in a undirected +ve weighted graph.
You are allowed to add at max one edge between any two nodes which are not directly connected to each other.
ex:
From | To | Weight
1 2 2
1 4 4
2 3 1
3 4 3
4 5 1
start node = 1, end node = 5.
extra edge weight = 2.
- JerryGoyal October 15, 2016 in United States1----(2)----2 | | | | (4) (1) | | | | 5-(1)-4----(3)----3 In this case answer would be 3 (from 1 - > 5 - > 4) Solution: 1----(2)----2 /| | / | | (2)/ (4) (1) / | | / | | 5-(1)-4----(3)----3
| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - -1of 1 vote
AnswersGiven an un-directed weighted graph G(V,E), find the minimum weight between two given nodes X & Y
- gsharma34065 October 14, 2016 in India
(i.e. sum of weights of edges between X & Y).
You can add an extra egde with weight W between any two nodes in the graph exactly one time (if required).| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersLet's say I have a word "I love chicken", I can break the number of characters in each word, like so: [1] [4] [7]
- J@sper October 11, 2016 in United States
[1,4] [4,7], [1,4,7].
Now let's say I have a max = 5. The phrases with equal or fever than 5 characters are "[I], [love], and [I, love]. The longest phrase is [I,love], which contains 2 words.
Complete the Length function given. It has 2 parameters:
1) An array of integers, named array
2) A maximum number, named max.
int Careercup( int [] array, int max) {
}
Example test case 1:
[3,1,2,3]
4
Output expected : 2| Report Duplicate | Flag | PURGE
Google Software Developer Arrays - 3of 3 votes
AnswersFind the largest and smallest number in a list. The list is stored as two sections, one in ascending order and the other in descending order.
- uno September 29, 2016 in United States
input [ 2 3 4 5 6 7 10 9 8 7]
smallest : 2
Largest 10| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersGiven an Array A with n elements. Pick maximum number of elements from given array following the rule:
- chan alex September 25, 2016 in United States
1. We cannot pick A[i] and A[j] if absolute value of (A[i] - A[j]) > absolute value of (i - j)
Example: {13,5,4}
Ans: 2
Pick 5 and 4.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersImplement method:
Lìst<Range> getRanges(Lìst<Shard> shards, Lìst<Key> keys)
That returns list of ranges. Each range represents multiple keys aggregated over a shard:
n-keys —> 1-shard —> l-range
Method should return no more than 1 range per shard that spans all keys or their parts belonging to this shard.
Each of the ‘Range` , 'Shard’ and ‘Key’ classes have ‘end’ and ‘start’ fields of int type, where ‘start’ is inclusive and ‘end’ is exclusive.
Example:
- ermilanardeshana September 21, 2016 in United States1—9, 12—59, 100—999 <— shards (input) 2—3, 6—8, 11—20, 200—220 <— keys (input) 2—8, 12—20, 200—220 <— ranges (output)
| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 0of 2 votes
Answershttp://www.geeksforgeeks.org/find-water-in-a-glass/
- vgupta.2119 September 18, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Developer - 2of 4 votes
AnswersFind the minimum of every sub-array of size k in an array of size n.
- vgupta.2119 September 18, 2016 in India
O(n) solution required.| Report Duplicate | Flag | PURGE
Google Software Developer - -1of 1 vote
Answershttp://www.geeksforgeeks.org/find-water-in-a-glass/
- vgupta.2119 September 18, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Developer - 1of 3 votes
AnswersFind the minimum of every sub-array of size k in an array of size n.
- vgupta.2119 September 18, 2016 in India
O(n) solution required.| Report Duplicate | Flag | PURGE
Google Software Developer - -1of 1 vote
AnswersSearching for a string in a DOM tree. A complete working solution was required. Assume you have any string matching algorithm available.
- vgupta.2119 September 18, 2016 in India
(Based on Ctrl+F search in chrome)| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm