Zenefits电面，带原始题目。

刚刚面完的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!

All possible shortest ways consist of some horizontal and some vertical moves, lets denote the mov

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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。就这样，供大家讨论一下，也不是真的有多难，当时不要被唬住，顺便求点大米。。

感觉好难啊, 楼主有什么思路吗?

darkwowgamer 发表于 2015-10-23 01:39
感觉好难啊, 楼主有什么思路吗?

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

就是递归，类似于leetcode的permutation sequence那道题的数学解法，楼上说的似乎有道理。

danielame1264 发表于 2015-10-23 02:38
就是递归，类似于leetcode的permutation sequence那道题的数学解法，楼上说的似乎有道理。

permutation sequence那题是把1，2，3，4，5，。。这样不重复的数排列，但楼主这题是几个H几个V进行排列，有重复啊

liyanjia92 发表于 2015-10-27 01:19
permutation sequence那题是把1，2，3，4，5，。。这样不重复的数排列，但楼主这题是几个H几个V进行排列 ...

所以我说类似啊，本质上是一样的，都是知道每一位一定是什么。

请问lz  HankerRank code pair,要跑的是说要通过run之后通过所有test case吗？

求助一下，这道题有没有比较好的解法，除了暴力解？