dropbox面经，vmware oa 题目

dropbox, letter combination of phone number
vmware: 一个2d gr

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

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

rate all combinaton再找第几个，求简单解法

VM的题感觉可以转换为给两个不同的字母，然后返回长度为L的第n个permutation。引文只有两个字母，还要求按字母顺序，所以可以这么做
给定h,v, h的字母顺序比较小，所以h=0, v=1, 如果要从[0,0] -> [2,2], k=3
距离是4，所以我们要生成长度为4的且0和1数量相等的第k个组合，然后这个问题就转换为
从000111开始，执行（next higher number with same set bit）k次，然后把结果的二进制的0和1替换为h和v

然后在g4g上找到了这个 http://www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/
这个算法O(1) space O(k) time, 不过感觉那么短时间根本想不出来

ShawnG 发表于 2016-9-1 11:21
先dp算出每个格有多少种走法，再每次判断每一步是否应该向下还是向右：大于一半向下；小于等于向右。

谢谢回复，很赞的想法，请问你看看我理解对了吗
比如（0，0）到（2， 3）3个h和2个v, 是边走变找第k个吗？
     0   1           2       3
0        h
1   v   hv/vh
比如到了1,1的位置，有2种情况，比如要求的最终k＝1
（第0种，最靠前的），那就向右走，对吗？谢谢指教。

jellyld 发表于 2016-8-24 06:59
说错了，是从0011开始

谢谢解答，不好意思，稍微有点没明白，比如从0，0到3，2， 那么应该是3个v两个h的permutation,也就是2个0,3个1的组合
最小的肯定是00011，最大的是11000
然后按照这个get next higher number的方法求下一个next number对吗？只要k不是大于2个0和3个1permutation的总数，就可以，对吗。就是说除非到了11000求next

总觉得一定有简单的解法，比如按照这个lexi order generate，或者dp之类的，求教

感觉就是个dp吧，对于f[i][j]来说, f[i - 1][j] + 'h' 和f[i][j - 1] + 'v' 已经是有序的了，merge一下就可以保证是有序的。

太谢谢啦，很棒的思路！～所以对于每个(x,y)保存一个list，所以dp[i][j]应该存一个list
f[i-1][j]的list和f[i][j-1]的list都一样长，无法保证前一个list中所有的都比后一个靠前，所以需要merge，如何merge效率比较高呢？

我觉得就是普通的merge吧，没想到更好的方法～

jellyld 发表于 2016-8-24 06:56
VM的题感觉可以转换为给两个不同的字母，然后返回长度为L的第n个permutation。引文只有两个字母，还要求按 ...

说错了，是从0011开始

楼主是内推的还是海投哇？

先dp算出每个格有多少种走法，再每次判断每一步是否应该向下还是向右：大于一半向下；小于等于向右。