Google Interview Questions
- 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 - 9of 9 votes
AnswersGiven an array of integers, sort the array into a wave like array, namely
- Zen April 22, 2014 in United States
a1 >= a2 <= a3 >= a4 <= a5.....| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 7of 7 votes
AnswersDetermine minimum sequence of adjacent values in the input parameter array that is greater than input parameter sum.
- bootcat April 20, 2014 in United States
Eg
Array 2,1,1,4,3,6. and Sum is 8
Answer is 2, because 3,6 is minimum sequence greater than 8.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 6of 6 votes
AnswersThe input is a sequence x1,x2,...,xn of integers in an arbitrary order, and another sequence
- Coder April 17, 2014 in United States
a1,a2,..,an of distinct integers from 1 to n (namely a1,a2,...,an is a permutation of
1, 2,..., n). Both sequences are given as arrays. Design an 0(n logn) algorithm to order
the first sequence according to the order imposed by the permutation. In other words, for
each i, Xi should appear in the position given in ai. For example, if x = 17, 5, 1,9, and a =
3, 2, 4, 1, then the outcome should be x = 9, 5, 17, 1. The algorithm should be in-place, so
you cannot use an additional array.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 4of 4 votes
AnswersConsider the array 3 5 7 6 3.
- Gaile April 10, 2014 in United States
Return the pair of indices that forms the slice where the difference between the maximum and minimum in the slice <= 2.
Output:
(0,0) (1,1) (2,2) (3,3) (4,4) (5,5)
(0,1) (1,2) (1,3) (2,3)
Example slices: 3 5, 5 7, 1 3, 2 3.
The following link
https://codility.com/media/train/solution-count-bounded-slices.pdf
has O ( n ) solution. But couldn't understand the O (n ) solution. Could some one explain with an example?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 8of 10 votes
AnswersFind next higher number with same digits.
- codechamp April 02, 2014 in United States for Knowledge Graph
Example 1 : if num = 25468, o/p = 25486
Example 2 : if num = 21765, o/p = 25167
Example 3 : If num = 54321, o/p = 54321 (cause it's not possible to gen a higher num than tiz with given digits ).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Ideas - 21of 23 votes
AnswersGiven a undirected graph with corresponding edges. Find the number of possible triangles?
- redsanket March 25, 2014 in United States
Example:
0 1
2 1
0 2
4 1
Answer:
1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 19of 19 votes
AnswersGiven two strings a and b, find whether any anagram of string a is a sub-string of string b. For eg:
- Masterchief117 March 23, 2014 in United States
if a = xyz and b = afdgzyxksldfm then the program should return true.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer String Manipulation - -6of 8 votes
Answersgiven a board with black (1) and white (0), black are all connected. find the min rectangle that contains all black.
- Obiwana March 21, 2014 in United States
example:
0 0 0 0 0
0 1 1 1 0
0 1 1 0 0
0 1 0 0 0
0 0 0 0 0
the min rectangle contains all black (1) is the rectangle from (1,1) - (3, 3)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - -3of 11 votes
AnswersGiven an array of Integers, and a range (low, high), find all continuous subsequences in the array which have sum in the range. Is there a solution better than O(n^2)?
- Obiwana March 21, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - -7of 7 votes
AnswersGiven k integers i_0, i_1, i_2, i_3,...i_k, find all possible expressions which uses + - * / and () to generate a result equals to target X.
- Obiwana March 21, 2014 in United States
() has the highest priority.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - -2of 6 votes
AnswersGiven a dictionary of words, and a set of characters, judge if all the characters can form the words from the dictionary, without any characters left.
- DoZerg March 20, 2014 in United States
For example, given the dictionary {hello, world, is, my, first, program},
if the characters set is "iiifrssst", you should return 'true' because you can form {is, is, first} from the set;
if the character set is "eiifrsst", you should return 'false' because you cannot use all the characters from the set.
P.S. there may be tens of thousands of words in the dictionary, and the chars set length could be up to hundreds, so I really need some efficient algorithm.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -3of 9 votes
AnswersMany sticks with length, every time combine two, the cost is the sum of two sticks' length. Finally, it will become a stick, what's the minimum cost?
- Vincent March 17, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 4 votes
AnswersGiven a dictionary, and a list of letters ( or consider as a string), find the longest word that only uses letters from the string. [I didn't meet this question, what's the best solution?]
- Obiwana March 11, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersInsert a element in a sorted circular linked list
- zealswap March 11, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersFor a given node in binary search tree find a next largest number in search tree.
- zealswap March 11, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 2 votes
AnswersWrite a function return an integer that satisfies the following conditions:
- Obiwana March 10, 2014 in United States
1) positive integer
2) no repeated digits, eg., 123 (valid), 122 (invalid)
3) incremental digit sequence, eg., 1234 (valid) 1243(invalid)
4) the returned integer MUST be the smallest one that greater than the input. eg., input=987, return=1023
function signature could be like this:
String nextInteger(String input)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 14of 14 votes
AnswersGiven a 2-D matrix represents the room, obstacle and guard like the following (0 is room, B->obstacle, G-> Guard):
- Obiwana March 10, 2014 in United States
0 0 0
B G G
B 0 0
calculate the steps from a room to nearest Guard and set the matrix, like this
2 1 1
B G G
B 1 1
Write the algorithm, with optimal solution.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 3 votes
AnswersYou are given a string which has numbers and letters. Numbers occupy all odd positions and letters even positions. You need to transform this string such that all letters move to front of array, and all numbers at the end.
- andy March 09, 2014 in United States for Google Search
The relative order of the letters and numbers needs to be preserved
I need to do this in O(n) time and O(1) space.
eg: a1b2c3d4 -> abcd1234 , x3y4z6 -> xyz346
Please don't submit your answers if it is not fulfilling the time-space complexity requirements.| Report Duplicate | Flag | PURGE
Google SDE1 - -4of 8 votes
AnswersWhat would happen if you have only one server for a web cache (a web browser cache whose key is url and value is the loaded content of the webpage) but huge numbers of clients? And how would you solve it? Assume the cache is implemented with a hashmap and a linkedlist.
- Guy March 06, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - -1of 1 vote
AnswersConsider a scenario where you open a file with your favorite editor (emacs on Linux or Microsoft Word on Windows).
- KevinK March 05, 2014 in United States
You notice that the application has a performance hit due to a recent fix made to the Editor application.
What will your testing Matrix look like that will convey the information that the performance of the application has degraded (or improved after bug fixes and re-design)?
In other words, the interviewer was saying that, if we had a graph showing values obtained from tests run over time for:
File I/O, hardware configuration, software configuration, graphics system, GPU, CPU etc.
then at the End Of the Day, looking at the reports, which parameters will instantly tell you that the performance has definitely increased?
(Also in other words he was asking the Matrix that will portray those parameters).| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Testing - 11of 11 votes
AnswersGive a N*N matrix, print it out diagonally.
- Mem February 28, 2014 in United States
Follow up, if it is a M*N matrix, how to print it out.
Example:
1 2 3
4 5 6
7 8 9
print:
1
2 4
3 5 7
6 8
9
This is the question in the phone interview.
Please share more questions.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - -6of 6 votes
AnswersModify the following code to add a row number for each line is printed
public class Test { public static void main(String [] args){ printParenthesis(3); } public static void printParenthesis(int n){ char buffer[] = new char[n*2]; printP(buffer,0,n,0,0); } public static void printP(char buffer[], int index, int n, int open, int close){ if(close == n){ System.out.println(new String(buffer)); }else{ if(open > close){ buffer[index] = ']'; printP(buffer, index+1, n, open, close+1); } if(open < n ){ buffer[index] = '['; printP(buffer,index+1,n,open+1,close); } } } }
Expected Output:
1.[][][] 2.[][[]] 3.[[]][] 4.[[][]] 5.[[[]]]
What changes needs to be done to accomplish the output expected?
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 25, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -3of 7 votes
AnswersFind a shortest path in a N*N matrix maze from (0,0) to (N,N), assume 1 is passable, 0 is not, 3 is destination, use memorization to cache the result. Here is my code. I am not sure if I am caching it right.
- Guy February 24, 2014 in United Statespublic static class MazeResult { public boolean solved; public List<String> res = new ArrayList<String>(); public int steps = Integer.MAX_VALUE; public MazeResult(boolean isSolved) { solved = isSolved; } } static Map<String, MazeResult> cache = new HashMap<String, MazeResult>(); static MazeResult solveMaze(int[][] m, int r, int c, List<String> path, HashSet<String> visited) { if (r < 0 || r >= m.length || c < 0 || c >= m[0].length) return new MazeResult(false); String cell = r + "" + c + ""; if (m[r][c]==0 || visited.contains(cell)) return new MazeResult(false); if (m[r][c] == 3) { MazeResult ret = new MazeResult(true); ret.res = new ArrayList<String>(path); ret.res.add(cell); ret.steps = path.size() + 1; return ret; } if (cache.containsKey(cell)) return cache.get(cell); path.add(cell); visited.add(cell); MazeResult ret = new MazeResult(false), temp = new MazeResult(false); temp = solveMaze(m, r, c+1, path, visited); compareResult(temp, ret); temp = solveMaze(m, r, c-1, path, visited); compareResult(temp, ret); temp = solveMaze(m, r+1, c, path, visited); compareResult(temp, ret); temp = solveMaze(m, r-1, c, path, visited); compareResult(temp, ret); path.remove(path.size()-1); visited.remove(cell); cache.put(cell, ret); return ret; } private static void compareResult(MazeResult temp, MazeResult ret) { if (temp.solved) { if (temp.steps < ret.steps) { ret.res = temp.res; ret.steps = temp.steps; } ret.solved = true; } }
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -3of 9 votes
AnswersFlatten an iterator of iterators in Java. If the input is [ [1,2], [3,[4,5]], 6], it should return [1,2,3,4,5,6]. Implement hasNext() and next().
- Guy February 24, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 3 votes
AnswersGiven a set of intervals, find the interval which has the maximum number of intersections (not the length of a particular intersection). So if input (1,6) (2,3) (4,11), (1,6) should be returned. Some suggest to use Interval Tree to get this done in O(logn), but I did not understand how to construct and use the Interval Tree after reading its wiki page. Is there any other way to do it? If Interval tree is the only option, please educate me how to construct/use one. Thanks.
- Guy February 23, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 1 vote
AnswersWhat happens when you type a link in any browser and click GO button? List all steps.
- KevinK February 21, 2014 in United States
What should be the issue if the browser app build that i have today is 1 second 250 milliseconds slower than yesterday's build? ASSUME: WiFi is perfect, loading 10 webpages from a controlled server - hence there are no infrastructure or server side delays causing this.
What would you think might be the issue? How would you debug?| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Debugging - 0of 0 votes
AnswersYou are given a string FOOFIGHTERS. You have to come up with an algorithm that will compress this string.
- KevinK February 21, 2014 in United States
You also have to make sure that you are not using extra memory. For example: FOOFIGHTERS will be compressed as FO2FIGHTERS. You should not use another array or bitfield to keep a frequency count for the individual letters.| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Algorithm - 0of 2 votes
AnswersFind the k-th Smallest Element in Two Sorted Arrays. I followed the algorithm from this post, http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
But it does not handle the case where there are duplicates? Does anyone know how to do that? Also, in Java, how should we reduce the size of the arrays? I used the code below, but did not work.
- Guy February 20, 2014 in United Statespublic static int kthSmallest2(int[] a, int[] b, int k, int a_left, int a_right , int b_left, int b_right) { if (a_left==a_right) return b[k-1]; else if (b_left==b_right) return a[k-1]; int m = a_right-a_left, n=b_right-b_left; int i = (int)((double)m / (m+n) * (k-1)); // i can be any number // make sure i + j = k - 1 // int i = (a_left+a_right)/2 + k/2; // i can be any number int j = k - 1 - i; int bj_1 = 0, ai_1 = 0; if (i==0) { ai_1 = Integer.MIN_VALUE; } // in case i = 0, outOfBound else { ai_1 = a[i-1]; } if (j==0) { bj_1 = Integer.MIN_VALUE; } // in case j = 0, outOfBound else { bj_1 = b[j-1]; } if (bj_1 < a[i] && a[i] < b[j]) // kth smallest found, b[j-1] < a[i] < b[j] return a[i]; if (ai_1 < b[j] && b[j] < a[i]) // kth smallest found, a[i-1] < b[j] < a[i] return b[j]; if ( a[i] < b[j] ) // if true, exclude a's lower bound (if 2 arrays merged, a's lower bound must // reside before kth smallest, so also update k. // also exclude b's upper bound, since they are all greater than kth element. return kthSmallest2(a, b, k, i+1, a.length-1, 0,j-1); else return kthSmallest2(a, b, k, 0, i-1, j+1, b.length-1); }
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 4 votes
AnswersFinding a pair of elements from two sorted lists(or array) for which the sum of the elements is a certain value. Anyway solution that can do better than O(a.length + b.length)?
- Guy February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm