|
|
|
|
|
|
l*****a
发帖数: 14598 | 7 fibonacci serials
有个著名的log2n算法
不过我觉得面世中回答那个或者面试者要求那个
的话
真是无聊 |
|
b****n
发帖数: 464 | 8 生物phd，纯计算的实验室，当年被生物奥赛忽悠，鄙视cs，一心觉得只有生物学才推
动人类社会向前进，后来如愿上了dream school dream系 以后，发现自己paper看不
进去， seminar听不进去，懒得想问题，另外手残得不行，非常毛躁，常常毁了样品或
者洒了试剂，继续做实验科学，幸福感低就不提了，迟早慢性把自己害死。不过话说回
来，生物这个学科是不需要鄙视的，我的同学里面，做得好的，乐在其中的，也大有人
在，只是对我这个个体而言，是走错路了。于是申phd的时候，决定改做计算。做着做
着发现非常喜欢能把东西做出来，别人还能用的感觉，所以就打算以后找码工的工作了。
无奈选校选老板的时候，都不是非常明智，以至于后来转行的路可用资源很少，全靠自
己打拼。
以上只是一些感慨，以下是找工作相关。
－－－－－
phd阶段做过的主要projects之一是生物方向的web applications，也做了一些machine
learning的皮毛。一开始找工作非常积极也非常desperate，各大网站每天刷新cv，找
人推荐，蹭隔壁学校的career service。不过题目练得很少，基... 阅读全帖 |
|
h**o
发帖数: 548 | 9 好吧，就是说哪章都会考，连Fibonacci Heaps，binomial heap...?
抱歉，我对于什么是基本点，什么不是没什么概念。 |
|
s*****n
发帖数: 162 | 10 Suppose you are developing a search engineer. Given a sequence of
numbers as a query string. You need to design algorithm/data structure such
that it can return whether this number sequence belongs to some famous
number sequences. For example, if the query string is “0 1 1 2 3 5”, it
might belong to a Fibonacci sequence. Note that the given sequence may not
always start from the beginning of a known number sequence.
My idea:
For those "famous" number sequences, we may cut them into smaller seque... 阅读全帖 |
|
b*****o
发帖数: 715 | 11 iteration != recursion.
Take a very simple example of computing Fibonacci array:
(1) This is recursion, but NOT DP:
int fib(int n) {
if (n <= 2) {
return 1;
}
return fib(n-1) + fib(n-2);
}
(2) This is DP:
int fib_dp(int n) {
int a = 1;
int b = 1;
int sum;
for (int i=0;i
sum = a + b;
a = b;
b = sum;
}
return sum;
}
stored |
|
l*******b
发帖数: 2586 | 12 嗯，functional里面的lazy evaluation sequence不知道怎么实现的．这个和
memorization有点像吧，像fibonacci数列那样的．不知道是bottom up的实现还是top
down的实现，bottom up貌似不需要stack 调用，top down就是递归了，当然这个例子
两个是等价的可以互相转化，可以写成尾递归的形式．一般的就不知道了．看看那位大
牛讲讲 |
|
g*****e
发帖数: 64 | 13 来自主题: JobHunting版 - 发Q家面经 此Q非彼Q。最近看到几个贴面Quantcast，就想把之前的面经发上来，SE职位。因为自
己面试前，
看到大家真诚的发面经，很有用很感激，所以也想发上来造福大家，攒人品。
1. HR，就是简单了解下情况，聊聊职位，面试流程。他家的hr很好，反应都很快。
2. Coding test。题目记不住了，和calculator有关，要用到的知识点是toplogical
sort，使用stack进行postfix expression的计算。没记错的话是两个小时，但是hr会
提前一个小时用邮件发过来。
3. Tech电面。简历+two sum。
4. HM聊组里情况，了解你。
5. Onsite
a. 组员, 两道题。careercup递归换钱题，只用stack排序题。
b. 组员，两道题。如何判断两棵bt相同，另一个记不清了，解法是bt的bfs。
c. HM，介绍组里的技术细节，好像没出题。我就傻傻的听，当时第一次onsite，
以为可以用这段时间休息。现在才知道，这里也可能是考察你问问题的水平呀。虽然问
出来一个好问题，但肯定狠狠不足。他画了好大一张图，当时脑袋很累了... 阅读全帖 |
|
c********t
发帖数: 5706 | 14 来自主题: JobHunting版 - 发Q家面经 b. 组员，两道题。如何判断两棵bt相同，另一个记不清了，解法是bt的bfs。
这道题不能 比较pre-order 和 in-order吗？
然后一道题，是factorial还是
fibonacci来着，先问计算f*(n)的time complexity，我答是O(n)，然后问如果求k个f*
值，怎么做的O(k+n)。其实就是iterative，维护一个f*(n)的数组，lazy computation
为什么是O(k+n)而不是O(n)
比如下面这样写（也可以写iteration）
int f(n){
a[n]=n*f(n-1);
return a[n];
}
不是O(n)吗？
，维护一个当前计算过的最大n的variable。 |
|
w***g
发帖数: 5958 | 15 【 以下文字转载自 Programming 讨论区 】
发信人: wdong (cybra), 信区: Programming
标 题: 算法导论重点
发信站: BBS 未名空间站 (Mon Oct 15 17:15:36 2012, 美东)
上次在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) 这个是具体的实现方法，可以和... 阅读全帖 |
|
c******t
发帖数: 391 | 16 请教第一题检测Fibonacci数列，题目是要求数列都是从1开始么？比如3,5,8,13这个算
么？ |
|
w**********4
发帖数: 157 | 17 是第一面，招的组是用户服务组。
第一个问题是问对数据结构的了解，熟悉哪些数据结构，然后给了一个场景是有一个网
站，现在要统计目前登录的人数，用户登录，将新用户添加，用户离开，将用户删除，
还可以将所以用户以字母顺序打印出来，请问选用什么数据结构可以有效的支持这些操
作，然后每个操作的时间复杂度是多少？
第二个题目就是一个老题，fibonacci 序列，写代码，然后把代码都给面试官听，然后
分析时间复杂度。 |
|
d**e
发帖数: 6098 | 18 ☆─────────────────────────────────────☆
beelin (beelin) 于 (Sat May 5 18:24:57 2012, 美东) 提到:
生物phd，纯计算的实验室，当年被生物奥赛忽悠，鄙视cs，一心觉得只有生物学才推
动人类社会向前进，后来发现自己paper看不进去， seminar听不进去，懒得想问题，
另外手残得不行，非常毛躁，常常毁了样品或者洒了试剂，继续做实验科学，幸福感低
就不提了，迟早慢性把自己害死。不过话说回来，生物这个学科是不需要鄙视的，我的
同学里面，做得好的，乐在其中的，也大有人在，只是对我这个个体而言，是走错路了。
于是申phd的时候，决定改做计算。做着做着发现非常喜欢能把东西做出来，别人还能
用的感觉，所以就打算以后找码工的工作了。无奈phd学校的限制，转行的路可用资源
很少，全靠自己打拼。
以上只是一些感慨，以下是找工作相关。
－－－－－
phd阶段做过的主要projects之一是生物方向的web applications，也做了一些machine
learning的皮毛。一开始找工作非常积极也非常d... 阅读全帖 |
|
h*******e
发帖数: 1377 | 19 收藏 fibonacci log n 算法。。。 |
|
O******i
发帖数: 269 | 20 和一个美国人吧。给一个矩阵和一个数k，要算另外一个矩阵。新的矩阵的每个位置是
老矩阵里面每个对应位置位中心边长为k的小矩阵的平均。用DP算法可以做到N^2。然后
实现这个算法。写了三个函数。
在火车上睡觉的时候想了个解法，不知道对不对。
这个题的背景实际上是二维数字图像处理的卷积滤波。这里是求平均，也可以求最大，
最小以及median, 其实也就是二维的离散拉普拉斯算符。
其实可以先考虑一维的情形。难点是如何用空间换时间，不需要每次都对k个数都重新
求和。对一维数组A, 如果构造辅助数组B, 使得
B[j] = A[0] + A[1] + ... A[j]
则A[m] + A[m + 1] + ... + A[m + k - 1] = B[m + k - 1] - B[m - 1]，可以O(1)时
间求得，而不用O(k)。
构造B的过程是DP, 类似Fibonacci的DP构造。
扩展到二维也是一样的，二维数组B每个元素的值，是二维数组A的左上顶点元素到右下
和B那个元素位置对应元素的子矩阵的和。
构造B的过程也是DP, 只是递归方程比一维情形稍微复杂些，是两个矩阵相加，减去相
交部分... 阅读全帖 |
|
c***p
发帖数: 221 | 21 转自
http://www.cnblogs.com/figure9/archive/2013/01/09/2853649.html
9个offer，12家公司，35场面试，从微软到谷歌，应届计算机毕业生的2012求职之路
1，简介
毕业答辩搞定，总算可以闲一段时间，把这段求职经历写出来，也作为之前三个半月的
求职的回顾。
首先说说我拿到的offer情况：
微软，3面->终面，搞定
百度，3面->终面，口头offer
搜狗，2面，悲剧
腾讯，1面，悲剧
布丁移动，3面，搞定
涂鸦游戏，3面，搞定
友盟，3面->CEO面，搞定
雅虎，4面->终面，搞定
微策略，2面，悲剧
人民搜索，3面->终面，搞定
人人，2面+终面+Special面，搞定
Google，7面，搞定
求职经历分为定位、准备、简历、笔试和面试这五个部分，大家挑感兴趣的看就成。
我的求职经历适用但不限于码农，不适用与企事业单位（据说是完全不同的考察标准和
流程）。废话比较多，大家耐心忍受，有什么问题可以跟帖提问。
2，定位
教育经历：本科在大连某工科院校，由于GPA比较惨烈+挂科，所以没保成研，毕业后修
了一年英语双学位，然... 阅读全帖 |
|
|
x******a
发帖数: 6336 | 23 is it the same as fibonacci?
#(fireman)= #(eman)+#(man) |
|
L******t
发帖数: 1985 | 24 做网络的大公司，在加州湾区，做data center switch的。有好几个位置，需要几年工
作经验。结果过来的简历都是老印。
上周面试了一个Tellabs过来的女老印，印度本科，有7年工作经验。谈吐不错（绝大部
分老印都如此）。问概念问题回答得很不错，确实做过相关工作。但一到编程让人大跌
眼镜！问了她几道C的题目：
bitmap操作，给一个index，写code set/unset 1 bit。几经提醒20分钟才搞对。
int *p = 0x1000, p+1 = ? 初始答案是0x1032
Fibonacci sequence，写出recursive and non-recursive的函数。non-recursive的写
不出来。
据说binary tree遍历写的不错，估计练过。
最后5个feedback，2个average，3个above average。要了。估计她起薪10万左右。
如果你觉得你有相关背景、编程比这位强、感兴趣，站内给我发信附上你简历的链接。
如果合适我会转发给hiring manager。不保证回复你（如果邮件太多的话）。
注：Fresh graduda... 阅读全帖 |
|
c********t
发帖数: 5706 | 25 都要了还怎么可能找别人。你咋不给过big neg呢？Fibonacci 能写出recursive，却不
能写出iteration 。。。。。。都要了。。。。。。。
记得justty写出quad tree都被拒了。老中，特别是男老中命苦啊！ |
|
i******r
发帖数: 793 | 26 fibonacci写不出确实有点。。。
不过这样的水平都拿10万offer了啊@_@ |
|
v*******e
发帖数: 326 | 27 fibonacci 不是要一层层下来剥吗？怎么会规模相当？ |
|
h******d
发帖数: 6 | 28 一直看本版，很多知识在找工作的过程中都用到了。现在找工作告一段落，奉献一下我
的面经回馈版上的同志们。
先贴Amazon的。感觉他们家考的知识面挺广，而且被问到了behavioral question。
上题目。
电面1：
1。如何判断一个byte有几个bit
2。判断一个整数中有几个bit为1，写代码
3。问一堆OO概念，比较forward & delegation, composition & aggregation, 继承，
多态，虚函数，等等
4。如何用树来实现STL map
5。如何找到一个文件夹下面所有的电话号码，写linux command
6。计算the nth fibonacci number， 写代码
followup: 如果输入的n不合法，比如输入负数，应该如何处理。是应该使用特殊的返
回值，还是抛出异常。比较两者
电面2：
1。hash如何解决collision. 插入操作的最佳，最差和平均时间复杂度
2。计算中序表达式的值。支持+,-,*,/,(,). 写代码
3。给一个log文件，包含n条记录。n是一个很大的未知数。如何随机选出k条记录
Onsite：
in... 阅读全帖 |
|
o****d
发帖数: 2835 | 29 why it is O(N+K)
do you mean the amortized complexity?
I understand that if it the heap is implemented as a Fibonacci heap, the
complexity of insert is amortized O(1), extract can also O(1) |
|
G****A
发帖数: 4160 | 30 我觉得对于IT公司面试，Fibonacci的题目应该不用考虑matrix-based approach。
onsite |
|
a***r
发帖数: 93 | 31
My implementation is based on BinaryHeap,insert's worst-case cost is O(logN)
Fibonacci Heap's insert amortized cost is O(1)
which C++ document are you referring to? |
|
A**u
发帖数: 2458 | 32 Industry experience with C++ and BOOST
Proficient in template and preprocessor metaprogramming techniques.
Understanding of modern CPU cache hierarchies and their impact on software
performance.
Software profiling and optimization experience
Test case and unit test development experience
Knowledge of advanced data structures like B-trees, binomial and fibonacci
heaps, AVL/Red Black trees, Splay Trees, Skip Lists, tries etc.
Able to recognize and code dynamic programming solutions, good knowledge... 阅读全帖 |
|
s*********s
发帖数: 318 | 33 来自主题: JobHunting版 - A家面试题 看来最近看题有进步。
给定word和100多个元素,对word做DFS search.返回第一条到底的path或空。
如果元素是1或2个letters.worst search space好像是fibonacci(len(word)). |
|
G****A
发帖数: 4160 | 34 都是大家熟悉的题
Q1, nth Fibonacci number. 要求尽可能多的解法。
follow-up, 每种解法的time/space complexity (要求function call的stack
overhead也看做space complexity).
Q2: c++基本概念。static, reference vs pointer, what is OOD, ...
Q3：列举并比较你常用的几种design patterns的作用和特点。
Q4: tree traversal, 要求level by level,按从底向上的顺序。同个level从左到右。
当我说要用DFS实现print by level的时候，此senior engineer先说“How could you
possibly print in level-order using DFS?”
解释完之后，senior engineer说：“ In the worst case, this will have
quadratic run time (if the tree is unbalanced)... 阅读全帖 |
|
k***u
发帖数: 46 | 35 非热门小startup，题目可以拿来练练，前3题是online coding test，后3题是电面
1 Longest palindrome string of a given string
2 Find the smallest prime Fibonacci number X larger than n, output the
sum of the prime divisors of X+1
3 Given an array of integers, find the number of subsets where the largest
number is the sum of the remaining numbers.
4.Return the output as a string containing the first occurrence of each
character in a given string
5.Given an input string containing spaces and a width, return an output
string o... 阅读全帖 |
|
u*****o
发帖数: 1224 | 36 来自主题: JobHunting版 - 发T家面经 Fibonacci这道题真是变化多端防不胜防。。。 |
|
p*****3
发帖数: 488 | 37 "要求打印出前n个fibonacci数。我一想这个简
单呀，但是美眉要求用recursive写。我吭哧吭哧写了几行，发现自己水平有限， get
stuck了" |
|
r*********n
发帖数: 4553 | 38 尝试写一下O(logN)的Fibonacci吧 |
|
d****3
发帖数: 123 | 39 让我写一个calculate the nth number in fibonacci sequence的函数：
我给出了一个非递归版本，
public static int fibnacci_M(int i) {
if (i<=2) {
return 1;
} else {
int[] value = {1,1};
int sum = 0;
while (i>2) {
sum = value[0] + value[1];
value[1] = value[0];
value[0] = sum;
i--;
}
return sum;
}
}
然后他问我如果用递归复杂度多少。之后为我这个函数能不能马上deploy到Server上,
然后can this functio... 阅读全帖 |
|
u*****o
发帖数: 1224 | 40 这题太可怕了..
我要是碰到了FIBONACCI肯定笑开花。。没想到后面隐藏着这么多陷阱。。
真是很傻很天真。。 |
|
v********n
发帖数: 18 | 41 nmark.... 同觉得自己图森破n【在 dy0953 (dy0953)的大作中提到：】n：让我写一个
calculate the nth number in fibonacci sequence的函数：n：n：我给出了一个非递
归版本，n：public static int fibnacci_M(int i) {n： if (i<=2) {n：
return 1;n： } else {n……nn--n[发自未名空间Android客户端] |
|
p****n
发帖数: 69 | 42 最近面了一些矿工/码工的职位，结果都是惨败而归。感觉好多时候都已经走到了最后
一步，结果还是失败了，实力和运气总有一样差那么一点点。今天把一些不太常见的题
发出来，希望对大家有帮助。同时也为今天的面试求祝福，发40个包子。
1. Generate Fibonacci number without iteration and recursion
2. Given two functions
vector has_ID(thread_id) // give a thread_id, return all locks it
currently has
vector want_ID(thread_id) // give a thread_id, return all locks it
is waiting
and a set of thread_ids, how do you determine if there is a deadlock in the
system
3. Complexity of solving a system of linear e... 阅读全帖 |
|
u*****o
发帖数: 1224 | 43 BLESS!!
1. Generate Fibonacci number without iteration and recursion
这个用matrix multiplication吗？O(logn) |
|
g****o
发帖数: 547 | 44 bless!
Fibonacci number这题怎么做？
就算用通项公式，矩阵乘法之类的做法也要iteration啊 |
|
v********n
发帖数: 18 | 45 nmark n【在 ponpon (ponpon)的大作中提到：】n：最近面了一些矿工/码工的职位，
结果都是惨败而归。感觉好多时候都已经走到了最后n：一步，结果还是失败了，实力
和运气总有一样差那么一点点。今天把一些不太常见的题发出来，希望对大家有帮助。
同时也为今天的面试求祝福，发40个包子。n：n：n：1. Generate Fibonacci number
without iteration and recursionn：n：n……nn--n[发自未名空间Android客户端] |
|
i****y
发帖数: 84 | 46 我写了个循环，请问这个是dp吗？
num[0]=1;
for(int n =0; n
if(num[n]==0)continue;
if(n+1
num[n+1]+=num[n];
if(n+2
num[n+2]+=num[n];
}
return num[num.length-1]; |
|
|
i****y
发帖数: 84 | 48 存量个数，互相存是不是更浪费时间，我要做两次加法，是不是很慢？ |
|
|
s*w
发帖数: 729 | 50 第一次看人把 fibo 写成这样子
有啥好处？ |
|
