l*y
发帖数: 70 | 1 有点晚， 3月的。 当时是个event，所以只面4轮，其中一轮behavioral,两轮程序一轮
设计。
--------------------------------------
Coding
1. Support undo and redo on a picture.
-- Two stacks, one for each
2. Now each command has a cost and we need peekMax() to get the most
expensive command so that we can potentially save the snapshop (of pic) and
store it to server for that command. How do you support the peekMax() method?
-- Suggested a heaping Heap and the stack are just pointers. O(lgn)
-- Hinted to get O(1) with an example
-- So... 阅读全帖 |
|
x*******5
发帖数: 1335 | 2 在上online的算法课
上面有个地方是
for (k=1; k
statement
下面的讲解是 the k-loop requires only 3lgN array access: the body is
executed lgN times and each time involves 3 array accesses
我能理解3 array accesses,可是想不通lgN怎么来的？
1，3，5，...., N-1
哪位前辈指点一下吧，
谢谢 |
|
r*******h
发帖数: 315 | 3 已经提交hc，但是属于borderline的case，分享面经求通过（之前1m3cd发过简单版）
，相关behavior问题都省略了。
一共五轮，午饭前三轮，午饭后两轮，其中两轮系统设计。因为从国内过来，
recruiter（印度女）特别跟第一个面试官讲我的时差反应，还请他向后面的面试官讲。
1.系统设计，面试官应该是摩洛哥人
给一个url和一个给定的方法genNextUrls可以返回所有从这个url可以直接链接到的url
。要求统计所有能访问到url数。
结果先让我coding，我以为搞错了，问要不要考虑一台机器处理不了的情况，面试官笑
了，说那是followup问题。
就用一个queue和一个hashset走bfs解决之（这里可以反衬我后面一个错误）。面试官
问如果要求判断一个url无效怎么办，我提到了exception处理两种思路，以及
genNextUrls可以怎么处理，面试官说可以，但是如果要求我的方法不能throw
exception出来，怎么让caller知道一开始的url给错了，我blabla。
面试官说现在回到你提到的scalable的问题，你的代码中有哪些地方是bo... 阅读全帖 |
|
h**p
发帖数: 211 | 4 感觉不会有lgN的解法，除非对树的形状有规定，比如perfect bst
普通的bst怎么用lgN的方法得到某一个sub tree的里面的节点个数？更别提规定值得大
小了 |
|
I******c
发帖数: 163 | 5 其实这道题我感觉最好的结果就是O(lgn*n)了
因为如果是O（n)的话，我们就可以在O(n)时间内找到每个元素在数组里的rank，实际
上我们就可以用O(n)排序了。但是理论上排序的最好结果（基于比较的）是O(n*lgn). |
|
j********r
发帖数: 127 | 6 写了半天说验证码过期，没有保存，再写一遍，哭
整体非常复杂，这里只设计指定车站之间余票和购买问题
假设列车车站数为n, 票种类(软／硬卧，软／硬座，站等)，求第x到y站之间的硬座票
数。
分析：因为某种座位在全程的总票数都固定，所以问题可以转化为求x到y站之间对应票
类最大的售出张数，可以只用最大型线段树模型(max segment tree).
设计: 对每趟车的每种座位生成一个单独的线段树，每个站生成一个叶子节点，记录本
站这种座位已出售票数。内部节点记录子树里面最大的座位售出数。
查询：查询x到y站之间最大售出票数，被总票数减，得到x,y之间票数余额。同时x,y之
间所有max值＋1. 查询复杂度O(lgn+k)
购买：只需处理收款和出票，无需操作线段树和对应数据库
回滚：如果购买失败／超时，回滚x,y之间的max值，复杂度同查询O(lgn+k)
除了单次查询速度有所提升，这样做可以减少锁的数量，传统查询O(n)而且需要锁n条
数据库记录，此设计只需要锁k条记录，在大量查询时可以显著提高并发性能。 |
|
d****g
发帖数: 7460 | 7 对你这么牛的人，我只好酸葡萄的说，你是蒙的！
mmm.想来还是直觉好，所谓的形象思维。话说聪明的人擅长算，（这是我），天才的人
擅长猜，（这个是你。）
我是基本穷举8x8发现里面全是０－７。可推16x16全是０－15.(8x8每个数加８即为８
x16)
32x32全是０－31. 4x4全是０－3, 2x2全是０－1.
推算法推了半天。基本是比较（m，n）mod 2 to the nth.即二进制的第一位，来确定
哪一个１／４区间。再比第二位来确定哪一个１／４ within １／４区间.
说句实话，这要是没想起来XOR，我就写出个实现XOR的递归程序来了。。（效率慢好几
十倍的说。）---不对，是O(LgN)和１的区别。---不对，都是LgN,所以是慢好几十倍。 |
|
|
|
T****u
发帖数: 424 | 10 RT-PCR 结果的计算方法
未名 三楼楼长 03-25-2011
RT-PCR 技术已经推广了有些年头。但从众多已发表的文章中不难看出，很多试验
者的计算多多少少都存在问题。甚至，有些介绍算法的文章都存在明显的错误。因
此，有必要对试验人员讲解计算方法。这样不仅可以尽可能避免计算错误，也能更
好地理解RT-PCR 原理。以下讲解只针对单色RT-PCR，也就是说，在任意一个
well 里，只能用一对primers 检测一个样品。
一、RT-PCR 到底要测什么？
RT-PCR（这里，RT 指 real-time。区别于rt：逆转录）是量化基因表达的一种方
法。如果说western blot 是针对蛋白水平，RT-PCR 就是针对mRNA 水平。
基因表达在蛋白水平上，已经经过了多个数量级的放大。或者说一个mRNA 模板
分子可以翻译出无数蛋白分子。所以，蛋白可以很容易地用抗体探测到。但
mRNA 数目太少，直接用探针检测有困难。所以必须要人为放大扩增才能检测
到。这就是PCR 的目的。
不管是先做逆转录得cDNA，再做PCR，还是逆转录+PCR 一气呵成，RT-PCR 归
根结底是以m... 阅读全帖 |
|
f****g
发帖数: 207 | 11 heap + 蛤丝膜噗
insert lgn, delete lgn, get o1, set o1
据说每使用一次蛤丝膜噗, 长者都+1s. 所以蛤丝膜噗的操作都是o1.
估计还得写一个comparator, 先比量再比时间, 毕竟size matters |
|
f**d
发帖数: 768 | 12 这是一本计算神经科学的优秀著作，全文拷贝这里（图和公式缺），有兴趣的同学可以
阅读
如需要，我可以分享PDF文件（－－仅供个人学习，无商业用途）
From Computer to Brain
William W. Lytton
From Computer to Brain
Foundations of Computational Neuroscience
Springer
William W. Lytton, M.D.
Associate Professor, State University of New York, Downstato, Brooklyn, NY
Visiting Associate Professor, University of Wisconsin, Madison
Visiting Associate Professor, Polytechnic University, Brooklyn, NY
Staff Neurologist., Kings County Hospital, Brooklyn, NY
In From Computer to Brain: ... 阅读全帖 |
|
t*******y
发帖数: 21396 | 13 lgN = A
lga*N = B (a是常数，所以lga也是常数)
A/B取极限，用罗必塔法则，得0 |
|
L*****G
发帖数: 12375 | 14 年轻人，不比这里的很多容易激动的lgn沉稳，小有不爽就按核按钮，这是美日最大的
担忧。 |
|
|
C*********l
发帖数: 10248 | 16 东海油气田、渔业资源的背后，是一盘什么样的国际政治大棋局
渔业争端
东海油气田问题，经过中日双方长时间的努力，终于在2008年达成了共同开发的协议。
协议签订之后却不见日方有进一步的实质性联合开发动作，反而这段时间以来，钓鱼岛
又成为了新的热点。
钓鱼岛热点的产生源头是，2010年10月在钓鱼岛沿海发生了一次中国渔船和日本海上保
安厅巡逻船之间的相撞事故。
钓鱼岛一带海域是优良的渔场。最近一段时间台湾当局行事非常低调，比如在日本都还
没有注意到的时候，就对“过分接近日本领海”的舰队长张凤强进行了处分。台湾当局
对这次香港发起的保钓行动不但不准台湾船舶同去，甚至不准香港保钓船只进入台湾港
口补给，这些举动在台湾岛内也遭到了传媒的激烈批判。台湾当局如此行事的真正理由
在于日台之间正在进行渔业协定的谈判，台湾当局担心如果谈不下来，台湾渔民就无法
去钓鱼岛海域捕鱼。
中国大陆对于水产品有着旺盛的需求，近年来中国和韩国、俄罗斯之间经常发生渔业纠
纷，甚至在遥远的太平洋岛国帕劳都有中国渔民被枪杀，所以没有让钓鱼岛周围丰饶的
渔业资源白白浪费的道理。
在2010年撞船事件之前，中日在钓鱼岛沿海还几乎... 阅读全帖 |
|
|
p****s
发帖数: 3184 | 18 “中央集权制大一统政体”有个屁“科学性”和“合理性”。
中央集权制，归根到底是基于tree数据结构的算法，中央就是root，蚁民是leafs，中
间的等级官僚是各层intermediates。
tree这种建模是万能的吗？哪个家伙万事都用tree来建模解决问题这人肯定就是个大傻。
network才是比tree更本质的对世界上事物的建模。
人体是细胞网络network of cells，人脑是神经元网络network of neutron cells。
互联网是路由器构成的网络network of routers，社会是人构成的网络network of
persons。
树也是网络的一种。
网络里情况较复杂，树只是其中很小的一类，根本没什么代表性。就和hypercube这种
网络一样，是比较极端的特例，可能在某些情况下其个别性能最佳（比如hypercube各
项指标都是均衡的O(lgn))，但总体性能未必好、甚至是坏成狗屁都很有可能。
举个例子，robustness和performance最好的name lookup server的结构是hypercube(
如CAN, Chord等其实... 阅读全帖 |
|
z****e
发帖数: 54598 | 19 logn的话空间复杂度要增加
现在可以预判需要的时间，快得多
而且海量数据容量在疯狂增长
也就是n->无穷大
你说lgn和常数差别不大？
呵呵 |
|
z****e
发帖数: 54598 | 20 lol
我是搞分布式计算的
你是不是不懂分布式计算在做什么？
还跟我说lgn和常量差别不大
我这边差别很大 |
|
t**x
发帖数: 20965 | 21 有点良心的都要搭手帮忙。。
满篇看到的就是嫉妒。。 就算那个女的有一点点贪便宜，难道谁不曾有过？！
只不过都是嫉妒，嫉妒人家生活好，家庭好，孩子好，座位就算差了些也比你们好。。
这个女的家庭情况看起来比90%的人好。。 比这个班上99%的人好。
这才是关键。。 都他妈的lgn嫉妒。 |
|
C**********e
发帖数: 23303 | 22 写这代码大概要一个小时呢
用hash的目的是保证独特序列统计在不同样本中出现次数和位置
前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗？
如果生物有这个可能性 那么在数学上就不可能找到母本了
另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率
这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以 |
|
|
a******u
发帖数: 317 | 24 http://sports.yahoo.com/oly/news?slug=dw-olympicswinnerslosers082408&prov=yhoo&type=lgns
Mr. Dan finally said something right.
WINNER – Chinese People
Nowhere in the world have I encountered friendlier people. Nowhere. Perhaps
it was Olympic pride.
Perhaps I was just an easily identifiable American with a press badge. It
didn’t matter. The Chinese
people wanted me to think well of them and their emerging country, and it is
quite clear that this
nation’s greatest resource is its citizens.
From th |
|
|
w****1
发帖数: 2887 | 26 “And the figure skating community wants to control who wins and who loses.
And what it does is it makes the component score more valid than the jumps s
o it can control whatever it wants. And that’s exactly what happened Thursd
ay night at Pacific Coliseum.”
http://sports.yahoo.com/olympics/vancouver/figure_skating/news?slug=es-thoug
hts021810&prov=yhoo&type=lgns |
|
|
|
|
|
|
|
|
|
m*****n
发帖数: 5245 | 35 ☆─────────────────────────────────────☆
thanksgiving (LEFT) 于 (Tue Dec 12 22:11:10 2006) 提到:
刚刚IBM面回来，问了一对自己做的东西。
技术问题有两个：
1）实现链表反转。
2）一列数n个，找到smallest number显然是只用 n-1 次比较。如果要同时找出
smallest number和 second smallest number，那么要多少次比较。
我说可以找两次，用n-1+n-2=2n-3次比较。
然后她提示可以用n+lgn-2次比较，不用外部空间。我想了想没想出来。
☆─────────────────────────────────────☆
glory (o7) 于 (Tue Dec 12 22:13:08 2006) 提到:
ibm的啥职位？谢谢
☆─────────────────────────────────────☆
glory (o7) 于 (Tue Dec 12 22:14:18 2006) 提到:
2) second sma |
|
|
g*******y
发帖数: 1930 | 37 成对的比较，找到最大数后，再比较所有跟最大数比较过的数？但空间呢? 可以做到O(
1)吗？如果空间做不到O(1)，2n -> n+lgn的改进也没什么意义吧。
当然，光看最少的比较次数，那这个是不错的。 |
|
a**********s
发帖数: 588 | 38 Yes, I think:
Consider a 3D grid of combination (NxNxN), each node (i, j, k) stands for a
combination: the ith, jth and kth numbers (sorted from small to large).
You can essentially rule out 1/8 when you compare the required sum with that
of (n/2, n/2, n/2). So this step's complexity is actually O(lgN).
The total asymptotic cost is dominated by the sorting, which is O(NlgN).
up |
|
a**********s
发帖数: 588 | 39 1. After ruling out 1/8, you proceed by 7 subproblems each of scale N^3/8.
So
f(N^3) = 7*f(N^3/8)+O(1)
The total complexity is O(log_{8/7}N^3) = O(lgN)
2. Just forget about these cases :) |
|
H*M
发帖数: 1268 | 40 ...
exponential for recursive one
using a dp way, you can get o(n)
using a matrix multiplication way o(lgn)
seems there is also a explicit formular for that, O(1)? |
|
k***e
发帖数: 556 | 41 嗯 是空间换时间。增加2n个指针，将search time从lgn提高到常数 |
|
h*********e
发帖数: 56 | 42 1. IMHO, if the array is sorted, then binary search O(lgN). If it's not,
then bit sort O(N). 0 bits are the missing numbers. |
|
H*M
发帖数: 1268 | 43 不需要增加field flag吧
这个算法是worst O(n)的 complexity
如果可以增加field,完全可以O(lgn) |
|
k***e
发帖数: 556 | 44 555 I made mistake again
it should be nlog{total sum} or n(lgn + lg(max))
when negative numbers are allowed, it is very messy. i am not quite sure the
binary search works. But DP definitely works, which require nk space and n^
2k time.
max}? |
|
k***e
发帖数: 556 | 45 来自主题: JobHunting版 - 限时2分钟 it really depends on the size of two arrays
if short one size is only o(n/lgn), definitely binary search should be used |
|
|
h*********e
发帖数: 56 | 47 In that way, the number of digits will be O(lgN), instead of a constant 3;
and the time complexity of the radix sort depends on that.
呢？ |
|
k***e
发帖数: 556 | 48 range tree
i don't remember the exact name.
Computational Geometry Algorithms and Applications, chapter 10
nlgn preprocessing, O(lgn+matched#)
efficient
range
a |
|
r****o
发帖数: 1950 | 49 基本的方法是O(n)，有没有O(lgn)的方法？ |
|
|
