一亩三分地论坛

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

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

Zenefits电面,带原始题目。

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

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

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

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

x
刚刚面完的Zenefits电面,感觉是一个人在印度的三哥,没有寒暄,直接上题, 题目是glassdoor上有的,很长,但废话很多,全文如下:
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!
. visit 1point3acres.com for more.
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.
. From 1point 3acres bbs
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,有没有更好的办法。于是又回到上面的想法,然后就跪了。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
最后问了一下三哥,他说可以每一位根据当前x,y,k知道要选啥,然后进入下一个sub problem。就这样,供大家讨论一下,也不是真的有多难,当时不要被唬住,顺便求点大米。。








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

使用道具 举报

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

个人感觉是递归
总共是(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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
就是递归,类似于leetcode的permutation sequence那道题的数学解法,楼上说的似乎有道理。

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 | 显示全部楼层
求助一下,这道题有没有比较好的解法,除了暴力解?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 04:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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