一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2192|回复: 20
收起左侧

Google店面,求过

[复制链接] |试试Instant~ |关注本帖
guixi107 发表于 2016-2-2 03:29:39 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
1月18号的Google技术店面,现在还没有消息,心里着急啊,这几天上班都难集中精神, 求过,求onsite

面试10点开始,用的是 google doc
电话试点准时打来,没有caller id
听声音是为中国大哥/小哥(自己心里开心不少),大哥开始和我了了自己做的事情,聊现在的项目,提到了为啥我用Java面试, 不用C#面试 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
大哥人很好,开始就说有2个题。

大哥人很好,题目也不难,自己code写的磕磕碰碰啊(google doc的indention也是惨不忍睹)
假设有个social network
( 1)返回朋友的朋友,但不是自己的朋友;
( 2 ) 返回朋友的朋友,担不是自己的朋友,按照出现的次数排序,也就是说加入一个人不是我的朋友,但是他是我所有的朋友的朋友,那么他应该是返回结果里面的第一个
. 1point 3acres 璁哄潧
需要自己定义数据结构,自己设计API和讨论test cases.
太紧张了, Map的API都写的不利索了。

求过啊

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| guixi107 发表于 2016-2-2 12:15:09 | 显示全部楼层
刚才收到 recruiter的电话,已过。多谢中国大哥/小哥,准备onsite去了
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 12:43:52 | 显示全部楼层
第二问可以在bfs或者dfs的时候顺便算下indegree?然后再用indegree排序?
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-2-2 14:56:33 | 显示全部楼层
johnjavabean 发表于 2016-2-2 12:43
第二问可以在bfs或者dfs的时候顺便算下indegree?然后再用indegree排序?

没有那么复杂, 只是找把second degree的people按照出现的次数输出,主要考察code写的干净(不要在输出前额外排序)
回复 支持 反对

使用道具 举报

aicp7 发表于 2016-2-8 07:38:34 | 显示全部楼层
guixi107 发表于 2016-2-2 14:56
没有那么复杂, 只是找把second degree的people按照出现的次数输出,主要考察code写的干净(不要在输出前 ...

关于在输出前要不要排序,感觉得分情况讨论吧。因为如果是用hashmap来实现二级朋友的话,不管是删除还是update,或者是新建都是O(1)的时间,但是hashmap就是需要最后在返回前,用Tree,PQ或者是ArrayList之类的来排序一下,然后输出。如果刚开始就是用PQ来实现二级朋友,删除,添加,或者update都需要O(logN)时间,只是最后可以直接输出。所以,我感觉关于在输出前要不要额外排序,是不是得分情况考虑啊?
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-2-8 07:53:47 | 显示全部楼层
aicp7 发表于 2016-2-8 07:38
关于在输出前要不要排序,感觉得分情况讨论吧。因为如果是用hashmap来实现二级朋友的话,不管是删除还是u ...

我的想法是(不一定是最优的)

public class People{
private string name;
. 鍥磋鎴戜滑@1point 3 acres  private List<People> friends;
}


public List<People> findPotentialFriendsByOrder(People p)
{
//....
}. 1point 3acres 璁哄潧

现在实现上面的方法,其实可以用TreeMap就可以了,那么不用额外排序了。
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-3-8 09:08:20 | 显示全部楼层
朋友的朋友,只考虑2nd degree么?还是要拿个q,把所有关系网里的人都考虑了?
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-3-8 09:32:59 | 显示全部楼层
kittycerry 发表于 2016-3-8 09:08
朋友的朋友,只考虑2nd degree么?还是要拿个q,把所有关系网里的人都考虑了?

ONLY second degree
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-3-8 14:04:13 | 显示全部楼层

谢谢!!!!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-9 04:05:21 | 显示全部楼层
写了下代码
  1. public class FriendsRecommendation {
  2. . more info on 1point3acres.com
  3.         class People {
  4.                 String name;
  5.                 HashSet<People> friends;
  6.         }

  7.         class Ele {
  8.                 int count;
  9.                 People people;

  10.                 public Ele(int c, People n) {
  11.                         count = c;
  12.                         people = n;
  13.                 }
  14.         }

  15.         public List<People> findPotentialFriends(People p) {
  16.                 List<People> res = new ArrayList<People>();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  17.                 HashMap<People, Integer> map = new HashMap<People, Integer>();
  18.                 for (People friend : p.friends) {
  19.                         for (People ele : friend.friends) {. 1point 3acres 璁哄潧
  20.                                 if (p.friends.contains(ele)) {
  21.                                         continue;
  22.                                 }
  23.                                 if (!map.containsKey(ele)) {
  24.                                         map.put(ele, 1);
  25.                                 } else {
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  26.                                         map.put(ele, map.get(ele) + 1);
  27.                                 }
  28.                         }
  29.                 }

  30.                 PriorityQueue<Ele> pq = new PriorityQueue<Ele>(new Comparator<Ele>() {
  31.                         public int compare(Ele e1, Ele e2) {
  32.                                 return e2.count - e1.count;
  33.                         }
  34.                 });
  35.                 while (!pq.isEmpty()) {
  36.                         res.add(pq.poll().people);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  37.                 }

  38.                 return res;
  39.         }
  40. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-3-9 05:04:39 | 显示全部楼层
bobzhang2004 发表于 2016-3-9 04:05 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
写了下代码
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
you will need @Override equals and hashcode so that People and Elem can work with the HashMap
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-3-9 05:28:59 | 显示全部楼层

你问的推荐好友那个,是这个题么?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-9 06:34:17 | 显示全部楼层
kittycerry 发表于 2016-3-9 05:28
你问的推荐好友那个,是这个题么?
. 1point3acres.com/bbs
应该是一样的啊,你觉得呢?
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-3-9 13:18:07 | 显示全部楼层
bobzhang2004 发表于 2016-3-9 06:34. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
应该是一样的啊,你觉得呢?

我看到的是这个,没看懂你描述的那个题。我看看你的代码然后给你feedback哈
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-10 00:08:11 | 显示全部楼层
guixi107 发表于 2016-3-9 05:04
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴you will need @Override equals and hashcode so that People and Elem can work with the HashMap

为什么需要呢?如果两个people不是一个object, 就应该是不想同的啊,就好像copy graph里面的class node一样。override是在两个不同的object要因为某个hash,使其一样吧。你可以给相关资料参考下吗?
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-3-10 03:46:18 | 显示全部楼层
bobzhang2004 发表于 2016-3-10 00:08
为什么需要呢?如果两个people不是一个object, 就应该是不想同的啊,就好像copy graph里面的class node一 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
hmm,

if you first put ele in the dictionary:. from: 1point3acres.com/bbs
  map.put(ele, 1)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
will map.containsKey(ele) return true if you don't override equals and hashcode()?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-10 05:25:43 | 显示全部楼层
guixi107 发表于 2016-3-10 03:46
hmm,

if you first put ele in the dictionary:

这里不应该就是要返回true吗?
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-3-15 11:05:24 | 显示全部楼层
感觉是不是可以这么做:
(1)用set1存所有朋友, 建一个map<int, set<person>>,key表示set<person>里的人拥有的朋友个数。
(2)for person in set1, 更新map,如果出现在map[1]里并且再次遇到,删除其在map[1]里的记录,添加到map[2]里。
(3)由于map是有序的,直接逆序输出
回复 支持 反对

使用道具 举报

grubbyfan 发表于 2016-3-16 00:43:49 | 显示全部楼层
sheepmiemies 发表于 2016-3-15 11:05-google 1point3acres
感觉是不是可以这么做:.鏈枃鍘熷垱鑷1point3acres璁哄潧
(1)用set1存所有朋友, 建一个map,key表示set里的人拥有的朋友个数。
(2)fo ...

我想法和你一样,用treemap,如果是java的话。. from: 1point3acres.com/bbs
但是runtime 会有问题。比如二级friend有n个人(包括重复计算的),其中不是我的friend有k个人(去重之后)。
1. 如果用hashmap,再sort的话,就是n * O(1)(insert) + O(klg(k)) (sort)
2. 如果用treemap,就是 n*(lg(k))(insert) + O(K) (output)
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-14 08:15:22 | 显示全部楼层

为什么People集合能检查是否还有Ele?这样应该会报错吧。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 05:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表