Google Interview Questions
- 1of 1 vote
AnswersWrite a program to return the longest repeating
- Blahfoo April 02, 2012 in India for SRE
substring in a string. eg. for "ababab", "abab" is the longest repeating substring.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersAssume you have two sorted integer arrays. How can you find the intersect of these two arrays? (Hint by asking question: assume that these two arrays can contain duplicated integers, and they do not have the same length) What is the time complexity? Write a function to implement it as follows:
- 6bw196 January 15, 2010void intersect(int *a, int *b, int la, int lb)
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 1of 1 vote
AnswersGiven a pattern and a string - find if the string follows the same pattern Eg: Pattern : [a b b a], String : cat dog dog cat
- AlgoBaba December 02, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a list of machines where each machine has a hard disk limit and memory capacity and given a list of processes where each process requires certain hard disk space and memory, write an efficient algorithm to match processes to machines. (You may assume process to server mapping is 1:1).
- Metta September 20, 2010
(I gave a brute force solution but the interviewer wanted a more optimal solution)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite a program to find the given new program can be scheduled or not?
- veeru April 23, 2019 in United States
Already scheduled Programs: P1(10,5), P2(25,15)
New Programs: P3(18,7), P4(12, 10).
In P1(10, 5), where 10 is the starting time, 5 is the execution time.
As The P3(18, 7) starts at time 18 and executes for 7 mins i.e., the end time is 18+7 = 25. So this time slot is free and there is no overlap with already scheduled programs. Hence P3 can be scheduled.
As the P4 overlaps with P1, So P4 cannot be scheduled.| Report Duplicate | Flag | PURGE
Google Software Engineer Data Structures - 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 - 1of 1 vote
AnswersGiven an array of integer, find the number of un-ordered pairs in that array, say given {1, 3, 2}, the answer is 1 because {3, 2} is un-ordered, and for array {3, 2, 1}, the answer is 3 because {3, 2}, {3, 1}, {2, 1}.
- lsdtc1225 November 02, 2014 in United States
Obviously, this can be solved by brute force with O(n^2) running time, or permute all possible pairs then eliminate those invalid pairs.
My question is does any body have any better solution and how would you do it because it seems like a dynamic programming problem. A snippet of code would be helpful| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersImplement a sudoku solution verifier function. The rules for sudoku is this:
You have a 9 by 9 board. This board is divided into nine rows, nine columns, and nine 3x3 blocks. In a solved puzzle, every row, every column, and every 0 block has to contain each of the digits from 1 to 9. This is an example of a solved puzzle:
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 05, 2014 in United States248|395|716 571|628|349 936|741|582 ---+---+--- 682|539|174 359|174|628 714|862|953 ---+---+--- 863|417|295 195|286|437 427|953|861
| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersGiven a set of non overlapping intervals
- Dev March 12, 2012 in United States
Example 1 :(1,4) (6,10) (14, 19) and another interval (13, 17) merge them as (1,4) (6,10) (13,19)
Example 2: (1,5) (6, 15) (20, 21) (23, 26) (27, 30) (35, 40)
New interval (14, 33)
Output should be
(1,5) (6, 33) (35, 40)
This is because the new interval overlaps with (6, 15) (20, 21) (23, 26) (27, 30)| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 1of 1 vote
AnswersWrite a function to find the nearest link on a webpage given the mouse x,y coordinates.
- bjh August 14, 2010
If your algorithm just iterates through all the links, give an idea of how to make it faster.| Report Duplicate | Flag | PURGE
Google Front-end Software Engineer Algorithm - 1of 1 vote
AnswersWrite an algorithm to check the winning condition in a tic-tac toe game for a NXN grid ? (Hint . can be done in O(1) need int ROW[N]; int COL[N]; int diagonal; int anti-diagonal )
- G January 29, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Brain Teasers - 1of 1 vote
AnswersGiven 2 words, return true if second word has a substring that is also an anagram of word 1.
- anonymous October 07, 2017 in United States
LGE , GOOGLE- True
GEO, GOOGLE - False| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersGiven a BST, maximum and minimum value, find the sum of nodes with values between the above range
- bicepjai September 25, 2012 in United States for Google Engineering| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Algorithm - 1of 1 vote
AnswersFind median of two sorted arrays.
- binu May 28, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Arrays - 1of 1 vote
AnswersWrite a function that takes a magic number and a list of numbers. It returns true if it can insert add or subtract operations in the list of numbers to get the magic number. Otherwise, it returns false.
- Pedro July 11, 2018 in United States
For example:
f(10, [1,2]) = false. There's no way to add or subtract 1 and 2 to get 10.
f(2, [1,2,3,4]) = true. 1 + 2 + 3 - 4 = 2.
f(0, []) = true
f(1, []) = false
f(1, [1]) = true
f(0, [1]) = false| Report Duplicate | Flag | PURGE
Google Software Developer - 1of 1 vote
AnswersGiven an input BST, find the minimum value difference between any two nodes in the tree.
- a.asudeh February 18, 2016 in United States
e.g:
....10
5 16
........12 20
answer: 2 (it happens between nodes 12 and 10)
describe the test cases you would use here?| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - 1of 1 vote
Answers
- Phoenix November 22, 2014 in United KingdomThere are multiple rooms in a floor. There are one or more fire exits. Each door can be designed with an option of pull or push. For fire safety, a door should be designed so as to open (push) towards the fire exit. Design a data structure to represent the floor and door design. A person could start from any room and moves towards fire exit. Write an algorithm to check if all the doors are designed to be pushed towards fire exit.
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersTraveler wants to travel from city “A” to city “D”.
There is a path from city “A” to city “D”.
Path consists of steps, i.e. travel from city “A” to city “B”.
Path is encoded as sequence of steps.
Sequence is in incorrect order.
Your task is to restore order of steps in the path.
Input (unordered sequence):
C -> D
A -> B
B -> C
Output (Correctly ordered list which represents path):
A, B, C, D
Implement following API:
- abc June 20, 2014 in Indiaclass Step { String start; String finish; }; class Node { String value; Node next; } List<String> findPath(List<Step> steps) { }
| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 1of 1 vote
AnswersFind numbers which are palindromic in both their decimal and octal representations
- geekofthegeeks November 01, 2013 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven N integer array, I want to fill the array with product of all numbers except the number in that cell.
- X July 04, 2013 in United States
What is the complexity ? Do not worry about 0's or negative numbers in the array.
[Interviewer was more interested in how the multiplication/division gets effected as number of bits required to represent the intermediate products increases.]| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 1of 1 vote
AnswersConvert a BST to max heap without using extra memory and in as optimum time as possible
- Anonymous October 17, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 1of 1 vote
Answersgiven 2 strings A and B. generate all possible solutions when B is merged in A.
- JerryGoyal May 22, 2016 in India
Ex: A = "hey"
B: "sam"
then solutions are :
heysam,hseaym,hesaym,sahemy etc.
notice that order should be the same for both of strings while merging.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 1of 1 vote
AnswersGiven 2 large number A and B, create a new number C using the digits from A which needs to be grater than B.
- hm August 21, 2015 in United States
e.g. A = 5281, B = 7443
C = 8125.| Report Duplicate | Flag | PURGE
Google Software Engineer Math & Computation - 1of 1 vote
AnswersGiven a start position and an target position on the grid. You can move up,down,left,right from one node to another adjacent one on the grid. However there are some walls on the grid that you cannot pass. Now find the shortest path from the start to the target.
- fmars September 07, 2014 in United States
(This is easy done by BFS)
Extend. If you can remove three walls, then what is the shortest path from start to the target. (I have no ideal except for enumerate all the possibility of three walls. It must be the silly solution.) Does anyone have any idea?| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 1of 1 vote
AnswersHaving an infinite stream of numbers write a function to take an element with equal probability for each.
- chandeepsingh85 September 26, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Probability - 1of 1 vote
AnswersSuppose we use binary search tree to implement set, design an algorithm that we can get an random element from the set, while maintain all the other set operations have same complexities.
- ywdong8809 March 07, 2013 in China| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
Answersexplain and write algorithm that implements and infinite binary counter, where add() takes O(1) time complexity
- adam2008 February 21, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersWrite a recursive function to convert Binary Code of a number into its equivalent Gray's code and the other way round.
- hello world February 27, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Coding - 1of 1 vote
AnswersGiven 3 input strings S1, S2, S3 for example take s1 = "hard" s2 = "work", s3 = "success"
- Anonymous May 29, 2011
assign numeric values (0-9) to each of the characters in these strings such that equation s1 + s2 = s3 holds true. Constraints are that all occurrence of a letter should be assigned the same digit. Return -1 if not possible. I told the algo using backtracking but he required in polynomial time for which I had no idea.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer