Twitter Interview Misc Part 2

http://www.1point3acres.com/bbs/thread-187666-1-1.html
print all acyclic path in a graph

就只有这一句很简单话 LZ先问 有向图吗 小哥说 你可以自己假设 LZ选择了假设有向图 然后我问图中有环吗 小哥说了acyclic path LZ当时就以为没有环 然后写了基本的DFS 写完之后 小哥说 看起来不对啊 然后小哥给我写了一个test case（没写这个case的答案）然后我才明白过来原来有环 然后很快就改好了代码 然后run 小哥又说不对！此时LZ内心是崩溃的 你到底要怎样 小哥这才把他写的test case的正确结果给了出来 

大概是这样的 输入1-->2 1-->3 1-->4 2-->3 3-->1 3-->2  然后LZ的code print的是 1,2,3   1,3,2  1,4  但是小哥要的其实是1; 1,2; 1,2,3; 1,3; 1,3,2; 1,4 就是要把每条路上的所有结果都print出来 但是没时间改了 小哥说没关系就这样吧 然后他问了时间复杂度 我分析了之后 小哥就说结束了

输入还有告诉你start node 就是path从哪个点开始走
如果这是一个complete graph 告诉start node 那么一共有多少条path
1. 先loop一遍，分别把每个节点的后序节点存起来到hashmap<node, List<node>>里.

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

还有就是每次recursion都先print一下 这样才能得到1; 1,2; 1,2,3这种  时间复杂度我也不会很会算 感觉像是n! 因为给定起点的complete graph有(n-1)!条能包含所有node的path

http://www.1point3acres.com/bbs/thread-185897-1-1.html
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.
第一题用hashset，如果在hashset里面就remove，最后剩下的就是odd count
第二题给了point的class存了x y坐标，小哥说可以修改，就在里面加个parent pointer
https://instant.1point3acres.com/thread/176754
269 Alien Dictionary 
336 Palindrome Pairs 
第三题是给了一个height的array，求连续的最大面积，忘记是leetcode上哪道题了～～～筒子么自己找找（这题她给了 暴力法，让我说code的意思，然后让我improve，哎，讨论了半天我也没做出来。。跪了。。只恨之前没有再刷一遍难题，侥幸心理不能有）
84 largest rectangle in histogram
https://instant.1point3acres.com/thread/154909
然后coding题目是 Alien dictionary 幸好在地里看了面经。。问了一下如果有loop怎么办 可能有多个序列怎么办 然后改了一下代码 也没跑 感觉有bug 

如果都输出的话思路应该是什么样的？如果用bfs做的话，每一层indegree为0的点都作permutation?

http://www.1point3acres.com/bbs/thread-188999-1-1.html
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
4. more info on 1point3acres.com
1
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
Sample output:
000101
110000
这题我在做之前看地里其他帖子分享过,我是用HashSet来做
第二題:
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

这题我作之前没看过,所以一看到有点慌,我列了N= 1~7的结果后,猜测就是在找prime number (时间不够,没想到怎么证明...),幸运通过所有test cases,

http://www.1point3acres.com/bbs/thread-185575-1-1.html
//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?
这题比较tricky,但是还是可以想通的，一棵树总共有   2 *n个 (left, right pointer)   然后有多少是 root指向child的呢？ n - 1个，所以为null的是n + 1个. visit 1point3acres.com for more.
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

https://instant.1point3acres.com/thread/177640
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. 

https://instant.1point3acres.com/thread/144247
第一轮 在log file里找东西 0 xxxxxx 1 xxxxxxx 5 xxxxxx 20 xxxxxx 35 xxxxxx 前面数字是timestamp，后面是内容。给你个range[7, 28], 让你找bytes的offset分别是多少。 

就是把整个log file当一个stream，然后找出比如 0 abcde 1 abc 2 abcd 你就return （8， 12）， 因为第一行有7byte，第二行5byte，所以前面的offset的开始就是第8byte，然后结尾的offset就是第12byte

第二轮是render tweets Inout: { id: 0, reply_to_id: 3; id: 1, reply_to_id: 0} 如果reply to是0，就是主tweet，否则是回复。让你存住这个，并且render。每有一个新tweet最快让它在相应的tweet thread下显示。 


知道JSON么？就是以这种形式的file来存你界面上twitter的关系。比如我是楼主，你回复我，我可以回复你的回复，这关系就是一层套一层。每一个发言都自己有个编号，它同时也是对另一个编号的reply

不好意思再打扰一下，就是说，输入的是json，json是一层层的关系，比如，如果A回复B回复C，那么输入的json大概如下：[A [B [C ]]]，现在要求的输出形式是A reply to id B, B reply to id C。不知道我理解的对不对，或者还是说我理解反了，输入是A reply to id B, B reply to id C，输出是[A [B [C ]]]，这道题的难点是什么呢？谢谢了。

还没你说的那么复杂，JSON就只有一层，每一个tweet就只对应一个reply。你说的就是C是1，B是2，A是3，然后JSON file就是[id: 1, reply: 0; id: 2, reply: 1; id: 3, reply: 2;]

任务是你自己用一个方法去render一个回复界面，你要用啥储存以上信息，并implement。至于你用什么data structure储存随你。难点在于Tree根本是错的，他说有更好的方法，也没告诉我。囧

这个解释很清楚了，所以就是输入是json那样的一层结构，要求的是你怎么存储并且输出tweets。. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴

感觉如果用tree是很直观的，因为每个tweet到最后若干人回复，就会扩展成tree的样子。我猜你的思路是这样的，对吧？

我感觉似乎也可以以每个人为主体，构成一个图，A回复了B表示 A指向B，然后再在每个node里面存储tweet的具体内容，具体可能需要再讨论。

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



最后一轮给一个string a, string b，查用a的字母能否拼出b。每个字母只能用一次。 
不过他说两个string都有可能很长很长。所以不要一次性把一个string都读完，要两个string一位一位读

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

首先要讨论一下string是什么编码 有多少种不同的character的可能性
.1point3acres缃�
如果是ascii的话 可以用一个 array 做map
如果string 只有字母 那一个size 52的 array 就够了

我猜面试官想考的是
假设如果有很长一个string 不能放到全部放在memory里 应该怎么办

这时候应该带用pointer 一部分一部分的读string 进来
同时跟面试官说
因为一位一位读进来 每次下到hard disk 这个constant opreation
实际上的time比较长
所以我要bring  a chunk of string to memory 再去读
https://instant.1point3acres.com/thread/177490
1. 美国妹子，在twitter工作了1年半。给两个字符串，target, source, 看target可以由source中的字符组成吗？follow up:source 很长
 2. 设计一个timer，每个一段时间run一个函数。follow up, 设计一个multi-timer
 3. 设计两个api, log_visit(), num_of_log_visit_last_5_mins() 
4. 远程会议，白人。search problem, dfs解决，简单不说了。

https://instant.1point3acres.com/thread/176875
给一个二维char array， 有的地方是墙，用x表示，例如 . . . . . .. . . x . .. x x . . .. . . . . . 同时给出起点和终点，可以向上向下向左向右走，有墙的地方不能走，求起点到终点的最短路径是多长。 

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 实现这三个功能 

https://instant.1point3acres.com/thread/177004
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: [, , , ]

https://instant.1point3acres.com/thread/139423
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)次。

3. 一个印度人，read4Bytes，分析好了写到一半突然问我“你以前一定做过这个题吧？”我说和同学讨论过类似的场景，他说，换一个，那时候还有15min...问我，给我50个bytes，不知道对方发来的内容是什么，怎么判断这个收到的消息是大端序还是小端序。我答的是协议上规定一个固定的帧结构。 版上有更好的解法嘛？

https://instant.1point3acres.com/thread/173166
然后coding，给一个2D matrix， 0表示路，1表示墙，给个start point和end point，求最短路径。直接上了bfs~ 

https://instant.1point3acres.com/thread/174452
让写text justification的程序了吗？还是说思路就行了呢？ 程序啊。这题也没啥特别思路吧主要看corner case

http://www.1point3acres.com/bbs/thread-173468-1-1.html
一道permutation。lz一开始没有用dfs做，直接用不断swap的方法来产生permutation（这样产生的Permutations是无序的），你这个国人大哥你这方法最后一个permutation是多少。有点卡壳，后来提示可以用草稿纸算一下，并且证明给他看怎么的出来的。

follow up如果要产生的Permutation有序怎么做？ 用dfs加个boolean数组，最基本的方法

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

https://instant.1point3acres.com/thread/172547

我说那就用HashMap吧，写好后优化成了HashSet，
没有就加，有就移除