## Friday, May 6, 2016

### Twitter Interview Misc Part 2

print all acyclic path in a graph

1. 先loop一遍，分别把每个节点的后序节点存起来到hashmap<node, List<node>>里.

2. 从起始点开始，做dfs，用hashmap记录这次路径上出现过的点，遇到出现过的或者没有后续节点的就停止（按照楼主的提示，应该每一层都加到结果的List里。。）

1.find integer appear odd times in an array
a. one odd count integer
b. multiple odd count integers
2. shortest path in 2d array with obstacles, given start and end point
a. output shortest path length
b. output indexes of the path nodes.

269 Alien Dictionary
336 Palindrome Pairs

84 largest rectangle in histogram

Input format:
N        // count of number in the input
d[0]        //1st number
d[1]        //2nd number
...
d[n-1]        //last number

Output format:
The first line contains a string of n bits, where the i-th bit (as read from left to right) indicates if there is any number before b which is equal to b.
The second line contains a string of n bits, where the i-th bit (as read from left to right) indicates if there is any number after b
which is equal to b.
Sample input:
6        //total 6 numbers given below
1
3
2. 鍥磋鎴戜滑@1point 3 acres
3. 鍥磋鎴戜滑@1point 3 acres
1
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
Sample output:
000101
110000

Return the count of numbers X in the range 1<=X<=N that satisfy the following property:
(X-1) !  % X = X-1

Input Parameter:
A single integer N
Constraints:
1 <= N <= 10^5
Output Format:
A single integer which in the count of the numbers that satisfy the above property.

Sample Input:
2
Sample Output:
2

Sample Input:
4
Sample Output:
3

//1) Given a post-fix expression as a space delimited string with +, -, *, / operators, and double value, evaluate an expression. e.g. "5 3 + 2 / 1 +" -> " (5 + 3 )/ 2 + 1" => 5
2) you have N mysql databases that return results in order, you need to build an API that returns the completely ordered lists, how will you solve this problem.

3) Given a text file that is delimited by either \$ or whitespace, how will you find top k words (Linux Commands)cat \$FILE_NAME | tr '\$' ' ' | tr ' ' '\n' | sort | uniq -c | sort -bnr | top k就是把delimiter替换成换行，然后按每个词排序，计算每个词出现次数，再取top

4) How many null pointers will there be in a binary tree with n nodes, where each node has two children ... one for left child, and another for right child?

https://www.quora.com/How-many-null-nodes-will-a-binary-tree-with-20-nodes-have
How many null nodes will a binary tree with 20 nodes have?
Consider a binary tree of n nodes.
Each node will have 2 pointers (may or may not be null). So the tree will have 2n pointers.
There are n nodes. Excluding the root node, every node must have a pointer pointing to it, i.e., n-1 not-null pointers.
So, no. Of null pointers = 2n - (n - 1) = n+1
1. 上来一个ABC小哥问我cache system，首先大致介绍一下什么是cache system以及用途，然而并没有问LRU cache，而是写LFU（Least Frequent Used），其实思路是一致的。implementation不再是用linked list，而是用一个priority queue来实现。
2. 第二个是一个白人小哥，稍微严肃一点，不过总体问题不算难。assuming tweet 包含（tweet id，内容，然后user id，信息），现在有两个API，GetTweetInfoByID（得到tweet 内容和user id），and GetUserInfoByID（得到user info），然后提供一个list的tweet ID，return 包含所有信息的tweet list，并且按照tweet的时间排序输出。 说白了，就是给你一串Id，然后通过两个API得到tweet的所有信息，然后排序输出。 午饭时间：基本是自助的形式，风格也很多，基本满足各种需求，饮食感觉还是很不错的。
3. 一个tag reorder的问题，一开始的形式是（tweet id -> tags）,现在更改了形式变成了 （tag -> tweet Ids）。现在给定一组更改前的，一组更改后的，但是这些数据有一定的偏差，所以要求哪些id上面的tag在reorder之后丢失了。 基本也就是把更改前的数据，按照逻辑换成目标模式，然后跟第二组数据进行对比，然后看看哪些tag丢了
4. distributed system： 总体意思就是用户可以提前定义发送tweet的时间，然后问分布式的服务器怎么消化那些潜在时间段的高流量的tweet发送。（本人不太懂分布式的东西，基本就是瞎扯的） 5. word break2.

然后设计一个ATM， OO design。 然后behavior一轮。

1.   static boolean ab(String a, String b) {
2.     Map<Integer, Long> ma = a.chars().boxed()
3.         .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
4.     Map<Integer, Long> mb = b.chars().boxed().鏈枃鍘熷垱鑷�1point3acres璁哄潧
5.         .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
6.     for (Integer i : mb.keySet()) { 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
7.       if (ma.containsKey(i) && ma.get(i) >= mb.get(i)) {
8.         // nop
9.       } else {. visit 1point3acres.com for more.
10.         return false;
11.       }
12.     }
13.     return true;
14.   }

.1point3acres缃�

3. 设计两个api, log_visit(), num_of_log_visit_last_5_mins()
4. 远程会议，白人。search problem, dfs解决，简单不说了。

javascript题：给一个string，输出另一个string，要求每一个字母间间隔一个空格，例如 输入 “hello world” 输出 “h e l l o w o r l d”写完要求用test case 测试
2 LeetCode Single Number，用java写的。

Twitter Onsite (Web client team)1 Leetcode Text Justification 2 Behavior questions
3 3.1 有一个function， 输入是一个string， 表示一个twitter post。 输出是一个string，但是里面的url都换成了一个24个字符的string。问如果让你unite test， 你会写哪些unit test case。（只写出你觉得需要的case即可，不需编程）。
3.2 javascript里有三个关于event的function，addEventListener(), removeEventListener(), dispatchEventListener(); 设计javascript data structure 实现这三个功能

Given a set of intervals on the number line, find the longest ordered sequence (consecutive in original order) of (a subset of) the intervals such that each consecutive interval is nested inside the previous one.“Nested” means this: If interval X is nested inside Y, then Y.a < X.a and X.b < Y.b. E.g. given [, , , , ] Return: [, , ]

Follow-up #1: Given a set of intervals on the number line, find the longest ordered sequence of (a subset of) the intervals such that each consecutive interval is nested inside the previous one.“Nested” means this: If interval X is nested inside Y, then Y.a < X.a and X.b < Y.b. E.g. given [, , , , , ] Return: [, , , ]

Follow-up #2: Given a set of intervals on the number line, find the longest sequence of (a subset of) the intervals such that each consecutive interval is nested inside the previous one.“Nested” means this: If interval X is nested inside Y, then Y.a < X.a and X.b < Y.b.Note: the original order doesn't need to be maintained. E.g. given [, , , , , ] Return: [, , , ]

1. 不用recursion遍历Binary Tree 设计 twitter ， 都还好。
2. 给really large streaming data, 用O(n)时间找出第k大的数。国人大哥几经提醒终于做出来了。
stream实现O(N)是： 1. 读2k个数到buffer 2. quick select找到第k大的数，和比他大的数。现在buffer里面一共k个数。 耗时O(k) 3. 重复1， 直到读完。一共O(n/k)次。

follow up上面你用了extra memory来产生有序的结果，那不用extra memory怎么做？  这里没让写code，只需给idea。这里可以观察permutation的规律，类似next permutation那道题，说了一下大概的idea，要解释清楚。