Google Interview Questions
- 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 - -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 - 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 4 votes
AnswersYou have a bunch of light bulbs. Store them as you wish. Implement a function that tells you if the light is on or off given its index and another one that toggles the state of the light bulbs given a start and end index.
- ad09 August 09, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - -1of 5 votes
AnswersFollow-up to above question:
- / July 31, 2016 in United States
Can you augment a BST to return the number of elements with node values in a given range?
If not, what other data structure would work?| Report Duplicate | Flag | PURGE
Google Software Engineer Data Structures - -1of 3 votes
AnswersWrite a function that takes as input an array of integers A, and two integers low and high.
- / July 31, 2016 in United States
Your function has to output pairs of indices: {(i,j), ...}
Where each pair of indices denotes that the subarray of A[i...j] has a sum in the range low <= sum <= high.
Apparently there are algorithms better than O(N^2).| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 4 votes
AnswersYou are currently in practice mode. This is a demo only.
- New Grad July 30, 2016 in United States
A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.
For example, consider the following array A consisting of N = 8 elements:
A[0] = -1
A[1] = 3
A[2] = -4
A[3] = 5
A[4] = 1
A[5] = -6
A[6] = 2
A[7] = 1
P = 1 is an equilibrium index of this array, because:
A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:
A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:
A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0
and there are no elements with indices greater than 7.
P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.
Write a function:
int solution(int A[], int N);
that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.
For example, given array A shown above, the function may return 1, 3 or 7, as explained above.
Assume that:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 16of 20 votes
AnswersGiven two object arrays of "id,weight" (sorted by weight), merge them together and create a one single array. If the "id"s are same values should be merged. Final resulting array should be sorted by weight. Result should be O(nlogn) in time complexity.
- dee707 July 28, 2016 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGiven a string return the longest palindrome that can be constructed by removing or shuffling characters.
- enkadi13 July 22, 2016 in United States
Example:
'aha' -> 'aha'
'ttaatta' -> ' ttaaatt'
'abc' -> 'a' or 'b' or 'c'
'gggaaa' -> 'gaaag' or 'aggga'
Note if there are multiple correct answers you only need to return 1 palindrome.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersA matrix is "Toepliz" if each descending diagonal from left to right is constant. Given an M x N matrix write the method isToepliz to determine if a matrix is Toepliz.
- enkadi13 July 22, 2016 in United States
Example:
Input:
67892
46789
14678
01467
Output:
True| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Arrays - 0of 0 votes
AnswersFind the index when slow and fast pointer meet in terms of n (length of list before cycle) and p ( length of loop in linked list).
- Deepak Agrawal July 16, 2016 in India
Let me meeting index is q then we should be able to find value of q when we pass n& p , there shouldn't be any extra variable.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 2 votes
AnswersGIven a list of words, and the number of rows and columns, return the number of words that can be fit into the rows and columns by stringing together each consecutive word. If the next word doesn't fit in the same line, it should move to the next line. Find an efficient solution for this. For eg.
- rucknrull July 14, 2016 in United States
List of words: { "Do", "Run" }
Number of columns: 9
Number of rows: 2
First row: "Do Run Do" (7 letters + 2 spaces fit into 9 columns)
Second row: "Run Do" (Only 2 words fit into 9 columns)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersYou have rating (0-10) of the hotels per user in this format:
- theconqueror July 07, 2016 in United States
scores = [
{'hotel_id': 1001, 'user_id': 501, 'score': 7},
{'hotel_id': 1001, 'user_id': 502, 'score': 7},
{'hotel_id': 1001, 'user_id': 503, 'score': 7},
{'hotel_id': 2001, 'user_id': 504, 'score': 10},
{'hotel_id': 3001, 'user_id': 505, 'score': 5},
{'hotel_id': 2001, 'user_id': 506, 'score': 5}
]
Any given hotel might have more than one score.
Implement a function, get_hotels(scores, min_avg_score) that returns a list of hotel ids that have average score equal to or higher than min_avg_score.
get_hotels(scores, 5) -> [1001, 2001, 3001]
get_hotels(scores, 7) -> [1001, 2001]
*/
How to solve this in C++ and Python?| Report Duplicate | Flag | PURGE
Google Software Engineer - -8of 8 votes
AnswersGiven set of characters and a dictionary find the minimum length word that contains all the word from the given word
- darklight June 19, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven an array of n integers. MaxPrefix is defined as count of elements those are greater than the element and in the right side of array wrt to the element. Write a program to give the max of MaxPrefix Ex. Input 10 -4 6 2 8 9 4 Output is 5
- darklight June 19, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven deck of cards let se 50 cards, now all are thrown on a table, after throwing some cards of them are now with face up and some are with face down, tell the probability of sum of all the face up cards is divisible by 7.
- Ajay Kumar May 29, 2016 in United States for Google Docs
Assume cards from 1 to 10, Answer should be generic so that we can get results for any number of cards, don't compare cards with playing cards, cards can be numbered from 1 to n| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven an MxN matrix, determine whether a path can be drawn through every node in the matrix such that the end node is next to the start node, and each node is only touched once.
- geekofthegeeks May 23, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a binary tree, find the largest subtree having atleast two other duplicate subtrees .
- geekofthegeeks May 22, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven the following decoder, write the encoder. (The encoder should be written to compress whenever possible):
- geekofthegeeks May 22, 2016 in United States
p14a8xkpq -> p14akkkkkkkkpq
(8xk gets decoded to kkkkkkkk. The only other requirement is that encodings be unambiguous)
Note that the String can have any possible ascii character| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 2 votes
AnswersGiven a list of pies (and the number of slices in each pie) calculate the maximum number of slices that nPeople could receive if each person got the same amount of slices and did not get slices from more than 1 pie.
- Dinkleberg May 09, 2016 in United Statespublic int getMaxSlices(List<Integer> pieSlices, int nPeople) { // return answer }
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - -15of 17 votes
AnswersIs Golang a good choice for coding interviews?
- amit April 20, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Engineer - -16of 18 votes
AnswersDoes Google/Microsoft/Amazon/Facebook allow Golang in coding interviews?
- amit April 20, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven multiple strings like "candy", "carry", "dummy", etc. These strings are stored as c3y, c3y and d3y etc. Write a function which returns a boolean if the string (like "carry" is unique in the dictionary)
- AirWind April 15, 2016 in United States
bool
isUniqueDictionaryWord(char *str)
If the strings are in a file and you load it when the program loads, how will you store it ?| Report Duplicate | Flag | PURGE
Google Software Engineer Hash Table - 1of 1 vote
AnswersGiven a string S, print the longest substring P such that P > S lexicographically.
- emb March 16, 2016 in United States
You may assume that such substring exists.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven an arbitrary tree starting at “root” where each node contains a pair of values (x, y), write a boolean function find(Node root, int x, int y) that returns true iff
- Basu March 08, 2016 in United States
* x is equal to a value "x" of any node n1 in the tree
* and y is equal to a value "y" of any node n2 in the tree
* and both n1 and n2 are at the same level in the tree
boolean find(Node root, int x, int y)
Example:
(1,120)
/ | \
/ | \
/ | \
(5,15) (30,70) (80,110)
/ | \ |
/ | \ |
/ | \ |
(35, 40) (45,50) (55, 65) (90, 100)
boo == true
find(root, 45, 100) == true
find(root, 30, 100) == false
find(root, 30, 70) == true
find(root, 70, 30) == false| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven a 2D matrix of integers, sort it such that:
- every row is sorted in ascending order from left to right
- every column is sorted in ascending order from top to down
- all items in the same row are unique
You may assume the input matrix is always valid, meaning that such a sort is always possible.
For example:
for input matrix1 3 5 3 2 4
the output could be any of the following:
valid output #1:1 3 4 2 3 5
valid output #2:
1 2 3 3 4 5
valid output #3:
1 3 4 2 3 5
One kinda trivial solution is to sort the 2D matrix column wise. For example, you can push all items into a heap and pop one after another, putting it into the matrix column after column. This would be a `O(n lg n)` time complexity where `n` is the number of items in the matrix, i.e., `n = rows*cols`. Can you design a more efficient algorithm?
- zhtt2009 February 29, 2016 in United States
Follow-up: What if all items in the same column are also required to be unique?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersImplement a Qsort similar to the build in one in C, but use an insertion sort instead
- J@sper January 30, 2016 in United States
void GoogleSort(void *ptr, int number, int SIZE, int (*functionp)(const void *, const void *)) {
}| Report Duplicate | Flag | PURGE
Google Software Engineer C - 5of 5 votes
AnswersYou are given a function bool rand_bit_p() that returns true with some unknown probability p and false with probability 1 - p.
- emb January 24, 2016 in United States
Write function rand_bit() using rand_bit_p that will return true and false with equal probability (that is, implement a fair coin, given unfair coin)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
Answers-How would you design Google Analytics (there are huge number of users and we need real-time analysis report)?
- Matt Chad January 20, 2016 in United States
-How would you detect trends?| Report Duplicate | Flag | PURGE
Google Software Engineer Large Scale Computing