一亩三分地论坛

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

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

PocketGems onsite 一道新题

[复制链接] |试试Instant~ |关注本帖
laurie洁 发表于 2015-9-27 00:31:39 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@PoketGem - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
这周四面的顺便在三番玩了一圈~突然觉得跟三番一比,西雅图有点二线城市的赶脚~~
扯远了~~. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
HR Ona: showed me around, then asked questions about why Pocket Gems, feedback on phone interviews, competing offers, and reasons to influence my choice.

Round 1: Dev 印度小哥
说话完全没有口音赞一个~上来介绍了一下他自己~上了一道新题
Question 1: Given 4 keys: 1 ‘A’; 2 Ctrl + A: selection; 3 Ctrl + C: copy; 4 Ctrl + P: paste. How to get the maximum number of ‘A’s in the console?
我的解法:
  • Use a int[] max to record the max number of ‘A’s at each length
  • Base case: max[n] = n, n <= 4
  • Scan from j: 1 to n - 3 to get the max: max[n] = max(max[n], max[j] * (n - j - 2 + 1))


Question 2: Room connections, BFS

Round 2: 很高的印度小哥,比较严肃,口音有点重哈~
Question 1: Max Product Subarray
Question 2: find sequence in an array of Strings, topological sorting.
Follow-up: what if the output needs to be the lexicographically smallest?
Use a PriorityQueue for BFS
Follow-up2: what if the input is invalid?
track the total number of nodes, and see if they are all visited

Round 3: Marko
Achievement System Design
上来写了满满半黑板的requirements and constraint
其实我写的code不多,更多在问问题和交流
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Round 4: David 穿着袜子进来的小哥
mutable String: charAt, substring, setCharAt
那个setCharAt果然很难,一直在各种纠结,不过小哥倒是很耐心啊~我都要弃疗了,他还没有放弃,感动一下~~

. from: 1point3acres.com/bbs 最后HR又进来扯了一下,然后跟我说meal和transportation也可以报销?意外啊~

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-9-27 00:35):
说错了,是周三面的~~周五写信来要reference和set up follow-up call~求问这是过了的意思吗?

评分

1

查看全部评分

chiuup 发表于 2015-9-27 03:37:49 | 显示全部楼层
round 1 Q1的問題有點沒看懂,可以稍微仔細講一下問題是什麼嗎?謝謝。
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-9-27 05:32:44 | 显示全部楼层
chiuup 发表于 2015-9-27 03:37. From 1point 3acres bbs
round 1 Q1的問題有點沒看懂,可以稍微仔細講一下問題是什麼嗎?謝謝。

就是给四个键,要求只能按N次,问怎样能够输出最多的A
回复 支持 反对

使用道具 举报

chiuup 发表于 2015-9-27 08:49:33 | 显示全部楼层
那求問一下room connections是哪題啊具體@@?
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-27 09:46:31 | 显示全部楼层
请问第四轮里mutable String是用什么存char的?
回复 支持 反对

使用道具 举报

chiuup 发表于 2015-9-27 13:17:28 | 显示全部楼层
wenqiang88 发表于 2015-9-27 09:46
请问第四轮里mutable String是用什么存char的?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
char linked list吧?+一個版本控制大概
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-27 19:35:10 | 显示全部楼层
chiuup 发表于 2015-9-27 13:17
char linked list吧?+一個版本控制大概
. 1point 3acres 璁哄潧
为什么要做版本控制?
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-9-28 01:25:18 | 显示全部楼层
DP 女神可否解释下第一题你的状态方程啊,怎么感觉 n 次按键最多可以输出 n-2个 A,选择拷贝不算,最后一直黏贴。
回复 支持 反对

使用道具 举报

chiuup 发表于 2015-9-28 07:51:22 | 显示全部楼层
wenqiang88 发表于 2015-9-27 19:35
为什么要做版本控制?

因為要可以訪問老字符串的同時訪問新字符串。
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-9-28 08:08:07 | 显示全部楼层
sevenwonder 发表于 2015-9-28 01:25
DP 女神可否解释下第一题你的状态方程啊,怎么感觉 n 次按键最多可以输出 n-2个 A,选择拷贝不算,最后一直 ...

不一定吧~比如n=7, 那么答案应该是1111234, 那么得到8个A
n=8, 11111234, 10个A 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
n=9, 111234234, 12个A
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-9-28 08:08:56 | 显示全部楼层
chiuup 发表于 2015-9-28 07:51
因為要可以訪問老字符串的同時訪問新字符串。

同意,要求是用一个char []来存最初的信息,然后version control
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-28 08:10:57 | 显示全部楼层
laurie洁 发表于 2015-9-28 08:08
同意,要求是用一个char []来存最初的信息,然后version control

那LZ是用linklist做的吗?
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-9-28 08:15:07 | 显示全部楼层
wenqiang88 发表于 2015-9-28 08:10
那LZ是用linklist做的吗?

不是,我用的是tree来做,这样存version更方便
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-28 08:24:17 | 显示全部楼层
laurie洁 发表于 2015-9-28 08:15
不是,我用的是tree来做,这样存version更方便
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请问具体要求是什么?如果是要从一个版本回到上一个版本,用linkedlist不是更好吗?
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-9-28 08:26:42 | 显示全部楼层
laurie洁 发表于 2015-9-28 08:08
不一定吧~比如n=7, 那么答案应该是1111234, 那么得到8个A
n=8, 11111234, 10个A 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
n=9, 111234234, 12个A

原来选择拷贝也算显示A啊,那就第一个字符是A后面都234这样每次234都会多一个A出来,这不就是最多N + N/3个A么?
回复 支持 反对

使用道具 举报

chiuup 发表于 2015-9-28 09:54:44 | 显示全部楼层
laurie洁 发表于 2015-9-28 08:15
不是,我用的是tree来做,这样存version更方便
.鏈枃鍘熷垱鑷1point3acres璁哄潧
的確用bst存版本 big O會小一些

补充内容 (2015-9-28 09:55):
不對,應該是balanced的tree才會降低複雜度?
回复 支持 反对

使用道具 举报

LawranceH 发表于 2015-9-28 11:50:34 | 显示全部楼层
laurie洁 发表于 2015-9-28 08:08
不一定吧~比如n=7, 那么答案应该是1111234, 那么得到8个A
n=8, 11111234, 10个A
n=9, 111234234, 12个A

不对,请问下 楼主,比如n=9, 可以这样吗 111234444,15个A? 可以这样算最大吗?
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-9-28 13:19:54 | 显示全部楼层
LawranceH 发表于 2015-9-28 11:50
不对,请问下 楼主,比如n=9, 可以这样吗 111234444,15个A? 可以这样算最大吗?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
哦,好像是15个。我是用dp array存每个N对应的最多的A,然后扫一边在后面加上234...4,找到最大值。表达能力有限哈
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-9-29 10:40:23 | 显示全部楼层
laurie洁 发表于 2015-9-28 13:19
哦,好像是15个。我是用dp array存每个N对应的最多的A,然后扫一边在后面加上234...4,找到最大值。表达 ...

为什么不是max[j] +  (n - j - 2 )*2?
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-9-29 10:45:55 | 显示全部楼层
sevenwonder 发表于 2015-9-29 10:40
为什么不是max[j] +  (n - j - 2 )*2?

不明白为什么是加?我觉得是乘诶~
max[j]*(n - j - 1)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 15:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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