Google Interview Questions
- 9of 9 votes
AnswersGiven a timer time() with nanosecond accuracy and given the interface
interface RealTimeCounter: void increment() int getCountInLastSecond() int getCountInLastMinute() int getCountInLastHour() int getCountInLastDay()
implement the interface. The getCountInLastX functions should return the number of times increment was called in the last X.
- peachandpotato January 29, 2014 in United States
(My note: an ideal solution will have space usage which does *not* grow unbounded with the number of calls to increment(). It seems to me that a solution involving a round-robin database could be good, but it sacrifices accuracy.)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 1 vote
Answersgiven a double linked list and an array of nodes in that dll,output number of clusters. example: dll: n1 n2 n3 n4 n5; array: n1 n4 n5; output 2( (n1) (n4 n5))
- laurentr January 29, 2014 in United States| Report Duplicate | Flag | PURGE
Google - 0of 2 votes
Answersgiven string of chars,find way to compress consecutive char with no ambiguity. example:daaad
- laurentr January 29, 2014 in United States
to d4*ad; 5eeeecd to 5*14*ecd| Report Duplicate | Flag | PURGE
Google - 0of 2 votes
AnswersWrite a routine that does secret santa in O(N) time. I don't really understand what it means by 'does secret santa' actually.
- Guy January 29, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGenerate MAX_INT (Max signed int value) using bitwise operators. Should work in 32 and 64 bit processors
- bartcois January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Bit Manipulation - 0of 0 votes
AnswersYou have a plain with lots of rectangles on it, find out how many of them intersect
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 2of 2 votes
AnswersSort a list of numbers in which each number is at a distance k from its actual position
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersStore a set of sudden-death tournament results in a compact format (eg. a bit array) and a set of predicted match results (also in a bit array). Score the predictions, giving one point per correctly guessed match, without unpacking the bit array into a more convenient format (ie. you have to traverse the tree in-place).
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersImplement a simple regex parser which, given a string and a pattern, returns a boolean indicating whether the input matches the pattern. By simple, we mean that the regex can only contain special character: * (star), . (dot), + (plus). The star means what you'd expect, that there will be zero or more of previous character in that place in the pattern. The dot means any character for that position. The plus means one or more of previous character in that place in the pattern.
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answers1. find all the combinations of a string in lowercase and uppercase. For example, string "ab" -> "ab", "Ab", "aB", "AB". So, you will have 2^n (n = number of chars in the string) output strings. The goal is for you to test each of these string and see if it match a hidden string.
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answerint[] first = {3}; // size 1
- Madan January 28, 2014 in United States
int[] second = new int[3]; // size 3
second[0] = 2;
second[1] = 4; //2,4
Second array has enough space to hold all elements of first and second array, where both the arrays are merged. Now write code to have first array into second.
The following Cracking the coding interview code doesn't work.
public static int[] merge2(int[] first, int[] second){
int lastA = first.length-1; //0
int lastB = second.length-1; //2
int indexMerge = (lastA + lastB);
while(lastA >= 0 && lastB >= 0){
if(first[lastA] > second[lastB]){
second[indexMerge] = first[lastA];
indexMerge--;
lastA--;
}else{
second[indexMerge] = second[lastB];
indexMerge--;
lastB--;
}
}
while(lastA >= 0){
second[indexMerge] = first[lastA];
indexMerge--;
lastA--;
}
return second;
}| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersYou are given a 2-Dimensional array with M rows and N columns. You are initially positioned at (0,0) which is the top-left cell in the array. You are allowed to move either right or downwards. The array is filled with 1's and 0's. A 1 indicates that you can move through that cell, a 0 indicates that you cannot move through the cell. Given a function numberOfPaths which takes in the above 2-D array, return the number of paths from the top-left cell to the bottom-right cell (i.e. (0,0) to (M-1,N-1)).
- Madan January 27, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 4 votes
AnswersGiven a kernal code in "0"th machine. How soon you can replicate the kernal across N machines. Now if the machines has upload and download bandwidth constraints, how can you impove the copy time.
- Guy January 24, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Operating System - -1of 1 vote
AnswersConsider in Java arraylist we have mix of int, double, float, string, etc. How will you find if a given index of arraylist have string. No need to worry about generics and type safe.
- Madan January 23, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 3of 3 votes
AnswersConsider the following array {1,2,3,4,5,2,5,4,4};
In the above array, index 4 could be considered as breaking point where summation of 0 to 4 in the array is equal to summation of 5 to end of array. We need to find the breaking point for the given array. I solved this. But follow up was for this array{1,0,-1,-1,1};
. Mathematically the later array's breaking point is 2.
- Madan January 23, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 3 votes
AnswersHow would you synchronize a linked list across multiple computers. If nodes are added/removed to a linked list on one computer, all others must reflect this change. Concurrancy must be accounted for. (java)
- Guy January 22, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - -4of 6 votes
AnswersBag-of-words model. Write the process of search based on inverted index. The follow up is given some attributes(an array), how to filter the search result.
- Guy January 22, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 3 votes
AnswersFind the shortest path in a maze (from origin to destination). I believe we are supposed to use Dijkstra or BFS. But what I am confused with is that Dijkstra computes the shortest path based on the distance of each edge. But a maze doesn't have weighted edges, and its shortest path should be 'minimum number of cells'. How can we make use of Dijkstra, or BFS?
- Guy January 21, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 2 votes
AnswersThe final question was just how to write a connection pool (i.e, a class that returns connections to the user, and if the user is done, returns them back to the pool)
- Guy January 19, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - -1of 1 vote
AnswersDifference between cloning a directed graph vs undirected graph. There are lots of tutorials on how to clone a directed graph online, such as leetcode. But what if it's undirected graph? It appears to me that it would be pretty much the same? For example,
public class Node() { public int data; public ArrayList<Node> adjacent; }
For example, A can have a neighbor called B. Therefore, we may traverse from A to B. For undirected graph, does it imply that B can always traverse back to A? Even if it does, if we use a hashtable to keep track of which node has been copied and processed in the queue, then the logic for cloning a directed graph should be the same as for a undirected graph, right?
- Guy January 19, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 3 votes
AnswersDoes a given file name match a single-star pattern? (can't use regex I assume)
- Guy January 18, 2014 in United States
index.html matches *.html
foo.txt does not match *.html
matches(“index.html”, “*html”) returns true
matches(“foo.txt”, “*html”) returns false
matches(“cat”, “c*t”) returns true| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 6 votes
AnswersGiven a set of intervals (time in seconds) find the set of intervals that overlap. Follow-up: what if we were to find the interval with maximum overlap.
- Guy January 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 8 votes
AnswersGiven a set top box:
- Guy January 18, 2014 in United States
a, b, c, d, e,
f, g, h, i, j,
k, l, m, n, o
p, q, r, s, t
u, v, w, x, y
z
Write code to give the character sequence given a word, For example, if the word is "CON", the function will print this:
Right//now we're at B
Right//now we're at C
OK//to select C
Down
DOwn
Right
Right
OK//to select O
Left//now at N
OK//to select N
note: Be careful when you're at Z. if you go to the right, you will get stuck.
Afterwards, the interviewer adds a space to the right of 'Z' to test the code.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 2 votes
AnswersHow do you design a Maze and what kind of data structures you use for Maze. In addition, write a method to print the shorted path from start to end point.
- Guy January 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 4 votes
AnswersDesign Short URL. (I am not sure what it even means)
- Guy January 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - -1of 1 vote
AnswersGiven two Binary trees. these trees "may" have right and left branches swapped. Now compare it.
- Guy January 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - -1of 1 vote
AnswersGiven a undirected graph, clone it. Now if the undirected graph has the neighbors with the nodes as same data - how do you make sure you create the exact same branches and also how do you make sure you don't run into loops for the exact node. He gave a empty directed graph and asked me write code after that.
- Guy January 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 1 vote
AnswersThere are 10,000 balls and may be 500 different colors of ball
- zarron January 17, 2014 in United States
Example: There are:
4 - red ball
5900 - Blue ball
3700 - Green ball
396 - mintcream ball
Or there may be 10,000 red balls.
Or all balls are has same range, i.e. 500 red, 500 blue, etc.
We don’t know the range of any ball and number of color balls, but the minimum is 1 color and maximum is 500 colors, and we have auxiliary array of size 500. how to arrange all same color ball together in minimum passes over balls? is it possible to do in less than two passes ??| Report Duplicate | Flag | PURGE
Google Computer Scientist Algorithm - -5of 7 votes
AnswersThere's a matrix. Each element in the matirx is a bit (0 or 1). Write a method to reverse this matrix. The matrix is stored in a one dimensional char array. The length of each row is given.
- Guy January 17, 2014 in United States
How do you improve your solution when handling large amount of data?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow do you add two numbers that are larger/longer than Integer datatype? I said I would use BigInteger , then he asked how will you add if the number is larger than BigInteger?
- Madan January 16, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1