May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 8110|回复: 47
收起左侧

狗家onsite面经

[复制链接] |试试Instant~ |关注本帖
pineapple1985 发表于 2016-10-14 11:11:04 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - Onsite |Failfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
已跪! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
onsite那天面完,记录下来的。应该有语法错误,大家将就着看吧。
1. Given a BST, print the numbers of the kth level in the following order: smallest, largest, second smallest, second largest..... 鍥磋鎴戜滑@1point 3 acres
2. Given a function readBlock(size_t blockID, char * buff) that reads the whole block of the given block. A block has 512* 1024 byte. Implement a function readBytes(size_t Len, size_t offset, chat * dest) that reads len bytes starting from the offset.
3. Simple self-driving car: let a list of instructions is given(aaararaa) for every second, calculate the destination of the car after car  follows all instructions. Here 'a' represents accelerate and 'r' represents reverse.  The car is only running along a straight line started at origin=0 and with velocity v=1. After an instruction 'a', the car will double its velocity. After  an instruction 'r', the car will reverse direction and reset its its speed to 1.
Follow up: given a destination(e.g., x= 5 or -5), generate a list of instructions to make the car arrive at the given destination after following all instructions. If there are more than one solution, return the one with minimal length.

4 given a list of votes and the time stamp for the vote. Find the leading candidates upto a given time stamp.  A vote has the name of a candidate and the timestamp for the vote.
Follow up:1.  find the top k candidates up to given  time stamp
Follow up 2: given a candidates ranking , find a timestamp that would resulted in the given order of candidates ranking. You only need to care about the candidates in the list.
.1point3acres缃
5. 1. Guess number with lower or high hints . Problem from leetcode. 2. There is a game about guessing number between 1 and n. This gam is played by two people A and B. When A guesses a number(e.g. 5), A need to pay that amount of dollars($5). Then B  will change the number that forces to gain maximal amount of earning. Assume they are both smart enough. What is the minimal amount that A needs to pay to finish this game? That is, there is only one number left and A will surely guess it right. Careful: B does not have a fixed number in mind. . more info on 1point3acres.com

Almost all questions ask about time and space complexity. Need to optimize it in some rounds.
-google 1point3acres



.1point3acres缃

评分

2

查看全部评分

本帖被以下淘专辑推荐:

zzgzzm 发表于 2016-10-17 02:23:15 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
5.2 就是LC375. 因为LC375的结果是保证能赢的最少的钱数,所以考虑的是最坏的情况。换句话说,当B在心中改答案的时候,对于A来说都可以认为B是“诚实”的,只要游戏结束后B“不得不”给出的答案和之前给出的所有反馈都是合理的,也就是说我们及时允许B在心中默默的改答案,B也只能在给出A反馈后的那个合理区间内改,随着给的反馈越来越多,B可更改答案的范围也越来越小,而且这些都是A原本就需要考虑到的最差情况。理解的关键在于一旦B给A一个反馈,那么B就是能在合理区间内改答案!

比如N=3,A最少需要¥2. 当A猜2的时候,A的最优策略之所以是猜2就是因为不论答案是1还是3,剩余游戏的总消耗是一样的(最差情况最小化),所以不论B在心中是改成1还是3对于A来说无所谓。

补充内容 (2016-10-17 02:29):
打个比方,大家玩升级牌的时候都要按花色出牌。如果有人作弊在某花色还有的情况下就使用了主花色,这在游戏结束之前可能很难被发现,但最终是肯定暴露的。同理B的“作弊”也只能在合理区间内改,但这些本来就该预计
回复 支持 1 反对 0

使用道具 举报

yhatl 发表于 2016-10-15 09:56:53 | 显示全部楼层
关注一亩三分地微博:
Warald
wtcupup 发表于 2016-10-14 12:32
恩 看来和LC375 不太一样
. 1point3acres.com/bbs
我擦,请问B改不改很重要吗
A的minimum必须cover所有number 好不好?
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-10-14 12:27:39 | 显示全部楼层
第五题的第二小题和leetcode 375 不同之处在于在A每次猜错之后,B可以改自己心中想的数字?
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-14 12:30:26 来自手机 | 显示全部楼层
其实没有猜对错之分。就是玩这个游戏,假设大家都足够聪明,一个想付尽量少的钱,一个想赚尽量多的钱。没有数字可猜就游戏结束
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-14 12:32:41 | 显示全部楼层
pineapple1985 发表于 2016-10-14 12:30
其实没有猜对错之分。就是玩这个游戏,假设大家都足够聪明,一个想付尽量少的钱,一个想赚尽量多的钱。没有 ...

恩 看来和LC375 不太一样
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-14 12:38:58 来自手机 | 显示全部楼层
嗯,我一开始也是往leetcode那道题的方向走,后来才想明白他的意思,然后没时间写完
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-10-15 10:28:20 | 显示全部楼层
请问楼主 第三题 . 鍥磋鎴戜滑@1point 3 acres
2个指令 之间的 间隔时间是多少,没有时间,怎么算距离呢?
回复 支持 反对

使用道具 举报

amszhou 发表于 2016-10-15 12:21:57 | 显示全部楼层
第一题见过, 觉得level order 最简单,但好像用stack来做更好。
第三题应该是要做段时间吧, 用recursion 并用 2D matrix 记录 speed, distance 组合下的最短时间,可能可以。主要考虑下一秒speed*2 >, =, < distance 下的几种情况。

第五题只想到LC的题,变形后就没思路了。。。
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-10-15 13:23:12 | 显示全部楼层
amszhou 发表于 2016-10-15 12:21
第一题见过, 觉得level order 最简单,但好像用stack来做更好。.1point3acres缃
第三题应该是要做段时间吧, 用recursion ...

level order/stack不都可以停在第k层么?为什么说后者更好
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-10-15 13:58:51 | 显示全部楼层
第三题followup就是每次有两个选择,a或者r,当position<t选a,>选r,深度就是path长短
回复 支持 反对

使用道具 举报

yhatl 发表于 2016-10-15 22:49:54 | 显示全部楼层
mengmeng88717 发表于 2016-10-15 13:58
第三题followup就是每次有两个选择,a或者r,当position选r,深度就是path长短

position<t未必选a,比如说到终点只有1了,但是speed是16,这时选r更好(raar)
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-15 22:58:28 来自手机 | 显示全部楼层
sunnyroom 发表于 2016-10-15 10:28
请问楼主 第三题
2个指令 之间的 间隔时间是多少,没有时间,怎么算距离呢?

1 second. Reverse 的时候只改方向跟速度,不前进
回复 支持 反对

使用道具 举报

qesss 发表于 2016-10-16 03:18:53 | 显示全部楼层
我觉得第五题和lc原题没有区别,本来那个数字A也不知道啊,按LC的思路A本来就是计划的最坏打算,最坏打算的意思就是B在一直变那个数。
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-16 03:23:14 来自手机 | 显示全部楼层
qesss 发表于 2016-10-16 03:18
我觉得第五题和lc原题没有区别,本来那个数字A也不知道啊,按LC的思路A本来就是计划的最坏打算,最坏打算的 ...

我刚看了leetcode题目。我靠,还真是一摸一样的做法。
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-10-16 13:31:16 | 显示全部楼层

嗯应该是两个都要走。。非递归的写成bfs那样就是最短指令了
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-10-16 14:01:33 | 显示全部楼层
第四题是给了一个candidate的名次,求相应的时间能得到这个名次,还是给了所有candidate的名次,求相应时间?
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-16 21:25:52 来自手机 | 显示全部楼层
没有所有,就是top k candidates的一个list
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-17 00:03:02 | 显示全部楼层
2. Implement "readBytes". 是假设每个Block一定可以读取512* 1024 byte的数据吗?不会有未填满的情况吧(比较LC Read4)。是这个意思吗?
我的C++Solution:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  1. void readBytes(size_t len, size_t off_set, char* dest) {
  2.   const size_t bs = 512*1024; // block size
  3.   size_t id = off_set/bs; // start block id. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.   size_t i = off_set%bs; // start index in block
  5.   size_t nbytes = 0; // num of bytes read
  6.   char buf[bs]; // buffer read by readBlock
  7.   while (nbytes < len) {
  8.     if (i >= bs) { // need to reload next block
  9.       i = 0; readBlock(id++, buf);   
  10.     }
  11.     dest[nbytes++] = buf[i++];
  12.   }
  13. }
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-17 00:37:55 | 显示全部楼层
1. “Given a BST, print the numbers of the k···” My idea is to use In-order traversal get all nodes in ascending order, cut the result at half, reverse the second half, and then merge them together alternatively.
  1. . Waral 鍗氬鏈夋洿澶氭枃绔,
  2. // get all node values in ascending order and save in a vector
  3. void InOrder(Node* r, vector<int>& inorder) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4.   if (!r) return;
  5.   InOrder(r->left, inorder);
  6.   inorder.push_back(r->val);. from: 1point3acres.com/bbs
  7.   InOrder(r->right, inorder);. 1point 3acres 璁哄潧
  8. }

  9. // get all node values in small-large order alternately.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10. vector<int> f(Node* r) {
  11.   vector<int> inorder;    . From 1point 3acres bbs
  12.   InOrder(r, inorder);
  13.   int n = inorder.size();
  14.   if (n < 3) return inorder;
  15.   vector<int> first(inorder.begin(), inorder.begin()+n/2);. visit 1point3acres.com for more.
  16.   vector<int> second(inorder.begin()+n/2, inorder.end());
  17.   reverse(second.begin(), second.end());. more info on 1point3acres.com
  18.   int i = 0, fi = 0, si = 0;. from: 1point3acres.com/bbs
  19.   while (fi < first.size() || si < second.size()) {
  20.     if (fi < first.size()) inorder[i++] = first[fi++];
  21.     if (si < second.size()) inorder[i++] = second[si++];  
  22.   }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.   return inorder;
  24. }
复制代码

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2016-10-17 00:46):. more info on 1point3acres.com
Both time and space complexity of the code above are O(N), where N is the number of nodes in BST.
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-29 04:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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