## Google Interview Questions

- 0of 0 votes
The input is a sequence x1,x2,...,xn of integers in an arbitrary order, and another sequence

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.

- 2of 2 votes
Consider the array 3 5 7 6 3.

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?

- 2of 4 votes
Find next higher number with same digits.

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 ).

- 10of 10 votes
Given a undirected graph with corresponding edges. Find the number of possible triangles?

Example:

0 1

2 1

0 2

4 1

Answer:

1

- 4of 4 votes
Given two strings a and b, find whether any anagram of string a is a sub-string of string b. For eg:

if a = xyz and b = afdgzyxksldfm then the program should return true.

- -4of 6 votes
given a board with black (1) and white (0), black are all connected. find the min rectangle that contains all black.

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)

- -2of 6 votes
Given 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)?

- -4of 4 votes
Given 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.

() has the highest priority.

- -3of 5 votes
Given 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.

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.

- -1of 7 votes
Many 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?

- 0of 4 votes
Consider N coins aligned in a row. Each coin is showing either heads or tails. The adjacency of these coins is the number of adjacent pairs of coins showing the same face.

You are given an implementation of a function:

function solution(A);

that, given a non-empty zero-indexed array A consisting of N integers representing the coins, returns the maximum possible adjacency that can be obtained by reversing exactly one coin (that is, one of the coins must be reversed). Consecutive elements of array A represent consecutive coins in the row. Array A contains only 0s and/or 1s:

0 represents a coin with heads facing up;

1 represents a coin with tails facing up.

For example, given array A consisting of six numbers, such that:

A[0] = 1

A[1] = 1

A[2] = 0

A[3] = 1

A[4] = 0

A[5] = 0

the function returns 4. The initial adjacency is 2, as there are two pairs of adjacent coins showing the same face, namely (0, 1) and (4, 5). After reversing the coin represented by A[2] the adjacency equals 4, as there are four pairs of adjacent coins showing the same face, namely (0, 1), (1, 2), (2, 3) and (4, 5), and it is not possible to obtain a higher adjacency.

Unfortunately, there is a bug in the implementation. Find it and correct it. You should modify at most two lines of code.

Assume that:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [0..1].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

function solution(A) {

var n = A.length;

var result = 0;

for (var i = 0; i < n - 1; i++) {

if (A[i] == A[i + 1])

result = result + 1;

}

var r = 0;

for (var i = 0; i < n; i++) {

var count = 0;

if (i > 0) {

if (A[i - 1] != A[i])

count = count + 1;

else

count = count - 1;

}

if (i < n - 1) {

if (A[i + 1] != A[i])

count = count + 1;

else

count = count - 1;

}

r = Math.max(r, count);

}

return result + r;

}

- 1of 3 votes
Given 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?]

- 1of 1 vote
Insert a element in a sorted circular linked list

- 2of 2 votes
For a given node in binary search tree find a next largest number in search tree.

- 1of 1 vote
Write a function return an integer that satisfies the following conditions:

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)

- 8of 8 votes
Given a 2-D matrix represents the room, obstacle and guard like the following (0 is room, B->obstacle, G-> Guard):

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.

- 1of 1 vote
You 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.

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.

- -1of 3 votes
What 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.

- 0of 0 votes
Consider a scenario where you open a file with your favorite editor (emacs on Linux or Microsoft Word on Windows).

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).

- 6of 6 votes
Give a N*N matrix, print it out diagonally.

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.

- -4of 4 votes
Modify 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?

- 1of 3 votes
Given an array of (unsorted) integers, arrange them such that a < b > c < d > e... etc.

- -2of 2 votes
Find 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.

`public 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; } }`

- -4of 4 votes
Flatten 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(). Note that the inner iterator or list might be empty.

- -4of 4 votes
Flatten 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().

- -1of 1 vote
Given 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.

- 0of 0 votes
What happens when you type a link in any browser and click GO button? List all steps.

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?

- 0of 0 votes
You are given a string FOOFIGHTERS. You have to come up with an algorithm that will compress this string.

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.

- -1of 1 vote
Find 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.`public 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); }`

- -1of 3 votes
Finding 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)?