脸家现场表演

10/07的UDay，10/14收了口头offer.


第一轮: 1) 一串儿数字，要求找出出现次数为奇数的那个数（仅有一个或不存在）。             2)利口幺六腰  要求想

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

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

和什么样的同事工作，你领导给过你的建设性的反馈，etc。反手出了一道 利口溜尔伊 变种 要求preserve task order

面完还以为挂了，无心参加后续游园活动，于是吃完午饭就溜了。

yiliaobailiao 发表于 2019-10-15 23:11
请问 第二轮第一题，怎么能在O（1）时间内实现呢？

类似LRU？
1. 用一个doubly linkedlist（或者LinkedHashMap）来维护插入元素的顺序
2. 再用一个HashMap 来记录unique元素在DLL中的位置（key：char， value：Node）
3. 还需要一个HashSet seen记录见过的重复元素

对于下一个元素，先看是不是存在于seen，如果不在但是存在于DLL，从DLL删掉（O(1)），并加入seen，如果是第一次见到，那么从末端插入（O(1))，最后返回头端的元素。

yiliaobailiao 发表于 2019-10-15 23:11
请问 第二轮第一题，怎么能在O（1）时间内实现呢？

我是用了一个double ended queue + hashmap.
Use the hashmap to keep track of number of occurrence for each element. When we see a new character, check from the head of the queue and remove nonunique characters.

thyang93 发表于 2019-10-16 01:06
I don't think this is amortized O(1). If you use a queue, each time you scan through the elements  ...

Assuming you encounter the duplicate character at index (n+1), you only need to do a O(n) scanning at the (n+1)-th time of data feed. (Since it's a data stream, you process character one at a time.) Since we do O(n) scanning per n times of data feed call, the operation is amortized O(1). Please follow up if things are still not clear.

And yes, you were right that we only need a hashset to tell if a character has been seen before. That's what I did in the interview.

10.3 uday 没结果的是不是凉了

请问 第二轮第一题，怎么能在O（1）时间内实现呢？

thyang93 发表于 2019-10-15 23:49
类似LRU？
1. 用一个doubly linkedlist（或者LinkedHashMap）来维护插入元素的顺序
2. 再用一个HashMap ...

哦哦。明白了。多谢多谢

taikoolyd 发表于 2019-10-15 19:55
10.3 uday 没结果的是不是凉了

不一定吧。因为我15号有个offer deadline，所以可能加快给我结果了？

吉姆一帆风顺 发表于 2019-10-16 00:31
我是用了一个double ended queue + hashmap.
Use the hashmap to keep track of number of occurrence f ...

I don't think this is amortized O(1). If you use a queue, each time you scan through the elements in the queue, it will take O(n). Also, as you stated, we only need to check if a char is unique, we probably do not need to cache the occurrence of a char, we just need to know if it has been seen.

恭喜lz，紫薯紫薯