10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 1080|回复: 16
收起左侧

亚麻Onsite新题

[复制链接] |试试Instant~ |关注本帖

2017(7-9月) 码农类 硕士 全职@Amazon - 内推 - Onsite |Fail在职跳槽

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

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

x
  1. 亚马逊的一个新题。<div>给一组操作,[left, left, right],然后长度是8</div><div>想象折纸,刚开始是1,2,3,4,5,6,7,8</div><div>left折就是</div><div>4,3,2,1</div><div>5,6,7,8</div><div>然后再按照left折就是</div><div>6,5</div><div>3,4</div><div>2,1</div><div>7,8</div><div>然后再按照right折就是</div><div>8</div><div>1</div><div>4</div><div>5</div><div>6</div><div>3</div><div>2</div><div>7</div><div>最后的结果就是8,1,4,5,6,3,2,7</div><div>就是按照这个按照这个操作,给出最后的输出结果。要求time log(n)</div>
复制代码

本帖被以下淘专辑推荐:

  • · Amazon|主题: 95, 订阅: 38
  • · Amazon|主题: 183, 订阅: 12
 楼主| f1371342385 发表于 4 天前 | 显示全部楼层
刚开始是1,2,3,4,5,6,7,8
第一次left:-google 1point3acres
4,3,2,1
5,6,7,8
第二次left
6,5
3,4
2,1
7,8
第三次right
8.鐣欏璁哄潧-涓浜-涓夊垎鍦
1.鏈枃鍘熷垱鑷1point3acres璁哄潧
4
5
6
3. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
2
7
最后的结果就是8,1,4,5,6,3,2,7
回复 支持 反对

使用道具 举报

RightSoFar 发表于 4 天前 | 显示全部楼层
看的眼花,整理一下
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
亚马逊的一个新题。
给一组操作,[left, left, right],然后长度是8
想象折纸,刚开始是1,2,3,4,5,6,7,8. more info on 1point3acres.com
left折就是
4,3,2,1
5,6,7,8-google 1point3acres
然后再按照left折就是
6,5
3,4. 鍥磋鎴戜滑@1point 3 acres
2,1. 1point3acres.com/bbs
7,8
然后再按照right折就是
8
1
4
5
6
3. 1point 3acres 璁哄潧
2
7
最后的结果就是8,1,4,5,6,3,2,7
就是按照这个按照这个操作,给出最后的输出结果。要求time log(n)
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 4 天前 | 显示全部楼层
RightSoFar 发表于 2017-9-16 10:24. From 1point 3acres bbs
看的眼花,整理一下-google 1point3acres

亚马逊的一个新题。

对的,老哥 稳!
回复 支持 反对

使用道具 举报

群星的尽头 发表于 3 天前 | 显示全部楼层
log(n)遍历一遍都不够吧?n * log(n) 倒是可以。
回复 支持 反对

使用道具 举报

xqdingo 发表于 3 天前 | 显示全部楼层
LZ求个思路~
回复 支持 反对

使用道具 举报

64203221 发表于 3 天前 | 显示全部楼层
二分查找就可以了吧
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 3 天前 | 显示全部楼层
64203221 发表于 2017-9-17 10:08
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 二分查找就可以了吧

想象折纸,这题最tricy的地方就是底下的会翻上去,想象一张1,2,3,4,5,6,7,8的纸条,然后来折。二分查找肯定不行
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 3 天前 | 显示全部楼层
群星的尽头 发表于 2017-9-17 09:50
log(n)遍历一遍都不够吧?n * log(n) 倒是可以。

面试官直接说就要lgn
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 3 天前 | 显示全部楼层
xqdingo 发表于 2017-9-17 10:04.1point3acres缃
LZ求个思路~
. 1point 3acres 璁哄潧
没做出来。。。
回复 支持 反对

使用道具 举报

群星的尽头 发表于 3 天前 | 显示全部楼层
f1371342385 发表于 2017-9-17 11:12
面试官直接说就要lgn

就算不管过程,但要把所有数输一遍就是n的时间复杂度啊。。。。。。
回复 支持 反对

使用道具 举报

草莓宝宝乖 发表于 前天 04:05 | 显示全部楼层
楼主你好,我觉得这个题目有问题,也有可能是我太菜,楼主见谅。我觉得的是问题是,第一次折纸,是把又半部分往上翻往翻得到4321,5678;如果是按照这样的折纸方法,就是往左折的话都是把右半部分往上往左翻,那么第二轮结果应该是21,78,65,34, 但是按照楼主接下去的操作都是右半部分往下折然后往左折。这样的话,不就是不一样的规律了吗?不知道我说的清楚不,望各位大神指教!. more info on 1point3acres.com

补充内容 (2017-9-18 04:07):
我觉得折纸的方向操作应该都是一致的,这样才能得出唯一一个答案吧,要不然怎么算这个答案呢?
回复 支持 反对

使用道具 举报

草莓宝宝乖 发表于 前天 04:08 | 显示全部楼层
草莓宝宝乖 发表于 2017-9-18 04:05.1point3acres缃
楼主你好,我觉得这个题目有问题,也有可能是我太菜,楼主见谅。我觉得的是问题是,第一次折纸,是把又半部 ...

时间复杂度的事情,我同意楼上的,一个数组再怎么样都要遍历一遍,那肯定是n了
回复 支持 反对

使用道具 举报

seannaes 发表于 前天 04:21 | 显示全部楼层
同求思路,答案数组就已经是n个数了,如果做到log(n)

补充内容 (2017-9-18 05:15):
这题感觉这个n 是长度而不是操作的次数把,这样应该就可以 log(n)了
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 前天 08:50 | 显示全部楼层
草莓宝宝乖 发表于 2017-9-18 04:05
楼主你好,我觉得这个题目有问题,也有可能是我太菜,楼主见谅。我觉得的是问题是,第一次折纸,是把又半部 ...

您好,您自己画一个纸片,自己试试就知道了,输入可能是LLR LLL RRR这种的,数组的长度是2^(len("LLL")),意思就是假如一开始给的是LL那么就是长度就是4,是LLL长度就是8,如果是LLLL那么长度就是16
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 前天 08:56 | 显示全部楼层
seannaes 发表于 2017-9-18 04:21. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
同求思路,答案数组就已经是n个数了,如果做到log(n)

补充内容 (2017-9-18 05:15):

对的,n是数组的长度,不是操作的次数
回复 支持 反对

使用道具 举报

草莓宝宝乖 发表于 前天 13:37 | 显示全部楼层
f1371342385 发表于 2017-9-18 08:50
您好,您自己画一个纸片,自己试试就知道了,输入可能是LLR LLL RRR这种的,数组的长度是2^(len("LLL")) ...

求思路,不知道该怎么做
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-20 03:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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