脸书 昂塞

找人内推了一波。
hr安排了店面：number of islands, follow up 输入数据量很大该怎么办~

然后约了一周之后的昂塞：
1. 一道蠡口腰斯散，楼主刷题不精没做过，当场现做，还被好几次友情

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

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

n了。还是有很多要补充，要学习的地方。
个人感觉面试是不难的，但是就是要控制自己紧张的心情在面试中，自己安静下来一个人做这些题其实很快的。大家加油！

第三题可以用presum做吧，应该是o(n)。

第四题 按联系人做union find 联系关系用hashmap+联系人ID来取得
比如 1: a@b.com, b@c.com
       2 :b@c.com, d@e.com
hashmap 存成{  b@c.com :{1,2}, a@b.com:{1},d@e.com{2}}
之后每个key - value pair 在hashmap中找union关系 就可以了
写了一下

1. def findgroup(data):
   
2.     relationgraph = {}
   
3.     email_to_user = {}
   
4.     def find(x):
   
5.         while relationgraph[x]!=x:
   
6.             x = relationgraph[x]
   
7.         return x
   
8.     def union(x,y):
   
9.         pa = find(x)
   
10.         pb = find(y)
    
11.         if pa!=pb:
    
12.             relationgraph[pa] = pb   
    
13.     for key in data:
    
14.         relationgraph[key] = key
    
15.         for email in data[key]:
    
16.             if email in email_to_user:
    
17.                 for user in email_to_user[email]:
    
18.                     union(user, key)
    
19.                 email_to_user[email].add(key)
    
20.             else:
    
21.                 email_to_user[email] = set([key])
    
22.     res = collections.defaultdict(list)
    
23.     for x in relationgraph:
    
24.         if relationgraph[x] == x:
    
25.             res[x] += [x]
    
26.         else:
    
27.             res[find(x)] += [x]
    
28.     return res.values()

复制代码

run了一个case

1. data = {1:["a@b.com","b@c.com"],2:["b@c.com","e@g.com"],3:["b@c.com","e@g.com"],
   
2.        4:["r@t.com","r@f.com"]}
   
3. print findgroup(data)

复制代码

似乎可以  :)

第三题写了下 O(n) && O(n)，不知道对不对
    public boolean subArraySum(int[] nums, int target) {
        if(nums == null || nums.length < 1) return false;
        Set<Integer> sums = new HashSet<>();
        sums.add(0);
        for(int i = 0; i < nums.length; i++) {
            nums[i] += (i > 0) ? nums[i - 1] : 0;
            if(sums.contains(nums[i] - target)) return true;
            sums.add(nums[i]);
        }
        return false;
    }

第四题是 期儿一 吧？
第三题有负数吗？

kevinxw 发表于 2018-5-5 03:39
第四题是 期儿一 吧？
第三题有负数吗？

第三题应该有负数，没问~汗
第四题给的key是联系人，所以不会重复，value是这个联系人的一些邮箱。看上去和其儿一有些像，但是差别还是很大的。

xdsb1989 发表于 2018-5-5 04:00
第三题应该有负数，没问~汗
第四题给的key是联系人，所以不会重复，value是这个联系人的一些邮箱。看上 ...

有负数好像就只能 O(n^2)了，不然全是正数的话就是一路加，加到sum超过target就减掉第一个数，是这个意思吧？
第四题我感觉key重复不重复好像也没啥关系。union find还是根据email来建的。利口那道题也不关名字啥事，就是最后输出的时候用一下

感觉设计题还挺难的

Yihead 发表于 2018-5-13 05:32
第三题可以用presum做吧，应该是o(n)。

我觉得第三题应该还有限制条件，如所有的数为非负整数什么的。否则如果输入有正有负，那么就没法提前终止而必须看到数组最后一个数。要是有这个限定条件，算法就会简单很多


if (s==null || s.length == 0) return false;
i=0, j=1;
sum=s[0];
while (i < s.length && j < s.length) {
   if (sum == target) return true;
  else if (sum > target) {
    sum -= s[i++];
  } else {
    sum += s[j++];
  }
}
return false;

第四题leetcode有，你搜搜，unionfind

crusader1812 发表于 2018-5-14 07:49
我觉得第三题应该还有限制条件，如所有的数为非负整数什么的。否则如果输入有正有负，那么就没法提前终止 ...

@Yihead 说得没错，可以用presum

presum[i]存s[0]+...+s[i]的值，然后存进hash，然后对每个presum[j]，如果hash里能找到presum[j]-target，则i~j满足条件。每步O(1)，全程O(n)