## Google Interview Questions

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

- 6of 6 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

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

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

- 5of 5 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) { }`

- 4of 4 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 !!).

- 1of 1 vote
You are given information about hotels in a country/city. X and Y coordinates of each hotel are known. You need to suggest the list of nearest hotels to a user who is querying from a particular point (X and Y coordinates of the user are given). Distance is calculated as the straight line distance between the user and the hotel coordinates.

- 3of 3 votes
Given a complete binary tree, print the outline of the tree in anti-clockwise direction, starting from the root. I.e. first print all the nodes on the left

edge of the tree going downwards, then print all the leaves going left to right (including leaves on both the last and the 2nd last level if necessary), then

print the nodes on the right edge of the tree going upwards.

Example tree:

A

/ \

/ \

B C

/ \ / \

D E F G

/ \ /

H I J

Expected Output: ABDHIJFGC

- 2of 2 votes
Design a two player battleship game to be played over internet

- 0of 0 votes
Suppose you have a million integer numbers.

Return all possible values of a,b and c such that

a+b+c<=d.

d will be provided to you.

ex: if the numbers are 1,2,3,4,5,6,7

and d=7

[1,2,3]

[1,2,4]

[1,2,3] will be same as [1,3,2] and [3,2,1]...

follow up:

Return all such parts that satisfy the above condition if d is not provided.

- 0of 0 votes
Given a string with multiple spaces write a function to in-place trim all spaces leaving a single space between words

e.g.

_ _ _ Hello _ _ _ World _ _ _

Hello _ World _ _ _ _ _ _ _ _ _

- 2of 2 votes
How many occurrences of a given search word can you find in a two-dimensional array of characters given that the word can go up, down, left, right, and around 90 degree bends?

Ex:

Count of occurrences of SNAKES

S N B S N

B A K E A

B K B B K

S E B S E

The answer is 3.

Write a program for that question.

- -1of 1 vote
Quest: create a Random number generator without using the java in build Random class?

public class GenerateRandomNumbers {

public static int seed = 10;

public void generateInt(int num){

seed = num;

for(int i=1;i<num;i++){

seed = ((int)System.nanoTime()%(i));

if(seed<=0)

seed = ((int)System.currentTimeMillis()%i);

System.out.println(seed);

}

}

public static void main(String[] args) {

new GenerateRandomNumbers().generateInt(20);

}

}

its a class to generate random numbers but the problem is It always starts with 0...!

Can someone add some more to this code.??

- 1of 1 vote
Given a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1.

Example:

Input : a?b?c?

Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.

- -1of 1 vote
Table 1: Parents -> (int id, int age)

Table 2: Children -> (int id, int age, int parent_id)

Get the parent id, his/her oldest and youngest children ids.

- -1of 1 vote
Table 1: Parents -> (int id, int age, int Child_id)

Table 2: Children -> (int id, int age, int parent_id)

Get the parent id, his/her oldest and youngest children ids.

- 0of 0 votes
given 10 files (text files) each of size of 900 Mb. givena another file named "hello". match the contents of this file with other 10 file and return the file whose contents closely match with the contents of file "hello"

- -1of 9 votes
Find minimum number of steps to reach the end of array from start (array value shows how much you can move).

- -1of 1 vote
Draw a graph as a graph. Assume there is graphics library to draw lines and all. Just tell how will you order the vertices such that the edges don't intersect and they seem ordered.