R*****i
发帖数: 2126 | 1 这个题目建议用红黑树做可能最快捷有效。红黑树每一次插入，删除都是log(k),求平
均值非常简单，就是根部的那个节点。所以总的计算量是O(nlog(k))。
以下是c/c++代码（需要修改数组，以便一个一个输入）。
#include
#include
#include
#define INDENT_STEP 4
enum rbtree_node_color {RED, BLACK};
typedef struct rbtree_node_t {
int value;
struct rbtree_node_t* left;
struct rbtree_node_t* right;
struct rbtree_node_t* parent;
enum rbtree_node_color color;
} *rbtree_node;
typedef rbtree_node node;
typedef enum rbtree_node_color color;
typedef struct... 阅读全帖 |
|
R****i
发帖数: 104 | 2 My solution is:
1) Sort the first array, O(nlog(n));
In the given example, the sort array is: 3, 4, 5, 6, 10, 12, 13, 15
2) Reconstruct the output based on the second array, but from the end of the
second array. In the given example, the last item is 2. So the item in the
output array should be 12 because 12 is before 13 and 15. 13 and 15 are the
two numbers which are greater than 12. Then we can reconstruct the second
last element which is 2 in the second array. Because 12 is taken out, so ... 阅读全帖 |
|
H*****l
发帖数: 1257 | 3 这个解法的复杂度有2^n吧？
好像用DP，可以降到nlog(n) |
|
M*********r
发帖数: 70 | 4 第一题能介绍下nlog(n)怎么做吗？或者给个link也可以。多谢了！ |
|
b*******e
发帖数: 123 | 5 来自主题: JobHunting版 - G新鲜面经 1.2, If I understand the question..
method 1. sort first, take second half intertwine first half. O(nlog(n))
speed.
method 2, (similar to method 1) use a heap, pop assign to even index, then
pop assign to odd index. O(n)
method 3, one pass, heapify, pop first assign to 1, then pop two, assign
larger one first, continue. O(n) one pass.
method 4, O(n), one pass constant space, look at i and i+1, if i is even and
A[i] > A[i+1] swap two value, if i is odd and A[i] < A[i+1] swap two value.
so method ... 阅读全帖 |
|
b*******e
发帖数: 123 | 6 指点下为什么要排序？ 直接往dictionary里加是O(n)，排序是O(nlog(n))。直接加不
是要快点？ |
|
b*******e
发帖数: 123 | 7 倆dictionary,hash size 分类先，hash内容再分类。还是比O(nlog(n))要快。而且如
果相同size文件不多的话，这个会很快。 |
|
b*******e
发帖数: 123 | 8 所有端点排序，做一个counter,遇到开始端点+1,遇到结束端点-1。最大的counter对应
的端点们就是最多重复的区间。
O(nlog(n))
vector maxoverlap(vector inputs){
typedef pair ENDS;
// all end points sort.
vector preends;
for(const auto & x: inputs){
preends.push_back(make_pair(1,x.start));
preends.push_back(make_pair(-1,x.end));
}
sort(preends.begin(),preends.end(),[](ENDS a, ENDS b){
return a.second < b.second; });
//combine same end points.
vector ends;
int i = 0;
while... 阅读全帖 |
|
h****y
发帖数: 137 | 9 这个不是新题了吧, EPI上的原题,
可以divide and conquer
也可以先排序, 从左往右scan, 同时maintain一个BST
两种都是nlog(n) |
|
h****y
发帖数: 137 | 10 这个不是新题了吧, EPI上的原题,
可以divide and conquer
也可以先排序, 从左往右scan, 同时maintain一个BST
两种都是nlog(n) |
|
d***n
发帖数: 832 | 11 是这个贴子里发出的
http://www.mitbbs.com/article_t/JobHunting/32569901.html
第二题是这样的：
n个Speaker，S1, S2, ...Sn
每个Speaker在不同的时间段有不同的音量如：
S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
...
请输出每个时间段及这个时间段内最大的音量
比如，只有S1和S2的话，输出就是
[1,2],vol=1, [2,5], vol=10, [5,6], vol = 1, [6,8], vol = 2, [8,12], vol = 8.
看了帖子后还是不明白O(nlog(n))是怎么解决的
有真正明白而且写过code的牛人能不能解释一下 |
|
d***n
发帖数: 832 | 12 是这个贴子里发出的
http://www.mitbbs.com/article_t/JobHunting/32569901.html
第二题是这样的：
n个Speaker，S1, S2, ...Sn
每个Speaker在不同的时间段有不同的音量如：
S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
...
请输出每个时间段及这个时间段内最大的音量
比如，只有S1和S2的话，输出就是
[1,2],vol=1, [2,5], vol=10, [5,6], vol = 1, [6,8], vol = 2, [8,12], vol = 8.
看了帖子后还是不明白O(nlog(n))是怎么解决的
有真正明白而且写过code的牛人能不能解释一下 |
|
l*********3
发帖数: 26 | 13
如果第二个参数是一个整数数组，代表每个字符串在permutation里的位置的话，这道
题就是一个sort问题。你需要排序整个数组，依赖于其对应的permutation序列值。
可以使用heap-sort，无额外空间，时间复杂度O(nlog n) |
|
l*********3
发帖数: 26 | 14
这道题不是NP-HARD的。
暴力法：建一个shortest path map。可以用Dijskstra算法。然后对每个点计算其到每
个器材所在点的距离。找最小值。
暴力法时间复杂度：shortest path map: n个点，每个O(nlog n)，总共O(n^2log n)。 |
|
d******b
发帖数: 73 | 15 这个题 不用dp。
直接用bitset就搞定了。
每一个 字符串 对应一个 bitset，或者 32位的整数，如果只是 字母的话。
如果有 这个字母，相应的位 就 mark 1，否则mark 0。
然后 以第一个为基准，扫描到 逻辑和 不为零的 全部删掉。
一直这样做下去。 直到找到逻辑和 为零的。
平均复杂度，应该在 nlog(n) 。
至于第二个，应该是在第一个的基础上，找出两个最大的。
这个不难了。 |
|
x****g
发帖数: 1512 | 16 “平均复杂度，应该在 nlog(n) 。”
你是怎么想当然算的？ |
|
g*****g
发帖数: 212 | 17 不确定是否有 nLog(n)的解，不过 n^2的解法是可以调优的。
首先先把数组sort了，按长度降序
string s[];//
int signature[];//
int length[];// length of each string
int n; // length of s
int max = 0;
for(int i=0; i
{
for(int j=i+1; j
{
if (length[i] * length[j] <= max)
{
break; // optimize 1, early stop
}
if (signature[i] & signature[j] == 0)
{
max = max(length[i] * length[j], max);
break;// optimize 2, no need to test rest
}
}
}
length |
|
s*******z
发帖数: 83 | 18 来自主题: JobHunting版 - 新鲜G面经 果然tricky, 给一个黑子只是为了确定搜索边界.
黑白子那个二分搜索~~, NLog(N)对吗? |
|
s*******z
发帖数: 83 | 19 应该是高维度空间里面的最近点对问题, 一个大牛说了可以再Nlog(N)的时间里面完成,
就用类似于二维平面的分治法来做.
但是实现起来也觉得好难, 还有就是维度高的时候,一分两半以后, 就算求距中轴的最
短距离的那些点的时候, 说不定也都是N^2的了. |
|
x****1
发帖数: 118 | 20 这道题以前讨论过。解法很简单。就是分别求x，y轴坐标的中值。所以下一道题是如何
求一个未排序数组中值，面试官提示说有O(n)解法，但是我只会nlog(n) |
|
p********2
发帖数: 17 | 21 Randomized Quicksort Variants：
Regularly, RANDOMIZED QUICKSORT selects a single pivot element uniformly at
random. In this problem you will analyze two possible modifications to this
choice of pivot.
For an integer parameter k>=1, the HYBRID RANDOMIZED QUICKSORT algorithm
uses regular RANDOMIZED QUICKSORT whenever n>K , but uses I NSERTION S ORT
whenever n<=k . Analyze the expected running time of HYBRID RANDOMIZED Q
UICKSORT in terms of n and k .
Argue that this sorting algorithm runs in O(nk+n... 阅读全帖 |
|
A*********c
发帖数: 430 | 22 我觉得是的，涉及到配对comparison，所以lower bound nlog(n).
Any improvements? |
|
A*********c
发帖数: 430 | 23 我觉得是的，涉及到配对comparison，所以lower bound nlog(n).
Any improvements? |
|
J*****a
发帖数: 4262 | 24 好像是复杂度nlog(n-k)？k是去除的元素数 |
|
p********n
发帖数: 165 | 25 用rabin-carp的方法 可以把每个单词都hash成一个数字，这样比较起来比较快，
至少可以优化成 O（n^2*m） m是平均每个句子里单词的个数， 稍微好一些。
另外一个优化： hash 每个句子的单词的时候，统计每个句子的单词数，并按照单词数
排序O(nlog(n))
这样，可以从第二最长的句子开始往后循环， 每次循环，假设到了第i个句子，要和所
有1...i-1的句子比，如果到目前为止share的单词数最大的solution >= 第i个句子的
整个单词数的时候，就可以中止程序。 算是一个early termination. |
|
m*****n
发帖数: 2152 | 26 其他nlog(n)排序方法要额外空间，就heap不要。 |
|
m*****n
发帖数: 2152 | 27 其他nlog(n)排序方法要额外空间，就heap不要。 |
|
r****t
发帖数: 10904 | 28 第一题也磕磕碰碰的。估计没刷题吧。第二题 sort 真的不行么? insertion sort 应
该O(n), 不如两分法好，但是也比 nlog(n) 好啊。 (lo+hi)/2 可能对方已经失去耐
心。
说据的莫名其妙, 情商也需要提高。 |
|
d**k
发帖数: 797 | 29 那就是说每次算个数都要scan n个元素
而不是从之前的scan 结果继续过滤，对吧？
确实是nlog(n) |
|
m*****n
发帖数: 2152 | 30 现在还不会，怎么办？
二维平面上面n个点，要求找出一个最多点的集合，满足集合中任意两点的连线的斜率
大于等于0，返回这个集合中点的个数。
要求写code，时间复杂度 nlog（n）。
加个hint，说白就是两个点i和j，当x_i >= x_j的时候，y_i >= y_j，等号不同时成立。
follow up：三维空间的时候，怎么办？m维空间的时候怎么办？ |
|
m*****n
发帖数: 2152 | 31 完全被虐死了，中间恨不得把电话给扔了。
下面说说过程，首先说明，全程面试官从来没说过我的任何回答是对还是错，我下面的
回答可能很多是错的。
一个西亚或者印度（口音不太像）面试官 A，一开始聊了一下background，然后丫说先
给你一道简单题做做吧，就是一楼的题。
一开始，听到二维平面，最多点，斜率，还以为是那到最多点共线的问题呢？心中一喜
，然后自己重复问题的时候，A 感觉完全不知道我在说什么。丫又重复了一遍问题，这
时才听懂。
当时第一反应是对一个维度排序，然后DP，说给A听了。
A：时间复杂度是多少？
me: O(n^2)
A: 不行，要nlog(n)。
me: （心理一紧，完蛋了，DP都不行）嘴上说好像可以剪枝。
A: How？
me: (心理说我怎么知道)，胡说半天，说什么用tree啦，找parent啦，连我自己都不知
道在说什么。
A: 好吧，假设你有2维的nlogn的算法了，3维怎么办？
me: 先找一个2维最多的点集，再对这个点集的第3维在做一次这个算法。
A: M维怎么办？
me： 依次类推。
A: 时间复杂度多少？
me: 大概是最坏是m*n*logn吧。
A: ... 阅读全帖 |
|
|
p****6
发帖数: 724 | 33 有一个tricky的地方，用java的hashmap记录的话，最后拿到结果的时间复杂度会是
nlog(n), 因为从hashmap里取出来是0,1,2，-1，-2这样非排序的顺序，如果用treeset
去sort才能拿出-2，-1,0,1,2这样的顺序。
对C++ std的map不熟，不知道C++的实现复杂度是多少。 |
|
y**********a
发帖数: 824 | 34 O(nlog n)
把临近的奇数换到偶数(index)上
void weirdSort(int[]A) {
assert((A.length&1)==1);
Arrays.sort(A);
for (int i=1;i+1
{A[i]^=A[i+1];A[i+1]^=A[i];A[i]^=A[i+1];}
} |
|
g***a
发帖数: 58 | 35 八月的时候面的fb，电面和onsite都是local的，发个面经给版上备战的xdjm参考，求
攒rp
电面：
先聊了聊自己的经历，为什么要来fb之类的问题，因为我有图像处理的背景，就问了一
题相关的。
给一个2D board，上面由 0 和 1 组成，0 背景，1是图像，求里面有多少个连通域，
follow up 是每个连通域的面积是多大。我先写了recursive的做法。后来面试官又要
求了iterative的做法
面完一小时之内，recruiter发邮件说电面过了，可以安排onsite
onsite：
第一轮：主要谈自己以前做的东西，面试官问得比较细，总之就扯了扯。问了一题
coding，给一个数组，问里面有没有两个数相加等于0，给了 O(n) time O(n) space的
做法，和 O(nlog n ) time和 O(1)space的做法
第二轮：给一个bst，和其中一个节点的value，求在bst中比这个节点大的下一个value
，面试官要求 O(1) space和 O(log N) time的解法。
第三轮: regular expression match, leet... 阅读全帖 |
|
w****n
发帖数: 37 | 36 签下Facebook，我漫长的找工作经历终于告一段落。这里写下点经历回馈大家。我是CS
PhD new grad。做的方向和工作没什么关系。曾经在一家大的硬件公司做过intern，
然后拒掉了他们的 return offer。
我初期投简历的时候，除了Google和一些小公司，基本上收不到任何回应。当时心急火
燎，没有任何正面反馈，心情很是沮丧。后来都到了要毕业，打算停止投简历的时候，
却忽然来了很多的onsite，最终转化为了最终接受的offer。甚至微软和亚马逊给我
onsite的时候，我都已经接受了别的offer，不打算去他们家面了。现在想想，应该是
赶上了公司的招聘季，所以才会有机会。这里要鼓励大家一定要有信心，不拿到满意的
offer绝不罢休。另外保持一个积极的心态也很重要。我刚刚开始面试的时候心里比较
没谱，总觉得自己不会的很多，所以面试时是一种诚惶诚恐的心态。后来逐渐改善，自
我暗示说看上去很难的题目，其实也没什么，只管会什么说什么。最后虽然还是有很不
会的题目，可是表现会好很多。
我的准备工作基本上是做leetcode。后来觉得leetcode熟悉了，就做了一些Topc... 阅读全帖 |
|
d********r
发帖数: 567 | 37 cong! chi
签下Facebook，我漫长的找工作经历终于告一段落。这里写下点经历回馈大家。我是CS
PhD new grad。做的方向和工作没什么关系。曾经在一家大的硬件公司做过intern，
然后拒掉了他们的 return offer。
我初期投简历的时候，除了Google和一些小公司，基本上收不到任何回应。当时心急火
燎，没有任何正面反馈，心情很是沮丧。后来都到了要毕业，打算停止投简历的时候，
却忽然来了很多的onsite，最终转化为了最终接受的offer。甚至微软和亚马逊给我
onsite的时候，我都已经接受了别的offer，不打算去他们家面了。现在想想，应该是
赶上了公司的招聘季，所以才会有机会。这里要鼓励大家一定要有信心，不拿到满意的
offer绝不罢休。另外保持一个积极的心态也很重要。我刚刚开始面试的时候心里比较
没谱，总觉得自己不会的很多，所以面试时是一种诚惶诚恐的心态。后来逐渐改善，自
我暗示说看上去很难的题目，其实也没什么，只管会什么说什么。最后虽然还是有很不
会的题目，可是表现会好很多。
我的准备工作基本上是做leetcode。后来觉得leetcode熟悉... 阅读全帖 |
|
g********r
发帖数: 89 | 38 merge2list不是有一道题么？先去验证一下正确性。mergeklist这题可以divide n
conquer 来节省时间到nlog(m), m is number of lists, and n is length of list |
|
l*********8
发帖数: 4642 | 39 C3 energy我连online test都没过啊。。。
第二轮<2>，用一个辅助数组保存local max value和下标。
例子：
input 对应的local_max array
{} {}
{3} {<3,0>}
{3,4} {<4,1>}
{3,4,2} {<4,1>, <2,2>}
{3,4,2,1} {<4,1>, <2,2>, <1,3>}
{3,4,2,1,3.5} {<4,1>, <3.5,4>}
更新local_max array的时候，将当前alue和下标插入到local_max array, 从local_
max末尾向前搜索，遇到比当前元素小的，就删除。 这样，local_max数组就是按value
逆序排列的，而前面更新local_max可以用二分搜索。 每次更新log n time, n次更
新nlog(n)
array |
|
t*****a
发帖数: 106 | 40 得是balanced tree才能保证O(nlog(n)), 否则还是O(n^2) |
|
x********u
发帖数: 1061 | 41 第二题难道不应该先hash一下然后直接找么？第一次需要求字典的hash，以后每次都只
需要O（nlog(字典长度）），考虑到string 的n很小，字典长度很长，这个应该比O（n
+字典长度）高效吧 |
|
I**********s
发帖数: 441 | 42 如果求最大的 B[i][j], 已有kadane函数 maxSubArray() 找最大连续子数组和，对最
大的 B[i][j]解法可以是：max( abs( maxSubArray(A) ), abs( maxSubArray( - A) )
).
现在求最小的 B[i][j]。暴力解法复杂度是O(n^2)。下面的方法可以做到O(nlog(n))
time, O(n) space: 先求部分和序列 S[i] = A[0] + A[1] + ... + A[i]，i = 0 to n
-1。所有n^2部分和可以由S序列中两项相减得到。对S排序，找相差最小的两项S[i], S
[j], B[i][j] 即得。 |
|
b******g
发帖数: 77 | 43 Initialization:
1. Given a list of meetings with each meeting represented by (meeting
id, start time, end time)
2. Convert each meeting (meeting id, start time, end time) into 2 tuples
meeting tuple (time, end type, meeting id). Sort all start and end meeting
tuples by time.
3. Initial a meeting number counter. If a new meeting room is needed,
the the next meeting room id is the counter value.
4. Initialize a hash map {meeting id: room id} to record which room uses
which id.
... 阅读全帖 |
|
d**********6
发帖数: 4434 | 44 这思路应该是对的，其实就是quick sort
虽然qs的worst case是
O(n)，但大家都接受一般情况O(nlog(n)) |
|
d**********6
发帖数: 4434 | 45 一用bs就不符合O(n)的要求吧，n个数都要搜一次，就是O(nlog(n))
一旦搜到有重复还得重新生成，生成完又搜一次，worst case会进入死循环的
我觉得mapping才是正道，traverse black list一次，用一个计数器i，每遇到bl中的
元素就跳到下一个，然后把i append到另外一个数组里，就得到map好的数组了
不过map会有问题的，生成的随机数不是平均分布的。你的题目说明不是很清楚，不是
平均分布的随机数有没有问题？ |
|
d**********6
发帖数: 4434 | 46 一用bs就不符合O(n)的要求吧，n个数都要搜一次，就是O(nlog(n))
一旦搜到有重复还得重新生成，生成完又搜一次，worst case会进入死循环的
我觉得mapping才是正道，traverse black list一次，用一个计数器i，每遇到bl中的
元素就跳到下一个，然后把i append到另外一个数组里，就得到map好的数组了
不过map会有问题的，生成的随机数不是平均分布的。你的题目说明不是很清楚，不是
平均分布的随机数有没有问题？ |
|
d*****u
发帖数: 17243 | 47 不会通分，也就能分析个循环语句了
比如连merge sort里那个nlog(n)怎么出来的都看不懂，这算是入门内容吧
而且以前没受过较多的数学训练，遇到麻烦点的问题很容易烦躁、放弃 |
|
r****7
发帖数: 2282 | 48 nlog(n)的话直接K路归并就行了。。。
to |
|
k****p
发帖数: 9 | 49 那样可以用priority_queue。priority_queue的函数名和stack一样的,pop,push,top很
好记。
面试官怎么看，我也不清楚。面试经验不多。。。
另外那个题也可以两两merge。假设总长度N,heap复杂度O(Nlog(K))。 两两merge的话
，每轮最多2N(list奇数2N,偶数N)。有log(K)轮。 |
|
r*g
发帖数: 186 | 50
觉得再咋地也得O(n)吧
任意数组求是否重复, 基于比较的最优复杂度是O(nlog(n))
这里有了取值限制 在[1, n] 可以优化到O(n) |
|
