## Google Interview Questions

- 1of 1 vote
Design an optimised algorithm to solve snakes and ladders with the least amount of roles possible under the assumption that you get whatever role you want when you role the dice.

- 3of 5 votes
Given an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter.

For Ex:

Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100]

n -> 2

Out put -> [100, 0] or [100, 2]

Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2

- 0of 0 votes
This is a two part question related to Markov string generation.

Part 1: Read a training set of strings. For each character in any of the strings, calculate the probability of seeing that character and store it for later use. (this part is about coming up with the right data structure and correct probability calculation).

Part 2: Based on the training set from Part 1, generate a random string of length N.

- 0of 0 votes
Given an API ReadFromDisk() which returns a block of 256 bytes from disk. Implement the API Read(SizeInBytes) which reads SizeInBytes bytes from the disk by calling only ReadFromDisk. Notice that every call to ReadFromDisk() will read the next 256 bytes from disk.

- 0of 0 votes
Given an API ReadFromDisk() which returns a block of 256 bytes from disk. Implement the API ReadEx(SizeInBytes) which reads SizeInBytes bytes from the disk by calling only ReadFromDisk. Notice that every call to ReadFromDisk() will read the next 256 bytes from disk.

- 2of 2 votes
You are given printouts from an algorithm which ran over an unsorted binary tree. One printout is from an in-order run and another from a pre-order run. Can you reconstruct the tree? If so, then write an algorithm.

- 1of 1 vote
You are given printouts from an algorithm which ran over a sorted binary tree. One printout is from an in-order run and another from a pre-order run. Can you reconstruct the tree? If so, then write an algorithm.

- 1of 1 vote
You have N points on a 2D surface. List K points at a shortest distance to the point (0, 0).

- 0of 0 votes
There is a company with 250 employees. Its records contain: EmployeeID, ManagerID (which is a reference to the EmployeeID of the manager).

Part 1. List directly reporting employees for a given ID

Part 2. List all (also indirectly) reporting employees to a given ID

- 1of 1 vote
Assume we only take the least significant digit of each value in fibonacci sequence, and form the sequence of digits into pairs. In those pairs, the first value of one pair is the same as second value of its predecessor.

As we know the fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21...

so the pair sequence is:

[1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 3], [3, 1] ...

Write a function to output the first n pairs of this sequence.

void Outputpairs(int n)

- 0of 0 votes
You are given a monochrome bitmap as a byte array (together with its width and height). Draw a horizontal line.

- 0of 0 votes
Part 1: You are given a computer #1 with array Foo, a computer #2 with array Bar and a spare computer #3. You need to apply a function F to corresponding/matching elements of the two arrays. How would you do that?

Part 2: Once you scale up, how would you balance the number of machines sorting with the machines applying the function?

Part 3: What if the master (which is distributing the work) dies and never recovers?

- 0of 0 votes
Print all the different possible subsets suming the given number

Ex:

Input:4

Output:

1111

112

121

112

13

31

- 1of 1 vote
You are given two strings. String T is a string where characters need to be reordered. String O contains characters (none of them repeated) which defines the order/precendence to be used while reordering the string T. Write an algorithm to do the reordering.

*** SPOILER ALERT ***

The question was pusposefully underspecified - upon questioning it was revealed that the string O might not necessarily include all characters used in string T - the characters not included in string O are supposed to be placed at the beginning of the resulting string (in no particular order).

- 1of 1 vote
You are given two arrays - A & B. The length of the arrays is the same - N. The values in the arrays are integers from 0 to N - 1 in random order and no number is repeated. You need to list a sequence of two-element swaps required to reorder the array A into the order of the array B. Additionally, at each step of the sequence you are allowed to swap two elements only if one of them is 0.

- 2of 2 votes
Given an array Of integers build a new array of integers such that every 2nd element of the array is greater than its left and right element.

eg:

[1,4,5,2,3]

o/p:

[1,4,2,5,3]

Soln proposed:

Step 1:Sort The array -> O(nlogn)

Step 2:Use 2 indices: one starting at leftmost index and other at rightmost index.

and populate the new array alterntely using the left pointer(index) first and then the right pointer and then increment the pointer used. till both the pointers meet/cross each other. -> O(n).

- 1of 3 votes
Problem Statement

Diameter

The diameter of a graph is the maximum shortest path between any two nodes.

At the beginning, there is a simple grpah contains exactly 1 node. Then we add new nodes one by one to the graph. Each time when we add a new node to the graph, we also add exactly one edge to connect this node to another node which already exists.

We want to find the diameter of the graph each time we add a new node. Note that each edge cost 1.

Input Format:

First line of the input contains one integer N, indicating how many new nodes we will add.

Then following N lines. The ith line contains an integer X, which means we add the ith node and an edge connecting the Xth node and ith node.

The original node is the 0th node.

Output Format:

Output N lines. The ith line is an integer indicating the diameter of the graph after adding the ith node.

Constraints:

0 < N <= 100000

0 <= Xi < i

i is counting from 1

Sample Input:

5

0

0

1

1

1

Sample Output:

1

2

3

3

3

Explanation:

Firstly the graph contains only node 0. The first line of output is 1 because the diameter becomes 1 when node 1 is added and connected to node 0. Diameter becomes 2 after adding node 2 to node 0. Then adding node 3, 4, 5, all of them are connecting to node 1, caculate the shortest path of all pairs of nodes, the maximum shortest path is 3, so the last 3 lines of output are all 3.

- 0of 2 votes
Write algorthim to determine the total time to make ice cream and when it leaves the store.

Consist of an order time, order number, and ice cream type.

“ice cream Type” is an integer: 0 for combo, 1 for vanilla. Order numbers are increasing.

We have three machines for making ice creams.

It takes 45 seconds to make a combo ice cream and 15 for vanilla. Can only make one ice cream at a time.

Need to determine total time to make ice cream and time the ice cream leaves the store (delivered).

In: order_time,order_num,ice_cream_type

Out: order_num,depart_time,total_time

- 2of 2 votes
Given a number "n", find the least number of perfect square numbers sum needed to get "n"

Example:

n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)

n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)

- 2of 2 votes
Find longest substring with "m" unique characters in a given string.

input: aabacbeabbed

output:

4 (aaba) for 2 unique characters

6 (aabacb) for 3 unique characters

- 0of 0 votes
You are given heights of n candles .

First day you lit one candle

second day you need to lit two candles

Third day you need to lit three candles

..........

........

till possible.

After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day.

So you need to tell the maximum number number of days , you can carry on lighting the candles.

Example : there are three candles of heights {2 , 2 ,2 }

Answer : 3

1.You light first candle on day one. heights -> {1,2,2}

2.You light second and third and extinguish first one . heights ->{1, 1,1}

3.You light all the candles. heights -{0,0,0}

- 0of 4 votes
Write a function that takes an integer as input and produces an output string.

Some sample Input/outputs are as follows

i/p o/p

1 - A

2 - B

3 - AA

4 - AB

5 - BA

6 - BB

7 - AAA

8 - AAB

9 - ABA

10 - ABB

11 - BAA

12 - BAB

13 - BBA

14 - BBB

15 - AAAA

- 1of 1 vote
Consider a social network graph like facebook. You are throwing a party and want to invite some of your friends. Design a algorithm to select top n friends from m friends using the social graph.

- 0of 0 votes
How would you optimize an elevator system for a building with 50 floors and 4 elevators ? Optimize in terms of lowest wait times for the users. Nothing related to power consumption.

- 0of 0 votes
Given the requirements of http://www.careercup.com/question?id=5769432498438144, implement the same task scheduler with parallel task execution.

- 0of 0 votes
Given the interface below, implement a task scheduler.

`interface Task { void Run(); Set<Task> GetDependencies(); }`

Additionally, the task scheduler should follow two rules.

1. Each task may only be executed once.

2. The dependencies of a task should be executed before the task itself.

- 1of 1 vote
Create a maze.

- 0of 0 votes
Play Scrabble. You have 7 letters to start from. Build the word with the highest score.

- 2of 2 votes
`Question: Given two strings, find number of discontinuous matches. Example: “cat”, “catapult” Output: 3 => “CATapult”, “CatApulT”, “CAtapulT”`

- 0of 2 votes
Given an array A[1...N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i...(i+k-1)] and A[j...(j+k-1)] such that i+k-1< j and swap A[i] with A[j], A[i+1] with A[j+1] ... and A[i+k-1] with A[j+k-1].

**Example:**

For n=6

6 7 8 1 2 3

Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays

we can get 1 2 3 6 7 8 , that is sorted.

How can we figure out minimum number of swaps in most effective way ?