## Google Interview Questions

- 2of 2 votes
As an input, you have points on a 2D graph. You aim to find a straight line that can fit as my points as possible. Return, the maximum number of points you can fit.

- 0of 0 votes
Given a pattern and a string - find if the string follows the same pattern Eg: Pattern : [a b b a], String : cat dog dog cat

- 0of 0 votes
Given N stacks, each stack contains Si elements, find the maximum sum of the M numbers in the N stacks. To get the number of the stack, only supporting get the top number. For example, S=[1,200,1,2,3], if you want to get the number 200, you need choose 3,2,1 first.

EX:

S1=[1,1,100,3]

S2=[2000,2,3,1]

S3=[10,1,4]

the maximum sum of the 3 numbers in the above stacks is 3+100+3=107.

Any better solution for this problem?

- 0of 0 votes
Combination of these two leetcode question.

Given a digital strings, find all the sentence it can represent.

Digital to letter mapping is same as telephone keypad.

Separating the letters according to a dictionary to form sentences.

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

https://leetcode.com/problems/word-break-ii/

- -1of 1 vote
// TokenBucket

// Goal: regulate a resource of some kind (1 token = 1 unit of a resource)

//

// init(start_tokens, max_tokens, fill_rate)

// get_tokens(int tokens)

// - block until those tokens are available in the token bucket

// - if number of tokens in the bucket is less than requested number of tokens, wait

// put_tokens(int tokens)

// - block until there is space in the token bucket for those tokens.

// fill_rate: x tokens per sec are added to the token bucket

Thread communication methods allowed are listed below. No thread safe collections are allowed.

// Lock()

// - lock()

// - unlock()

// ConditionVariable()

// - wait(lock, max_time_to_wait_in_secs)

// - releases lock before sleep and then reacquires lock upon waking

// - notify(): This wakes up 1 waiter on this condition variable

// - notifyAll(): Wakes up all waiters on this condition variable

- 3of 3 votes
Tom works in a warehouse. A billion (1,000,000,000) boxes are arranged in a row. They are numbered from one to one billion (from left to right). Some boxes contain a basketball (at most one basketball in each box). In total, there are N basketballs.Tom wants to organize the warehouse. He would like to see all the basketballs arranged next to each other (they should occupy a consistent interval of boxes). In one move, Tom can take one basketball and move it into an empty box. What is the minimum number of moves needed to organize the basketballs in the warehouse?

Write a function:`class Solution { public int solution(int[] A); }`

that, given an array A containing N integers, denotes the positions of the basketballs (the numbers of the boxes in which they are placed) and returns the minimum number of moves needed to organize the basketballs in the warehouse.

For example, given: A = [6, 4, 1, 7, 10], your function should return 2 because the minimum number of moves needed to arrange all basketballs next to each other is 2. There are several ways to do it. For example, you could move the ball from the first box to the fifth, and the ball from the tenth box to the eighth. You could also move the ball from the first box to the fifth, and the ball from the tenth box to the third instead. In any case, you need at least two moves.

To be done in O(nlogn) Time complexity and O(1) space complexity

- 1of 1 vote
You are the main character in a game where you have to defeat a number of enemies in order. The player has a strength value and an initial amount of money. Each enemy also has a strength value, plus a price.

When facing each enemy you can either:

1) Fight him (if your strength is enough). You keep your money.

2) Bribe him (if you have the necessary money). You subtract the enemy's price from your money, and it joins you and adds its strength to yours.

Given a starting strength and amount of money, calculate the optimal strategy and the amount of money you end with (-1 if impossible).

This can be easily solved recursively in O(2^n) basically trying out each option at every enemy. But is there a polynomial solution, maybe involving DP?

- 1of 1 vote
Given a list of coin values, and quantity of each type of coin. Write a

program to return the set of all possible sums which can be made using those

coins.

ex. coins = [10, 50, 100, 500]

quantity = [5, 3, 2, 2]

sum could be 400 , 300 ,200 , 100

- 1of 1 vote
n points on a 2D space. You observe the points from (0,0) with viewing direction and viewing angle.

Given an array (xn,yn), and a viewing angle v (45 degree), find the direction that can observe max number of points.

- 0of 0 votes
Write a function that compares Spanish strings, how would you handle special cases like 'ch' ?

c < ch < d, ch will be represented as 2 ASCII characters

- 2of 2 votes
Given a function getRandom that returns a random double in [0,1). Write a function getRandomPermutation(int n) that takes a positive integer n as argument and returns a random permutation of first n natural numbers.

- 0of 0 votes
You are given a sorted list of distinct integers from 0 to 99, for instance [0, 1, 2, 50, 52, 75]. Your task is to produce a string that describes numbers missing from the list; in this case "3-49,51,53-74,76-99".

Examples:

[] “0-99”

[0] “1-99”

[3, 5] “0-2,4,6-99”

- -1of 1 vote
Assume (n+1) points on a 2D space. You observe the points from (0,0) with viewing direction and viewing angle.

Given an array (xn,yn), and a viewing angle v (45 degree), find the direction that can observe max number of points.

- 2of 2 votes
Given 'n' circles (each defined by center and radius)

Write an algorithm to detect if circles intersect with any other circle in the same plane

Better than O(n^2) complexity

- 1of 1 vote
Return the pivot index of the given array of numbers. The pivot index is the index where the sum of the numbers on the left is equal to the sum of the numbers on the right. Input Array {1,2,3,4,0,6}

- 1of 1 vote
Given the village of a map represented as a 2D grid containing houses,bushes and open-spaces, write a program to find a point for conducting a meeting in the map. Such point should be minimum from all the houses in the village.

Eg.`# # # # # # # A # # B # # # # # # # C # # # # # #`

# -> represents the bushes

A, B, C -> position of houses

I provided a O(n*a*b) approach, where n-> no. of houses , a,b->dimensions of the grid.

The interviewer asked me for some special cases. Can it be done more efficiently?

- 2of 2 votes
Write an algorithm that returns any duplicate in an array of integers. The algorithm must run in O(n) time and O(1) space. (hint: the integers in the array are not greater than the size of the array).

- 2of 2 votes
Create a function to calculate the height of an n-ary tree.

- 0of 0 votes
Given a binary tree & the following TreeNode definition, return all root-to-leaf paths.

Definition of TreeNode:`public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val) { this.val = val; this.left = this.right = null; } }`

EXAMPLE

`Given the following binary tree: 1 / \ 2 3 \ 5 All root-to-leaf paths are: [ "1->2->5", "1->3" ]`

From Lint Code - http://www.lintcode.com/en/problem/binary-tree-paths/

- 3of 3 votes
You are given a scrambled input sentence. Each word is scrambled independently, and the results are concatenated. So:

'hello to the world'

might become:

'elhloothtedrowl'

You have a dictionary with all words in it. Unscramble the sentence.

- 2of 2 votes
Given a string "2-4a0r7-4k", there are two dashes which we can split into 3 groups of length 1, 5, 2.

If we want each group to be length 4, then we get "24A0-R74k"

Given a String A and an int K, return a correctly formatted string.

IF A is "2-4A0r7-4k" and B is 4, string is "24A0-R74K"

IF K is 3, string is "24-A0R-74K" as the first grp could be shorter.

- 0of 0 votes
Given an n-ary tree, find the longest sequence in it. The sequence doesn't end to start at the root. It can go from leaf to leaf.

- 1of 1 vote
Given an NxN grid with an array of lamp coordinates. Each lamp provides illumination to every square on their x axis, every square on their y axis, and every square that lies in their diagonal (think of a Queen in chess). Given an array of query coordinates, determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on,…

- 1of 1 vote
Find the shortest path between a start node and end node in a undirected +ve weighted graph.

You are allowed to add at max one edge between any two nodes which are not directly connected to each other.

ex:

From | To | Weight

1 2 2

1 4 4

2 3 1

3 4 3

4 5 1

start node = 1, end node = 5.

extra edge weight = 2.`1----(2)----2 | | | | (4) (1) | | | | 5-(1)-4----(3)----3 In this case answer would be 3 (from 1 - > 5 - > 4) Solution: 1----(2)----2 /| | / | | (2)/ (4) (1) / | | / | | 5-(1)-4----(3)----3`

- 0of 0 votes
Given an un-directed weighted graph G(V,E), find the minimum weight between two given nodes X & Y

(i.e. sum of weights of edges between X & Y).

You can add an extra egde with weight W between any two nodes in the graph exactly one time (if required).

- 1of 1 vote
Let's say I have a word "I love chicken", I can break the number of characters in each word, like so: [1] [4] [7]

[1,4] [4,7], [1,4,7].

Now let's say I have a max = 5. The phrases with equal or fever than 5 characters are "[I], [love], and [I, love]. The longest phrase is [I,love], which contains 2 words.

Complete the Length function given. It has 2 parameters:

1) An array of integers, named array

2) A maximum number, named max.

int Careercup( int [] array, int max) {

}

Example test case 1:

[3,1,2,3]

4

Output expected : 2

- 3of 3 votes
Find the largest and smallest number in a list. The list is stored as two sections, one in ascending order and the other in descending order.

input [ 2 3 4 5 6 7 10 9 8 7]

smallest : 2

Largest 10

- 2of 2 votes
Given an Array A with n elements. Pick maximum number of elements from given array following the rule:

1. We cannot pick A[i] and A[j] if absolute value of (A[i] - A[j]) > absolute value of (i - j)

Example: {13,5,4}

Ans: 2

Pick 5 and 4.

- 0of 0 votes
Implement method:

`Lìst<Range> getRanges(Lìst<Shard> shards, Lìst<Key> keys)`

That returns list of ranges. Each range represents multiple keys aggregated over a shard:

n-keys —> 1-shard —> l-range

Method should return no more than 1 range per shard that spans all keys or their parts belonging to this shard.

Each of the ‘Range` , 'Shard’ and ‘Key’ classes have ‘end’ and ‘start’ fields of int type, where ‘start’ is inclusive and ‘end’ is exclusive.

Example:`1—9, 12—59, 100—999 <— shards (input) 2—3, 6—8, 11—20, 200—220 <— keys (input) 2—8, 12—20, 200—220 <— ranges (output)`

- 1of 1 vote
http://www.geeksforgeeks.org/find-water-in-a-glass/