Google Interview Questions
- 3of 5 votes
AnswersLook at the sequence below:
- amirtar May 05, 2015 in United States
1, 11, 21, 1211, 111221, 312211, ...
Write a code that receives n and returns the nth element of the sequence. If it gets 4 as input of the method it should return 1211.| Report Duplicate | Flag | PURGE
Google Software Engineer - 3of 5 votes
AnswersThere are several people sitting in the cinema, some of them are couples, some are not, they decide to swap their seats so that the couples can seat together, please calculate the minimal swap numbers.
- xblwyc October 07, 2015 in United States
1. the swap can happen between any two position.
2. E.g. AABCCDB -> AADCCBB, ans is 1| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 5 votes
Answersgiven a dictionary of wrods,find the pair of word with following property:
- haozyname November 19, 2013 in china
1,the two word don't have same letter.
2,the multiple of the two word's length is maximum.
i give a simple O(n*n*k)(k is the average length of word) method.but i think there will be better one .| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 5 votes
AnswersPhone screen Q: String encoding and decoding: Design a method that converts a list of strings into a single string which can be later converted back to the list.
- aonecoding January 15, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Programming Skills - 3of 5 votes
AnswersYou're given a machine (Let's say a sprinkler). The machine is controlled with a software component that has UI. The user can set different parameters in the UI. for example : 'speed' : 120 'pressure' : 30
- GeorgyBoy December 30, 2013 in Israel
Change the system so it will accept an arithmetical expression in the UI. The expression can contain constants, parameters (e.g 'speed') and operators.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Object Oriented Design - 3of 5 votes
AnswersQ: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.
- aonecoding January 15, 2017 in United States/usr /local profile.jpg /bin config.txt dest.png /rbin image.gif /sys /re /tmp pic.jpg ..... ……
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
- IKnowThings January 28, 2017 in United States
eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"
I was thinking of the following approach,
Build a Trie for all words in the Dict - O( n * k) where k is the longest string in the dict
For each character c, in S check if there is a word in Trie that starts with it and has the letters that appear in S after c. We can short circuit based on remaining characters and the length of longest string found so far.
This should take O( N * k) where N is length of S.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven a circular single linked list.Write a program that deletes every kth node until only one node is left.
- Aashish August 01, 2012 in India
After kth node is deleted, start the procedure from (k+1)th node.
e.g.list is 1->2->3->4->5->1
k=3
1. You are at 1, delete 3.
List is: 1->2->4->5->1
2. You are at 4, delete 1
List is: 2->4->5->2
3. You are at 2,delete 5
List is: 2->4->2
4. You are at 2, delete 2
List is: 4
Return 4.
How efficient you can do it?| Report Duplicate | Flag | PURGE
Amazon Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a binary search tree (BST), write a mehtod that will convert this BST into a doubly linked list that is sorted (ascending or descending order) and returns the first element in this list. You may assume you are given following Node class:
public class Node { public Node left, right; public String val; }
Example: The following BST
- autoboli January 06, 2015 in United States
G
/ \
A T
can be converted into a list
A = G = T
Do it in place! Hnce the memory complexity of your algorithm shoul be O(1).| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersYou are given a string S. Each character of S is either ‘a’, or ‘b’. You wish to reverse exactly one sub-string of S such that the new string is lexicographically smaller than all the other strings that you can get by reversing exactly one sub-string.
- Rahul Sharma October 09, 2014 in India
For example, given ‘abab’, you may choose to reverse the substring ‘ab’ that starts from index 2 (0-based). This gives you the string ‘abba’. But, if you choose the reverse the substring ‘ba’ starting from index 1, you will get ‘aabb’. There is no way of getting a smaller string, hence reversing the substring in the range [1, 2] is optimal.
Input:
First line contains a number T, the number of test cases.
Each test case contains a single string S. The characters of the string will be from the set { a, b }.
Output:
For each test case, print two numbers separated by comma; for example “x,y” (without the quotes and without any additional whitespace). “x,y” describe the starting index (0-based) and ending index respectively of the substring that must be reversed in order to acheive the smallest lexicographical string. If there are multiple possible answers, print the one with the smallest ‘x’. If there are still multiple answers possible, print the one with the smallest ‘y’.
Constraints:
1 ? T ? 100
1 ? length of S ? 1000
Sample Input:
5
abab
abba
bbaa
aaaa
babaabba
Sample Output:
1,2
1,3
0,3
0,0
0,4| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 3of 3 votes
AnswersYou are given a dictionary, in the form of a file that contains one word per line. E.g.,
- audi March 14, 2013 in United States
abacus
deltoid
gaff
giraffe
microphone
reef
qar
You are also given a collection of letters. E.g., {a, e, f, f, g, i, r, q}.
The task is to find the longest word in the dictionary that can be spelled with the collection of
letters. For example, the correct answer for the example values above is “giraffe”. (Note that
“reef” is not a possible answer, because the set of letters contains only one “e”.)| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersWrite a program to determine whether n/2 distintinctve pairs can be formed from given n integers where n is even and each pair's sum is divisible by given k. Numbers cannot be repeated in the pairs, that means only you can form total n/2 pairs.
- topjobsncr October 09, 2012 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b's and can only have up to two consecutive 'c's
- djway August 10, 2016 in United States for None
Example:
findStrings(3) returns 19
since the possible combinations are: aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb
and the invalid combinations are:
abb,bab,bba,bbb,bbc,bcb,cbb,ccc| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
Answerssuppose a string is consists of a, b, and c
- codingfunnyguy November 25, 2013 in United States
Now given a integer N, output the amount of all possible strings of length N that don't of have consecutive a,b,c.
e.g. given N=5, string bacca is invalid since the first 3 letters have consecutive a,b,c. and bbbbb is valid.| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersGiven a string pattern of 0s, 1s, and ?s (wildcards), generate all 0-1 strings that match this pattern.
- lsecrease June 25, 2013 in United States
e.g. 1?00?101 -> [10000101, 10001101, 11000101, 11001101].
You can generate the strings in any order that suits you.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
AnswersGiven an array A[], find (i, j) such that A[i] < A[j] and (j - i) is maximum.
- lyra_vega November 09, 2011 in -| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersA binary search tree is given. Find the ceiling value present in the BST of a given key.
eg-8 3 12 2 6 10 15 4
key - 13 => 15
- LAP June 24, 2013 in United States
key - 4 =>6
key - 8 =>10| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 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 - 3of 3 votes
AnswersCount smaller elements on right side
- NaiveCoder February 27, 2012 in India
eg : [4,12,5,6,1,34,3,2]
o/p [3,5,3,3,0,2,1,0]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
Answers# take an array and print non over lapping in order pairs. example:
- thegeek21 June 05, 2016 in United States# [1,2,3,4] => input # output below is in order combination # (1234) # (1)(234) # (1)(23)(4) # (1)(2)(34) # (12)(34) # (12)(3)(4) # (123)(4) # (1)(2)(3)(4)
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersFind if a given binary tree has duplicate sub trees or not.
- neer.1304 December 25, 2015 in United States
(Two leaf nodes of a parent do not count as subtree)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersSuppose we are given an array A[1 .. n] with the special property that A[1] ≥ A[2] and
- Anonymous March 24, 2011
A[n − 1] ≤ A[n]. We say that an element A[x] is a local minimum if it is less than or equal
to both its neighbors, or more formally, if A[x − 1] ≥ A[x] and A[x] ≤ A[x + 1]. For example,
there are five local minima in the following array:
9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9
We can obviously find a local minimum in O(n) time by scanning through the array. Describe
and analyze an algorithm that finds a local minimum in O(log n) time.| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersGiven n light bulbs, write two methods.
- cup August 19, 2015 in United States
isOn(i) to determine if a light bulb is on
toggle(start, end) to toggle all the light bulbs in the range
One caveat, write toggle so that it is less than O(n) complexity| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
AnswersFind popular item in sorted array of natural numbers.
- dreamchaser1984 February 25, 2015 in United States
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Algorithm - 3of 3 votes
AnswersCode for computing a^b and optimize it.
- AlgoAlgae April 25, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
AnswersYou have a lists with integers. Find all the pairs of numbers that sum less than or equal to to a particular number k. The list contains minimum 5 Million number.
- hirajhil February 05, 2014 in United States
(I provided a n^2logn solution but they may be looking forward to having a better answer).| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 3of 3 votes
AnswersQuestion: You are given a CSV file with 3 columns -- all integers:
- nicolasvin1982 December 05, 2013 in United States
id,parent,weight
10,30,1
30,0,10
20,30,2
50,40,3
40,30,4
0 is the assumed root node with weight 0
which describes a tree-like structure -- each line is a node, 'parent' refers to 'id' of another node.
Print out, for each node, the total weight of a subtree below this node (by convention, the weight of a subtree for node X includes the own weight of X).
You may assume that the input comes pre-parsed as a sequence of Node objects
(substitute the appropriate syntax for java/python/c++):
Node {
int id;
int parent;
int weight;
// ... you can add other fields right here, if necessary
}
implement the following:
public void printSubTreeWeight(List<Node> nodes) {
....}| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer - 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 - 3of 3 votes
AnswersI had two interviews with Google
- sameer November 17, 2015 in India
first) one with US person...he asked decent question with lot of hints...experience : positive
and
then second) interview with person from India...I prepared for one month but he asked me very tough one graph/tree question...never gave single hint and based on that one question he judged my seven years of experience in Software Development (I never experienced what they say...Google looks for approach and not final answer)
Q.1 : Arrange array in wave form A1 > a2 < a3 > a4 ...
O(n.log-n) (Note: its not A1 >= A2)
Q.2 : Given Graph with Tree characteristics, find one node as root so that height of tree will be minimum| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm