[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3058|回复: 7
收起左侧

Zenefits电面,带原始题目。

[复制链接] |试试Instant~ |关注本帖
danielame1264 发表于 2015-10-21 03:38:10 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类General 硕士 全职@Zenefits - 网上海投 - 技术电面  | Fail | 在职跳槽

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

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

x
刚刚面完的Zenefits电面,感觉是一个人在印度的三哥,没有寒暄,直接上题, 题目是glassdoor上有的,很长,但废话很多,全文如下:. From 1point 3acres bbs
Bob just reached Gridland, a 2D world divided in many cells. Each cell is denoted by a pair (r,c) where r>=0 and c>=0. From a cell (r,c) one can move to (r+1,c), (r,c+1),(r-1,c) and (r,c-1).

Bob is standing at cell (0,0) and he wants to go to cell(x,y) in the smallest number of moves. But there are so many possible shortest path and in some of the path there are dangerous dragons. But Bob knows that if he uses the lexicographically kth shortest path, he will be able to avoid the dragons!

All possible shortest ways consist of some horizontal and some vertical moves, lets denote the moves by H and V.  A possible way to go from (0,0) to (2,2) is HVHV, that means he first made a horizontal move, then a vertical move, then a horizontal move again and finally a vertical move. HVVH can be another possible way but HVHV is lexicographically smaller that HVVH.

Given the value of k find the lexicographically kth path to go from (0,0) to (x,y) using smallest number of moves. Note that k is numbered from 0 to P-1 where P is number of possible paths. So for the example above HHVV is the lexicograpically 0th path.

Input Parameters:
You need to complete a function gridLand. If will take an array of string inp as parameter. Each element of the inp will represent a single case in the form "x y k".

Return Value:
Return an array of string, ith element of the array should contain answer of ith test case.

Constraints
1 <= |inp| <=100000
1 <= x <= 10
1 <= y <= 10
0 <= k < number of paths

Sample Input
inp={"2 2 2", "2 2 3",}
Sample Output
{"HVVH","VHHV"}
Explanation
All the paths of going to (2,2) from (0,0) in lexicographically increasing order:

0. HHVV
1. HVHV
2. HVVH
3. VHHV
4. VHVH
5. VVHH

HankerRank code pair,要跑的,精简一下就是说,从(0,0)到(x,y),会产生一个路径string,路径一定是x个H和y个V组成的,再给你一个K,求在所有路径里面按照字母排序的第K个路径。

我最开始就在想每一位可以根据x,y,k,total number of paths得到一定的结论是H还是V,没想通,后来觉得直接去写递归可能会中途有灵感。感觉类似binary string,但是1和0的资源有限。
然后只能起始HHHHHVVVV,dfs然后维护一个K, 每有一个结果就k减1,k是0的时候输出当前的结果,相当于求permutation,然而被三哥说是brute force,有没有更好的办法。于是又回到上面的想法,然后就跪了。。。

最后问了一下三哥,他说可以每一位根据当前x,y,k知道要选啥,然后进入下一个sub problem。就这样,供大家讨论一下,也不是真的有多难,当时不要被唬住,顺便求点大米。。



. from: 1point3acres


. 围观我们@1point 3 acres

darkwowgamer 发表于 2015-10-23 01:39:53 | 显示全部楼层
感觉好难啊, 楼主有什么思路吗?
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-10-23 02:12:55 | 显示全部楼层
darkwowgamer 发表于 2015-10-23 01:39
.1point3acres网感觉好难啊, 楼主有什么思路吗?

个人感觉是递归
总共是(x+y)!/x!/y!种,
然后,如果k> (x-1+y)/(x-1)!/y!,第一个就是V,要不然第一个就是H,然后递归第二个,。。。
回复 支持 反对

使用道具 举报

 楼主| danielame1264 发表于 2015-10-23 02:38:53 | 显示全部楼层
就是递归,类似于leetcode的permutation sequence那道题的数学解法,楼上说的似乎有道理。
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-10-27 01:19:39 | 显示全部楼层
danielame1264 发表于 2015-10-23 02:38. From 1point 3acres bbs
就是递归,类似于leetcode的permutation sequence那道题的数学解法,楼上说的似乎有道理。
. more info on 1point3acres
permutation sequence那题是把1,2,3,4,5,。。这样不重复的数排列,但楼主这题是几个H几个V进行排列,有重复啊
回复 支持 反对

使用道具 举报

 楼主| danielame1264 发表于 2015-10-27 01:30:51 | 显示全部楼层
liyanjia92 发表于 2015-10-27 01:19
permutation sequence那题是把1,2,3,4,5,。。这样不重复的数排列,但楼主这题是几个H几个V进行排列 ...

所以我说类似啊,本质上是一样的,都是知道每一位一定是什么。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-12-4 10:03:14 | 显示全部楼层
请问lz  HankerRank code pair,要跑的是说要通过run之后通过所有test case吗?
回复 支持 反对

使用道具 举报

ZaneRan 发表于 2016-11-1 12:01:23 | 显示全部楼层
求助一下,这道题有没有比较好的解法,除了暴力解?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-24 14:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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