一亩三分地论坛

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

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

f店面

[复制链接] |试试Instant~ |关注本帖
haoshenxiong 发表于 2016-8-30 10:01:45 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Pass在职跳槽

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

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

x
1. Validate BST,拿stack写的,让演示了一个test case
2. Task那道题,很多面经都提到过。就是比如给你一串task,再给一个cooldown,执行每个task需要时间1,两个相同task之间必须至少相距cooldown的时间,问执行所有task总共需要多少时间。比如执行如下task:12323,假设cooldown是3。总共需要的时间应该是 1 2 3 _ _ 2 3,也就是7个单位的时间。再比如 1242353,假设cool down是4,那总共时间就是 1 2 4 _ _ _ 2 3 5 _ _ _ 3,也就是13个单位的时间。

三哥,迟到了十多分钟,然后顺延了十多分钟。大概介绍背景之后他比较详细地问了下我的project,当时还以为他在刻意拖时间,但后来感觉他人还是不错的。不过时间确实很紧,两道题都跑test case还是比较费时间的,第二题没有写出O(n),写了个O(n*k)的。

评分

3

查看全部评分

Xochitl 发表于 2016-8-31 13:29:42 | 显示全部楼层
我也是今天面的,因为太没有代表性了,就没有po了,考的reg ex match,感觉大家应该都会。。。
回复 支持 1 反对 0

使用道具 举报

qxr 发表于 2016-8-30 11:21:32 | 显示全部楼层
恭喜楼主!请问楼主用的什么语言面试的?谢谢!
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-8-30 22:11:48 | 显示全部楼层
请问lz怎么跑test case?
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-8-30 23:32:48 | 显示全部楼层
2. .1point3acres缃
HashMap<taskId, lastIdx>, 每次当前task是否已在map中,是的话,根据gap来更新total时间,更新map entry
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-8-30 23:33:47 | 显示全部楼层
1.stack的意思

补充内容 (2016-8-30 23:34):
1.stack的意思是post-order traversal么
回复 支持 反对

使用道具 举报

 楼主| haoshenxiong 发表于 2016-8-31 13:11:43 | 显示全部楼层
qxr 发表于 2016-8-30 11:21
恭喜楼主!请问楼主用的什么语言面试的?谢谢!

我用Java写的
回复 支持 反对

使用道具 举报

 楼主| haoshenxiong 发表于 2016-8-31 13:15:28 | 显示全部楼层
pawprinter 发表于 2016-8-30 22:11
请问lz怎么跑test case?

就是给一个例子,按照写的代码line by line口头跑。。最好是在代码上面(或者下面)把用到的变量写出来,每跑一行更新一下变量的值(如果有变化的话),这样过程比较清楚。
回复 支持 反对

使用道具 举报

 楼主| haoshenxiong 发表于 2016-8-31 13:16:03 | 显示全部楼层
tigercode 发表于 2016-8-30 23:33
1.stack的意思

补充内容 (2016-8-30 23:34):

用的stack inorder traversal
回复 支持 反对

使用道具 举报

liyoulu 发表于 2016-9-28 04:18:28 | 显示全部楼层
tigercode 发表于 2016-8-30 23:32
2.
HashMap, 每次当前task是否已在map中,是的话,根据gap来更新total时间,更新map entry

有没有代码,学习一下
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-10-3 08:17:17 | 显示全部楼层
lz啊,1242353 with cool time 4为什么不是2314523?为什么要13个单位时间?
回复 支持 反对

使用道具 举报

 楼主| haoshenxiong 发表于 2016-10-4 13:14:33 | 显示全部楼层
pawprinter 发表于 2016-10-3 08:17
lz啊,1242353 with cool time 4为什么不是2314523?为什么要13个单位时间?

不能改变task顺序
回复 支持 反对

使用道具 举报

garygao1993 发表于 2016-10-4 14:13:34 | 显示全部楼层
. 1point 3acres 璁哄潧
用双向队列维护长度为 cooldown 的窗口配合一个集合来查看这个窗口里面存不存在某个任务,是不是就能 O(n)了?
回复 支持 反对

使用道具 举报

garygao1993 发表于 2016-10-4 14:24:07 | 显示全部楼层

用 C++ 写大概是这样
  1. int totalTime(vector<int>& tasks, int cooldown) {
  2.         int total = 0;
  3.         deque<int> dq;
  4.         unordered_set<int> prev_tasks;
  5.         for (int task : tasks) {
  6.                 if (dq.size() == cooldown + 1) {
  7.                         prev_tasks.erase(dq.front());
  8.                         dq.pop_front();
  9.                 }. 1point 3acres 璁哄潧
  10.                 if (prev_tasks.find(task) != prev_tasks.end()) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11.                         total += cooldown;
  12.                         prev_tasks.clear();. 鍥磋鎴戜滑@1point 3 acres
  13.                         dq.clear();
  14.                 } else
  15.                         total++;. from: 1point3acres.com/bbs
  16.                 prev_tasks.insert(task);
  17.                 dq.push_back(task);
  18.         }
  19.         return total;
  20. }
复制代码
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2016-10-5 10:32):
对 cooltime 理解有误,这个代码是错的...
回复 支持 反对

使用道具 举报

garygao1993 发表于 2016-10-4 14:34:08 | 显示全部楼层
好像楼上大大的方法更简单直观
大概码了一下. more info on 1point3acres.com
  1. int totalTime2(vector<int>& tasks, int cooldown) {. 1point 3acres 璁哄潧
  2.         int cur_time = 0;
  3.         unordered_map<int, int> prev_tasks;
  4.         for (int task : tasks) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.                 if (prev_tasks.find(task) != prev_tasks.end() &&
  6.                         cur_time - prev_tasks[task] < cooldown) {
  7.                         cur_time += cooldown;
  8.                         prev_tasks[task] = cur_time;
  9.                 } else {
  10.                         cur_time++;
  11.                         prev_tasks[task] = cur_time;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.                 }
  13.         }
  14.         return cur_time;
  15. }
复制代码
. more info on 1point3acres.com
补充内容 (2016-10-5 10:33):-google 1point3acres
对 cooldown 时间理解有误,中间那段应该改成 if (prev_tasks.find(task) != prev_tasks.end() &&
                        cur_time - prev_tasks[task] <= cooldown) {
                        cur_time += cooldown + 1 - (cur_time - prev_tasks[task]...

补充内容 (2016-10-5 10:34):
if (prev_tasks.find(task) != prev_tasks.end() &&
                        cur_time - prev_tasks[task] <= cooldown) {
                        cur_time += cooldown + 1 - (cur_time - prev_tasks[task]);
                        prev_tasks[task] = cur_time;. Waral 鍗氬鏈夋洿澶氭枃绔,
                }
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-10-5 01:13:49 | 显示全部楼层
.1point3acres缃
orz....那这题变得更简单了
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-7 21:03:06 | 显示全部楼层
哎呀感谢楼主分享 不过请问一下O(n)的做法怎么做?。。 只会map的n*k。。>.<各位求指教。。
回复 支持 反对

使用道具 举报

shenrf 发表于 2016-10-18 12:58:48 | 显示全部楼层
何打发123 发表于 2016-10-7 21:03
哎呀感谢楼主分享 不过请问一下O(n)的做法怎么做?。。 只会map的n*k。。>.

n*k 是什么意思啊? 用map过一遍不是O(n)就可以了吗?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2016-10-18 12:59):
不懂你们说的k是代表了什么?
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-18 13:48:24 | 显示全部楼层
shenrf 发表于 2016-10-18 12:58. visit 1point3acres.com for more.
n*k 是什么意思啊? 用map过一遍不是O(n)就可以了吗?

补充内容 (2016-10-18 12:59):

k是cooldown的时间
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-10-18 14:40:32 | 显示全部楼层
shenrf 发表于 2016-10-18 12:58
n*k 是什么意思啊? 用map过一遍不是O(n)就可以了吗?

补充内容 (2016-10-18 12:59):

因为当你插入了空操作后,HashMap里面的各个entry的位置要变化。
ABCABC 4
A = 0
B = 1
C = 2
A  = 3 (差距只有3, 所以在CA之间插入一个空操作,所以Update Map里面的B和C,B-1 = 0, C-1 = 1)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 09:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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