一亩三分地论坛

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

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

Teradata and Amazon 面试总结,积攒人品

[复制链接] |试试Instant~ |关注本帖
tangxukai 发表于 2014-3-4 02:07:15 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 本科 实习@Amazon - 校园招聘会 - HR筛选 校园招聘会 |Other

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

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

x
背景:加州USC,编程一般,经历比较龊,网上投了一些简历,然后拿到若干面试,amazon和teradata面试结束,正在等待结果,拿点面经分享一下。
teradata:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1. 一个未排序的数组有一千万,里有若干个数缺失,找出那几个数。
2.求实现segment tree的插入删除增加操作。
amazon:
1.一个数组里有很多个字符串,求出现频率第k大的字符串(注意可能有多个哦)。
2.求一个数的所有因数。
3.boggle problem。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
经验:刷题是王道,算法思路总结是王道。楼主当时卡死在因数那道题了,估计是早饭没吃,大脑缺血了:(。祝大家好运,好好学习

评分

6

查看全部评分

北美农民 发表于 2014-3-4 02:14:04 | 显示全部楼层
楼主teradata第一题咋做的? amz第2题咋做的? 第三题是啥意思?
回复 支持 反对

使用道具 举报

 楼主| tangxukai 发表于 2014-3-4 05:51:05 | 显示全部楼层

teradata第一题用bit vector,这样利用bit来存储相应的数字是否出现过。
amz第二题本来是可以直接暴力做的,我选择了先求出质因数然后做combination相乘,在质因数那里卡主了。
第三题:. From 1point 3acres bbs
假设有一个字符序列"txeddsa",然后给你一个字典:"xeddsa","saxeddt","faienfoma",。。。
要求判断字符序列的所有permutation中,字典中会不会出现相同的。
我的做法就是先写个递归的permutation,然后N^2查找。
回复 支持 反对

使用道具 举报

austurela 发表于 2014-3-4 07:12:45 | 显示全部楼层
lz shi da ji de undergrad? GanJue KaoDe HaoNan A...
回复 支持 反对

使用道具 举报

 楼主| tangxukai 发表于 2014-3-4 08:03:04 | 显示全部楼层
austurela 发表于 2014-3-4 07:12
lz shi da ji de undergrad? GanJue KaoDe HaoNan A...

南加州master第二个学期。其实也不难,就是跟cracking code完全不一样。
回复 支持 反对

使用道具 举报

sumingche 发表于 2014-3-4 11:11:38 | 显示全部楼层
tangxukai 发表于 2014-3-3 16:51 . Waral 鍗氬鏈夋洿澶氭枃绔,
teradata第一题用bit vector,这样利用bit来存储相应的数字是否出现过。
amz第二题本来是可以直接暴力做 ...

teradata 这家hr 邮箱可以告诉下吗?
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-4 12:06:16 | 显示全部楼层
tangxukai 发表于 2014-3-3 16:51
teradata第一题用bit vector,这样利用bit来存储相应的数字是否出现过。
amz第二题本来是可以直接暴力做 ...

一千万个请问你咋知道缺失的那个是哪个啊?  比如原长度为5数组是{1,3,4,5,6}, 现在的数组是{1,5,6} 你咋知道缺了啥?

算因子那道题可以用一个hash, 每次往里边加质数因子以及把已有的乘一遍也加进去。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

boggle那道题你应该用anagram的办法, 或者统计每个char出现的频率是否一样就够了。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-4 12:14:11 | 显示全部楼层
居然要求实现线段树, 日哦。 咋不出树状数组呢。。
回复 支持 反对

使用道具 举报

lhn9021 发表于 2014-3-4 12:30:30 | 显示全部楼层
北美农民 发表于 2014-3-4 12:06
一千万个请问你咋知道缺失的那个是哪个啊?  比如原长度为5数组是{1,3,4,5,6}, 现在的数组是{1,5,6} ...
. From 1point 3acres bbs
bit array[] java用 bitset 然后 set(index, true) 然后从头到尾扫描就行了

补充内容 (2014-3-4 12:31):
这题肯定是给定范围 缺失几个数  把你原数组改成 1 2 3 4 5 6就对了
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-4 12:33:53 | 显示全部楼层
lhn9021 发表于 2014-3-3 23:30 .鐣欏璁哄潧-涓浜-涓夊垎鍦
bit array[] java用 bitset 然后 set(index, true) 然后从头到尾扫描就行了

补充内容 (2014-3-4 12:31): ...
. From 1point 3acres bbs
你的case的话, 不需要用额外空间。
回复 支持 反对

使用道具 举报

lhn9021 发表于 2014-3-4 13:05:46 | 显示全部楼层
北美农民 发表于 2014-3-4 12:33 . 1point 3acres 璁哄潧
你的case的话, 不需要用额外空间。

{56, 3, 23, 77....}总共2千万个数 范围3-30000003
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-4 13:09:20 | 显示全部楼层
lhn9021 发表于 2014-3-4 00:05
{56, 3, 23, 77....}总共2千万个数 范围3-30000003

这样每个数放到对应有序的位置就行了,in place, 记录没有出现的位置就行。

n/32的空间复杂度还是n
回复 支持 反对

使用道具 举报

lhn9021 发表于 2014-3-4 13:19:54 | 显示全部楼层
北美农民 发表于 2014-3-4 13:09
这样每个数放到对应有序的位置就行了,in place, 记录没有出现的位置就行。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

n/32的空间复杂度还是n

inplace swap是没问题 不过我觉得你应该考虑一下3kw int的空间是多大
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-4 13:25:17 | 显示全部楼层
lhn9021 发表于 2014-3-4 00:19
inplace swap是没问题 不过我觉得你应该考虑一下3kw int的空间是多大

啥意思? in place还要考虑别的啥?
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-4 13:33:52 | 显示全部楼层
lhn9021 发表于 2014-3-4 00:05
{56, 3, 23, 77....}总共2千万个数 范围3-30000003

我重新看了lz的题目。 1000W个数, 若干个缺失。 我的问题是, 不知道缺失的是哪些怎么找。 你的assumption是每个数有范围, 2千万个数范围3-30000003, 请问这个case是怎么知道哪些是缺失的?
回复 支持 反对

使用道具 举报

 楼主| tangxukai 发表于 2014-3-5 00:50:04 | 显示全部楼层
北美农民 发表于 2014-3-4 12:06 . Waral 鍗氬鏈夋洿澶氭枃绔,
一千万个请问你咋知道缺失的那个是哪个啊?  比如原长度为5数组是{1,3,4,5,6}, 现在的数组是{1,5,6} ...

说的对,用anagram的方法显然要更好。
回复 支持 反对

使用道具 举报

 楼主| tangxukai 发表于 2014-3-5 00:50:58 | 显示全部楼层
北美农民 发表于 2014-3-4 13:09
这样每个数放到对应有序的位置就行了,in place, 记录没有出现的位置就行。

n/32的空间复杂度还是n

. 鍥磋鎴戜滑@1point 3 acres做大数据的,n 和 n/32的区别还是很大的,
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-5 00:52:13 | 显示全部楼层
tangxukai 发表于 2014-3-4 11:50 . From 1point 3acres bbs
做大数据的,n 和 n/32的区别还是很大的,

你怎么知道哪些数缺失了? 还是数据范围就是1-1000W? 如果是的话, n/32的空间都不需要
回复 支持 反对

使用道具 举报

 楼主| tangxukai 发表于 2014-3-5 00:56:58 | 显示全部楼层
北美农民 发表于 2014-3-5 00:52
你怎么知道哪些数缺失了? 还是数据范围就是1-1000W? 如果是的话, n/32的空间都不需要

我在题中忘记讲了,这个数据范围就是假定1 - 1000W. 你是怎么做到n/32空间都不用的?
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-5 01:02:19 | 显示全部楼层
tangxukai 发表于 2014-3-4 11:56
我在题中忘记讲了,这个数据范围就是假定1 - 1000W. 你是怎么做到n/32空间都不用的?

检查元素i是不是在index [i - 1]上, 如果不是就放到这个位置上, 然后对这个位置上的元素继续迭代这个过程。 最后看如果位置i没有元素 i + 1, 那么i + 1就缺失了。 也是线性的。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 06:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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