t******l
发帖数: 10908 | 1 奥物的近似部分确实要靠直觉。
但现代美帝改革后的奥数，空间建模解法和自动机建模解法，也一样需要直觉，尽管不
需要近似。。。当然改革前的祖国奥数尽是些抽屉原理证明题，更多的 raw brain
power，对空间建模寻找 solution path 解法不强调。。。当然部分原因是当年马工计
算科学没有发展，缺少对 computational solution 的意义的评价。。。而不像物理学
一直尊重 computational solution 也是 solution 的概念。
: 呵呵, 有些东西装是装不出来的.
: 某些名媛的名, 是臭名昭著的名
: 化学竞赛到了后面并不是那么容易的, 虽然没有大学的知识底子是玩不转的, 但
是解题
: 尤其是比较难的题目还是要靠逻辑技巧.
: 其实化学更像是个奥数的二线竞赛, 利用的基础规则体系不一样, 逻辑严密度差
一下,
: 复杂度低一些.
: 但是推理逻辑还是很类似的. 其实名媛可能不知道的, 很多奥化兼的是奥数, 奥
数被淘
: 汰了以后来玩奥化的.
: 反而奥物是另... 阅读全帖 |
|
发帖数: 1 | 2 物理奥赛有个屁直觉，只有到全国决赛这种级别才有点思维和技术含量，初赛复赛就是
闷头死算，谁算的快谁分高，所以女生一般扛不下来
: 奥物的近似部分确实要靠直觉。
: 但现代美帝改革后的奥数，空间建模解法和自动机建模解法，也一样需要直觉，
尽管不
: 需要近似。。。当然改革前的祖国奥数尽是些抽屉原理证明题，更多的 raw
brain
: power，对空间建模寻找 solution path 解法不强调。。。当然部分原因是当年
马工计
: 算科学没有发展，缺少对 computational solution 的意义的评价。。。而不像
物理学
: 一直尊重 computational solution 也是 solution 的概念。
: 是解题
: 一下,
: 数被淘
: 的人非
|
|
s*****r
发帖数: 43070 | 3 【 以下文字转载自 JobHunting 讨论区 】
发信人: wsclock (精确), 信区: JobHunting
标 题: F家详细面经，有工作经验被拒(超长慎入)
关键字: facebook,interview
发信站: BBS 未名空间站 (Fri Sep 22 20:45:31 2017, 美东)
简单总结：CS博士，奔5了，申请facebook software engineer，不是headquarter。
onsite后第三天收到据信。估计死在system design上。面试简况如下。详细的在后面。
Screening 和final round头两个都是coding interview，都做到了bug free。题目不
难，即使没刷过题，也容易有思路。唯一不足的是，有一个coding写的代码不是时间复
杂度最低的。虽然后来给出了优化的办法，但是没有时间写优化的代码了。
下一个是system design，感觉不太好。其中一个问题是估计要多少个server，我解答
的时候，最大的失误可能是没有问每秒钟多少个transaction，面试官也没给这个条件
。面试官指出... 阅读全帖 |
|
y*j
发帖数: 3139 | 4 解析解法==平面几何，辅助线，定理一大堆，看上去很奇妙，但不能generalize。
数值解法==解析几何，看似蠢笨，但非常实用，最终击败了平面几何。
：马工牛顿法一招鲜解决 99.9999% 的使用偏微分方程 。。。 根本不用啥测度论或者
泛函分析 。。。
：偏微分方程的解析解法，基本上就是纯数学家自己看看 。。。 世上有实用的而不是
空想的美学函数里，有几个是古希腊人不会解但现代纯数学家会解的？ 。。。
：优化算法更不要说了，实用中都不超过牛顿法 。。。
：从古希腊人的角度，牛顿之后的数学，实用中除了多算几个方程以外，基本就是纯哲
学 。。。 古希腊人需要抽象数学是为了走地中海后方沙滩登陆的计算 。。。 现代纯
数学搞这么抽象，但又不能 worm hole 时间旅行，球用啊 。。。 难道登月也要测度
论？
：【 在 forsythia(器人二代) 的大作中提到: 】
：
: 时摊姐，没有测度论，勒贝格积分，泛函分析就是空中楼阁，只剩下几个算例
。
: 没有泛函分析，偏微分方程理论就只能叫数理方程引论了...
：
|
|
d*****u
发帖数: 17243 | 5 Supervised机器学习本质都是data fitting。
如果输入或状态的空间很小，其实没有特别约束参数的解法（包括暴力解法）是最好的。
但如果各种可能太多，需要训练一个系统来准确处理没见到过的数据。
对于一个N维二元向量，有2^N种赋值（输入），暴力解法必须都走一遍。但是现实中的
问题里，这N个维度有各种复杂的dependency，而神经网络可以较好地模拟这种
dependency，所以可以在训练数据不足的情况下也做出比较好的预测。不用有2^N个
instance |
|
W******2
发帖数: 1453 | 6 【明慧网二零一一年五月十日】每当捧起《转法轮》，读到第三讲，“我们上次在吉林
大学办班时”那一段法，作为吉林大学大法弟子，我们都感到格外幸运和荣耀。从一九
九二年九月到一九九四年九月，师父曾经七次亲临吉林大学传法，办过两期三个法轮功
学习班，亲自为学员选定炼功点，两次与吉林大学学员座谈，两次亲临炼功点看望学员
，一次在吉林大学为长春市法轮大法辅导员解法。长春是师父的家乡，是最早得到大法
洪恩福泽的地方。
师父在《转法轮》里写到在吉林大学办班时发生的故事，使这一段历史在未来的宇宙中
永存。这段珍贵的记忆一直激励着吉林大学大法弟子在大法中不断精進，圆满完成自己
的责任和历史使命，不负师父的慈悲厚望。
师父传法已有十九年了，回想师父当年在吉林大学传法的情景，仍然历历在目，仿佛昨
日。今天，我们把这珍贵的记忆记录下来，与同修分享，了却我们的一桩心愿，也是献
给“世界法轮大法日”的一份特殊礼物。
师父亲自选定炼功点
一九九二年九月十七日，长春第四期法轮功学习班结束，师父晚上就要到北京去，车票
已经买好了。吉林大学一位参加过师父班的学员恳请师父在离开长春之前，到吉林大学
来看看。师父同意了。
九月... 阅读全帖 |
|
s***r
发帖数: 783 | 7 看来你到现在还不明白哪丢分。
国内不要求特定解法，但要求一个完整的解法。你跳步骤那里开始，解法就不完整了，
后面如果算你蒙的，当然不给分。
我当年随便跳步骤，没有问题，因为老师相信我会。你的老师看来不相信你。 |
|
o*********c
发帖数: 62 | 8 我的两个research tasks 都是给出了新问题的formulation,然后在high level上描述
解决问题的基本方法,比如说可以把该问题转化为一个已知类型的问题然后套用某种方
法解决.至于具体的象research paper那种detailed 的解法是没有的.我也的确不知道
我的设想是否真的行的通. 如果真的有了concrete的解法了,是不是就已经是可以成文
了?那样的话这部分工作就不能claim成proposed research tasks了吧.这部份工作是不
是就是所谓的prior results了?这个就是我第一部分中我已有工作的描述.
其实很多问题如果你确信某个方法能解,那么实际上你已经把这个问题解决了.
根据你所说的,proposal的写作好像存在一个固有的怪圈:对于proposed research, 如
果如你而言必须要很明确地描述该如何解决,并且给出足够的detail来说服reviewer你
建议的方法的确能解决问题,那么实际上该问题就已经不是问题了,对吧?既然不是问题
了,那还propose 去研究它干嘛?小结一下,这个怪圈就是:propose ... 阅读全帖 |
|
g*******y
发帖数: 1930 | 9 附带些小面经，这次是第二轮的google onsite，就在学校附近的local office(离我家只有3miles距离，呵呵)，安排这轮的原因是上一轮面试中没有涉及到system and design的问题。
这次只有两轮，每轮只有45分钟(我开始搞错了还以为1h的)。本来觉得就是专门考design类问题，结果没想到，可能是他们内部安排面试的时候没有交代清楚，今天的两个面试官似乎都不知道这个。。。后来我只有主动跟第二个面试官说，希望问一些system design方面的问题。
题目签了NDA不太方便透露，不过我还是想大概提提，都是些很经典的老题，不知道为什么，我每次面试的题，难度都是比较低的。。。不知道是不是别人觉得我的水平不太够。。。
今天第一个人居然是老印，唉，第一次领教老印的厉害。。。第一个题目是最简单最经典也是最难的linked list题目(呵呵，其实大家也能猜到了)，我当然知道经典解法，不过经典解法确实也很难想到，于是我就只说了另外一个普通直接容易想到的解法(但是就没那么巧了)。中间漏了一个check null pointer的地方(郁闷)。接下来出了个简单的数学题(无 |
|
I********T
发帖数: 22 | 10 看到一道面试题
给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出
共同的URL。
这个题目在网上看到有两种解法：
解法一：（1），读取文件，计算HASH，按HASH值分段放入不同的文件，文件数可以比
较多，两个
文件的URL，分开不同的文件放（a1，a2,...，b1，b2，...），保存时可以把HASH值也
保存进
去，避免再次计算HASH值
（2），对每一个HASH段，读出两个文件中的一个，比如a1，对HASH值有冲突的放一个
连表里，然
后读b1文件，取HASH值和URL，如果HASH值在a1中有，则进一步判断URL是否相同。
解法二：Bloom Filter（广泛应用于URL过滤、查重。参考
http://en.wikipedia.org/wiki/Bloom_filter、
http://blog.csdn.net/jiaomeng/archive/2007/01/28/1496329.aspx）
可是我算了下内存4G，换成bit位是4 * 2^30 * 8 =32 *2^30 个位， 数据有5*2^30,
这样把全部
内存用来做h |
|
h**k
发帖数: 3368 | 11 不用搞这么细，你把那个DP的解法吃透就行。那篇文章是研究这个NP问题的近似解法，
并指出什么条件下这个近似解法是最优解。这个只有专门研究算法的才关心。面试没有
人会问这个。 |
|
i**********e
发帖数: 1145 | 12 更新：
Finding the Maximum Height of a Binary Tree
这题就是寻找二叉树的最深度，利用DFS可以轻松解决。挑战的是：如何写非递归的版
本。有两种解法，一是用BFS，解法比较直接。另一种解法是转换成非递归BFS，方法请
参考In-Order Traversal Iterative Solution.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
y*********e
发帖数: 518 | 13 这个题目可以说是在考察边界条件，面试者应该跟考官沟通好。一般情况下 N
应该是非负的整数。若是遇到负的整数怎么办？抛出异常就可以了。若是
integer overflow怎么办？
最naive的解法是O(N)。此题也可以优化到O(logN)，我曾经遇到这个面题，
当时想出来的解法如下：
计算X^1, X^2, X^4, X^8, ..., X^M, X^(2M)，使得M <= N < 2M。
那么欲求的值就介于X^M和X^(2M)之间。然后用二分法确定 N 的位置。
从X^1, X^2, 涨到 X^M (M <= N < 2M)，需要O(logN)的时间。然后在M
和2M里面确定N的位置，需要O(logN)的时间。整个解法还需要O(logN)的空间
。 |
|
i**********e
发帖数: 1145 | 14 谢谢你的回复，你的解法我没想过，的确也是另一种对的解法。
但是我的解法和你有点不一样。
就用你给的例子，我们要寻找的target=12。
00 02 03 04 05 06
01 04 07 11 15 16
02 05 08 12 19 20
03 06 09 16 22 23
10 13 14 17 24 25
18 21 23 26 30 31
首先，无论什么情况都好，我们都会选定中间那列来进行binary search。
中间那列就是03,07,08,09,14,23。
binary search告诉我们12在 09 和 14之间。
那么我们就可以把这个矩阵分成两个小矩阵。
XX XX | 03 | 04 05 06
XX XX | 07 | 11 15 16
XX XX | 08 | 12 19 20
XX XX | 09 | 16 22 23 |
|
i**********e
发帖数: 1145 | 15 还有另外一个解是用两个 stack，解法很巧妙，很简洁。这不是我想出来的，在
careercup 上找到的。但是空间复杂度比一个 stack 的解法还要多一些。（O(N)
space，N 是 节点的总数）
解法如下：
1. Push the root node to the first stack.
2. Pop a node from the first stack, and push it to the second stack.
3. Then push its left child followed by its right child to the first
stack.
4. Repeat step 2) and 3) until the first stack is empty.
5. Once done, the second stack would have all the nodes ready to be
traversed in post-order. Pop off the nodes from the second stack... 阅读全帖 |
|
g********d
发帖数: 203 | 16 贡献一下我的面经吧，希望能有帮助。和大家碰到的题比，我的都很简单了，但是自己
水平真的太烂，一路下来，磕磕碰碰的。
电面是去年12月的，已经忘了什么题了，好像都是和data scaling/transformation有
关的 ，挺简单的，没有要我写code。所以没什么可说的了。
Onsite 1 上个礼拜二:
第一个：ABC mm，进来就直接往white board冲。让我写一个in order binary tree iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个很应该是feedback
最差的。
第二个：白人，很friendly。一半behavior，加两道题：test anagram和字典里找所有
anagrams，没要写code，就是在纸上描述一下步骤。这个感觉最好。
第三个：白人 ，hiring manager，很down to earth。问我怎么从一个机器传... 阅读全帖 |
|
i**********e
发帖数: 1145 | 17 其实那题 merge k sorted arrays 是再也经典不过的题。
还有，其实你选择用 brute force 来写反而更难，很多细节要处理，要一次写对比较
麻烦。
相反的，用 heap 来做就反而容易多了，而且解法更优。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的
hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便
吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个
很应该是feedback |
|
n***i
发帖数: 777 | 18 最近面了2个，全部失败，都是技术面试。正在反思。其实自己练了挺多数据结构算法
，编程也挺多，也
在白板上自己写code，觉得写的不差。这两次面试，有一次是因为面试官给了一个抽象
的题，一下脑子
转不过来，想复杂了，因为平时都是练的很具体的well-defined的题目，最后反应过来
的时候，写了
一些，估计面试官觉得反应太慢，不smart。 还有的情况是给出了一个解答，这个解法
可能是平时准备
过的，然后面试官说如果这换一下，那换一下，怎么办，或者还有什么其他方法，然后
就有点思考速度
过慢。 面试官提示了一点，估计他希望我马上反应出来，但是我花了挺长时间才想明
白说出来，总是没
有给人smart的感觉，给人印象是对于问题的敏感性比较差。
我自己分析问题可能主要有以下一些：
1） 平时重coding而轻思考。总觉得技术面试就是coding要熟。看题目练习时 如果5-
10分钟想不出
来就看解答，然后只求把解答的方法coding出来，觉得就满足了。没有从多角度思考问
题，思考有没有
其他解法，各种解法优劣。
2）抽象能力弱，平时太着重于具体小问题，而轻设计层面的思考，导致一旦出现抽象
概... 阅读全帖 |
|
g*********s
发帖数: 1782 | 19 发信人: uglyduke (一苇居士), 信区: JobHunting
标 题: 绝对精华，offer＋面经
发信站: BBS 未名空间站 (Wed Mar 30 21:34:37 2011, 美东)
Amazon的offer，95k+15k
基本情况：
国内大学cs本科，杭州小公司SDE工作1年半，L1来了公司美国总部作PM。工作不到2年
离职开始找工作。L1签证到今年2月就过期了，算是黑着身份找的，挺不容易。
google电面。大我10多届的学长打来，问题范围比较广，但内容基础，考察面：
1 基本数据结构，如array和list
2 十六进制的基本题
3 多线程，线程与进程的区别，windows下的多线程编程基础，livelock技术，读写者
4 给了几个数比大小
5 c++的基本知识，多态，vptable，引用，常，构造析构，static的用法等等小东西
6 浏览器里输入URL后发生什么
on site在santa monica
1 behavior+60秒点击最多的问题，coding。
2 coding，实现一个DFS，不过缺一些条件。
3 大规模问题，有点特殊性的字串排序... 阅读全帖 |
|
f*********i
发帖数: 197 | 20 A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bianry tree找两个节点的最
小公共父亲, 一开始是允许有父节点的,然后扩展到没有父亲节点,我给了O(nlogn)解法
public static BinaryTree tree_least_comm... 阅读全帖 |
|
f*********i
发帖数: 197 | 21 解法一:这个是版上经常提供的,
1) 先reverse string,/O(n)
2) 找两个string的最大common substring //O(n^2) time, maybe O(n^2)space
解法二:
1) 对每一个string中的character, 向前后分别查找看看它们是否相等 O(n^2)
考虑ABA 和ABBA这两种情况
个人觉得第二个解法好些,不需要太多space |
|
p*****u
发帖数: 310 | 22 搞得我现在郁闷无比。准备了一肚子算法，可上来就问array去掉重复的算法，说了个
最简单的hash table 解法，就让我写code，准备再讨论其他解法。可刚写完code，大
老板来了，一问，正在讨论hash table。就问如何不用lock实现多线程的读写hash
table。憋了半天，想了个versioning，貌似他不满意，于是乎就翘翘了。回家翻了翻
书，好像还有atomic variable的解法。有大虾说说吗？ |
|
p*****u
发帖数: 310 | 23 Write a Program to rotate a matrix by 90 degrees。 这题有啥好解法吗？正方形
网上有in place的解法，不知长方形有啥好解法？ |
|
h******k
发帖数: 810 | 24 本周面了某L公司，说说经历吧。一共五场九个人，除第一场host manager一人半小时
，其它都是两人一master一shadow一小时。
1. 介绍公司产品，发展方向；本人介绍做的项目，most challenging project.
2. 150题8.2：imagine a robot sitting on the upper left hand corner of an NxN
grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot？讨论时间复杂度空间复杂度。如何优化。
3. given two linked lists of object references, how to check if the third
one is a merge of these two, notice that different references could point to the same object, and ... 阅读全帖 |
|
p****e
发帖数: 37 | 25 尝试回忆一下我面试时给出的做法及我的思路：
我一开始就是给你的这种解法（我是用Floyd算法，给出所有点对的值），只可惜效率
不高：
假设一共有V个人，和E个关系，
那么最坏情况下，用Dijkstra算法判断任意两个人的关系，需要O(E + VlogV)的时间，
不用额外空间的话。
用Floyd算法的话，需要O(V^3)的时间预处理，O(V^2)的缓存，之后只需要O(1)的时间
判断。
这时间面试官说，如果给出的关系很少，人很多，你这个算法太浪费了。
那我想，他要的算法，复杂度必须是基于E的，才有戏。而基于关系来处理问题，肯定
把关系中出现的人加到一个一个group中间去的（因为不能再cover所有的人了）
于是我给了一个新的做法：
当我看到一个关系（A,B 朋友）的时候，我就把A，B加到一个group中去，如果出来一
个(B,C,敌人）的时候，就把C加到另外一个group中去。总之是把A的朋友们放到一个
group, 其它人放到另外一个group。这里忽略一些细节，最后可以得到两个group., 然
后对新的一对人，只要看一下他们在哪个group中就行了。这里我用的对应group的数... 阅读全帖 |
|
g*****i
发帖数: 2162 | 26 **********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You went
to the bookshop but fail to find, you have 5 minutes, what will you do?
you have to test 10... 阅读全帖 |
|
g*****i
发帖数: 2162 | 27 **********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You went
to the bookshop but fail to find, you have 5 minutes, what will you do?
you have to test 10... 阅读全帖 |
|
K*****k
发帖数: 430 | 28 对经典题，知道了解法，自己也练过后，我想应该去找最简洁的写法。一些技巧可以减
少代码的行数或者不必要的判断。
比如Carrer Cup上的解答有类似的语句
...
if (!Func(x))
return false;
return true;
其实可以简化为写成
return Func(x);
把三行代码缩小为一行了。
还记得费马的话吗：
对于这个问题我有了一个巧妙的解法，可惜书页里的边缘太小，写不下了。
对于我们：
对这道题我有一个绝对可行的解法，可惜这个白板太小了，写不下了。 |
|
g*********e
发帖数: 14401 | 29 第二题是：Suppose I give you a dictionary
of words; the size of the dictionary is finite. Each word in the
dictionary is composed from a set of characters; the size of the alphabet is
finite. Find the longest word in the dictionary with the property that it
can be built one character at a time and at each step is a valid word in the
dictionary.
e.g. Dictionary = Webster
Alphabet = A-z
a -> at -> cat -> chat -> chart -> charts -> …..
估计挂在这道题上面了, 当时说完解法在算复杂度那里纠结了一会儿。先不说解法，打
算面google的自己想一下能... 阅读全帖 |
|
K*****u
发帖数: 241 | 30 判断一棵二叉树是否平衡
在第五版前Gayle认为只需要判断最高深度和最低深度的值是否相差不超过1就可以。
解法虽然简单，但偷换了概念，是错误的
虽然最高深度和最低深度的值相差不超过1的树一定是平衡的，但反过来却不对。换句话说，二叉树最高深度和最低深度的值相差不超过1 是 二叉平衡树 的 充分 而非 必要 条件
也就是说那个解法偷换成了更强的要求（虽然解法更简单)，但这样的树只是平衡树的一个真子集。
请大家自行构造一棵最大深度和最小深度的值超过1的二叉平衡树，加深对二叉平衡树概念的理解。 |
|
i**********e
发帖数: 1145 | 31 这道题经典解法（Step-wise linear search, 也就是 lz 的解法） 是 O(N+M)，不是
O(N*M). 可以选择从左下角 或者右上角 都可以。
网上已经列出五种解法 并一起以真实数据比较算法速度。发现竟然 Improved Binary
partition （利用二分） 的算法是最快的。但是这个算法的复杂度非常难证明，如果
有人可以证明出来，我愿意发完我所有包子给他。
Binary Search: 31.62s
Diagonal Binary Search: 32.46s
Step-wise Linear Search: 10.71s
Quad Partition: 17.33s
Binary Partition: 10.93s
Improved Binary Partition: 6.56s
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part |
|
H*****1
发帖数: 4815 | 32 对，面researcher的话，基本不用准备coding的
你只要会把问题抽象出来，有足够的数学功底能够解决这个问题就好了
不需要考基本的数据结构和算法
sde就不同，一般是给你已经定义清楚的问题，不需要什么高深的数学知识去求解
你需要实现一个解法，要求高的需要一个高效的解法或者有其他约束的解法 |
|
M*****e
发帖数: 568 | 33 之前帖子的一道题，没有想到特elegant的解法。主要是需要一个list存储能够蓄水的
点，而这些点选择的标准是不能小于当前点和list中的前一个点，说起来比较绕口。
不要说从左扫一个从右扫一个的解法，这种解法没办法解决中间有两个峰的情况，比如
3 1 8 1 9 1 5 => 2+7+4=13
X）Onsite 老题新酒，直方图，天上下雨，求能存多少水
E.G:
3,1,5 => 2
3,1,0,5 => 5
很假单的O(N)扫描就行
扩展是改成Online的算法，就是说：
有些地方高度随时会变，
E.G.
3,1,5 => 3,0,5 => 3
3,1,0,5 => 3,3,0,5 => 3
设计一个算法，最快的返回改变高度之后的结果 |
|
|
r********g
发帖数: 1351 | 35 数组四个元素：5,6,3,3
最佳解法是：把5减成3，cost是2次decrements,把6减成3，cost是3次decrements，这
样得到的结果是：3,3,3,3 total cost是5
另外一个解法是：把最后2个3删掉，cost是3+3=6，这个就不是最优解法。
楼上的DP是正解。。。膜拜中。。 |
|
d*******a
发帖数: 21 | 36 来自主题: JobHunting版 - FB面经~ 飞机晚点了，正好趁这个时间写下约好的FB的面经。
先说下我的情况，国内211重点大学计算机小硕，本科也是一所211重点大学的计算机系
毕业的，可能这个是拿到面试的原因，所以稍微提一下。
我大概是2月份发简历给FB的，发了简历后过了一段时间突然收到面试的通知。但和其
他同学有点不同的事，HR没让我做Puzzle，直接就开始电面了，不知道为什么。
第一次电面是HR的情况确认，大概20来分钟，一是看看英语够不够用，二是传说中的
Behavior Questions，基本上就是为什么要来FB啊，想在FB做什么啊，这些问题。这轮
应该不算面试，只是个基本情况确认的感觉。
第二轮电面是技术面，45分钟，5分钟聊下项目，然后就是做题。题目两道，一个是分
层打印二叉树，一个是老式手机键盘数字对应字母，给几个数字，求全部可能的组合。
都很简单，没有准备过也能做出来。不过FB题都这样，不难，但代码要写的漂亮，最好
是Bug Free的。据说FB基本不做测试，早上想到一个Idea，下午实现，晚上就内部上线
了。也许这也是原因之一。如果做完后时间很多的话可以聊很多问题，尽量问问面试官
的team做什么，然后有... 阅读全帖 |
|
N*****8
发帖数: 253 | 37 来自主题: JobHunting版 - 请问两道题 版本有贴过这题，但是原帖中没有O(n)的解法。但是还是好奇，到底有没有O(n)的解法。
还有一道相似题就是inversion count了，就是给个array算在右边比自己大的元素个数
。就是mergesort的变形了，但是好像也没有O(n)的解法，同样空间不限。 |
|
G******i
发帖数: 5226 | 38 ☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Sat Oct 29 00:10:37 2011, 美东) 提到:
**********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You ... 阅读全帖 |
|
i*********7
发帖数: 348 | 39
我怎么觉得两个解法都有点不对劲。。
第一个解法你走一遍给我看看怎么能从1 -1 2这个循环体中得到2 1.
第二个解法感觉上是O(N^2）的算法吧 |
|
n******n
发帖数: 49 | 40 最近骑驴找马，onsite了几家常见的公司，有的已经悲剧。
有些面试官，不置可否，让我心理很没有底。
比如上周四面了狗狗，最后一轮面试官问我generating a random permutation of a
given array. 我答了shuffle算法。面试官似乎不太认可我的解法，问我怎么证明我的
解法对。我问proof或者test, which do you prefer? 他就反说which do you think
is more important. 真不知道他是不是要为难我。说了很多，面试官一直在记录我的
解法，什么feedback都没有。
不知道面霸们大牛们，碰到这种情况怎么处理？看过别人说，为难你的面试官其实最后
说不定让你过，对你nice的可能背后捅你一刀，什么面试不一定要做出来只要思路(我
觉得能秒杀就秒杀。。。)，不太准啊。。。
题目也做了不少了，但是越发觉得一是自己水平还是不够，二是面试不仅是实力运气有
的时候更重要的是说出面试官心里的那个解答让他认同。求bless...T___T |
|
n******n
发帖数: 567 | 41 lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
典型DP解法简单。。。。 |
|
n******n
发帖数: 567 | 42 lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
典型DP解法简单。。。。 |
|
t********e
发帖数: 1169 | 43 不是做理论的，尝试解释一下， 理论大牛别笑
P跟NP是关于决定性问题(Decision problem)的分类， 有些决定性归于p类， 有些归于
np类. 决定性问题就是些回答是yes/no的问题。
关于一个决定性问题， 比如说旅行推销员问题，人们既关心要多久才能”找到“一个
正确解， 也关心给定一种解法， 多久才能”验证“这个解法是否正确。
如果一个决定性问题的正确解可以在多项式时间内“找到”，那就是属于p类问题
如果能够在多项式时间内”验证“一个解法是否是这个决定性问题的正确解， 那就属
于np问题 |
|
c********t
发帖数: 5706 | 44 不错，和那个link解法一样。当然有论文有O(n)解法，看不到。
这个题还真有在interview碰到的。如果要写codes,我觉得还是 n size heap的解法最
容易实现。 |
|
c********t
发帖数: 5706 | 45 响应号召，发中文题
二叉树求两结点间最大路径问题已经有很好解法。
现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
比如：
3
/
4
/ \
1 2
结果为10
请问有什么好的解法？
我有一个笨解法，指数时间复杂度，为了不影响大家做题，会在跟帖贴出。 |
|
b*****s
发帖数: 36 | 46 我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
的master的package。
onsite面经如下：
一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
behavior问题作为开场白。
被问到的算法题如下：
1. 一个string当中，求出现多于一次的最长的substring。
eg: "abcabcaacb" -> "abc"
eg: "aababa" -> "aba"
这题我没有想到最优解，代码也没有写完，也被面试官认可。
2. 整数乘法：multiply(int x, int y)
这题本身虽然简单，但是考虑所有情况bug-free还是不容易
3. 老题：reverse words in a sentence
4. string edit distance的递归解法，我以前只写过DP解法的，经提示写出递归解法
感想&建议：
1. 我被5个人面了8个小时，从早上9点到下午5点，包括45分钟午饭。... 阅读全帖 |
|
R**y
发帖数: 72 | 47 小弟现在正在做Career up 150, 这是我的第一遍，速度很慢，有时一题得做3个小时左
右，审题，自己想，看它的解法，搜网上的解法，再抄一遍书上的解法。一下2-3个小
时就过去了，有时一下午稍微来点事情打扰就只能做一题了，这样一周就2-3章左右。
不知道板上大牛做150，速度如何，有什么好建议没有，谢谢各位了。 |
|
m***k
发帖数: 946 | 48 你的回复里感觉有几处不清楚和错误的地方。
1. “Then the complexity in this case is O(column length * \log(row length))“
假设ColumnLength=m, RowLength=n, 你说的复杂度就是m*log(n)，这其实比堆解法的
复杂度k*log(n)快得多，因为k可以等于n*m/2. 堆解法的复杂度worst case是O(n*m*
log(n)).
2. "this solution's worst case complexity is greater than O(m*n/2)"
这不是很显然的么: O(k*log(n)) = O(n*m*log(n)) > O(M*n).
>>>总结一下：
1. 堆解法，复杂度是k*log(n), worst case (k=m*n/2, median)时，复杂度为O(m*n*
log(n))
2. 间接二分法，复杂度是O(n*log(max-min)). 具体方法是：
(1) 求一个整数x在矩阵中第几大，O(n)
(2) 在[a, b]范围的整数内，找出一... 阅读全帖 |
|
d**e
发帖数: 6098 | 49 ☆─────────────────────────────────────☆
runPython (凸-.- 我挺郭德刚) 于 (Tue Apr 3 12:09:56 2012, 美东) 提到:
也可能做题，但是流程不一样，比如先问一个如何判断binary search tree， 不会，
然后人又很耐心的问其它问题。
☆─────────────────────────────────────☆
Westridge (西岭) 于 (Tue Apr 3 12:19:27 2012, 美东) 提到:
不做码工应该不过这些的，做系统算法的甚至不需要涉及编程
☆─────────────────────────────────────☆
zhaichun108 (onlylonely) 于 (Tue Apr 3 12:34:02 2012, 美东) 提到:
做不了research， 进不了学术界的fresh phd能比小硕小本编程强吗？
不能的话考你一下做题有什么问题吗
☆─────────────────────────────────────☆
... 阅读全帖 |
|
l*****a
发帖数: 559 | 50 第二题leetcode上只给出了nlgn的解法。lgn的解法是如何得到的？
第一题有lgn的解法，不过嫌复杂被放弃掉了。 |
|
