## Google Interview Questions

- 0of 0 votes
Write a program which will bold the sub-string found in string (HTML Style).

`Example: string = "HelloWorld HelloWorld" substringList = ["el", "rl"] Make it like HTML Style:- NewString = "H<b>el</b>loWo<b>rl</b>d H<b>el</b>loWo<b>rl</b>d`

- 1of 1 vote
Phone screen Q: String encoding and decoding: Design a method that converts a list of strings into a single string which can be later converted back to the list.

- 0of 0 votes
Q: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.

`/usr /local profile.jpg /bin config.txt dest.png /rbin image.gif /sys /re /tmp pic.jpg ..... ……`

- 0of 0 votes
Q: List all comments in the given segment of codes. It's pretty tricky since there is a lot of things to be considered, especially the escape characters.

- -2of 2 votes
Write code to traverse a NxM matrix in a zig-zag fashion

- -1of 1 vote
Given a random string (reasonable length L), knowing all possible font sizes (e.g. font Fn has min_width, max_width, min_height, max_height), knowing fixed screen size, find the max font size that can display said string

- 0of 0 votes
Implement a2i - what are the edge cases you can think of? Signed integer only, subject to OS dependent MIN, MAX values

- 0of 0 votes
Running with Bunnies

====================

You and your rescued bunny prisoners need to get out of this collapsing death trap of a space station - and fast! Unfortunately, some of the bunnies have been weakened by their long imprisonment and can't run very fast. Their friends are trying to help them, but this escape would go a lot faster if you also pitched in. The defensive bulkhead doors have begun to close, and if you don't make it through in time, you'll be trapped! You need to grab as many bunnies as you can and get through the bulkheads before they close.

The time it takes to move from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave - you can move to and from the bulkhead to pick up additional bunnies if time permits.

In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.

Write a function of the form answer(times, time_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size, return the set of bunnies with the lowest prisoner IDs (as indexes) in sorted order. The bunnies are represented as a sorted list by prisoner ID, with the first bunny being 0. There are at most 5 bunnies, and time_limit is a non-negative integer that is at most 999.

For instance, in the case of

[

[0, 2, 2, 2, -1], # 0 = Start

[9, 0, 2, 2, -1], # 1 = Bunny 0

[9, 3, 0, 2, -1], # 2 = Bunny 1

[9, 3, 2, 0, -1], # 3 = Bunny 2

[9, 3, 2, 2, 0], # 4 = Bulkhead

]

and a time limit of 1, the five inner array rows designate the starting point, bunny 0, bunny 1, bunny 2, and the bulkhead door exit respectively. You could take the path:

Start End Delta Time Status

- 0 - 1 Bulkhead initially open

0 4 -1 2

4 2 2 0

2 4 -1 1

4 3 2 -1 Bulkhead closes

3 4 -1 0 Bulkhead reopens; you and the bunnies exit

With this solution, you would pick up bunnies 1 and 2. This is the best combination for this space station hallway, so the answer is [1, 2].

Test cases

==========

Inputs:

(int) times = [[0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 0, 1], [1, 1, 1, 1, 0]]

(int) time_limit = 3

Output:

(int list) [0, 1]

Inputs:

(int) times = [[0, 2, 2, 2, -1], [9, 0, 2, 2, -1], [9, 3, 0, 2, -1], [9, 3, 2, 0, -1], [9, 3, 2, 2, 0]]

(int) time_limit = 1

Output:

(int list) [1, 2]

- 0of 0 votes
Random generate a NxN matrix with only four types of element: 1,2,3,4.

However, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)

ex:

valid:

1 2 1 1

3 1 4 2

1 2 4 2

3 1 2 3

invalid because the first column has element 1 appears three times and all 1s are connected to each other :

1 2 1 3

1 3 4 2

1 2 4 4

2 3 2 2

- 0of 0 votes
An interesting question asked in Google’s phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation.

Follow up: Minimize steps needed.

ex:

{1 2 3 -1 4 5}

move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5}

push 1 to the output list because you move car 1 to the empty spot

suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.

- -3of 3 votes
Given a string and dictionary of words, form a word by removing minimum number of characters. Characters can be removed in-order only.

- 0of 0 votes
Find longest consecutive path in a binary tree.

1. the path can be decreasing or increasing, i.e [1,2,3,4] and [4,3,2,1] are both valid

2. the path can be child-parent-child, not necessarily a parent-to-child path

similar to this question: http://www.geeksforgeeks.org/longest-consecutive-sequence-binary-tree/

- 0of 0 votes
Implement delete operation for N-ary tree. Your function should return a list of roots after deletion operation. Notice that your delete function only delete one node instead of a subtree. The delete function takes a list of nodes to be deleted.

`private class TreeNode { int val; TreeNode[ ] child; } List<TreeNode> delete(TreeNode root, HashSet<TreeNode> set) { }`

- 3of 3 votes
Return the length of longest possible chunked palindrome string.

Examples :

Input : VOLVO

Output : 3

Explanation :

(VO)L(VO)

Input : merchant

Output : 1

Explanation : No chunks possible.

Input :

ghiabcdefhelloadamhelloabcdefghi

Output : 7

Explanation :

(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)

- 2of 2 votes
Given a list of manager and employee information represented in hashMap entries {AAA->BBB,CCC,EEE},{CCC->DDD}.

Print company structure tree with proper indentations. BBB, CCC and EEE directly reports to AAA, so they have one white space before "-", DDD reports to CCC, it has two whitespace before "-". The input is map<String,List<String>>`-AAA -BBB -CCC -DDD -EEE`

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

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

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