一亩三分地论坛

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

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

纽约狗家Onsite

[复制链接] |试试Instant~ |关注本帖
cpz1234 发表于 2016-11-15 11:58:27 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
NY 狗家onsite 一共5轮在职跳槽免了电话面试,5轮4轮白人一轮国人,算是运气不错,国人大哥出的题很简单,感觉是放了下水
第一轮:Find common element within 2 arrays. follows: 1.如果一个很大一个比较小怎么办(binery serach in larger array),如果larger array can not fit in mem?(truncate into files and binery search in the target file), what if larger array is even larger that on machine can not store? (master - slave, and parallel searching in each slave machine), what if both arrays are very large?
第二轮:lc 394, follow, how to encode, ex abcabcd => 3[abc]d, follow up没答完,这轮搞不好要差评了。
第三轮:一个binery search tree,删除某个layer的所有node之后重新construct一个新的BST, 要求新tree是complete的。我的做法是1.先tree level traversal 原来的tree,删掉一层之后所有node合到一个array里面sort。2. 创建一个新的complete tree with x nodes, where x == length of the previous array in step1. 3。in order traverse 新tree,把第一步得到的array值填进去。面试官表示满意
朋友带去午饭,食堂不错
第四轮:如何创建迷宫,需要保证只有一条路径到出口并且所有tile都能reach. 面试官比较nice,每当想偏了的时候都给了关键提示,最后顺利做出。大致方法是从起点开始dfs,keep一个visited matrix,下一步上下左右的顺序是随机的但是保证上下左右都走一遍。每走一步就把走过的路径加入到一个path dictionary里面,pathDic = {fromTile : toTile} 任何不在这个dict里面的两个tile不能走过(中间🈶墙),问了个follow up问题是n*n的迷宫墙的数量是多少(2*n*(n-1) - (n - 1)), 他只准备这一题,做完后还有15分钟,又做了一道比较简单的题,基本上属于浪费一下垃圾时间
第五轮:问题是有个data feed实时收到[timestamp, value], ex:[1, 5.23], [2, 6.32] ... 不过有可能会收到之前时间的value update.比如又来个[1, 5.77], 这时timestamp 1的值就从5.23 变成5.77. 问题是如何keep track of the largest value so far. 我的方法是keep 一个合理大小的heap保存前n大的value,问了一些问题关于如何选择heap size大小之类的,都属于言之有理即可的. 1point3acres.com/bbs


补充内容 (2016-11-23 11:57):. from: 1point3acres.com/bbs
今天HR电话说过了,接下来就是team match,所以有一轮表现不好也不用太担心

补充内容 (2016-11-23 11:58):. from: 1point3acres.com/bbs
前面有个type,迷宫墙总数是(2*n*(n-1) - (n*n - 1))

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| cpz1234 发表于 2016-11-15 12:02:02 | 显示全部楼层
第二轮follow up之前地里有同学报过,当时没仔细琢磨,不会还是不会,这次吃了大亏了。小伙伴们要好好利用面经呀。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-11-15 13:16:32 | 显示全部楼层
第二题的followup是什么啊?
回复 支持 反对

使用道具 举报

cezheng2 发表于 2016-11-15 13:25:14 | 显示全部楼层
第五轮,加入你的heap size是n,

补充内容 (2016-11-15 13:28):
如果先来了n个feed (1,2),(2,2)...(n,2),这时候你的heap有n个2,然后来了(n+1, 1.5),这时候不会被放入堆中,之后又来了n个更新的feed(1,1),(2,1)..(n,1)的话,你的heap就只剩下n个1了,这时候max value就不对了
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-15 14:18:33 | 显示全部楼层
看不太懂第四轮的解法..能否再说明一下?谢谢!
回复 支持 反对

使用道具 举报

gabrielzhuyun 发表于 2016-11-16 03:14:42 | 显示全部楼层
请问楼主,第二题follow up啥思路啊?在不同index换不同长度尝试嘛?
回复 支持 反对

使用道具 举报

 楼主| cpz1234 发表于 2016-11-17 11:20:22 | 显示全部楼层
cezheng2 发表于 2016-11-15 13:25
第五轮,加入你的heap size是n,

补充内容 (2016-11-15 13:28):

你说得对,面试的时候跟跟面试官讨论如何选择heap size,如果update频率比较高heap就要选的大一些,当然也可以重新扫一遍所有结果重新生成heap
回复 支持 反对

使用道具 举报

 楼主| cpz1234 发表于 2016-11-17 11:29:15 | 显示全部楼层
catinclay 发表于 2016-11-15 14:18
看不太懂第四轮的解法..能否再说明一下?谢谢!

从起点开始DFS,正常的DFS方向是固定,这里DFS方向顺序需要随机,然后每个格子只走到一次,走过就记录在visited matrix里面以后再也不能visit这个格子。所有DFS走过的路径就是通路,没有走过的路径默认是墙。可以用一个hashmap来存所有路径,我用的形式shi是 {(1,2): [(2,2), (1,3)]} 表示(1,2) 可以走到(2,2), (1,3)
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-17 12:29:55 | 显示全部楼层
cpz1234 发表于 2016-11-17 11:20
你说得对,面试的时候跟跟面试官讨论如何选择heap size,如果update频率比较高heap就要选的大一些,当然 ...

为了时间效率,是不是应该再存一个hashMap mapping time->heap iterator来保证O(1)时间查找heap中的某个元素? 我不熟悉Java请见谅。

若是C++的话(C++ priority_queue不支持iterator和remove),我用set<pair<int,double>>来存pair(time, value) ordered by value(insert时间也是O(logN)),再用unordered_map<int, set<pair<int,double>>::iterator>来指向set中的位置。这样当收到一个以前的pair(time, value)时才能O(1)时间将旧的value从set中删除,再将新的加入。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
至于这个heap size,若要即时询问当前最大值的话感觉必须是O(N)空间啊。我的假设是这个feed就是个stream, 每次只能读取一个,若当前不存的话以后就再也找不回来了。不知面试时有什么假定?
回复 支持 反对

使用道具 举报

 楼主| cpz1234 发表于 2016-11-17 12:51:45 | 显示全部楼层
zzgzzm 发表于 2016-11-17 12:29. visit 1point3acres.com for more.
为了时间效率,是不是应该再存一个hashMap mapping time->heap iterator来保证O(1)时间查找heap中的某个 ...

忘记讲我用一个大hashmap存所有的price ticket,这个题属于遇到国人放水,也属于运气好,没有太大参考价值,遇到了随便扯扯,言之有理就行
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-17 12:52:31 | 显示全部楼层
cpz1234 发表于 2016-11-17 11:29-google 1point3acres
从起点开始DFS,正常的DFS方向是固定,这里DFS方向顺序需要随机,然后每个格子只走到一次,走过就记录在v ...

看LZ的DFS意思相当于是找所有不自交的从起点到终点的路径(不在路径上的就自动设计为墙)。如果是这样的话,这种迷宫只能保证存在一条路径到出口并且所有tile都能reach,没法保证路径唯一性啊。
例如3X3迷宫从(0,0)走到(2,0)的两个不自交路径:
(0,0)-(1,0)-(1,1)-(0,1)-(0,2)-(1,2)-(2,2)-(2,1)-(2,0)
(0,0)-(0,1)-(0,2)-(1,2)-(2,2)-(2,1)-(1,1)-(1,0)-(2,0)
这样3X3网格无任何墙的迷宫本不具有路径唯一性的,但却有不自交路径经过所有节点。
. from: 1point3acres.com/bbs
补充内容 (2016-11-17 14:02):
follow up:n*n的迷宫墙的数量是多少(2*n*(n-1) - (n - 1)) 这个不应该等于n*n - path length吗?还是我想完全偏离了?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-17 13:52:47 | 显示全部楼层
第四轮:创建迷宫,若就是相当于是找所有不自交的从起点到终点的路径,我写了一下DFS的,每次搜索4个不同方向,若没有走过就加到path中,最后收集所有的paths。然后paths的条数(除去节点一样只是顺序不同的)就是迷宫个数吧。是不是这个意思吗?
  1. void dfs(pair<int,int> c, pair<int,int> e, Path& p) {
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  2.   if (c == e) { ps.push_back(p); return; }
  3.   if (!inRang(c) || visited[c]) return;
  4.   visited[c] = true; p.push_back(c);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5.   for (auto& d:dirs) dfs(c+d, e, p);
  6.   p.pop_back(); visited[c] = false;
  7. }

  8. Paths findAllPaths(int n, pair<int,int> s, pair<int,int> e) {
  9.   N = n;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.   for (int i = 0; i < N; ++i)
  11.   for (int j = 0; j < N; ++j) visited[make_pair(i,j)] = false;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.   Path p; dfs(s, e, p);
  13.   return ps;
  14. }
复制代码

自定义的type,global variables和helper functions是:
  1. typedef vector<pair<int,int>> Path;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2. typedef vector<Path> Paths;. Waral 鍗氬鏈夋洿澶氭枃绔,

  3. int N; // dimension of maze
  4. Paths ps; // all non self-intersecting paths
  5. map<pair<int,int>, bool> visited;
  6. Path dirs = { {1,0},{-1,0},{0,1},{0,-1} }; // 4 directions
  7. pair<int,int> operator+ (const pair<int,int>& x, const pair<int,int>& y)
  8. { return make_pair(x.first+y.first, x.second+y.second); }

  9. bool inRang(pair<int,int> c)
  10. { return c.first >= 0 && c.first < N && c.second >= 0 && c.second < N; }
复制代码
回复 支持 反对

使用道具 举报

 楼主| cpz1234 发表于 2016-11-17 13:57:48 | 显示全部楼层
zzgzzm 发表于 2016-11-17 12:52
看LZ的DFS意思相当于是找所有不自交的从起点到终点的路径(不在路径上的就自动设计为墙)。如果是这样的 ...

你想复杂了,也怪我没讲太清楚,面试官问的是n*n的迷宫里面有多少面墙,有多少个通路(可以看做两个格子之间有个门)
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-17 14:29:02 | 显示全部楼层
cpz1234 发表于 2016-11-17 13:57
你想复杂了,也怪我没讲太清楚,面试官问的是n*n的迷宫里面有多少面墙,有多少个通路(可以看做两个格子 ...
. more info on 1point3acres.com
感谢解释。我一般认为墙或空格都占据一个格子。。。呵呵
那么这个就是一笔画问题了?从起点到终点无重复地走遍N*N个格子(Tiles)有多少走法?这样顺序不同就代表打穿的墙是不一样的了。那我觉得就是我在12层的code Line 2中加上只有当前路径长度ps.length()==n*n-1(不算终点)时再加到结果中去吧。-google 1point3acres
但好像也有无解的情况吧,2X2迷宫,起点(0,0) 终点(1,1). 还是我又想偏了,呵呵。。。

那么所有墙总数=2N*(N-1),路径长度必然N*N就打穿N*N-1面墙,所以还剩2N*(N-1)-(N*N-1) = (N-1)^2面墙
回复 支持 反对

使用道具 举报

jefferyy 发表于 7 天前 | 显示全部楼层
楼主可以告诉下 迷宫type是怎么定义的么?
多谢多谢
回复 支持 反对

使用道具 举报

luofeidream 发表于 7 天前 | 显示全部楼层
我有一轮和楼主第三轮一样,不过这一轮之前还做了两道关于二叉树的题。其实那道题不用先得到node再sort,直接中序遍历完就得到有序的了,复杂度更好一些。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 14:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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