P**********k
发帖数: 1629 | 1 前几天电面F家，出了一道two sum的题，可惜我基本没刷过题，
然后现想，从O(N^2),到O(NlogN)，最后面试官美女提示下给出了O(N)的解，
写了三个算法，估计面试官也无语了，可能想给个水过，没想到竟然遇到没刷过题的，
回来搜了一下leetcode，发现是第一道题easy题目，真tmd伤不起啊。。。。
估计也没有下文了。。。 |
W***o
发帖数: 6519 | |
d*********g
发帖数: 234 | 3 lz是面senior吗
【在 P**********k 的大作中提到】
: 前几天电面F家，出了一道two sum的题，可惜我基本没刷过题，
: 然后现想，从O(N^2),到O(NlogN)，最后面试官美女提示下给出了O(N)的解，
: 写了三个算法，估计面试官也无语了，可能想给个水过，没想到竟然遇到没刷过题的，
: 回来搜了一下leetcode，发现是第一道题easy题目，真tmd伤不起啊。。。。
: 估计也没有下文了。。。
|
u**u
发帖数: 668 | 4 是啊 他家题库小，还多是旧题
楼主估计很久。。。没找工作了 |
d**x
发帖数: 243 | 5 2sum，应该是个初始题吧。目测套路为5分钟搞定，然后后面估计会3sum，4sum吧。送
分题了，现在这个年头不刷题就面fg，醉了醉了啊。 |
p*********g
发帖数: 2998 | 6 2 sum, o(n)
3 sum, o(nlogn)
4 sum, o(n2)
背都背下来了 |
D**********0
发帖数: 1022 | |
g***i
发帖数: 4272 | 8 3 sum能 n log n?
【在 p*********g 的大作中提到】
: 2 sum, o(n)
: 3 sum, o(nlogn)
: 4 sum, o(n2)
: 背都背下来了
|
W***o
发帖数: 6519 | 9 我觉得需要n^2吧，因为for-loop 里边嵌套着一个双指针的while-loop怎么着也得n *
n
【在 g***i 的大作中提到】
: 3 sum能 n log n?
|
z******s
发帖数: 197 | 10 有一种非常复杂的nlogn解答，但是我相信99.99%的人现场解释不清楚，时间都不够
【在 g***i 的大作中提到】
: 3 sum能 n log n?
|
|
|
r******l
发帖数: 10760 | 11 这是对hash table不熟悉所致，多面面就熟悉了。很多貌似无法再优化的题都是用上
hash table搞定的，本质上还是空间换时间。
【在 P**********k 的大作中提到】
: 前几天电面F家，出了一道two sum的题，可惜我基本没刷过题，
: 然后现想，从O(N^2),到O(NlogN)，最后面试官美女提示下给出了O(N)的解，
: 写了三个算法，估计面试官也无语了，可能想给个水过，没想到竟然遇到没刷过题的，
: 回来搜了一下leetcode，发现是第一道题easy题目，真tmd伤不起啊。。。。
: 估计也没有下文了。。。
|
d**e
发帖数: 6098 | 12 刚好前几天看到好像说这种解法是2014年才出来的。不过还没研究过怎么解。
【在 z******s 的大作中提到】
: 有一种非常复杂的nlogn解答，但是我相信99.99%的人现场解释不清楚，时间都不够
|
g***i
发帖数: 4272 | 13 学一学。谢谢
【在 d**e 的大作中提到】
: 刚好前几天看到好像说这种解法是2014年才出来的。不过还没研究过怎么解。
|
l**i
发帖数: 139 | |
e*******o
发帖数: 4654 | |
b**1
发帖数: 6 | 16 https://en.wikipedia.org/wiki/3SUM
O(n ^ 1.5) is very hard to get, not mention O(nlogn)... |
d**x
发帖数: 243 | 17 是啊，我想了半天没觉得3sum是O(nlogn)，正准备求教。面试的时候答出来O(n^2)应该
过关。 |
d**e
发帖数: 6098 | 18 我错了。。。我重新翻了一下前几天看的，的确没有直接说O(nlogn)，只是说比O(n^2)
快。我觉得14年才出来的解法肯定是复杂到我看不懂，所以也没看下去，也想当然地认
为是O(nlogn)。。。
【在 b**1 的大作中提到】
: https://en.wikipedia.org/wiki/3SUM
: O(n ^ 1.5) is very hard to get, not mention O(nlogn)...
|
e*******s
发帖数: 1979 | 19 不用那么新潮的解法 n2就够了
2)
【在 d**e 的大作中提到】
: 我错了。。。我重新翻了一下前几天看的，的确没有直接说O(nlogn)，只是说比O(n^2)
: 快。我觉得14年才出来的解法肯定是复杂到我看不懂，所以也没看下去，也想当然地认
: 为是O(nlogn)。。。
|
d**e
发帖数: 6098 | 20 如果面试官期望比O(n^2)快的解法，我觉得ta不是想装13就是想被雷劈
【在 e*******s 的大作中提到】
: 不用那么新潮的解法 n2就够了
:
: 2)
|
|
|
e*******s
发帖数: 1979 | 21 要么是故意想挂你
要么就是看看你会不会聊天 那就当他想聊天 顺着他聊聊好了 这些别人写在论文上发
出paper的东西显然不是自己想想就能想出来的
【在 d**e 的大作中提到】
: 如果面试官期望比O(n^2)快的解法，我觉得ta不是想装13就是想被雷劈
|
t******w
发帖数: 167 | 22 hug hug,,,我也没刷题，刚面的亚麻怕是挂了。。。20分钟就要编出什么来，构思都不
够，对于没刷题的人。。。。这世道，，，不活了。。。 |
s****r
发帖数: 68 | 23 请问2 sum O(n)怎么做？我看到有些答案说先scan一遍，build map or hash map，
then query that map。但是这个
1. 如果用map，build map一般是二叉树把，nlog(n).
2. 如果hash map，worst case n^2。而且平均也可能大于O(n)。
【在 p*********g 的大作中提到】
: 2 sum, o(n)
: 3 sum, o(nlogn)
: 4 sum, o(n2)
: 背都背下来了
|
d**e
发帖数: 6098 | 24 一般认为普通的map存取是O(1)，以这个为基础再决定是O(n)。
【在 s****r 的大作中提到】
: 请问2 sum O(n)怎么做？我看到有些答案说先scan一遍，build map or hash map，
: then query that map。但是这个
: 1. 如果用map，build map一般是二叉树把，nlog(n).
: 2. 如果hash map，worst case n^2。而且平均也可能大于O(n)。
|
s****r
发帖数: 68 | 25 这个不正确吧。对排序的map，build map is nlog(n), access is O(logn).
对hash map，更复杂。需要分析average and worst case。
一般面试，除非要求，尽量不用map这种现成的复杂结构吧：你把复杂性都隐藏在
library里了，有时算法设计意义不大了。
【在 d**e 的大作中提到】
: 一般认为普通的map存取是O(1)，以这个为基础再决定是O(n)。
|
d**e
发帖数: 6098 | 26 面试而已了，一般就用基本的数据结构set/map我会认为为O(1)的。
你想得这么复杂，会打击我刷题的积极性的 :(
【在 s****r 的大作中提到】
: 这个不正确吧。对排序的map，build map is nlog(n), access is O(logn).
: 对hash map，更复杂。需要分析average and worst case。
: 一般面试，除非要求，尽量不用map这种现成的复杂结构吧：你把复杂性都隐藏在
: library里了，有时算法设计意义不大了。
|
H**********5
发帖数: 2012 | 27 现在的亚麻面试官会把你在白板上写的代码抄在他笔记本上跑。
【在 t******w 的大作中提到】
: hug hug,,,我也没刷题，刚面的亚麻怕是挂了。。。20分钟就要编出什么来，构思都不
: 够，对于没刷题的人。。。。这世道，，，不活了。。。
|
s****r
发帖数: 68 | 28 Actually, I think that my suggestion is true in many cases. Just have a
sense that some interviewers want you to design data structures/algorithms
from the scratch. At least you need to ask them in the very beginning if
using in-stock library is allowed or not. For example, for many string
related questions, they don't want you to use string::find() method.
For 2-sum question, a possible answer flow can be:
1. Discuss how to solve it in O(n) if the array is sorted.
2. Then in the general case, you may first sort the array, and then use the
algorithm in 1. Here, you can discuss all kind of sorting algorithms.
3. Is there a smart way to integrate sorting and 1 together? If so, give
your solution (note that using map is not a smart way :-)).
If you answer the question with the above steps, I think that you will
be considered as a candidate with solid problem-solving skills.
【在 d**e 的大作中提到】
: 面试而已了，一般就用基本的数据结构set/map我会认为为O(1)的。
: 你想得这么复杂，会打击我刷题的积极性的 :(
|
P**********2
发帖数: 77 | 29
the
这个第3步怎么融合能比nlog(n)更好？
【在 s****r 的大作中提到】
: Actually, I think that my suggestion is true in many cases. Just have a
: sense that some interviewers want you to design data structures/algorithms
: from the scratch. At least you need to ask them in the very beginning if
: using in-stock library is allowed or not. For example, for many string
: related questions, they don't want you to use string::find() method.
: For 2-sum question, a possible answer flow can be:
: 1. Discuss how to solve it in O(n) if the array is sorted.
: 2. Then in the general case, you may first sort the array, and then use the
: algorithm in 1. Here, you can discuss all kind of sorting algorithms.
: 3. Is there a smart way to integrate sorting and 1 together? If so, give
|
t******w
发帖数: 167 | 30 我的一定不会了。。。。没写完，而且估计思路都错了。。。可是我只刷了几个题，只
能按一个接近的来套了，，，感觉不但要刷过，而且还要很熟，不然连用哪个都想不起
【在 H**********5 的大作中提到】
: 现在的亚麻面试官会把你在白板上写的代码抄在他笔记本上跑。
|
|
|
s****r
发帖数: 68 | 31
I don't know a comparison sorting based algorithm better than nlog(n). But I
can show some idea to integrate efficient sorting with 2-sum together. The
idea is to embed 2-sum check in quick sorting method as following:
Say the array is [a1, a2, ..., an], and the sum is s.
1. Select one element, such as, a1, then get b1 = s - a1. Assume that a1 <
b1, and use a1, b1 to partition the array to three parts A11, A12, A13, so
that the element in the first part A11 is no more than a1, and the element
in the third part A13 is no less than b1. If b1 is in the array, then the
problem has been solved.
2. If b1 is not in the array, then a1 is not the answer. And two numbers can
only be in A11 + A13 (a1 can be removed to reduce one element) or A12.
3. Recursively work on A11+A13 and A12 until you find 2 numbers or find
nothing in each branch.
Since quick sort is an efficient sorting method in most of cases, the above
method should also be efficient method for 2-sum.
If the array holds integers in a range, and s is not significantly bigger
than n, you can consider the method based on counting sort, which is O(n+s).
【在 P**********2 的大作中提到】
:
: the
: 这个第3步怎么融合能比nlog(n)更好？
|
E*********e
发帖数: 767 | 32 这个视频最后问如果数组长度很大不能一下放到memory里时，男的说把它分成chunk再
把chunk的结果merge起来，似乎不对吧？可能两个数分别位于不同chunk中，那各chunk
各自找是找不出来的啊
【在 D**********0 的大作中提到】
: https://www.youtube.com/watch?v=XKu_SEDAykw&t=319s
: 2sum都不会有点说不过去哈
|
u**u
发帖数: 668 | 33 咳咳，恩，应该是 access O(long L)
L 是map size
最坏情况是一直加数 log(1) + log (2) +...log(n)
= log(n!) 比n 还是要级数小一点（在n goes to infinity）的情况下。
【在 s****r 的大作中提到】
: 这个不正确吧。对排序的map，build map is nlog(n), access is O(logn).
: 对hash map，更复杂。需要分析average and worst case。
: 一般面试，除非要求，尽量不用map这种现成的复杂结构吧：你把复杂性都隐藏在
: library里了，有时算法设计意义不大了。
|
P**********2
发帖数: 77 | 34
I
The
so
can
谢分享！
【在 s****r 的大作中提到】
:
: I don't know a comparison sorting based algorithm better than nlog(n). But I
: can show some idea to integrate efficient sorting with 2-sum together. The
: idea is to embed 2-sum check in quick sorting method as following:
: Say the array is [a1, a2, ..., an], and the sum is s.
: 1. Select one element, such as, a1, then get b1 = s - a1. Assume that a1 <
: b1, and use a1, b1 to partition the array to three parts A11, A12, A13, so
: that the element in the first part A11 is no more than a1, and the element
: in the third part A13 is no less than b1. If b1 is in the array, then the
: problem has been solved.
|
e***a
发帖数: 1661 | 35 u were brave enough to interview with F. |
