脸家面经，感谢各位大哥求放水。。

只有三轮不知道是不是不招人了随便面一下。但是各位大佬认真的很好。两个国人大哥做题，一个白人大叔主要behavior。
第一个把下面的格式的字符串变成树：node有键，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

成03ab02cd01ee的压缩。都两个两个的考虑
第三个国人大哥在k个排序list里找中位数

第三题我有两种解法 权当抛砖引玉
假设共N个元素， K个list

您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2018-4-3 08:35):
这里均假设N远大于K，否则暴力解法即可

第三题假设k个数列，每个数列平均长度n。
暴力一点，对数值二分（initial_min=int_min, initial_max = int_max），对于每一个猜测的数值，都能在log(n)内得出每个数列中有多少个大于/小于这个int，从而得到全部数列中有多少个数小于这个值。
所以每一次二分耗时k*log(n)，总复杂度还是k*log(n)

第三题怎么做啊

不招人了？...

同问第三题怎么做啊？最naive的是merge到一起去中间那个，可是不会这么简单吧。。。

第一题就是给的这种格式么？LZ 怎么parse的啊

houqingniao 发表于 2018-3-26 06:56
第一题就是给的这种格式么？LZ 怎么parse的啊

第一题用两个stack可以做把，一个用来存tag，一个用来存treenode，

同问第三题。
两个的话还可以binary search到log(n1+n2)
k个的话只能想到先1pass确定长度，再用PQ来输出一半这种感觉O(n+logk)

第一题是我当时电面的题。我构造了一个Node data structure. 里面有name 和 value，分别存node1， aaaa这种string值。然后read char one by one。如果遇到<就检测下一个字符是不是/。不是就一直读下去，遇到下一个就把之前的入栈，然后存name和value。是“/”就出栈。

不太明白第一题，怎么判断父节点和相应的子节点？<node1>aaaaa<node2>bbbbb</node2><node3>cccc</node3><node4>dddd</node4></node1>

foreveriii3 发表于 2018-4-1 17:09
同问第三题。
两个的话还可以binary search到log(n1+n2)
k个的话只能想到先1pass确定长度，再用PQ来输出 ...

我觉得是先计算总长假设为N，然后K个序列都取min（各自长度，N/2/K），这些值互相比较，除了最大的那个，其余的都可以去掉。二分法。