## Google Interview Questions

- 0of 0 votes
Write a program to implement Double Linked List from Stack with min. complexity.

- 0of 0 votes
Find the 90th percentile of a stream of numbers between 1 and 10^6.

Followup: What if there is not enough memory to store all numbers and no upper bound.

- 0of 0 votes
You 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.

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

- 5of 5 votes
Given a number M (N-digit integer) and K-swap operations(a swap

operation can swap 2 digits), devise an algorithm to get the maximum possible integer?

Examples:

M = 132 K = 1 output = 312

M = 132 K = 2 output = 321

M = 7899 k = 2 output = 9987

M = 8799 and K = 2 output = 9987

- 2of 2 votes
Problem Link：https://code.google.com/codejam/contest/4214486/dashboard#s=p1

At new years party there is a pyramidal arrangement of glasses for wine. For example, at the top level, there would just be one glass, at the second level there would be three, then 6 and then 10 and so on and so forth like the following image

.

The glasses are numbered using 2 numbers, L and N. L represents the level of the glass and N represents the number in that level. Numbers in a given level are as follows:

Level 1:

1

Level 2:

1

2 3

Level 3:

1

2 3

4 5 6

Level 4:

1

2 3

4 5 6

7 8 9 10

Each glass can hold 250ml of wine. The bartender comes and starts pouring wine in the top glass(The glass numbered L = 1 and N = 1) from bottles each of capacity 750ml.

As wine is poured in the glasses, once a glass gets full, it overflows equally into the 3 glasses on the next level below it and touching it, without any wine being spilled outside. It doesn't overflow to the glasses on the same level beside it. It also doesn't overflow to the any level below next level (directly).

For example: When the glass of L = 2 and N = 2 overflows, the water will overflow to glasses of L = 3 and N = 2, 4, 5.

Once that the bartender is done pouring B bottles, figure out how much quantity in ml of wine is present in the glass on level L with glass number N.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of three integers, B, L, N, B is the number of bottles the bartender pours and L is the glass level in the pyramid and N is the number of the glass in that level.

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the quantity of wine in ml in that glass.

- 1of 3 votes
There is an array of 3-tuple, in the form of (a, 1, 5). The first element in the tuple is the id, the second and third elements are both integers, and the third is always larger than or equal to the second. Assume that the array is sorted based on the second element of the tuple. Write a function that breaks each of the 3-tuple into two 2-tuples like (a, 1) and (a, 5), and sort them according to the integer.

E.g. given (a, 1, 5), (b, 2, 4), (c, 7, 8), output (a, 1), (b, 2), (b, 4), (a, 5), (c, 7), (c, 8).

- -1of 1 vote
There are a large number of leaves eaten by caterpillars. There are 'K"' caterpillars which jump onto the leaves in a pre-determined sequence. All caterpillars start at position 0 and jump onto the leaves at positions 1,2,3...,N. Note that there is no leaf at position 0.

Each caterpillar has an associated 'jump-number'. Let the jump-number of the i-th caterpillar be A [i]. A caterpillar with jump number 7 keeps eating leaves in the order 1,241,3*1,... till it reaches the end of the leaves - i.e, it eats the leaves at the positions which are multiples of /'.

Given a set 'A' of 'IC elements. 'e<=15.,. 'N'<=109, we need to determine the number of uneaten leaves.

Input Format:

N -number of leaves

A - Given array of integers

Output Format:

An integer denoting the number of uneaten leaves.

Sample Input:

N = 10

A = [2,4,5]

Sample Output:

4

Explanation

1,3,7,9 are the leaves which are never eaten. All leaves which are multiples of 2, 4, and 5 have been eaten.

Java Code:`public class Solution { //need to complete the function below static int countUneatenLeave(int N, int[] A { } public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in); final String fileName = System.getenv("OUTPUT_PATH"); BufferedWriter bw = new BufferedWriter(new FileWriter(fileName)); int res; int _N; _N = Integer.parseInt(in.nextLine()); int _A_size = Integer.parseInt(in.nextLine()); int[] _A = new int(_A_size]; int _A_item; for(int _A_i = 0; _A_i < _A_size; _A_i++) { _A_item = Integer.parseInt(in.nextLine()); _A[_A_i] = _A_item; } res = countUneatenLeaves(_N,_A); bw.write(String.valueOf(res)); bw.newLine(); bw.close(); } }`

- -1of 1 vote
There are a large number of leaves eaten by caterpillars. There are 'K"' caterpillars which jump onto the leaves in a pre-determined sequence. All caterpillars start at position 0 and jump onto the leaves at positions 1,2,3...,N. Note that there is no leaf at position 0. Each caterpillar has an associated 'jump-number'. Let the jump-number of the i-th caterpillar be A [i]. A caterpillar with jump number 7 keeps eating leaves in the order 1,241,3*1,... till it reaches the end of the leaves - i.e, it eats the leaves at the positions which are multiples of /'. Given a set 'A' of 'IC elements. 'e<=15.,. 'N'<=109, we need to determine the number of uneaten leaves. Input Format: N -number of leaves A - Given array of integers Output Format: An integer denoting the number of uneaten leaves. Sample Input: N = 10 A = [2,4,5] Sample Output: 4 Explanation 1,3,7,9 are the leaves which are never eaten. All leaves which are multiples of 2, 4, and 5 have been eaten.

Java Code

public class Solution {

//need to complete the function below

static int countUneatenLeave(int N, int[] A {

}

public static void main(String[] args) throws IOException {

Scanner in = new Scanner(System.in);

final String fileName = System.getenv("OUTPUT_PATH");

BufferedWriter bw = new BufferedWriter(new FileWriter(fileName));

int res;

int _N;

_N = Integer.parseInt(in.nextLine());

int _A_size = Integer.parseInt(in.nextLine());

int[] _A = new int(_A_size];

int _A_item;

for(int _A_i = 0; _A_i < _A_size; _A_i++) {

_A_item = Integer.parseInt(in.nextLine());

_A[_A_i] = _A_item;

}

res = countUneatenLeaves(_N,_A);

bw.write(String.valueOf(res));

bw.newLine();

bw.close();

}

}

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

(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?

- -4of 4 votes
Given an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and vice-versa maintaining the order of appearance.

Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.*

Example:`Input: arr[] = {1, 2, 3, -4, -1, 4} Output: arr[] = {-4, 1, -1, 2, 3, 4} Input: arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8} output: arr[] = {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0}`

Limitations:

a) Use O(1) extra space

b) Time Complexity should be O(N)

c) Maintain the order of appearance of elements as in original array.

- 0of 0 votes
. In an unsorted array of numbers that occurs an odd number of times except one that occurs an even number of times, find the number that occurs an even number of times

- -1of 1 vote
Solve Travelling salesman problem using Iterative Deepening Search Algorithm.

Edit:

You have been given distance between each pair of cities and the number of cities

- 0of 0 votes
You are given a list of items / combo_items with their price list.

And you are given list of items to buy.

Now you are asked to find which combination to buy so that it costs you minimum.

It doesnt matter if you are getting some extra items if it costs less.

Sr.No Price | Items/Combo_Items

1. 5 | Burger

2. 4 | French_Frice

3. 8 | Coldrink

4. 12 | Burger, French_Frice, Coldrink

5. 14 | Burger, Coldrink

Input Items to Buy:

Coldrink

Output(Sr.No)

3

Input Items to Buy:

Burger Coldrink

Output(Sr.No)

4

Input Items to Buy:

Burger French_Frice

Output(Sr.No)

1,2

- 2of 2 votes
Write a function which, given two integers (a numerator and a denominator), prints the decimal representation of the rational number "numerator/denominator".

Since all rational numbers end with a repeating section, print the repeating section of digits inside parentheses; the decimal printout will be/must be

Example:

1 , 3 = 0.(3)

2 , 4 = 0.5(0)

22, 7 = 3.(142857)

etc..

- 0of 0 votes
Write a function which, given two integers (a numerator and a denominator), prints the decimal representation of the rational number "numerator/denominator".

Since all rational numbers end with a repeating section, print the repeating section of digits inside parentheses; the decimal printout will be/must be

Example:

1 , 3 = 0.(3)

2 , 4 = 0.(5)

22, 7 = 3.(142857)

etc..

- 2of 2 votes
You are given a text file that has list of dependencies between (any) two projects in the soure code repository. Write an algorithm to determine the build order ie. which project needs to be build first, followed by which project..based on the dependencies.

Bonus point: If you can detect any circular dependencies and throw an exception if found.

EX: ProjectDependencies.txt

a -> b (means 'a' depends on 'b'..so 'b' needs to be built first and then 'a')

b -> c

b -> d

c -> d

Then the build order can be

d , c, b, a in that order

- 7of 7 votes
There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?

Ex:

Servers capacity limits: 8, 16, 8, 32

Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8

For this example, the program should say 'true'.

Ex2:

Server capacity limits: 1, 3

Task capacity needs: 4

For this example, program should return false.

Got some idea that this needs to be solved using dynamic programming concept, but could not figure out exact solution.

- 1of 1 vote
Find the longest words in a given list of words that can be constructed from a given list of letters.

Your solution should take as its first argument the name of a plain text file that contains one word per line.

The remaining arguments define the list of legal letters. A letter may not appear in any single word more times than it appears in the list of letters (e.g., the input letters ‘a a b c k’ can make ‘back’ and ‘cab’ but not ‘abba’).

Here's an example of how it should work:

prompt> word-maker WORD.LST w g d a s x z c y t e i o b

['azotised', 'bawdiest', 'dystocia', 'geotaxis', 'iceboats', 'oxidates', 'oxyacids', 'sweatbox', 'tideways']

Tip: Just return the longest words which match, not all.

- 1of 1 vote
Given 2 set of arrays of size N(sorted +ve integers ) find the median of the resultant array of size 2N.

(dont even think of sorting the two arrays in a third array , though u can sort them. Try something better than order NLogN

- -6of 6 votes
Write a method to return first five 10 digit prime numbers

- 2of 2 votes
Write a method to return first five 10 digit prime numbers.

- 11of 11 votes
Output top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below:

1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...

- 2of 2 votes
Find the longest sequence of prefix shared by all the words in a string.

"abcdef abcdxxx abcdabcdef abcyy" => "abc"

- 6of 6 votes
Given a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print sequence of increasing adjacent sequential numbers.

ex:

1 5 9

2 3 8

4 6 7

should print

6 7 8 9

- 2of 2 votes
Give efficient implementation of the following problem.

An item consist of different keys say k1, k2, k3. User can insert any number of items in database, search for item using any key, delete it using any key and iterate through all the items in sorted order using any key. Give the most efficient way such that it supports insertion, search based on a key, iteration and deletion.

- -3of 3 votes
Swap 2 nodes in a Binary tree.(May or Maynot be a BST)

Swap the nodes NOT just their values.

(preferably in Java please..(My requirement not theirs :p))

ex:

5

/ \

3 7

/ \ /

2 4 6

swap 7 and 3

5

/ \

7 3

/ / \

6 2 4

- -4of 6 votes
You have an array of integers(size N), such that each integer is present an odd number of time, except 3 of them(which are present even number of times). Find the three numbers.

Only XOR based solution was permitted.

Time Complexity: O(N)

Space Complexity: O(1)

Sample Input:

{1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9}

Sample Output:

1 6 8

- 7of 7 votes
Given an unsorted array of integers, you need to return maximum possible n such that the array consists at least n values greater than or equals to n. Array can contain duplicate values.

Sample input : [1, 2, 3, 4] -- output : 2

Sample input : [900, 2, 901, 3, 1000] -- output: 3

- 1of 1 vote
Traveler 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:`class Step { String start; String finish; }; class Node { String value; Node next; } List<String> findPath(List<Step> steps) { }`

- 7of 7 votes
Given a Binary Search tree of integers, you need to return the number of nodes having values between two given integers. You can assume that you already have some extra information at each node (number of children in left and right subtrees !!).