## Google Interview Questions

- 0of 0 votes
you have a interface called Op and a Filter interface

interface Op<T> {

public boolean hasNext();

public boolean<T> next();

}

interface Filter<T1, T2> {

public boolean filter(T1 t1, T2 t2);

}

design a MutualOp that has below API, MutualOp should return the ops that combine op1 and op2, also should meet with the filter

class MutualOp implements Op{

public MutualOp(Op left, Op right, Filter<Op, Op> filter) {

this.left = left;

this.right = right;

this.filter = filter;

}

public boolean hasNext {

......

}

public T next {

......

}

}

- 0of 0 votes
calculate minimum h-index for a sorted integer array(http://en.wikipedia.org/wiki/H-index)

- 0of 0 votes
Assuming you're playing one game that you need guess a word from a dictionary. You're given a machine you can try to guess the word, the machine will return how many characters has been matched by your guess. Design a system to crack the word.

- 0of 0 votes
Permutate a list of string

this question is supposed permutate the characters instead of who string,

as input example {"red", "fox", "super" }, the expected output is

rfs

rfu

rfp

rfe

rfr

ros

rou

rop

roe

ror

rxs

rxu

rxp

rxe

rxr

efs

efu

efp

efe

efr

eos

eou

eop

eoe

eor

exs

exu

exp

exe

exr

dfs

dfu

dfp

dfe

dfr

dos

dou

dop

doe

dor

dxs

dxu

dxp

dxe

dxr

- 0of 0 votes
A 2D array filled with integer, define a flow from one point to its neighbor only if the value of current point is not less than its neighbor's value. Consider up edge and left edge as east coast, bottom edge and right edge as west coast, find all position that it can flow to east coast and west cost both

- 0of 0 votes
Simplify the implementation below as much as you can.

Even better if you can also improve performance as part of the simplification!

FYI: This code is over 35 lines and over 300 tokens, but it can be written in

5 lines and in less than 60 tokens.

קוד: בחר הכל

static int func(String s, char a, char b)

{

if (s.isEmpty()) return -1;

char[] strArray = string.toCharArray();

int i=0;

int aIndex=0;

int bIndex=0;

while (aIndex=0 && bIndex==0 && i<strArray.length)

{

if (strArray[i] == a)

aIndex=i;

if (strArray[i] == b)

bIndex=i;

i++;

}

if (aIndex != 0)

{

if (bIndex == 0)

return aIndex;

else

return Math.min(a, b);

}

else

{

if (bIndex != 0)

return bIndex;

else

return -1;

}

}

- 0of 0 votes
Given 1 byte. Write a function that checks that it have exactly 3 bits which equal to 1.

- 0of 0 votes
Write a function

bool fancy_shuffle(char* s);

which rearranges characters in the string given as input, in such a way that no same character occurs twice in a row (that is, next to each other).

If such rearrangement is not possible, the function should return false.

- 0of 0 votes
Given an array of numbers, find a pair whose sum is closest to zero.

- 0of 0 votes
You are given a log of wood of length `n’. There are `m’ markings on the log. The log must be cut at each of the marking. The cost of cutting is equal to the length of the log that is being cut. Given such a log, determine the least cost of cutting.

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

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