CareerCup

1/4 round of FB on-site interview, Master Degree, Hired
1.1 diameter of tree
1.2 find the point which have the maximum overlap of intervals

1 year exp. Interviewed at Cambridge, MA

Round1
LC304. Follow-up: given a char stream instead a string as the input, get the longest substring with at most K distinct characters.

Round2
Find out the area of a number of squares on a plane, an advanced version of LC223.
Had no clue on that problem at all so the interviewer kindly gave another one LC305.

Round3
Similar to LC393 but the interviewer made a slightly different rule for encoding.
Follow-up: decode with utf-16. It took quite a while for me to understand the rules.

Round4
Card game rule: the hand is drawn from a pack of cards (no jokers).
Play cards ONLY when they are
1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).
2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).
Find out whether the player is able to play the whole hand given.
e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.
[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.

given a string of number, you can add a + or * sign between any two numbers, find the maximum value you can get
ex. s = "89" --> 8 * 9 = 72
int maxNumber(String s){}

A new species has been discovered and we are trying to understand their form of communication. So, we start by identifying their alphabet. Tough Mr. Brown managed to steal a vocabulary that has words in it in ascending order and a team already identified the letters. So, we have now ordered words as sequences of numbers, print every letter once in ascending order.

[3,2]
[4,3,2]
[4,1,1]
[1, 2]
[1, 1]

alphabet: [3, 4, 2, 1]

Given a string, find the longest substring without repeating any character.

Design a service that keeps track of mobile users as they check in at different locations. This service will get informed of each check-in in real time (a user/location pair) and must be able to answer the following queries in real time:

1. Where is user U right now?
2. What users are at location L right now?

The following requirements apply:

1. A user can only be at one location at a time. If user U checks in at location X and then at location Y, they are no longer at location X.

2. A check-in only valid for at most 2 hours. If user U checks in at location X and then does nothing for 2 hours, they are no longer at location X.

The service should have durable enough storage that you can restart it without losing all of your data It should not store everything in memory.

what kind of DB will you use and how data will be organized and any indexes. If storage is spread out over multiple databases(locations), how is that done?

scalability/availability consideration, how will be distribute multiple servers. what happens when the traffic goes 10x all of sudden. What happens if one of the server goes down.

Google full-time phD candidate w/ work experience.

Q1. On a 1 meter walkroad, randomly generate rain. The raindrop is 1 centimeter wide.
Simulate how raindrops cover the 1 meter [0~1] road. How many drops does it take to fully cover the 1meter?

Q2. Find out the maximum number of isosceles triangles you can make from a plane of points(cannot reuse points)

Q3.Longest holiday - Every city has a different days of holidays every week. You may only travel to another city at the weekends. What is the max days of holiday you can get this year.

Q4.
Design merchandising product data storage service

Give you an unsorted integer iterator
and a percentage that is expressed in double (for example, 0.4 for 40%),
and find the number of the sorted array at the percentage position.
Example: Enter [1 3 2 5 4 6 7 9 8 10], and 0.6, you will return 6
public int findNumber(Iterator<Integer> nums, double percent){
}

An ABC notation in a tree is defined as folllows:
1. "0" means travel left
2. "1" means travel right
3. "Undefined" means hit the root
4. "Not Found" means not present in tree

Given a BST insertion order, {5,2,8,3,6,9,1} find the ABC notation for 6, 1, 10, 2 which is "10","00","NotFound", "0"

Google On-site in May

Create a class with a collection of integers.
Enable 3 APIs:
void append(int x),
int get(int idx),
void add_to_all(int x)，//add x to all numbers in collection
These methods should run in O(1) time.


Follow-up
In addition, implement
void multiply_to_all(int x)
The same required to run in O(1) time

Given a n*m size 2D array with integers from 1 to n*m - 1 in it.
Integers are not sorted. The last position of the matrix stays a movable block.
For each time, you can swap the movable block with any adjacent number.
And eventually you will have the integers sorted and the movable block returned
to its starting position. Think about an approach to print the path.
(You can assume it always have at least a solution)

How to get the repeating decimal pattern of a division? (e.g 1/3, 1/6)

Given input - xyzonexyztwothreeeabrminusseven as a string, return an integer as the sum of all numbers found in the string
Output - 1 + 23 + (-7) = 17

Given a preorder traversal of a BST, print out the inorder transversal of the BST
public void printInorder(int[] nums){}

Implement circular buffer with read & write functions

Coding III
Implement int divide(int a, int b) without division or mod operation.



## Round IV
Behavioral Questions + Project Walk Through + Coding (Validate BST)

## System Design V
Design memcache to enable read, write and delete (single server, non-distributed infrastructure).
Which data structure to go with?
Eviction rules?
How to minimize segmentation?
How to handle concurrency?

## Extra
After two weeks they called me to an extra round of system design.
How to store social graphs?
How to handle concurrent read/write requests(read heavy) on one server.

Given a m x n array filled with 1's & 0's. Find all the rectangles which are filled with all the 1's.


Note : - It is guaranteed that there won't be any overlapping rectangles.

Find Famous person in the list of persons.

A person is a famous person if he doesn't know anyone in the list and everyone else in the list should know this person.

The function isKnow(i,j) => true/ false is given to us. No need to worry about it.

Goal is to find the famous person in O(n) complexity.

Given a array of integers there is one that is repeated several time. How would you compute the length of the sequence of repeated elements.
Assuming the initial array is sorted can you do better than O(n) both for spatial and temporal cost?

Given a 2D character array of size NxN. Find if there is a path from the cell 'R' to the cell 'T'. You can go left, right, up, down from a cell and you cannot pass through any cell marked with 'X'.

Example input:
X__R_X
X_XXX_
______
_XX_XX
XT__X_

Output: true

Print all permutations of a given string.

Implement power function. The function should take two numbers as input (e.g. 2,3) and return 8 as output

See link below for hints and answer https://baquerrizvinotes.blogspot.in/2017/05/how-to-crack-amazoncom-technical.html

You have a array with integers:

[ 1, -2, 0, 6, 2, -4, 6, 6 ]

You need to write a function which will evenly return indexes of a max value in the array.
In the example below max value is 6, and its positions are 3, 6 and 7. So each run function should return random index from the set.

Try to implement with O(n) for computation and memory.
Try to reduce memory complexity to O(1).

You have a binary tree which consists of 0 or 1 in the way, that each node value is a LOGICAL AND between its children:

0
   /   \
  0     1
 / \   / \
0   1  1  1

You need to write a code, which will invert given LEAF and put tree in a correct state.

Given a binary tree of integers, write code to store the tree into a list of integers and recreate the original tree from a list of integers.

Here's what your method signatures should look like (in Java):

List<Integer> store(Node root)
Node restore(List<Integer> list)

Example Tree:

5
/ \
3 2
/ / \
1 6 1

Implement pow(x, n)

Pick three numbers a, b, c from an array of integers to get the maximum product a * b * c.

Began with the O(N^3) solution. Then the interviewer give clues on optimization by sorting the array.

Given a large file with sentences and query string, design a system (Class, data structs, functions, etc) and algorithm to return the smallest window (start and end offsets) in the input file where the query words (in any order) are seen in the text file. What is the time complexity?

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.
Ex: "bedbathandbeyond" would be "bed bath and beyond" which are all dictionary words.