k******a
发帖数: 44 | 1
那个元素就是nlogn了。如果这样，不如直接排序，nlogn，然后找m位置的数了 |
|
y*******n
发帖数: 99 | 2 没太懂你得意思
unique prime factorization是指用它来encode num？那比如5个2， 和 一个32， 怎
么区别？
entropy也没太懂，需要nlogn space是区别n种random的状态，这个问题只要把那个
single number识别出来就可以了，而且不是区别所有n个不同数，加上本身题目已经说
了其他数出现N次，遍历数组时，有N种状态，这些状态是depenedent的，space应该少
于NlogN |
|
l********6
发帖数: 129 | 3 虽然没做过 但是目测复杂度也就是降到nlogn吧 不知道有没有大神能想出线性的解法
nlogn的话就从后往前遍历 用一个set存之前的那些数 然后拿到下一个数的时候 在set
里面找upperbound 然后得出upperbound前面有多少个数 再把这个数插到upperbound之
前 整体上相当于维护一颗bst（实际上是rbtree）
[在 lalo (lalo) 的大作中提到：]
：给一个数组，比如【5，2，6，1】
：对于5，它的右边有两个数字比它小；对于2，它的右边有一个比小；6的右边有1个比
它小；1的右边0个比它小.
：........... |
|
y*********e
发帖数: 518 | 4 想了下，这个题用greedy算法解。有点类似dijkstra算法求最短路径。
首先用一个priority queue来装已经发现的字符串，按照字典序排序。
比如输入是cbacdcbc，
scan到了第三个字符的时候，p_queue里面只有一个值 cba。
当scan到第四个字符c的时候，有了重复。这个时候有两个选择：
a. 把 c 从 cba 里面删除，变成 bac。
b. 不理会新遇到的 c，还是 cba。
把a选项和b选项再重新丢回p_queue。
如此重复一直到字符串结尾。返回p_queue的第一个值。因为p_queue是一个按照字典序
排好的priority queue，所以返回的结果一定就是答案。
伪代码如下：
let q = p_queue
for each c in string:
let s = q.empty() ? "" : q.dequeue()
if not c in s
s += c
q.push(s)
else:
s1 = del c in s
s1 += c
q.push(s)
q.push(s1... 阅读全帖 |
|
P**H
发帖数: 1897 | 5 nlogn的排序真很难想到？最直接的插入就是nlogn。
难道就应该什么都不学，聊聊天拿offer？ |
|
t******4
发帖数: 134 | 6 恕我多言……插入排序是n平方吧，移动也有开销啊
：nlogn的排序真很难想到？最直接的插入就是nlogn。
：难道就应该什么都不学，聊聊天拿offer？ |
|
P**H
发帖数: 1897 | 7 nlogn的排序真很难想到？最直接的插入就是nlogn。
难道就应该什么都不学，聊聊天拿offer？ |
|
t******4
发帖数: 134 | 8 恕我多言……插入排序是n平方吧，移动也有开销啊
：nlogn的排序真很难想到？最直接的插入就是nlogn。
：难道就应该什么都不学，聊聊天拿offer？ |
|
d**e
发帖数: 6098 | 9 我错了。。。我重新翻了一下前几天看的，的确没有直接说O(nlogn)，只是说比O(n^2)
快。我觉得14年才出来的解法肯定是复杂到我看不懂，所以也没看下去，也想当然地认
为是O(nlogn)。。。 |
|
z*********n
发帖数: 1451 | 10 这是面试题吗？还是实际工程问题？
单纯追求更高速度，只能牺牲空间。
基于这个前提：“同一个data，findIndices会被执行多次”
最简单暴力的办法：
提前预处理计算好所有两两组合的结果，你的例子里，
预处理完后，应该有一项长成这样：
[100, 157] - [0,3,5,7]
至于输入的（100, 200）怎么map到[100,157],这个trivial吧。
这样的话预处理大概是n^3logn的时间，查询是logn的。
上面做法空间大小是 unique(A)^2*n (~=O(n^3))，按lz的数据规模，大了点
那就只能考虑牺牲查询时间，节约空间和欲处理时间：
考虑建个segment tree吧（按你的例子）：
[100, 300, 25, 123, 3, 157, 9, 103, 304]
排序后：
[3, 9, 25, 100, 103, 123, 157, 300, 304]
把上面这个数组建成segment tree，每个节点存对应range的坐标集合
类似：
（3...304)
[0,1,2,...,... 阅读全帖 |
|
R********n
发帖数: 3601 | 11 【 以下文字转载自 JobHunting 讨论区 】
发信人: DK100 (dark knight), 信区: JobHunting
标 题: salesforce怎么这么难进啊
发信站: BBS 未名空间站 (Tue May 27 22:25:29 2014, 美东)
将近三个月里两次面它家，
第一次折在第一个电话onsite了，一个巨长的名字的老印，coding题不难，看一段代码
，指出哪有问题，第二题是删除linkedlist里的一个node，就用一个指针。然后就是写
sql query，老印说要用having，我说ok，然后就写了一个带having的，然后第二天就
收到拒信，说db太弱。。。这个确实没机会练，也没机会接触。
过了一阵子网投另一组，然后店面，计算一个数组的inverted元素的个数，没见过，直
接给了O(n^2)的，然后问如何改进，实在没想到，就说应该用binary search或者merge
sort的，最低也就是O(nlogn)了，店面过了，然后是一轮code challenge，不难，2个
小时做完发过去。然后onsite，
5轮，每轮一个小时，尼玛，其... 阅读全帖 |
|
h*****a
发帖数: 1992 | 12 我觉得nlogn的文章还是很不错的，写的挺风趣，对外行人来说还是很有用的，比直接看
王的paper容易多了。也许nlogn是加了一些文学渲染，但是bbs也不是什么academic
workshop，不需要太叫真吧。
有
resistant);如果任给一个输入,都能找着另一个输入和它有相同的hash值,那这个hash
击
很
人
只
HA1了,而且大牛们已经担心SHA1也保不了多少天了,必须去造新的hash函数.造个新hash函
且
个
当
攒机子,IBM攒的好一点,电子商场攒的差一点而已.现在突然有人举个例子说Intel的PIII(
且
举
能
出
夸 |
|
z*********n
发帖数: 8 | 13 我指的是O(NlogN)复杂度的算法，要求找出每个点的所以K-NEAREST NEIGHBORS。
好象K=1的情形是有的，DELAUNEY TRIANGULATION，复杂度为O(NlogN)。
多谢指教或是任何有关信息。 |
|
j****a
发帖数: 1277 | 14 按第一个字母排序 nlogn
a->d时 要找d开头的节点 logn
traverse一边 整体还是nlogn |
|
s*****w
发帖数: 215 | 15 因为平常处理大量数据的时候都是import到database里面的。所以没有想过这个问题。
最近遇到一个问题，是关于Array Sort的。
Array有Array.Sort(）方法，看了msdn说他用了Quick Sort Algorithem. The average
the method is O(nlogn) operation, the worst case it is an O(n^2) operation.
这是不是意味着，我们处理这些数据的时候没有必要自己写binary tree的data struct
ure，（C#里面没有BinaryTree的data type)，因为BTree是O(nlogn) operation. 如果
自己写BTree，好处在哪里？ |
|
t****t
发帖数: 6806 | 16 你这就接近于胡搅蛮缠了
通常的说法, quicksort 平均O(nlogn),最差O(n^2), radix是O(n), hash也是O(n)
如果要谈细节,都可以找出毛病来
quicksort worse case O(nlogn)?可以啊,加一个大常数你干不干
radix, 样本空间很大怎么办
hash, 找不到好的函数怎么办 |
|
w***g
发帖数: 5958 | 17 看大家都不吱声，我来抛砖引玉。我其实没什么好的算法。我觉得就是需要O(nlog k)。
第三种情况可能有巧妙的办法，但是前两种情况没什么好说的：
k = 3: O(n), 好歹每个数都要看一遍吧。
k = n/2: O(nlogn)，因为k = n/2的复杂度和k = n其实是一样的，而排序n个数需要O(
nlogn)。
of
(a
for
algorithms. |
|
n********5
发帖数: 323 | 18 一道面试题，是需要写一个函数getAnagram()
这个函数是定义在一个Class里面，这个Class还有一个函数addWord()，用来向这个类
加入任意
word。
我的思路是用hashtable，当add word的时候，把需要加入的word sort一遍，然后查找
hash，如
果已经存在，就是用linkedlist的方式，把新加的word link到最后。这样getAnagram(
)只需要遍
历一遍这个hashtable就可以知道当前输入的words 所有的Anagram。
如果考虑sort的时间复杂度是O(nlogn), hashtable的lookup是O(1)，这个getAnagram(
)函数的效
率是O(nlogn)，假设getAnagram()的pass in是需要查找的word。
这个思路还有什么其他办法可以优化的吗？或者还有其他思路吗？谢啦！ |
|
w***g
发帖数: 5958 | 19 上次在CS版答应给划重点的，发到这儿算了。我手上是第二版。我觉得转行的没有基础
的看完下面这些(约300页，全书1/3的样子）在算法上基本上能达到科班出身水平。可
以按书本身的顺序看，也可以按下面给出的顺序看。
A. 基本概念
1-3 pp.1-61
B. 基本程序设计方法
穷举法 看眼八皇后问题的接法和产生全排列的方法
贪心法 16.1-16.3 pp.370-393
23.1-23.2 pp.561-580
动态规划 15.1-15.4 pp.323-356
分治法(divide and conquer) 本书没有专门的章节讲这个，需要自己随便上网搜搜。
结合下面章节看
选中位数 9.1-9.3 183-189
快速排序和二分查找
回溯(recursion) 这个是具体的实现方法，可以和上面三类方法结合。书中没有。可以
自己动手编一下算fibonacci数和解Tower of Hanoi问题的算法，体会一下回溯算法的
基本结构。看眼下面的页面
http://en.wikipedia.org/wiki/Memoiz... 阅读全帖 |
|
w***g
发帖数: 5958 | 20 上次在CS版答应给划重点的，发到这儿算了。我手上是第二版。我觉得转行的没有基础
的看完下面这些(约300页，全书1/3的样子）在算法上基本上能达到科班出身水平。可
以按书本身的顺序看，也可以按下面给出的顺序看。
A. 基本概念
1-3 pp.1-61
B. 基本程序设计方法
穷举法 看眼八皇后问题的接法和产生全排列的方法
贪心法 16.1-16.3 pp.370-393
23.1-23.2 pp.561-580
动态规划 15.1-15.4 pp.323-356
分治法(divide and conquer) 本书没有专门的章节讲这个，需要自己随便上网搜搜。
结合下面章节看
选中位数 9.1-9.3 183-189
快速排序和二分查找
回溯(recursion) 这个是具体的实现方法，可以和上面三类方法结合。书中没有。可以
自己动手编一下算fibonacci数和解Tower of Hanoi问题的算法，体会一下回溯算法的
基本结构。看眼下面的页面
http://en.wikipedia.org/wiki/Memoiz... 阅读全帖 |
|
w***g
发帖数: 5958 | 21 你这个问题用专有名词讲叫 find the medoid under Manhattan/L1 distance。如果对
Manhattan distance做K-Medoid聚类的话是一个超频繁调用的操作。不知道你的最小生
成树的解法是从哪儿看来的。前面database指出了解这个问题的关键，就是在
Manhattan distance下X和Y独立。不过他的解法我实在没有看明白，只能猜一下。
我们的目标是任意给P点中的一点可以用O(1)算出所有点(P到自己的距离是0，包不包含
无所谓）到该点的距离之和sum(P)。这样所有点过一遍用O(n)就可以找出最优点。
这个sum(P)又可以分解 sum_x(P_x)+sum_y(P_y)。 sum_x和sum_y的算法相同。下面用
计算sum_x加以说明。
加入有一串值x1, x2, ...，要计算任意一个xi的sum_x(xi)值。可以对所有x排序O(
nlogn)。
x1, x2, x3, ...
然后对各个i计算 left_i = x1 + x2 + ... + xi-1
right_i = x{i+1}... 阅读全帖 |
|
l*******l
发帖数: 248 | 22 我觉得眼熟。。。
就是不确定 n+nlogn = nlogn |
|
I*****a
发帖数: 5425 | 23 【 以下文字转载自 JobHunting 讨论区 】
发信人: barbie6676 (barbie), 信区: JobHunting
标 题: 发面经 回报本版
关键字: 面经
发信站: BBS 未名空间站 (Sat Nov 16 11:49:17 2013, 美东)
背景：本科生物，统计master + 9个月工作经验
结果: offer: amazon, facebook, linkedin, google
Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
电面：
Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
有问题怎么trouble shooting的开放问题。
Linkedin 两个：
1 binary tree level order traversal, leetcode原题
2 pow(x,2) leetcode原题
3 判断一个string表示的数字是否valid，类似l... 阅读全帖 |
|
h******n
发帖数: 3599 | 24 某个中科院院士在李劲的博士答辩会上， 清了清嗓子， 怯生生地问：李劲同学，你看
这个信号压缩解码可不可以这么解释。。。。。。？ 后面旁听的笑倒一片
这个故事告诉我们， 小时了了 大未必佳， 反例是 邓艾老乡肉肉，格莱斯高 貌似
有后来居上， 赶超李劲的趋势
李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
h******n
发帖数: 3599 | 25 某个中科院院士在李劲的博士答辩会上， 清了清嗓子， 怯生生地问：李劲同学，你看
这个信号压缩解码可不可以这么解释。。。。。。？ 后面旁听的笑倒一片
这个故事告诉我们， 小时了了 大未必佳， 反例是 邓艾老乡肉肉，格莱斯高 貌似
有后来居上， 赶超李劲的趋势
李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
c********v
发帖数: 1278 | 26 你是不是刚本科毕业？
一个算法没有理论支持，能叫算法？
那叫ad hoc
你学算法的时候，老师没跟说
看问题然后就直接写for while if就是ad hoc吗？
人家是Cooley分析以后，发现如果直接上DTFT, 有redundant的项(items)
然后用了一个tricks把这个redundant的去掉，从n^2变到nlogn
有DP的思想在里边 |
|
w********r
发帖数: 14958 | 27 跟你说了多少次了。算法不等于暴力穷举。
最简单的Ｐ问题， 让你去给一串数字排序你怎么排？
最好的算法复杂度 是O(n)至O(nlogn)之间。是暴力穷举吗？ 靠你人脑算，你能比
电脑方法好吗？
人脑这个叫Heuristics,没有任何保证能赢。 只不过是经验基础上一定的演绎。 很
多种棋局，任何人都没有见过。 人只能靠猜加蒙。这时人脑的能力等于零。
之所以围棋大师，实际上是因为他见过类似的。或者所有会下棋的只会下那几种套路。
最早都是那几个师傅教出来的。 |
|
w*********a
发帖数: 9279 | 28 不完全是， 关键贡献在于1，Expected time complexity不超过nlogn； 2，适用于任何
非线性物理系统
换句话讲，计算机速度再提高1000倍左右， 任何controller都要下岗。控制理论已经
渐入黄昏。 |
|
h******n
发帖数: 3599 | 29 某个中科院院士在李劲的博士答辩会上， 清了清嗓子， 怯生生地问：李劲同学，你看
这个信号压缩解码可不可以这么解释。。。。。。？ 后面旁听的笑倒一片
这个故事告诉我们， 小时了了 大未必佳， 反例是 邓艾老乡肉肉，格莱斯高 貌似
有后来居上， 赶超李劲的趋势
李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
h******n
发帖数: 3599 | 30 李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
k******k
发帖数: 888 | 31 李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
e**a
发帖数: 2169 | 32 李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
H*******s
发帖数: 537 | 33 李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
m********5
发帖数: 17667 | 34 李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
O******2
发帖数: 2739 | 35 李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
d******a
发帖数: 32122 | 36 李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李昌钰博士当场就不吭声了 |
|
d*******3
发帖数: 8598 | 37 李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
G***i
发帖数: 150 | 38 知道numerical 范围的话 如果不是很多 可以用 bucket 或者 radix sort O(n)
complexity
一般的话 comparison sort 直接上quick sort好了 average O(nlogn) |
|
n********g
发帖数: 6504 | 39 算法复杂度从n^2到nlogn。发paper不算啥。具体到工程上enable了无数可能。“我们
一生中最重要的数值算法”，20世纪十大算法。1805年由高斯提出。
我最早在图像处理上遇到快速傅里叶变换。 |
|
t******l
发帖数: 10908 | 40 从 quadratic 到 superlinear，在工业界大尺度运算上，是革命性的。
: 算法复杂度从n^2到nlogn。发paper不算啥。具体到工程上enable了无数可能。
“我们
: 一生中最重要的数值算法”，20世纪十大算法。1805年由高斯提出。
: 我最早在图像处理上遇到快速傅里叶变换。
|
|
n********g
发帖数: 6504 | 41 搞算法的知道，n^2和nlogn天人两隔人鬼殊同。一切可以归结为傅里叶运算的过程都因
此白日乘龙飞升。整个人类文明从蒙昧走到光明。
以n=1000估计（不大，还没出1000000），快了100倍左右。 |
|
n********g
发帖数: 6504 | 42 谢谢分享。一边看杨幂床戏一边看完回收。
依靠再多的奴隶压迫再薄的工资在n^2下也轻易被nlogn几个疯子碾压。数手指数到时间
的尽头只不过是区区一个实数。
才爬出countable，有没有的坑。人家已经在可能和不可能的楼梯上爬了好久。
代差就意味着两个师被一个连打垮。从这个比例看，志愿军精锐军团和世界的距离和廊
坊之战的满清末代骑兵比好不到哪里去。 |
|
发帖数: 1 | 43 一个O(NLogN)一个O(N^2）
外星人估计也用象形文。 |
|
h******n
发帖数: 3599 | 44 某个中科院院士在李劲的博士答辩会上， 清了清嗓子， 怯生生地问：李劲同学，你看
这个信号压缩解码可不可以这么解释。。。。。。？ 后面旁听的笑倒一片
这个故事告诉我们， 小时了了 大未必佳， 反例是 邓艾老乡肉肉，格莱斯高 貌似
有后来居上， 赶超李劲的趋势
李同学亲口说他博士期间， 信号处理写了十几万行C程序， 奥赛金牌罗三木说， 他妈
的好程序五百行就够， 比如快速傅里叶变换，复杂度从 O(n^2)降低到O(nlogn)， 何
必要几十万行程序滥竽充数， 李博士当场就不吭声了 |
|
r*****e
发帖数: 620 | 45 离散傅立叶变换的复杂度是就N^2吧, A是对的
FFT是NlogN
估计你没分清楚DFT和FFT, 错上加错给了个正确答案，没有丢脸:) |
|
a**********s
发帖数: 588 | 46 求两个序列的LCS, 如果你知道其中有一个是单调的, 就能在linear时间中找到. |
|
|
h*********i
发帖数: 116 | 48 是求所有单调升子序列还是一个就行啊
如果一个子序列就行的话，那就是linear阿，贪心法就行。 |
|
r********7
发帖数: 42 | 49 一个就行。
假设 X=[0,2,0,4,3,1,5,0];
Y sorted by X = [0,0,0,1,2,3,4,5]
如何greedy求LCS？ |
|
h*********i
发帖数: 116 | 50 就是线形由左至右扫描。。。总是保留当前序列最大值。。然后看下一个元素是否比当
前序列中最大值大。。如果有比这个最大值大的就把这个元素加入子序列如果没有这个
最大值大就跳过但前元素再往下看。一直到所有元素都被扫描完。这样就是一格单调升
序列了。。。 |
|
