发帖数: 1 | 1 曹擦 不就是 用个map 和移动sorted array 之后扫一遍两种基本方法选一种
然后再根据条件改一改
: 什么啊，2Sum的重复性在于，比如允许一个元素用两次，不允许一个元素用两次。
: 比如只有5，那input 10怎么办？
: 其次，如果有多个结果怎么办？要求都返回，怎么去重？
: 还有，如果不允许用HashTable怎么办？
: 总之，看似非常简单，其实snowday是不会的。
|
|
h*********n
发帖数: 11319 | 2 最简单的，现在就是Epic也不可能考2sum了。他这种没经验转行的，至少leetcode
medium起。
小蒙古明显是去jobhunting看了两天刷题贴就出来挖坑，但是积累不够，所以只能用上
他看得懂的素材，反而露馅了。 |
|
s***n
发帖数: 593 | 3 显然不是啊。
出多难的题，都会有华人去啃，还能啃下来。
像是黄皮马工进FLAG要刷题，出hard题。
人烙印三姐随随便便问个2sum就进了，白皮也是。
不管什么标准，要达到的目标都是限制黄皮infestation.
黄皮太多就是不好，念一千遍，就是摆在眼前的事实。 |
|
发帖数: 1 | 4 忘了这两是啥了。放狗找到以前已经做过。2SUM是faster than 98.86%。3SUM不行，只
比38%的快。 |
|
发帖数: 1 | 5 你懂个鸡巴。F1毕业了赶紧回国吧。现在还有想留美的？
再说了你会做2SUM吗，能找到工作吗 |
|
m*****f
发帖数: 1243 | 6 say a1, a2, a3, ....an:
compute the sum one by one and list them as a new list
a1, a1+a2, a1+a2+a3, a1+a2+a3+a4,.....,a1+....+an,
this will take O(n).
now the question becomes find two numbers a, b in this new list, that
a - b = that particular number, which is a typical 2sum problem solved
in O(n)
Possible follow-up: if the word "consequtive" is removed, then it becomes a
0/1 knapsack problem, could be solved by dp. |
|
b******t
发帖数: 965 | 7 两个指针一左一右往中间走
类似 sorted array之2sum problem |
|
b******t
发帖数: 965 | 8 两个指针一左一右往中间走
类似 sorted array之2sum problem |
|
r*****b
发帖数: 310 | 9 @utar: this approach may not work, as we may find duplicates in the 2sums.
For instance, give an array [3, 6, 2, 7, 4, 5], and the target 18, we may
find there are three entries whose value is 9. If we include the time
complexity for resolving the conflicts, the time complexity is not O(n^2).
Here is my post with an implementation with O(N^2 * LogN) complexity.
http://basicalgos.blogspot.com/2012/03/12-4sum_11.html
值, |
|
u**r
发帖数: 663 | 10 这个可以在找到匹配的时候附加判断吧。
哈希表里头可以记录每个2sum的元素index,找到匹配的时候判断以下index是否重复就
是了. |
|
r*****b
发帖数: 310 | 11 @utar: this approach may not work, as we may find duplicates in the 2sums.
For instance, give an array [3, 6, 2, 7, 4, 5], and the target 18, we may
find there are three entries whose value is 9. If we include the time
complexity for resolving the conflicts, the time complexity is not O(n^2).
Here is my post with an implementation with O(N^2 * LogN) complexity.
http://basicalgos.blogspot.com/2012/03/12-4sum_11.html
值, |
|
u**r
发帖数: 663 | 12 这个可以在找到匹配的时候附加判断吧。
哈希表里头可以记录每个2sum的元素index,找到匹配的时候判断以下index是否重复就
是了. |
|
l**********1
发帖数: 415 | 13 貌似这种的时间复杂度极高啊，而且用recursion的话，空间复杂度也很大啊。有没有
什么巧妙的算法呢?像2sum可以在O(nlogn) constant space得到。还是巧妙的算法对于
interview太过复杂，这个就足够了？谢谢！ |
|
|
g****y
发帖数: 240 | 15 第二题2sum？如果要速度的话，可以用hashtable。这样就可以O（n）了 |
|
j********g
发帖数: 244 | 16 3. 白板：找到sum是0的subarray，N^2 --> linear，写code。
这个是2sum吗。。。其他还有什么是可以linear的呀?。。。恕我愚钝。。 |
|
i****y
发帖数: 58 | 17 第一轮电面。。。果然是个三哥。。。
我人生的第一次面试就献给了A家。。能不跪么。。。
1.先自我介绍，我还扯了一个project
2.问啥是hash表，时间复杂度，怎么handle collison (我就说出了用list做chaining,
和open addressing)
那人问我还有啥。。。于是开始干笑。。。
3. 啥是polymorphism
4. 如何设计stack使得push() pop() min()都是constant time
5. 2sum题，给定一个int[] 一个target，求a+b=target pairs, allow duplicates .
求做法和时间复杂度。
我是用一个HashMap> 来做的，key存的是差，value里
存的是每个满足此差的index
三哥问我为啥hash表里要存index，不能存个数么。。
顺便求个bless, 看来以后要常驻此版了，大牛们关照。。。。 |
|
g*********e
发帖数: 14401 | 18 碰到烙印 必须问longest palindrome O(n)
碰到老中 就问2sum O(n) |
|
g*****e
发帖数: 282 | 19 应该是美国人，但就是听不清，不知道是不是对方免提或者别的问题，几乎每个问题都
要重复两遍，郁闷
聊了简历和项目，问了thread safe的一些东西，不深
两个题
1. if a string is a valid number
2. 2sum, and how to optimize it
大家好好做leetcode吧 |
|
j********g
发帖数: 244 | 20 2sum, and how to optimize it
which solution did you give? how to optimize? |
|
i******r
发帖数: 793 | 21 在网上申的Amazon
本来想申请社招岗位，HR非把我放到campus hire里面
第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
两次电面之后，HR说要追加一次电面。
第三次电面，两题：
如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
问的点，就改成用类似Floyd算法来做，但是效率就不高了。
第三次电面结束后几分钟，HR就发信把我拒了，难过了半天：（
回忆起来，第一次电面没做好，因为当时在路上，没法用电脑写程序，只能口述。
第三次电面，想来是最后一个图论题目没做好。
以后有机会再试试A家，不拿到onsite不甘心啊。 |
|
i******r
发帖数: 793 | 22 在网上申的Amazon
本来想申请社招岗位，HR非把我放到campus hire里面
第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
两次电面之后，HR说要追加一次电面。
第三次电面，两题：
如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
问的点，就改成用类似Floyd算法来做，但是效率就不高了。
第三次电面结束后几分钟，HR就发信把我拒了，难过了半天：（
回忆起来，第一次电面没做好，因为当时在路上，没法用电脑写程序，只能口述。
第三次电面，想来是最后一个图论题目没做好。
以后有机会再试试A家，不拿到onsite不甘心啊。 |
|
r*****e
发帖数: 146 | 23 确实是变成了2sum.
没有什么空间时间要求，就是想跟大家讨论讨论是否还有什么好方法。 |
|
r*****e
发帖数: 146 | 24 For BST case, time: O(N), space: O(N)
1) in-order scan the tree into an array,
2) 2sum scan the array
弱问一下，若是用get_next(), get_pre()从两边往中间扫。
具体的get_next()和get_pre()的实现是什么？
(1) 存个临时变量，以及相应的栈？ 若是如此，每次get_next()的时间是O(1),stack
takes O(N) space.
(2) 不存临时变量，每次binary search the next closest value? time is O(logN),
space is O(1)
If we adopt option (1),for bst case, time is O(N), space is O(N)
If we adopt option (2),for bst case, time is O(NlogN), space is O(1)
不知理解是否正确，请指教 |
|
e***n
发帖数: 68 | 25 我目前为止2面都没有任何云文档，都是说的
今天刚刚2面，2题很简单2sum 和isbst |
|
m*******1
发帖数: 77 | 26 把标题改了更符合版上的规范。
————————————————————————————
上周四的onsite， retail 组，四个面试官，前两个是印度人，
第一个让写一个hashmap, 我用linkedlist处理collision, 然后按照cracking code 上
面讲的写了一个非常简单的hash 函数，他说太简单，我后来改了一个复杂些的，用每
一个char * i *13再求和构建。然后问了一些java的基本题目，都答了上来。
第二个让解决一个迷宫，先问我用什么数据结构，我先说数组，他不满意，后来我说可
以用图，然后类似于BFS来进行查找，同时保持一个backtrack map来记录路径。然后写
代码。
后两个是美国人
第三个写populate 同一层的二叉树，可以非常稀疏，我写了出来，无bug。然后问了
2sum, 3sum，都答了上来。然后问了machine learning基本知识，也都答了上来。
第四个是系统设计和分析，包括判断哪里出问题以及策略等。最后一个问题我想了一段
时间，我们出了面试房间到厨房继续，十几分钟后我想了出来，然后就结束了。
今天收到电话，悲... 阅读全帖 |
|
d*******8
发帖数: 30 | 27 发一下面经吧：
1. Binary Tree Inorder Traversal
2. UTF-8 String 编码
3. 3sum的问题
感觉问的都是很基础的东西。第一个表interview算法还行，但是写code有点慢。第二
个因为写过，就直接写出来了nlogn的算法，感觉面试官还不知道从2sum变形过来一样。
两周后回信说
We carefully reviewed your background, experience, and interview feedback
and unfortunately we didn't find there to be a close enough match for a
Software Engineering Internship position at this time. We will continue to
use our database to match your profile with new opportunities and will reach
out to you if we find an opening fo... 阅读全帖 |
|
c**i
发帖数: 306 | 28 刚结束了bb家的面试，攒RP报个面筋。之前邮件里说是2个SDE面我，就一轮，实际去了
发现是有三个
SDE面，都是非CS专业三哥。总共一个小时，寒暄了20分钟的之前做过的project，简单
问了一些基本的coding知识，然后做了2个题，2个题都没做好，估计是肯定杯具了。之
前低估了bb家面试的难度，准备的太欠缺了，在这给大家提个醒一定要准备充分。第一
个题是写个函数输出所有的满足前三位和等于后三位和的六位数，比如156723，我写了
个bruteforce的，被要求优化，想了下说可以利用对称性减一些运算量，但是要考虑有
padding zero的情况，后来时间不多了也就不了了之了，面试官说其实是可以推出个公
式的，晕。第二个题是给一个8*8的board，其中有两个点被block了不能放东西，现在
给定这两个店的坐标，写个程序检测可否用domino pizza来覆盖这个board，其中每个
格子只能被覆盖一次，被block的不能覆盖，domino pizza就是1*2或者2*1的格子，开
始想和能不能往DP上靠，发现走不通，于是有点慌，经提示说把二维board转成一维，
说了一点尝试... 阅读全帖 |
|
l*****a
发帖数: 14598 | 29 那怎么办？
2sum的怎么解？
inOrderTraverse怎么写？ |
|
h*******l
发帖数: 22 | 30 虽然记得不太清楚， 贡献一下面经回馈本版吧。只onsite过G和Y。其他大多电面， 而
且久远，就记不了那么清楚了。
Y 电面一个小时，只有一次电面，过了就onsite。难度和大多数电面都差不多。
Y我有两个onsite
第一个
1. 问了买卖股票（很遗憾， 没做过，不过最后还是整出线性时间的算法了，花的时间
比较多，要是leetcode上做过，会快很多），
2. LC Sequence（基础，飞快写完递归和非递归解法）；
3. hashtable实现 (基础，TA过高级数据结构)；
4. 二叉树高度，要求非递归解法
5. 数组找到第k个最大的（高频题，selection sort，平均n，最坏n平方；也可以用大
小为k的heap做，让我实现了其中一个）
6. 给一个堆，里头有无序的数，排序之，要求只用堆数据结构，最好只用两个，复杂
度最好用nlogn（我当时没有达到他的要求，看上去用了两个stack，其实用了程序自己
的stack，复杂度也没有达到n平方）
7. 单链表，有环，数据部重复， 找到环， 要求给出两种做法 （cracing google
interview上的题，两个指针... 阅读全帖 |
|
f*****7
发帖数: 92 | 31 之前板上有一位大哥
应该是amazon的面试人员
发了一个面试的FAQ
介绍了大致难度，以及面试官希望的答案
题目有2sum，最长回文子串
哪位朋友还有那个帖子?
麻烦给个链接
非常感谢
祝您新年快乐！ |
|
J*******n
发帖数: 2901 | 32 是不是这个？我下周也有个面试，前两天看到这个就copy了下来
第一次电面，问了两题：2sum和判断一个binary tree里面是否有环第二次电面，也是
两题：判断两数相加的结果是否会溢出，以及求N以内的素数
两次电面之后，HR说要追加一次电面。
第三次电面，两题：
如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
问的点，就改成用类似Floyd算法来做，但是效率就不高了。
第三次电面结束后几分钟，HR就发信把我拒了，难过了半天：（
回忆起来，第一次电面没做好，因为当时在路上，没法用电脑写程序，只能口述。
第三次电面，想来是最后一个图论题目没做好。 |
|
p***r
发帖数: 1098 | 33 我onsite过，failed.
记得问了电梯系统的设计题，2sum and 3sum，LRU cache的设计和实现 |
|
|
r**h
发帖数: 1288 | 35 3sum不应该是先排序然后固定一个点做2sum吗？
O(N^2)时间O(1)空间
less than O(N log N)time is not possible，上次讨论过的 |
|
|
d**********x
发帖数: 4083 | 37 3sum就别再讨论如何nlogn了，没有意义
C |
|
j********x
发帖数: 2330 | 38 正确解法是mail fb面试官或者原贴主。。。 |
|
k***x
发帖数: 6799 | 39 原帖是找到一组(a,b,c)使得a+b+c=0，3sum是要找到所有这样的解 |
|
|
s****9
发帖数: 22 | 41 我错了 应该是 lgn + lgn/2 + lg n/4 .. |
|
g******z
发帖数: 893 | 42 主要考概率，machine learning的基本概念，当然还有coding
面试官1：
（1）naive bayes的原理，要求推公式解释
（2）svm的原理，推公式解释。什么是support vector
（3）naive bayes和svm的比较，哪种分别在什么情况下比较好，为什么
（4）kernel function的概念，在什么情况下用
（5）cross-validation的概念，在什么情况下用
面试官2：
（1）一个urn里有red，blue，green三种小球，分别的个数都已知。给一个uniform
random number generator产生[0，1]之间的数，要求写一个function随机选取小球，
选取的概率跟球的分布一致
（2）怎么测试（1）中function的正确性
（3）open question：给一个url的list，可以利用什么信息来对它们进行打分排序（
比如user click的log）。
（4）给若干个url和一个user click的log，问怎么对这些url排序比较合理，给出理由
面试官3：
（1）leetcode OJ的unique p... 阅读全帖 |
|
r*****e
发帖数: 792 | 43 先上个F的题吧：
第一个人，coding：
2sum，给了sort后2个ptr的解法，问还能更快吗？那就hash吧，但是
用了unordered_map,又问有别的container吗，才反映过来用hashset就够了。
然后是计算a^b%c， 假设a,b,c都很大，但都是int32.过程中因为他先提到了
prime number，以为是要计算prime，于是后悔好长时间没有看那个什么sieve的
算法了，导致有点精神不集中。回过神来以后做出来了，就是二分，但是
有个地方没注意temp结果应该用int64存一下，一再追问下答出来了。整体这轮
感觉还不错。说个题外话，面试的是个从google跳过去的胖子，好像是个东欧
人，在写题目的时候挺个大肚子，吭哧吭哧的，看得我想笑。 |
|
s*******s
发帖数: 1031 | 44 最小元素不一定在一头一尾的。
比如：
a...............b..c..d..............e
最小的两个元素在中间。
晕，我的算法也有问题。
看来对剩下的元素做2Sum，找出的每一对都可能是valid选择。那就是多叉树了。 |
|
s*******s
发帖数: 1031 | 45 最小元素不一定在一头一尾的。
比如：
a...............b..c..d..............e
最小的两个元素在中间。
晕，我的算法也有问题。
看来对剩下的元素做2Sum，找出的每一对都可能是valid选择。那就是多叉树了。 |
|
z***k
发帖数: 282 | 46 如果最底层有大量的1和2，那么每次都会有很多2sum对，这样没法确定顺序吧
比如如果答案是112121212一共13,就有所有配对，而且有重复的。 |
|
J****3
发帖数: 427 | 47 刚面完第三轮 估计悲剧了
1. Leetcode populating next right node
2. 2sum->3sum->4sum
3. 这轮最蛋疼。。。一上来给了个git 的地址 ssh 到后是memcached C++ 版本的源码
。 先告诉我有Incr 和 decr 两种atomic operation。 但并没有mult operation。 要
求实现并运行例子. 这完全没听说memcache.. 虽然倒是实现这个mult的原理比较简单
。。。
哎 感觉实战一下就虚了 |
|
z*******3
发帖数: 13709 | 48 一开始那几题是有点难
尤其是2sum，第二题有相当难度
所有题目里面，第二题难度能排前几
第二题过了之后，一马平川 |
|
z*******3
发帖数: 13709 | 49 2sum写个排序写半天
后面全部Arrays.sort()搞定 |
|
g****o
发帖数: 547 | 50 2sum 不是应该hashmap吗？
排序达不到o(n) |
|
