一亩三分地论坛

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

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

Zappos OA 算法题

[复制链接] |试试Instant~ |关注本帖
大成若缺 发表于 2016-2-9 14:48:09 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Zappos - 网上海投 - 在线笔试 |Other其他

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

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

x
第一次做OA,四道题. visit 1point3acres.com for more.
1、给一个字符串,返回回文子字符串个数

2、在一个万圣节派对上,有一块无限大的长方形巧克力,小红切给她的男朋友吃。只能切成1*1的正方形,他一共能切N刀,求问最多能产生几颗巧克力。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
N = 5: 2 * 3 = 6块. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
N = 6: 3 * 3 = 9块
N = 100000: 50000 * 50000 = 2500000000块
. more info on 1point3acres.com
3、小明想给他的女朋友写情书,但是羞于写得太露骨,于是希望写成只有非常intelligent的人才能看得懂的情书。给一个字符串,将它变成回文,求问需要多少次变化。每次变化之能decrement其中的一个字母。
abcd -> abba
abcd -> abcc -> abcb -> abca - > abba


4、对于一个二维数组(x, y),每次可以有两种运算,一种是变成(x + y, y),一种是变成(x, x + y)。问给四个整数a、b、c和d,(c, d)是否可能由(a, b)经过这种变化变成。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

1

查看全部评分

hyj143 发表于 2016-2-11 02:08:38 | 显示全部楼层
syxgtsyxgt 发表于 2016-2-10 15:19
第三题也没有思路 哭了
. Waral 鍗氬鏈夋洿澶氭枃绔,
double pointer 一前一后轮流扫, 找两个字母的差距
回复 支持 1 反对 0

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-10 10:57:19 | 显示全部楼层
jedihy 发表于 2016-2-10 09:21. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
lc有相似的题目longest palindrome substring,n^2的明显比n^3快很多,n^3用python根本没法ac 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (20 ...

好的,你把O(n)的算法讲出来,我给你大米
回复 支持 1 反对 0

使用道具 举报

googlerr 发表于 2016-2-9 15:58:36 | 显示全部楼层
第二题 感觉是偶数就是n^2/4 奇数就是(n-1)/2*(n+1)/2 不知对否?
回复 支持 反对

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-9 16:05:59 | 显示全部楼层
googlerr 发表于 2016-2-9 15:58
第二题 感觉是偶数就是n^2/4 奇数就是(n-1)/2*(n+1)/2 不知对否?

奇数是 (n / 2) * (n / 2 + 1)
偶数是 (n / 2) * (n / 2).鏈枃鍘熷垱鑷1point3acres璁哄潧
主要是超出范围的处理
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-2-9 16:20:04 | 显示全部楼层
第四题 a,b,c,d 有正数有负数么?
回复 支持 反对

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-9 16:46:19 | 显示全部楼层
没有考虑这个问题 不妨碍吧?
回复 支持 反对

使用道具 举报

白丁117 发表于 2016-2-10 00:58:56 | 显示全部楼层
请问lz zappos的intern是不是只能去las vegas? thx
回复 支持 反对

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-10 01:45:47 | 显示全部楼层
hyj143 发表于 2016-2-9 16:20.鐣欏璁哄潧-涓浜-涓夊垎鍦
第四题 a,b,c,d 有正数有负数么?
.1point3acres缃
我想了一下 是正数
回复 支持 反对

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-10 01:46:13 | 显示全部楼层
白丁117 发表于 2016-2-10 00:58
请问lz zappos的intern是不是只能去las vegas? thx

好像是 youarewelcome
回复 支持 反对

使用道具 举报

uhey 发表于 2016-2-10 01:57:16 | 显示全部楼层
想问最后一题,用的什么方法做的
回复 支持 反对

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-10 04:12:38 | 显示全部楼层
uhey 发表于 2016-2-10 01:57
想问最后一题,用的什么方法做的

我用的BFS
回复 支持 反对

使用道具 举报

liujzhi2 发表于 2016-2-10 04:45:56 | 显示全部楼层
想问下楼主第一题的time complexity,  我的想法总是你n^3....
回复 支持 反对

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-10 04:55:32 | 显示全部楼层
liujzhi2 发表于 2016-2-10 04:45. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
想问下楼主第一题的time complexity,  我的想法总是你n^3....

第一题是最难的
我用n^3做的 快的方法没想出来
回复 支持 反对

使用道具 举报

liujzhi2 发表于 2016-2-10 06:03:53 | 显示全部楼层
感觉只能这样做啊, 要不然就要dfs。。更慢。。。
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-2-10 08:02:28 | 显示全部楼层
大成若缺 发表于 2016-2-10 01:45
我想了一下 是正数

好的哈 如果全是正数的话 就简单很多~
回复 支持 反对

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-10 08:03:17 | 显示全部楼层
hyj143 发表于 2016-2-10 08:02. 鍥磋鎴戜滑@1point 3 acres
好的哈 如果全是正数的话 就简单很多~

是正数 但是我可能没有用最优解
回复 支持 反对

使用道具 举报

SuperMe 发表于 2016-2-10 08:57:24 | 显示全部楼层
第三题如果字符串是 ceeb 结果是多少
回复 支持 反对

使用道具 举报

jedihy 发表于 2016-2-10 09:05:21 | 显示全部楼层
大成若缺 发表于 2016-2-10 04:55
第一题是最难的
我用n^3做的 快的方法没想出来

最快O(n)可以做,但是太难写。
O(n^2)可以很简单的写出来,就是扫描数组的时候,把那个字符当成回文的中点,往两边看是否可以扩展。
这里有两种情况。
回文长度是奇数/偶数。偶数就是两个字符为中点,奇数就一个字符为中点。


补充内容 (2016-2-10 09:06):
能够我加大米吗

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-10 09:15:12 | 显示全部楼层
jedihy 发表于 2016-2-10 09:05
最快O(n)可以做,但是太难写。
O(n^2)可以很简单的写出来,就是扫描数组的时候,把那个字符当成回文的中 ...

对, 这是manchester算法
但是这种比n^3还要慢 不知道为什么
回复 支持 反对

使用道具 举报

jedihy 发表于 2016-2-10 09:21:43 | 显示全部楼层
lc有相似的题目longest palindrome substring,n^2的明显比n^3快很多,n^3用python根本没法ac

补充内容 (2016-2-10 09:22):
求大米
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 18:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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