# Phone Screen @Uber Oct. 26th, 2015

Given a pattern and an input string, check if the input string matches the pattern.

Eg.
pattern: abab
input: howwhathowwhat
mapping: a => how, b => what
so match(abab, howwhathowwhat) -> true
match(abab, whathowhowwhat) -> false
match(“”, “”) -> true
match(“a”, “a”) -> true
match(“ab”, “abab”) -> true
match(“aaaa”, “howwhatwhathow”) -> false
match(“aaaa”, “whatwhatwhatwhat”) -> true

Each char in pattern string can match 1-n chars in input string. Same char can only match same string. Different chars can match same strings.

```class Solution {
public boolean match(String pattern, String input) {
if (pattern == null || input == null || input.length() < pattern.length()) {
return false;
}
Map<Character, String> map = new HashMap<>();
return matchHelper(pattern, 0, input, 0, map);
}

public boolean matchHelper(String pattern, int index, String input, int inputIndex, Map<Character, String> map) {
if (index == pattern.length()) {
if (inputIndex == input.length()) {
return true;
}
return false;
}
char c = pattern.charAt(index);

if (map.containsKey(c)) {
String val = map.get(c);
if (inputIndex + val.length() <= input.length() && val.equals(input.substring(inputIndex, inputIndex + val.length()))) {
return matchHelper(pattern, index + 1, input, inputIndex + val.length(), map);
}
} else {
for (int i = inputIndex; i < input.length(); i++) {
String val = input.substring(inputIndex, i + 1);
map.put(c, val);
if (matchHelper(pattern, index + 1, input, i + 1, map)) {
return true;
}
map.remove(c);
}
}
return false;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.match("", "")); //true
System.out.println(s.match("a", "a")); //true
System.out.println(s.match("ab", "abab")); //true
System.out.println(s.match("abab", "howwhathowwhat")); //true
System.out.println(s.match("abab", "howwhatwhathow")); //false
System.out.println(s.match("aaaa", "howwhatwhathow")); //false
System.out.println(s.match("aaaa", "whatwhatwhatwhat")); //true
}
}```
Share

# Sqrt(x)

Sqrt(x)

Implement int `sqrt(int x)`.

Compute and return the square root of x.

Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

Challenge

O(log(x))

Solution: Binary search O(log(x)). Remember to use Long during computation

```public int sqrt(int x) {
// find the last number which square of it <= x
long start = 1, end = x;
while (start + 1 < end) {
long mid = start + (end - start) / 2;
if (mid * mid <= x) {
start = mid;
} else {
end = mid;
}
}

if (end * end <= x) {
return (int) end;
}
return (int) start;
}```

# Shortest Word Distance I, II & III

Word Distance I – Only called once

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = `["practice", "makes", "perfect", "coding", "makes"]`.

Given word1 = `“coding”`, word2 = `“practice”`, return 3.
Given word1 = `"makes"`, word2 = `"coding"`, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: One pass. O(n), Every time find an occurrence of word1 or word2, compare the distance of p1 and p2.

```public int shortestDistance(String[] words, String word1, String word2) {
int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;

for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1))
p1 = i;

if (words[i].equals(word2))
p2 = i;

if (p1 != -1 && p2 != -1)
min = Math.min(min, Math.abs(p1 - p2));
}

return min;
}```

Shortest Word Distance II – API, will be called multiple times

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = `["practice", "makes", "perfect", "coding", "makes"]`.

Given word1 = `“coding”`, word2 = `“practice”`, return 3.
Given word1 = `"makes"`, word2 = `"coding"`, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: First preprocess the word to dict, which is a <word, list of index>map.

Then every time just get the word only check two list of indexes.

```public class WordDistance {
Map<String, List<Integer>> dict;
public WordDistance(String[] words) {
dict = new HashMap<>();
for(int i=0;i<words.length;i++){
if(dict.containsKey(words[i])){
}else{
List<Integer> indexes = new ArrayList<>();
dict.put(words[i], indexes);
}
}
}

public int shortest(String word1, String word2) {
if(dict==null||!dict.containsKey(word1)||!dict.containsKey(word2)){
return 0;
}
int res = Integer.MAX_VALUE;
List<Integer> indexes1 = dict.get(word1);
List<Integer> indexes2 = dict.get(word2);
int index1 = 0;
int index2 = 0;
while(index1<indexes1.size()&&index2<indexes2.size()){
res = Math.min(res, Math.abs(indexes1.get(index1)-indexes2.get(index2)));
if(indexes1.get(index1)<indexes2.get(index2)){
index1++;
}else{
index2++;
}
}
return res;

}
}```

Shortest Word Distance III – word1 could be the same as word2

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = `["practice", "makes", "perfect", "coding", "makes"]`.

Given word1 = `“makes”`, word2 = `“coding”`, return 1.
Given word1 = `"makes"`, word2 = `"makes"`, return 3.

Note:
You may assume word1 and word2 are both in the list.

Solution: if word1==word2==words[], then p1=p2=i, and every time we update p1, we check the distance between p1 and p2.

```public int shortestWordDistance(String[] words, String word1, String word2) {
int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;

for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
p1 = i;
if (word1.equals(word2) && p1 != -1 && p2 != -1) {
min = Math.min(min, Math.abs(p1 - p2));
}
}

if (words[i].equals(word2)) {
p2 = i;
}

if (!word1.equals(word2) && p1 != -1 && p2 != -1) {
min = Math.min(min, Math.abs(p1 - p2));
}
}

return min;
}```

# Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example

Given the below binary tree:

```  1
/ \
2   3```

return `6`.

Solution: Divide and Conquer. for each node, calculate two maxPath:

1. maxSinglePath: start from root to any nodes, could be empty. 从root往下走到任意点的最大路径，这条路径可以不包含任何点.

2. maxPath: 从树中任意到任意点的最大路径，这条路径至少包含一个点. Max path in the tree, can not be empty, doesn’t have to include root.

So the result is root.maxPath

O(n) time complexity. Each node is visited once.

Version 1. cleaner version, with global variable

```public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/

int maxPath = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
maxSinglePath(root);
return maxPath;
}

public int maxSinglePath(TreeNode root){
if(root==null){
return 0;
}
//devide
int left = Math.max(0, maxSinglePath(root.left));
int right = Math.max(0, maxSinglePath(root.right));

//conquer
maxPath = Math.max(maxPath, left+right+root.val);

return Math.max(left, right)+root.val;
}
}```

Version 2. jiuzhang, with result class

```private class maxPathResult {
int maxSinglePath;
int maxPath;
public maxPathResult(int maxSinglePath, int maxPath) {
this.maxSinglePath = maxSinglePath;//start from root to any nodes, could be empty
this.maxPath = maxPath;//max path in the tree, can not be empty, doesn't have to include root
}
}
public int maxPathSum(TreeNode root) {
return helper(root).maxPath;
}

public maxPathResult helper(TreeNode root) {
if (root == null) {
return new maxPathResult(0, Integer.MIN_VALUE);
}
//devide
maxPathResult left = helper(root.left);
maxPathResult right = helper(root.right);

//conquer
int maxSinglePath = Math.max(left.maxSinglePath, right.maxSinglePath) + root.val;
maxSinglePath = Math.max(maxSinglePath, 0);

int maxDoublePath = left.maxSinglePath + right.maxSinglePath + root.val;

int maxPath = Math.max(Math.max(left.maxPath, right.maxPath), maxDoublePath);
return new maxPathResult(maxSinglePath, maxPath);
}```

# Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree `{3,9,20,#,#,15,7}`,

```    3
/ \
9  20
/  \
15   7
```

return its zigzag level order traversal as:

```[
[3],
[20,9],
[15,7]
]```

Solution: Use two linked list to represent curr level and the next level. While iterating through the node on the current level, we put the child nodes to next level in order based on if the current level is odd or even.

If current is odd level, so next level should be right->left, so we always insert right node in front of left node.

If current is even level, so next level should be left->right, we always insert left node in front of right node.

```public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
while (!curr.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
while (!curr.isEmpty()) {
TreeNode node = curr.remove();
//current is odd level
//so next level should be right->left
if (res.size() % 2 == 0) {
if (node.left != null) {
}
if (node.right != null) {
}
}
//current is even level
//so next level should be left->right
else {
if (node.right != null) {
}
if (node.left != null) {
}
}
}
curr = next;
}
return res;
}```

# First Missing Positive

#### First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

Example

Given `[1,2,0]` return `3`, and `[3,4,-1,1]` return `2`.

Challenge

Your algorithm should run in O(n) time and uses constant space.

```public int firstMissingPositive(int[] A) {
if (A.length == 0) {
return 1;
}
int i = 0;
while (i < A.length) {
if (A[i] != i + 1) {
if (A[i] <= A.length && A[i] > 0 && A[A[i] - 1] != A[i]) {
swap(A, i, A[i] - 1);
} else {
A[i] = 0;
i++;
}
} else {
i++;
}
}
for (int j = 0; j < A.length; j++) {
if (j + 1 != A[j]) {
return j + 1;
}
}
return A.length + 1;
}

public void swap(int[] nums, int a, int b) {
int tmp = nums[a];
nums[a] = nums[b];
nums[b] = tmp;
}```

# Crawler With Sleep(), Condition Variable & Semaphore

Here we have multiple crawlers which infinitely checking if the task table has any task with status=new, if so we take one task then crawl the page. If the page is a list of the links to other page, we create a task for each link and save to task table. If the page is a real news page, we save it to page table. Eventually we read all the real pages from the page table.

# 1. Use sleep()

What we can do is if while check if there is any new task in the table, if not, we make the thread sleep for a certain time.

```void crawler() {
while (true) {
//before reading, needs to lock the table
if (taskTable.find(state == 'new') == null) {
//give up the lock if there is nothing to consume
sleep(1000);//*
} else {
//release the lock;
//if page.type is a page including a list of links to the news
}
}
//if page.type is a news page,
else {
lock(pageTable);
release(pageTable);
//we still need to update the task by setting the status to be "done"
}
}
}
}```

So the problem using sleep is:
1. 在每次轮询时，如果t1休眠的时间比较短，会导致cpu浪费很厉害；
2. 如果t1休眠的时间比较长，又会导致应用逻辑处理不够及时，致使应用程序性能下降。

# 2. Conditional Variable

1. 释放Mutex
2. 阻塞等待
3. 当被唤醒时，重新获得Mutex并返回

In this case, we put all the waiting crawler thread into cond.waitList if there is any.

## cond_wait(cond, mutex):

```cond_wait(cond, mutex) {
lock(cond.waitList);
release(cond.waitList);

release(mutex);
sleep()；
lock(mutex);
}```

## How to use cond_wait()?

```lock(mutex);
while (!condition） {
cond_wait(cond, mutex);
}
change the condition
unlock(mutex);```

## cond_signal(mutex):

```cond_signal(cond) {
lock(cond);
if (cond.waitList.size() > 0) {
}
release(cond);
}```

## How to use cond_signal(mutex)?

```lock(mutex);
set condition = true;
cond_signal(cond);
unlock(mutex);```

## So the crawler will become:

```void crawler(){
while(true){
//it has to be while instead of if
}

cond_signal(cond); //*
}
}else{
lock(pageTable);
unlock(pageTable);

}
}
}```

# 3. Semaphore

## wait(semaphore):

this means if semaphore is larger than 0, if not, it starts waiting until both happens:

1. semaphore.value>=0

2. someone wakes it up

```wait(semaphore){
lock(semaphore);
semaphore.value--;
while(semaphore.value<0){
release(semaphore);
block(this.process);
lock(semaphore);
}
}```

## signal(semaphore):

```signal(semaphore){
lock(semaphore);
semaphore.value++;
if(semaphore.processWaitList.size()>0){
process = semaphore.processWaitList.pop();
wakeup(process);
}
release(semaphore);
}```

## So the crawler now becomes:

```while(true){
//we are not querying taskTable here so no need to lock taskTable

}
}else{
lock(pageTable);
release(pageTable);

}
}```

Ref: jiuzhang.com

# System Design SNAKE原则 (以NetFlix为例)

1. Scenario
2. Necessary: constrain/hypothesis
1. Daily active user? Ask! eg. 5,000,000
2. Predict
1. User
1. Average Concurrent Users = daily_active_user * average_online_time / daily_seconds
= 5,000,000 * (30*60) / (24*60*60)
= 104,167/s
2. Peak users = average_concurrent_users * 6 = 625,000/s
2. Traffic
1. Video traffic speed = 3mbps
2. MAX
3. Memory
1. Memory per user = 10KB
2. MAX daily memory = 5,000,000 * 2 * 10 = 100GB
(T级以内的内存都是可以解的)
4. Storage
1. Total movie = 14,000
2. Movie storage (视频会有不同版本) = total_movie * average_movie_size = 14,000*50GB = 700TB
3. Application: service/algorithm 模块设计
4. Kilobit: data 数据设计， 不同数据的存储模型
1. 比如用户服务可以用mysql, 查询逻辑强
2. 电影文件就用文件存，不用数据库
5. Evolve: 和面试官沟通
1. Step1: Analyze
1. with
1. More constrains
2. New use cases
3. Deeper, more details
2. from the views of
1. Performance
2. Scalability
3. Robustness
2. According to 面试官, 加深某一部分的设计

# Producer & Consumer with Java wait(), notify() and notifyAll()

1. Keywords & Methods:

• Synchronized
• `synchronized` keyword is used for exclusive accessing.
• To make a method synchronized, simply add the synchronized keyword to its declaration. Then no two invocations of synchronized methods on the same object can interleave with each other.
• wait()
• Tells the calling thread to give up the monitor and go to sleep until some other thread enters the same monitor and calls notify().
General syntax for calling `wait()` method is like this:

```synchronized (lockObject){
while (!condition) {
lockObject.wait();
}
//take the action here;
}```
• notify()
• Wakes up the first thread that called `wait()` on the same object. It should be noted that calling `notify()` does not actually give up a lock on a resource. It tells a waiting thread that that thread can wake up. However, the lock is not actually given up until the notifier’s synchronized block has completed. So, if a notifier calls `notify()` on a resource but the notifier still needs to perform 10 seconds of actions on the resource within its synchronized block, the thread that had been waiting will need to wait at least another additional 10 seconds for the notifier to release the lock on the object, even though `notify()` had been called.
```synchronized(lockObject)

{
//establish_the_condition;

lockObject.notify();

}//lock is given up after synchronized block is ended```
• notifyAll()
• Wakes up all threads that are waiting on this object’s monitor. The highest priority thread will run first in most of the situation, though not guaranteed. Other things are same as `notify()` method above.
```synchronized(lockObject)
{
establish_the_condition;

lockObject.notifyAll();
}```

2. Example

Producer and Consumer:

1) Producer thread produce a new resource in every 1 second and put it in ‘taskQueue’.
2) Consumer thread takes 1 seconds to process consumed resource from ‘taskQueue’.
3) Max capacity of taskQueue is 5 i.e. maximum 5 resources can exist inside ‘taskQueue’ at any given time.

Producer:

```public class Producer implements Runnable {
private int MAX_CAPACITY;
//instead of having an int counter,
//we use a wrapper object, so that it can be passed by reference
private Counter counter;

public Producer(List<Integer> taskQueue, int max_capacity, Counter counter) {
this.MAX_CAPACITY = max_capacity;
this.counter = counter;
}

@Override
public void run() {
//infinite loop so that producer keeps producing elements at regular interval.
while (true) {
try {
//here it has to be while instead of if since if after it is waken up,
//someone else takes the lock and change the taskQueue size
//if check will still go through and start producing
": Queue(size=" + taskQueue.size() + ")is full, now start waiting...");
}
//simulating time delays in consuming elements.
counter.increase();
//Calling notifyAll() because the last-time wait() method was called by consumer thread
//(that’s why producer is out of waiting state), consumer gets the notification.
} catch (InterruptedException e) {
e.printStackTrace();
}
}
//do something else
}
}
}```

1) Here “`produce(counter++)`” code has been written inside infinite loop so that producer keeps producing elements at regular interval.
2) We have written the `produce()` method code following the general guideline to write `wait()` method as mentioned in first section.
3) Once the `wait()` is over, producer add an element in taskQueue and called `notifyAll()` method. Because the last-time `wait()` method was called by consumer thread (that’s why producer is out of waiting state), consumer gets the notification.
5) Note that both threads use `sleep()` methods as well for simulating time delays in creating and consuming elements.

Consumer:

```public class Consumer implements Runnable {

}

@Override
public void run() {
//infinite loop so that consumer keeps consuming elements whenever it finds something in taskQueue..
while (true) {
try {
": Queue(size=" + taskQueue.size() + ")is empty, now start waiting...");
}
//simulating time delays in consuming elements.
//Once the wait() is over, consumer removes an element in taskQueue and called notifyAll() method.
//Because the last-time wait() method was called by producer thread
//(that’s why producer is in waiting state), producer gets the notification.
} catch (InterruptedException e) {
e.printStackTrace();
}
}
//do something else
}
}
}```

1) Here “`consume()`” code has been written inside infinite loop so that consumer keeps consuming elements whenever it finds something in taskQueue..
2) Once the `wait()` is over, consumer removes an element in taskQueue and called `notifyAll()` method. Because the last-time wait() method was called by producer thread (that’s why producer is in waiting state), producer gets the notification.

Counter:

Noted that we need a counter as an id for each task. Since we might need more than one producer, instead of passing int or Integer(both of them are immutable), we need to have a wrapper object so that we can pass by reference to be shared between multiple producers.

```public class Counter {
int val;
public Counter(){
val = 0;
}
public void increase(){
val++;
}
public void decrease(){
val--;
}
}```

Test:

```public class ProducerConsumer {
public static void main(String[] args) {
Counter c = new Counter();
tProducer1.start();
tProducer2.start();
tConsumer1.start();
tConsumer2.start();
}
}```

Output:

Producer1: Produced:0
Producer1: Produced:1
Consumer2: consuming 0
Consumer2: consuming 1
Consumer1: Queue(size=0)is empty, now start waiting…
Producer2: Produced:2
Consumer1: consuming 2
Consumer2: Queue(size=0)is empty, now start waiting…
Producer1: Produced:3
Consumer2: consuming 3
Consumer1: Queue(size=0)is empty, now start waiting…
Consumer2: Queue(size=0)is empty, now start waiting…
Producer2: Produced:4
Consumer2: consuming 4
Consumer2: Queue(size=0)is empty, now start waiting…
Consumer1: Queue(size=0)is empty, now start waiting…
Producer1: Produced:5
Producer1: Produced:6
Producer1: Produced:7
Producer1: Produced:8
Producer1: Produced:9
Producer1: Queue(size=5)is full, now start waiting…
Consumer1: consuming 5
Consumer2: consuming 6
Consumer2: consuming 7
Consumer2: consuming 8
Consumer2: consuming 9
Consumer2: Queue(size=0)is empty, now start waiting…