一亩三分地论坛

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

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

dropbox面经,vmware oa 题目

[复制链接] |试试Instant~ |关注本帖
pinkdatura 发表于 2016-8-4 00:13:22 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Dropbox - 内推 - 技术电面 |Pass在职跳槽

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

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

x
dropbox, letter combination of phone number
vmware: 一个2d grid,可以向下用v,可以向右用h,从左上角开始走,到一个点有好几种hv的排列组合,返回他们按字母顺序的的排列,比如0,0 到2,2. 鍥磋鎴戜滑@1point 3 acres
0 hhvv
1 hvhv
2 hvvh
3 vhhv
4 vhvh
5 vvhh
比如给你(2,2)还有3那你就得返回vhhv,
我基本是generate all combinaton再找第几个,求简单解法

.1point3acres缃. 鍥磋鎴戜滑@1point 3 acres

评分

1

查看全部评分

 楼主| pinkdatura 发表于 2016-8-4 00:17:23 | 显示全部楼层
总觉得一定有简单的解法,比如按照这个lexi order generate,或者dp之类的,求教
回复 支持 反对

使用道具 举报

liangyue268 发表于 2016-8-4 01:23:41 | 显示全部楼层
感觉就是个dp吧,对于f[i][j]来说, f[i - 1][j] + 'h' 和f[i][j - 1] + 'v' 已经是有序的了,merge一下就可以保证是有序的。
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-4 02:29:55 | 显示全部楼层
太谢谢啦,很棒的思路!~所以对于每个(x,y)保存一个list,所以dp[i][j]应该存一个list
f[i-1][j]的list和f[i][j-1]的list都一样长,无法保证前一个list中所有的都比后一个靠前,所以需要merge,如何merge效率比较高呢?
回复 支持 反对

使用道具 举报

liangyue268 发表于 2016-8-4 06:57:18 | 显示全部楼层
我觉得就是普通的merge吧,没想到更好的方法~
回复 支持 反对

使用道具 举报

jellyld 发表于 2016-8-24 06:56:31 | 显示全部楼层
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-google 1point3acres

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

回复 支持 反对

使用道具 举报

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

说错了,是从0011开始
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-28 04:06:01 | 显示全部楼层
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
回复 支持 反对

使用道具 举报

小逻辑 发表于 2016-8-30 02:30:21 | 显示全部楼层
楼主是内推的还是海投哇?
回复 支持 反对

使用道具 举报

ShawnG 发表于 2016-9-1 11:21:31 | 显示全部楼层
先dp算出每个格有多少种走法,再每次判断每一步是否应该向下还是向右:大于一半向下;小于等于向右。
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-9-1 11:47:10 | 显示全部楼层
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种,最靠前的),那就向右走,对吗?谢谢指教。
回复 支持 反对

使用道具 举报

ShawnG 发表于 2016-9-2 02:05:35 | 显示全部楼层
pinkdatura 发表于 2016-9-1 11:47
谢谢回复,很赞的想法,请问你看看我理解对了吗. visit 1point3acres.com for more.
比如(0,0)到(2, 3)3个h和2个v, 是边走变找第k个吗 ...

恩恩差不多这个意思~ 如果k>n/2,需要将k减去n/2就好了,这个思路把全排列都写出来就秒懂
回复 支持 反对

使用道具 举报

UCLA_andy 发表于 2016-9-14 08:52:26 | 显示全部楼层
想问下楼主VM是什么职位的OA?就一道题吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 08:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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