i***1
发帖数: 95 | 1 很有意思的题目。。。
我有个idea，如果一个串是palindrome，那么对它的hash，从头到尾，和从尾到头是一
样的。
譬如用这样的hash方法。
int hash(char a[], int n)
{
int res = 0;
for(int i=0;i
res = ((res*37)+(int)char[i])%3137;
}
在扫描的同时，保存另一个hash值。（和上面的hash方法要有点变化）
在此基础上，可以用bloom filter的方法，减少false positive的可能性。 |
|
k***g
发帖数: 58 | 2 不知道这个bitmap有什么用，原来数组中的数，出现次数肯定大于等于1，跟直接扫描
数组有区别？
上的数字，这
样这个hashtable的大小会小很多。 |
|
r*******3
发帖数: 35 | 3 在BOSTON，去面过一次，感觉氛围挺好，可惜被默拒了。 |
|
f****g
发帖数: 313 | 4 电话面试
1st:
1. 讨论我的博士研究项目
2. 如果SNMP agent不能获取数据，或者获取的数据不符合预期，如何诊断该问题？
3。我做过的最有挑战的项目是什么？
4。用邮件写代码,然后讨论我写的代码：
unsigned char * get(int sizeOfArray, int sizeOfRecord);
void release(unsigned char* ptr);
该函数可以实现：
unsigned char ** array = get(5, 10);
snprintf( array[0], 10, “hello world\n”);
snprintf( array[1], 10, “hello again\n”);
5。Java的基本概念
2nd
1。Apache的log file如何找访问量最大的网页 （用linux shell写个小script）
2。如果某网站访问量突然增加，可能是什么情况发生，如何确定各种情况（1。暂时的
Popularity激增 2. DDOS Attack 3. 网站添加新的内容）
3。Java基本概念+设计扑克牌的类
4。读re... 阅读全帖 |
|
l*********r
发帖数: 674 | 5 那个访问序列，A 1-2-3-4或者A 1-2算么？还是就是找长度为3的？如果长度不定，2-3
, 3-4, 2-4也是答案阿（any subsquence of 2-3-4）。是不是找最长的sequence？这
样2-3-4就是唯一解了。 |
|
s*********l
发帖数: 103 | 6
所以对这道题来说，即使不用额外空间，时间复杂度也是O(kN)，
k的上限和N无关, 所以不能说是O(N^2),而且平均情况下k会小很多
看出现重复的概率, 没有错, 样本空间越大,重复概率越低, 平均扫描长度越长,
所以对那些假定样本空间可以无限大的情况, 最坏情况下复杂度会退化到O(N^2), 但同
样用Hash的话,最坏情况下的时空复杂度会是多少? |
|
y***m
发帖数: 7027 | 7 发散式思考，选择最优策略，次优策略。。存list把。。。每个策略一个queue呢？这
样按原定计划就是一步步move out? 不过决策树也是挺好的解决模型吧
hashmap只是初步考虑，按棋子名取信息，不过你说的类似坐标方式二者结合可能会更
方便.. |
|
e****a
发帖数: 449 | 8 是啊，当时就觉得计算机比较体力活，而且当时也觉得高考高分，应该怎么都不会有生
计问题的，应该
可以去追求一些觉得有趣的东西，国家难道还会让高考高分的学生没饭吃吗？ 结果赤
裸裸的现实就是这
样..... |
|
s*****y
发帖数: 897 | 9 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
s*****y
发帖数: 897 | 10 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
d*******l
发帖数: 338 | 11 恩，居然大家都没注意到。上面想法一度有些混乱，总结一下，这题可以用递归做，每
个节点的maxsum依赖于3部分，一部分是根节点到它的sum，还有就是它左右子树向下的
最大path的sum，所以参数中要保存根节点到当前的sum，递归的过程中，在向下推的时
候是把这一部分求出来，向上收的时候是计算向下path的最大sum并且更新最大值。这
样应该没错了。 |
|
s***c
发帖数: 50 | 12
ssd的好处在于它的random access.
cache里每项记录要有一个refcount，如果一个记录正在被使用，它的refcount>0。这
样在evict时该记录就不会被reclaim了。 |
|
f********e
发帖数: 166 | 13 1.visit那个矩阵是不是必须当参数，不能当static变量？
2.destination不一定是右下角,应该传参，我不太清楚的是base case，我觉得是
destination上下左右四个位置，直接返回，加到path里，mark visit,而不是只是
destination 的左上角的位置
不对。。，应该是那个选为min的加到path里。。。咋判断啊？？
不知道对不对，嘿嘿，谢谢
样 |
|
y*******g
发帖数: 6599 | 14 DP？
是说Floyd–Warshall?
复杂度差的比较大吧
样 |
|
f********e
发帖数: 166 | 15 1.visit那个矩阵是不是必须当参数，不能当static变量？
2.destination不一定是右下角,应该传参，我不太清楚的是base case，我觉得是
destination上下左右四个位置，直接返回，加到path里，mark visit,而不是只是
destination 的左上角的位置
不对。。，应该是那个选为min的加到path里。。。咋判断啊？？
不知道对不对，嘿嘿，谢谢
样 |
|
y*******g
发帖数: 6599 | 16 DP？
是说Floyd–Warshall?
复杂度差的比较大吧
样 |
|
c**j
发帖数: 103 | 17 这个太牛了！big cong！
能问下 数学这方面怎么准备吗？
你那个数学方面的题 大概是 概率的？ 几何的？ （求点线距离，点在polygon内这
样的）
还是 线代 高数的？ 认识个印度人（master）google intern被问了differential
equation.. 数学这方面就是把大学的全都再看看？ |
|
c**j
发帖数: 103 | 18 这个太牛了！big cong！
能问下 数学这方面怎么准备吗？
你那个数学方面的题 大概是 概率的？ 几何的？ （求点线距离，点在polygon内这
样的）
还是 线代 高数的？ 认识个印度人（master）google intern被问了differential
equation.. 数学这方面就是把大学的全都再看看？ |
|
r**********1
发帖数: 292 | 19 我又看了一遍，这段就是对叶子节点的直接处理，避免了进一步的call。 我不觉的这
样有啥不妥的。 |
|
c*****r
发帖数: 108 | 20 来自主题: JobHunting版 - 电面犯二了 我觉得这个题目是挺容易搞错的。 当时他这么问的，说given two binary search
trees, write a function to decide whether they contain he same value(s)...
我不记得他说的是value还是values了。 反正中间我以为只要两棵树有一个value是一
样的就好了。于是解法就如你所说。 然后听了他的testcase以后，才知道是要所有的
元素都一样，但是不考虑位置。 那么也就稍微modify一下记录一下count。
总之就是犯傻了。
search. |
|
p*i
发帖数: 411 | 21 第一题的virtual table应该是啥样的？
我想的是
class D
vtable (A)
+0 D:f(); // (D*)->f() evaluates to this
vtable (B)
+0 A:f(); // (D*)->B::f() evaluates to this
(D*)->A::f() is ambiguous
第2题要么给A定义一个不带参数的ctor，要么在B的ctor中explicitly call A's ctor
还有最后static_cast(B)应该改成 static_cast(B*)
static_cast(B)(new A(1))会去找B的接受一个A*参数的ctor（不存在），而且返回的不是指针 |
|
i*********7
发帖数: 348 | 22 答成屎一样。他让我随便写一个程序，然后问我，跑完了程序后，堆栈应该长啥样。
堆栈我倒没有画错。但是解释的跟屎一样。 |
|
i*********7
发帖数: 348 | 23 答成屎一样。他让我随便写一个程序，然后问我，跑完了程序后，堆栈应该长啥样。
堆栈我倒没有画错。但是解释的跟屎一样。 |
|
s*********5
发帖数: 514 | 24 我老面试的时候，有一个坏毛病，就是有时候问题一下子不好回答，假装没听懂，再问
一遍什么意思，争取思考时间，结果最新的一次面试，被批评沟通有问题，had
problem with larger concept, 我靠晕倒。
这两次就注意很多了，没听懂也假装听懂，然后说点大概念的话，慢慢套内容。
各位老中们还是要注意，面试的时候集中注意力听问题，语言表现尽量干净利落。
总之面试要注意听，不要乱说话。另外要表现谦虚，满脸笑容，和蔼可亲，像小甜甜一
样讨人喜欢。
还有写code不要急着写，可以放慢一点节凑，不要出错或者少出错。大错小错都不要。
写好了自己用一两个例子检查一下，再跟面试官说可以了。
我老发现现在面试遇到瓶颈了，拿不到offer往往是各种各样小问题，莫名其妙，不是
做题做不出。 |
|
r********g
发帖数: 1351 | 25 数组四个元素：5,6,3,3
最佳解法是：把5减成3，cost是2次decrements,把6减成3，cost是3次decrements，这
样得到的结果是：3,3,3,3 total cost是5
另外一个解法是：把最后2个3删掉，cost是3+3=6，这个就不是最优解法。
楼上的DP是正解。。。膜拜中。。 |
|
t**********h
发帖数: 2273 | 26 我不知道啊，别人贴出来的神贴，我保存了一下而已，我只能confirm Amazon是真的这
样的 |
|
C***U
发帖数: 2406 | 27 他是bst树
所以给定来的顺序以后树bst就确定了
可以用递归算法来做这个问题吧
N(k)=2(N(x)+N(y))
这里x是left subtree的node数
y是right subtree的node数
x+y=k-1
这里的2倍是因为left subtree和right subtree的进来顺序可以整体交换一下
不知道这个样对不对 |
|
g****y
发帖数: 240 | 28 trie默认是按照lexicographic order排序的。你可以按照frequency 排序吧。不过这
样就要有个update的问题。 |
|
|
|
b*******S
发帖数: 17 | 31 容错的话 先看有没有single point of failure
有的话 想办法变双份或多份 (请参考DNS的设计)
然后再来要问到底要那种层词的容错
是要挂掉后修得回来(Backup回来就可以继续动)
还是资源都给双份或多份 所以有错可以知道 或是可以经过计算把错误略掉
或是直接考虑东西本来就会东坏西坏 (如map reduce),把坏掉当常态 然后就把没算完
的重算就是
知道要那一种层次的容错后 就可以开始考虑各种resources 范例如下
CPU failure
RAM (e.g., ECC)
Storage (e.g., Hadoop file system)
Database (e.g., 异地备份)
Network (e.g., 双网路卡)
可扩展性就比较虎烂了
因为首先要知道甚么样的扩展性
是指memory space可以增大 还是CPU运算量可以一直冲
如果以Hadoop来讲 要变快就一直加 nodes,但是 map 跟reduce中间的中间值需要排序
等等 也会有个bottleneck,但是这bottle neck,可能不好估
像super computing就... 阅读全帖 |
|
|
P******r
发帖数: 842 | 33 这个linear解法简单，所以下一步应该是log，除非像那个同时找min和max的能从2n个
比较降到1.5n comparison。如果这么分析下来，就是devide and conquer了。即使这
样，答案也不好想。 |
|
s*******y
发帖数: 44 | 34 题目中说是set，我不放心问了是否允许重复，说允许。hash的办法可以处理这个重复
的情况。否则的话可以排序后用线性时间先去重，不影响最后的时间复杂度。
他面试还有个特点，在你写code的时候，不停地发问你这里好像不对吧，是不是应该这
样那样，思路很容易被打乱。也许边写边解释是一个应付面试官的办法，或者先写注释
伪码？这个实际中该怎么对付比较好？ |
|
l**b
发帖数: 457 | 35 刚刚电面的。东欧人，320 * 200 的screen，只能表示黑白2种颜色。要求你写一个
flip的function把某个长方形区域里面的pixel由黑变成白或者由白变成黑。
小结一下，一开始就说了用bit vector，结果觉得后悔了，应该先用int array的，这
样下手会快很多。结果一下子用一个array去表示，想怎么从x，y变成array index想了
半天。大脑抽筋了。 |
|
M******e
发帖数: 103 | 36 大概一个多月之前面的，期间多次Email问结果及报销的情况，HR均置之不理。这种情
况，知道自己肯定没戏。但不告诉我如何报销，让我非常郁闷。今天终于收到HR的据信
，也就放心了。
他家的面试一点不难，5个人有4个拿着简历问你以前做的项目，一副心不在焉的样子。
这也让我怀疑自己是被拉去做分母了。
一个三哥算是问了几个coding的问题。这位三哥毕业于阿三国烂校，拿了一个UC学校的
master. 在我以前面试遇到的面试官中，有的是看着聪明，交流起来觉得确实聪明；有
的是看着就不聪明，自己却非要装出一种聪明样。这位三哥就是后面这种情况。
整个面试出了三道编程题。对每一道题，要么作出咄咄逼人装，要么作出高深莫测装，
让人很不舒服。
第1道是2维平面有多个点，求出能给最多colinear的点的个数。CC150上有，hash
table解决。
第2道是在一个rotated array中找一个数，easy.
第3道是求kth number. 我说了两种方法， 1）heap O(nlongN) 和2）quick select O
(N)。他说写2）吧。Code很快写完了。他不停地问我time co... 阅读全帖 |
|
j******2
发帖数: 362 | 37 这样想会不会很naive
hash_map family_index
vector > family_members
每读一行，如果family_index里有parent没child或者有child没parent，新的那个就随
旧的那个加入family。如果两个都没有就新建一个family set。如果两个都有但是不一
样，就让child随parent，并把child的set和parent的set合并，并修改所有child成员
的family_index.
要查的时候就看family_index里两个id的值是不是一样。 |
|
b****g
发帖数: 192 | 38 how does HashMap works in Java？
我不明白问题是什么意思，他让我以put（key，value）为例，我就说用key算出
bucket的位置，把value存进去。
他就继续问我怎么用key算出存在hash表的位置。
这才明白他是在问我Java HashMap怎么计算hash value.跟他确认了一下，就是这个意
思。
我说就是用hash function算，他又问我到底是怎么算的，总之就是问得很细致，看样
子是要求我看过代码才行。
面试结束后，我按了一下这个页面
http://www.docjar.com/html/api/java/util/HashMap.java.html
不知道是不是源代码。
又找了一下hash函数，就是移位异或操作。
hash函数的输入参数是把key用hashCode函数计算成一个整数。hashcode的返回值实际
是object的address。
可是，java不是不能找地址吗？
我看了代码，不过hashCode函数前面有个native关键字，意思是用其他语言写的函数。
看来java里用别的语言写的函数来找对象地址了。
谁能找到... 阅读全帖 |
|
|
|
h*****9
发帖数: 6643 | 41 就瞧着 Applied Material 那 CEO 的 ＷＳ 样，就不该去。 |
|
y******e
发帖数: 193 | 42 没必要说。 只要不是在同一个老板手下， 或者你们两个是上下级， who cares？ 我
知道很多大公司里面， 夫妻都在同一个公司的大把大把。有的还特别喜欢招夫妻， 这
样稳定。 或者一个进来了， 再把自己的配偶搞进来。 让HR知道你们是一家唯一的影
响是， 有些公司可能会只有一份relocation package per family。 |
|
p*******4
发帖数: 45 | 43 做设计提的时候，他是会把要求都先给你提出来， 还是说要你自己一步一步问出来？
比如那个十字路口，具体要求会先给你提出来吗？？
另外，onsite的时候大家都穿啥样了。。。 |
|
r*********n
发帖数: 4553 | 44 1)从一堆distinct, not continuing, increasing integers里面找出 value和index一
样的数，in sublinear time
这到题可以用binary search吧 |
|
j******i
发帖数: 229 | 45 我一老美同事一直强烈反对招某人入组，基本是话都说绝了，还到处游说别的同事。最
后抗不住另一个大妈更强势，更说了算，终于还是招了（基本也是做个样给这人瞧瞧,
你瞎搅和，我就偏招)。结果这个同事头天来上班，我这同事跟那新来的一起聊得那个
亲热啊，而且还是主动凑过去嘘寒问暖的。
要是你，你猜得出来这人背后黑过你吗？可这就是现实，其他人看个满眼可谁会随便告
诉你？ |
|
a******e
发帖数: 710 | 46 对头。 我的research更是偏数学和Mac层。 而且是wireless的，和internet的还不一
样.. |
|
k******e
发帖数: 375 | 47 就是申请manager的职位啊。我问了recruiter了，她说虽然manager不用写code，但同
样得懂底层的技术，还得做code review。
我的技术强项其实这几年多在architecting, business processes这些方面。所以如果
真的考最基本的算法什么的，现在不复习的话一定回答得不够精确。 |
|
E********c
发帖数: 37 | 48 我的经历比较非典型，不过还是分享一下或许可以供极少数非码工人士参考。
职位是analytics相关的。 经过两轮电话面试，考察SQL和个人简历上的相关工作经历
，然后是一整天的onsite。面筋最后附上，先说我的问题吧。
我的背景从本科到master都属于文科，不过辅修了几门统计和数据库的课，因此去年毕
业后跑去一个startup做用户数据报告分析的工作，基本技能就是excel, sql, data
visualization 和一点点统计软件知识（R, SAS)了。最近并没有找工作不过忽然收到
Amazon recruiter的邮件，有点跃跃欲试，想见识一下大公司的面试是啥样的，也没想
到会拿offer什么的，就想锻炼一下面试技巧吧，于是答应了面试。结果一路运气很好
，很顺利地就拿到offer,现在就面临两难处境，到底是接收好呢还是放弃。
接受Offer的好处是，待遇比现在公司好，可以学到新东西，对career发展有帮助，我
现在的公司属于中小型的吧，没那么有名气。我的担心是亚马逊工作很累，（拿到
Offer后在 bbs查了下，大家都说work life balance是很差的），我... 阅读全帖 |
|
|
l*****u
发帖数: 20 | 50 最后一题不太懂，相同结点必须是位置一样，value一样？且父结点的value和位置也一
样？ |
|
