一亩三分地论坛

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

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

Pocket Gems Onsite 面经

[复制链接] |试试Instant~ |关注本帖
crisc3 发表于 2015-12-8 12:42:25 | 显示全部楼层 |阅读模式

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

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

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

x
来发个面经,直接上题
1. leet code 原题word break 问你run time
2. 一个design题,要求把json文件parse一下 然后insert进database, 但是有诸多要求,最后相当于 自己设计的class 涉及hashtable vtable function pointer等等

3. 一个键盘 4 个键,1,2,3,4 按下1 屏幕上出现一个字母'A', 按下2,相当于ctrl+A 全选,按下3,等于复制,按下4 相当于ctrl+V粘贴。但是粘贴不会覆盖原来内容,比如按下1234,那么会有2个'A'而不是一个。 问题来了,给你N次机会,你能最多让屏幕上出现几个 A。问running time
4. 两个问题 第一个是 BFS找path,第二个问题是有一个pizza, 分成N份,每份质量不同,A 和 B 轮流拿,A 先拿,第一份随便拿,但是 第二份之后,就只能拿最边上的那份。也就是说 第二次之后,只能拿开口两边的pizza。问你:作为B,如果 A 先拿了一份,剩下一个开口的pizza, 你能拿到的pizza总和最多是多少。 follow up: 如果你是 A,你先拿,你最多能拿多少pizza。

面试官都挺好的 交流挺多,让人感觉参与度蛮高的。
 楼主| crisc3 发表于 2015-12-16 01:21:44 | 显示全部楼层
inkhay 发表于 2015-12-15 15:51.鐣欏璁哄潧-涓浜-涓夊垎鍦
求问LZ第三题,是用什么方法解的题,DP还是greedy。。。或者都不是。。。求提供一点思路 多谢多写

用 DP 做,在考虑i次按键的时候,你去用最后一次出现"23"的index进行分类。比如i = 8, 最后一次"23"可能出现在第j: -1,2,3,4,5,6位(-1代表没出现过), 那么之后按到的4粘贴的长度就是dp[j], 比如i = 5的时候,那么就是xxxxx234 所以dp[8] = max(dp[j]*(i-j) + dp[j]) for all j

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

inkhay 发表于 2015-12-15 15:51:49 | 显示全部楼层
求问LZ第三题,是用什么方法解的题,DP还是greedy。。。或者都不是。。。求提供一点思路 多谢多写
回复 支持 反对

使用道具 举报

inkhay 发表于 2015-12-16 13:56:45 | 显示全部楼层
crisc3 发表于 2015-12-16 01:21
用 DP 做,在考虑i次按键的时候,你去用最后一次出现"23"的index进行分类。比如i = 8, 最后一次"23"可能 ...
-google 1point3acres
太感谢了!另外关于pizza的题目,题目本身我没有特别明白,对于B来说,是可以安排A去拿哪一块,从而达到自己最大化的目的么?
.1point3acres缃
补充内容 (2015-12-16 14:46):
另外除了暴力recursive 求所有情况,还有什么方法么,总觉得可以用dp什么的解,但是总感觉要把整个pizza展开成array,并不能保证开口两边的连续关系。。。好忧桑,后天onsite的说
回复 支持 反对

使用道具 举报

 楼主| crisc3 发表于 2015-12-16 15:07:22 | 显示全部楼层
inkhay 发表于 2015-12-16 13:56
太感谢了!另外关于pizza的题目,题目本身我没有特别明白,对于B来说,是可以安排A去拿哪一块,从而达到 ...

第三题可以参考:http://www.geeksforgeeks.org/how ... ng-given-four-keys/

第四题 其实geeks里面也有 我看到过 但是找不到了。大概思路是 DP,这么做:
假设有array A, size n = 5, [5,1,2,3,4] 由题意 我们只能取收尾的item, DP[i,j]代表在A.substr(i,j)的情况下,先取的人能得到的最坏情况的最大 Pizza。那么DP[0][4]是多少呢?考虑取的可能性,可能取5,可能取4.
如果取了5,对手可能取1 这样留下234,可能对手取4,留下123,对于自己取4进行同样的考虑,所以
DP[0][4] = max( 5+min(DP[1][3],DP[2,4]), 4+min(DP[0,2],DP[1,3]) )。这样就可以做 DP 了
其实你再进一步想一想,假设对手和你一样聪明,换位思考,可以得到
DP[0][4] = sum(0,4) - min(DP[1,4],DP[0,3]))
回复 支持 反对

使用道具 举报

inkhay 发表于 2015-12-17 08:36:52 | 显示全部楼层
crisc3 发表于 2015-12-16 15:07
第三题可以参考:http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-key ...

太牛了!!! 太感谢了!!!看你最近的面经,他家设计题也改了,本来系统设计也不是特别明白。到时候碰碰运气。多谢!
回复 支持 反对

使用道具 举报

shenhualong 发表于 2016-1-31 11:21:56 | 显示全部楼层
求问楼主parse json那题能说详细点吗?马上要面了,感觉这题很迷糊。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 02:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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