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

一亩三分地论坛

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

dropbox面经,vmware oa 题目

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

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

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

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

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


评分

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.本文原创自1point3acres论坛
距离是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, 不过感觉那么短时间根本想不出来

回复 支持 反对

使用道具 举报

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. more info on 1point3acres
然后按照这个get next higher number的方法求下一个next number对吗?只要k不是大于2个0和3个1permutation的总数,就可以,对吗。就是说除非到了11000求next
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

小逻辑 发表于 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. from: 1point3acres
1   v   hv/vh
比如到了1,1的位置,有2种情况,比如要求的最终k=1-google 1point3acres
(第0种,最靠前的),那就向右走,对吗?谢谢指教。
回复 支持 反对

使用道具 举报

ShawnG 发表于 2016-9-2 02:05:35 | 显示全部楼层
pinkdatura 发表于 2016-9-1 11:47. 1point 3acres 论坛
谢谢回复,很赞的想法,请问你看看我理解对了吗
比如(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?就一道题吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-24 10:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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