11/04 热腾腾的狗家电面，求onsite

听说面完到地里来报个面经拿到onsite的概率会变大？面完就来分享了（之前快码完了结果不小心页面被关了，再次码完分享，只求onsite）

约的美东下午2点，准时来了LA的电话，3分钟相互寒暄之后直接上题。

1.Given a text file, remove all the duplicate lines, maintaining the order such that the first occurrences of the lines stay in the same order.
照例先问file size,能不能用extra space。小哥说take it easy你开心就好 ，于是用hashset解决，我问能不能把input简化成int[] array存hashcode,小哥先问了how to hash和conflict的问题，然后问存hashcode的话本来的出现顺序如何维护，我说加个map。小哥同意，于是1分钟码完，中间出个小bug,因为用的hashset,小哥问顺序如何维护，我说那就linkedhashset,他同意。
follow up就是常规的file size大到内存放不下怎么办，我就说split into small pieces然后sorting去重

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

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

r的确只会那两种解法，挂了我也认了，毕竟白人小哥从头到尾套路太深，真的不知道他是想故意放水还是来个十动然拒。。接下来刷题一定要多想solution, 多想follow up。

不求大米，只求好运，给个onsite吧！



补充内容 (2016-11-10 03:56):
今天中午收到hr电话给onsite了，感谢白人小哥放水

补充内容 (2016-11-10 03:58):
打算预约12.15左右的onsite, 如果有12月onsite狗家的同学欢迎加微信sunyu566376一起准备面经题

duziyuanyang 发表于 2016-11-10 22:38
如果用unordered_set的话请问如何保证set里元素在text里的出现顺序呢

不知道我是不是有点没太理解题意，lz说的是不是读入一个文件中所有的行，按照原有顺序输出每行数据，如果遇到重复的，保留第一次出现的数据，其他的重复元素不输出？ 如果这样的话，我的意思是set用来保存读入的数据，起到去重作用，输出还是照常输出，不管是直接打印还是说写到另外的文件中，set跟输出没关系。原有的文件中的行的顺序就是遍历这个文件读入数据的顺序吧

duziyuanyang 发表于 2016-11-11 23:32
比如原来是[1,1,2,2,2,3,3], hashset里是[3,2,1]或者是[3,1,2], 请问你的方法如何返回[1,2,3]

1. vector<int> output;
   
2. set<int> st;
   
3. for(auto a : input){
   
4.         if(st.count(a) > 0)
   
5.                 continue;
   
6.         else{
   
7.                 output.push_back(a);
   
8.                 st.insert(a);
   
9.         }
   
10. }
    
11. return output;

复制代码

请问楼主是怎么回答how to hash和conflict的问题？

prodigalr 发表于 2016-11-5 04:51
请问楼主是怎么回答how to hash和conflict的问题？

就是讲一下hash function还有两种collision ,说下利弊

Lz能不能讲讲第一题具体怎么做
用map是存什么信息

jiongjiongyoush 发表于 2016-11-5 05:15
Lz能不能讲讲第一题具体怎么做
用map是存什么信息

打个比方，本来文本里存的是google-> onsite->google-> onsite->wanted, 假设"google"的 hashcode是2, "onsite"的dashcode是"1", wanted是"0", 我们不能根据hashcode的大小来决定相对顺序，所以需要先把string-> hashcode的mapping关系先记录下来

duziyuanyang 发表于 2016-11-6 10:27
打个比方，本来文本里存的是google-> onsite->google-> onsite->wanted, 假设"google"的 hashcode是2, "o ...

存string和hashcode是怎么保持order呢。。。。TT没懂
hashcode是指hashvalue么，如果有collision怎么办

fresh grad但是是猎头找的？

jiongjiongyoush 发表于 2016-11-6 10:53
存string和hashcode是怎么保持order呢。。。。TT没懂
hashcode是指hashvalue么，如果有collision怎么办

你可以自己强制性的把"google"的hash value map 成0， "onsite"的hashvalue-> 1, "wanted"->2这个样子，相当于做一个normalization

freeaccount 发表于 2016-11-6 11:02
fresh grad但是是猎头找的？

hr联系的

lz说的第一题，如果用C++的话，应该直接用个unordered_set记录已经输出过的数据就可以了吧，set中没有的就输出并且记录在set中，set中有的就不输出，而且，感觉很多hash function基本都是语言的标准库提供，还需要自己设计吗