n****e
发帖数: 629 | 1 Fibonacci Q-Matrix
参见小尾羊大拿的日记经验 |
|
c*****o
发帖数: 178 | 2 这个马的规则好像不对，有8种可能。至于方法我也是这么想的，但是原文里面提示用
Fibonacci数列，我不太明白。 |
|
n******h
发帖数: 50 | 3 well. the possibilities for each grid near the piece follow the binomial
form of Fibonacci series. check that out. |
|
l**n
发帖数: 88 | 4 前面的帖子说用fibonacci数列，但是没怎么搞明白
两个玩家， 一堆石头，假设多于100块, 两人依次拿， 最后拿光者赢， 规则是
1. 第一个人不能一次拿光所有的
2. 第一次拿了之后， 每人每次最多只能拿对方前一次拿的数目的两倍
求先拿者必胜策略, 如果有的话 |
|
l******o
发帖数: 144 | 5 哦, 我确实忽略了一个地方. 看来应该是fibonacci没错.
1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个， 必然让对手先面对8的情况
事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n |
|
l******o
发帖数: 144 | 6 很好奇, 如果把2倍改成3倍, 结果会是怎么样的?
哦, 我确实忽略了一个地方. 看来应该是fibonacci没错.
1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个， 必然让对手先面对8的情况
事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n |
|
D*C
发帖数: 97 | 7 试着做了一下，不确定对不对。。。
因为时间也满足f(n)=f(n-1)+f(n-2).那么f(n)/f(n-1)=1+f(n-2)/f(n-1)
令 a(n)=f(n)/f(n-1)那么有a(n)=1+1/a(n-1)求极限得到a(n)=(1+sqrt(5))/2
所以F(n+1)要162s
long |
|
|
b***e
发帖数: 1419 | 9 T(n) = T(n-1) + T(n-2) + 1
Let f(n) = T(n) + 1, we have:
f(n) = f(n-1) + f(n-2). This is just fib, where:
f(n) = 1.618^n + 0.618^n
So when n is large:
T(n+1) = f(n) - 1
= 1.618 * f(n-1) - 1
= 1.618 * (T(n) + 1) - 1
= 1.618 * 101 - 1
= 162.42
long |
|
r**u
发帖数: 1567 | 10 30分钟，全部都是最近版上出现的题，resume一点没问。问了个fibonacci，iterative
and recursive implementation, which one is more costly。
只有一轮phone screen，好简单，然后就on-site，貌似招很多人，同志们抓住机会。
我犯了俩个愚蠢的错误，move on. Good luck! |
|
l**3
发帖数: 45 | 11 一个小时
问了些简单的oop问题，polymorphism什么的，还有些behavior问题。
让写一个fibonacci函数，念给他听。
经典的家具设计问题。以前没好好想过，wood chair, steel chair, wood table,
steel table。怎么设计类，使得添加新的家具和材料更容易。比如说要加plastic
desk，wood bookcase什么的。同时要提供测试接口，比如是否着火，最大承重什么的。
有牛人知道怎么复习这类design问题吗？使劲看design pattern也不知道怎么用到具体
的设计里。 |
|
a********1
发帖数: 750 | 12 heap只是优先队列的数据结构，怎么实现可以自己去实现，比如fibonacci heap 通常
就不用数组 |
|
a****x
发帖数: 89 | 13 刚面完，recruiter面的，和大家面的题基本一样
1. what's your most challenging problem in your projects?
2. (following 1)what you could do better, if you could go back?
3. what's your preference on position?
4. Fibonacci coding.(recursive and iterative, difference)
5. test a calculator.
6. find a candidate's phone number knowing only first name, last name,
school and email.
7. which group you would like to work most? |
|
I**********s
发帖数: 441 | 14 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
w***9
发帖数: 13 | 15 我master做的安全方向，因此面的security组。
一面(感觉一面整个是在考察计算机安全的背景知识)：
1.为什么选择amazon; 2. what's ur favorite vulnerability? 我说了缓冲区溢出和
分布式DOS攻击，然后他就要我都详细都展开说（包括原理，哪些预防措施等等）；3.
what's hash function？我问是普通CS说的哈希还是密码学里的哈希，他就要求我都展
开说，重点说密码学的哈希。4.他问我对在linux/unix里写程序熟吗，我说还成，然后
他其实想叫展开说说segfault。5. 问我对网络熟悉不，我只能问哪个方面，然后他叫
我说说TCP和ICMP，还问得比较细。后来好像还问了一下paging的东西，我没怎么答上
来。
二面（相比于一面，这个就很general）
问了一些OOP的概念，叫写了一个fibonacci数列的代码，叫设计一个virtual animal
kingdom，然后问了一个在一堆HTML文件里找电话号码的题。另外的时间就是问了下我
的background等。
很幸运拿到了onsite，约了月底。因为方向对口 |
|
D***h
发帖数: 183 | 16 很强。
bless!
我master做的安全方向，因此面的security组。
一面(感觉一面整个是在考察计算机安全的背景知识)：
1.为什么选择amazon; 2. what's ur favorite vulnerability? 我说了缓冲区溢出和
分布式DOS攻击，然后他就要我都详细都展开说（包括原理，哪些预防措施等等）；3.
what's hash function？我问是普通CS说的哈希还是密码学里的哈希，他就要求我都展
开说，重点说密码学的哈希。4.他问我对在linux/unix里写程序熟吗，我说还成，然后
他其实想叫展开说说segfault。5. 问我对网络熟悉不，我只能问哪个方面，然后他叫
我说说TCP和ICMP，还问得比较细。后来好像还问了一下paging的东西，我没怎么答上
来。
二面（相比于一面，这个就很general）
问了一些OOP的概念，叫写了一个fibonacci数列的代码，叫设计一个virtual animal
kingdom，然后问了一个在一堆HTML文件里找电话号码的题。另外的时间就是问了下我
的background等。
很幸运拿到了onsite |
|
j**l
发帖数: 2911 | 17 递归版本没让写，但我知道tail recursion, 编译器实际会把它优化为循环。
算阶乘和Fibonacci数列都可以用尾递归，引入一个累乘器和累加器参数。链表逆置用
递归也可以再引入一个参数来实现尾递归 |
|
f*****y
发帖数: 444 | 18 fibonacci 利用中间结果解很方便
// find a fib number that is just less then n
long found_fib(long n)
{
long a,b,temp;
a = 0;
b = 1;
while (b < n)
{
// a,b -> b, a+b
cout << b << " ";
temp = b;
b += a;
a = temp;
}
return a;
} |
|
f*****y
发帖数: 444 | 19 fibonacci 利用中间结果解很方便
// find a fib number that is just less then n
long found_fib(long n)
{
long a,b,temp;
a = 0;
b = 1;
while (b < n)
{
// a,b -> b, a+b
cout << b << " ";
temp = b;
b += a;
a = temp;
}
return a;
} |
|
A********l
发帖数: 184 | 20 网上扔的简历，一周后recruiter来电话约了电话面试。
hiring manager打来电话，问了简历上的问题，比较简单。然后问了一个简单的题目:
如何找出apache weblog中访问最多的几个url。用linux shell如何实现，用java如何实现。
过几天另一个组的hiring manager也来电话，聊了聊，比较开心。
几天后约了onsite，见了10个人，每次两个人。问题都比较简单。
round 1:
hiring manager 1， 聊天，很开心。
round 2:
一个在akamai干了11年的老年软工
2.1 设计course registration的数据库schema
2.2 Fibonacci递归和非递归实现
2.3 三个盒子，一个装的全是白旗子，一个全是黑棋子，一个是混合，但是所有的
label都是错误的，你可以从盒子中draw几个棋子。如何纠正盒子的label，同时保证
draw的次数最少
2.4 两个dice，如何label，使得他们的可以表示01-31中的所有数字
round 3：
两个老年软工:
3.1 聊天
3.2 程序找错，一个计算两个集 |
|
j**l
发帖数: 2911 | 21 需要你用bit操作给出O(log N)的算法吧，也可用来结合矩阵乘来求Fibonacci数列 |
|
s****a
发帖数: 528 | 22 NUANCE的，我做了3天，给出的解法据面试的说是最好的，为此拿到OFFER
做的不比我差的可以拿20个包子，欢迎讨论
下礼拜给答案
The Fibonacci palindrome problem |
|
q******8
发帖数: 848 | 23 上来先是说了说简历。然后直入主题，写出fibonacci两种实现，给出复杂度。瞬间完
事。然后出了道算法。给一个matrix，每个element给的值代表高度。问这个matrix能
撑多少水。给出算法。不要求程序实现。比如3×3的矩阵，最外一圈都是3，然后中间
一个元素是0，那么这个矩阵可以撑3个单位的水。 |
|
v*****u
发帖数: 406 | 24 1.统计问题：
[0,1], random generator gives even distributed number (x).
how to get a linear distributed series (y), such that the probability
of 0
is 1, and the probability of 1 is 0. (that is, p(y) = 1-y)。
2.Fibonacci 序列，要求精确到小数点后8位精度。怎么样精确到后8位呢？ |
|
d**f
发帖数: 264 | 25 死在第二次电面上,没有准备好
题都很常见
1.whether an int is power of two?
2.non-recursion Fibonacci serials.
3.count how many words in a string?
4.ransom notes
5.design a restaurant reservation system.
1.design a stack, push(), pop() and max() in O(1)
2.union two sorted int array
3.design a least recently used (LRU) cache systems. All operation in O(1). |
|
x****k
发帖数: 2932 | 26 一家IB的Analytics developer的onsite，只记得部分题目，一些比较简单的题目就不
写了。括号后是我认为的答案或者提示。
1. write a iterative function to calculate fibonacci sequence
2. what is the difference of Delete table and truncat table.(about sql &
database)
3. what is ACID.(about sql or database)
4. write a find() for BST, How to decide the element could not be found.((
less than && No left child) || (large than && no right child))
5. how to reverse a link list using one point
(should I use recursive calling)
6. find the sizeof(int) wit... 阅读全帖 |
|
g*********s
发帖数: 1782 | 27 能O(1)输出max必须要用堆吧？Fibonacci heap？ |
|
k*p
发帖数: 1526 | 28 cong!
昨天和组里很nice的中国人电面了一下，今天拿到了intern的机会，第一个intern阿=0
=内牛满面
发包子！按Fibonacci number发=0= |
|
j****1
发帖数: 15497 | 29 Fibonacci number? what is that?
Thanks
=0 |
|
H***3
发帖数: 87 | 30 re, hehe, 赞Fibonacci number
=0 |
|
g*********s
发帖数: 1782 | 31 来自主题: JobHunting版 - fb 面经 the problem in the phone is dp, just like Fibonacci?
2, 5, 6 are all classical.
4, i know little about web, so no comments. :)
1, i'm not sure about what rule the pattern follows. can u elaborate it?
3, in case of 2-color only, partition() in quicksort()? so for 3-color
case, u treat two colors as the same first, then distinguish them in the
2nd pass. avg time is O(N) while space O(1). is this good enough?
.)
.
running time
太
种,
然后 |
|
M7
发帖数: 219 | 32
2)
复杂度上差远了。static variable的方法其实就是loop的方法。而用递归的方法的复
杂度
就恐怖了。
30
是这样。这里复杂度没有区别。所以考的是技巧。 |
|
g*********s
发帖数: 1782 | 33
那用全局变量也一样吧。线程安全性有问题。
这个技巧有什么用呢？针对某些不方便提供辅助数据结构的语言如Scheme和Haskell？
觉得Amazon这种题都挺偏的。 |
|
j********x
发帖数: 2330 | 34 啥意思，不用loop 用递归，但是又不许递归？。。。 |
|
M7
发帖数: 219 | 35 I don't know. You may ask your interviewer about that. :)
For most positions, interviewers are not interested in Lisp/Prolog kind of
languages at all. One of the interviewers told me "Use any language, but no
lisp...." |
|
j*****u
发帖数: 1133 | 36 说实话这个题太没意思了，比用stack写queue还无聊。。
不知道这样写满不满足他的要求(不用全局变量)
int Fib(int n, int a, int b)
{
return n <= 1 ? b : Fib(n - 1, b, a + b);
}
wrapper function call的时候Fib(n, 1, 1);
2)
30 |
|
g*********s
发帖数: 1782 | 37 我在想栈模拟队列那个大概也有背景？比如远古时代的机器硬件底层只有栈…… |
|
w*z
发帖数: 75 | 38 第一个就是用递归实现循环的意思吧
#include
int a = 1;
int b = 1;
bool first = true;
void f(n) { // print all fib nums <= n in normal order, n >= 1
if (first){
cout<
first = false;
}
int c = a + b;
if (c > n)
return;
cout<
a = b;
b = c;
f(n);
}
2)
30 |
|
o****u
发帖数: 714 | 39 python code
a = 1
b = 1
def f(a,b,i):
if i == 10:
return
a = a + b
print a
f(b,a,i+1)
print a
print b
f(a,b,1)
def f2(a,b,i):
if i == 10:
return
a = a + b
f2(b, a, i+1)
print a
print ' '
f2(a,b,1)
print a
print b
2)
30 |
|
P********l
发帖数: 452 | 40 1. Reverse print the sequence
Because f(n)=f(n-1)+fn(-2), we have f(n-2)=f(n)-f(n-1). We just needs two
numbers and back trace to f(0). In the process, no new variables are needed.
2. top down dynamic programming
f(n)=f(n-1)+f(n-2) is not allowed, but f(n)=f[n-1]+f[n-2] is allowed.
check
http://www.sureinterview.com/shwqst/123005
Also try a search there to see if the question has an answer. |
|
E**h
发帖数: 6 | 41 void Print_Fibonacci_Reverse(uint32_t n)
{
static uint32_t n0 = 0;
static uint32_t n1 = 1;
if (0 == n)
{
cout << n0 << endl;
return;
}
if (1 == n)
{
cout << n1 << endl;
cout << n0 << endl;
return;
}
uint32_t result = n1 + n0;
n0 = n1;
n1 = result;
Print_Fibonacci_Reverse(n - 1);
result = n1 - n0;
n1 = n0;
n0 = result;
cout << result << endl;
return;
} |
|
c******n
发帖数: 4965 | 42 rather simple ah
first get
Fn. Fn-1.
then while I > 0
temp = fn-1
fn-1 = fn - fn-1
fn = temp
I -- |
|
m****v
发帖数: 84 | 43 很可能会有一个在Palo Alto的实习机会，公司愿意给房子住两人间，或者给点钱自己
找。如果自己
找的话，可能会有交通不便、租金贵等问题，但是会自由很多。请问大家觉得哪个选择
比较合适呢。
谢谢。
同时在此汇报碰到过的面试题若干（来自不同公司的面试环节），抱歉之前没有整理过
，如果有时间
会把它们整理好再发一下。
算法、数据结构：
Prefix Tree
Kth element
BST serialization
quicksort
heap, heapsort
M links, find the Kth element
判断二叉树合法
按层打印二叉树
矩阵找最大和子矩阵
设计：
任务管理
交通系统
语言：
dynamic_cast, static_cast, ...
virtual function
exception in destructor
malloc, dealloc
polymorphism
regex in perl/python/etc.
数学、概率：
Monte Carlo: give an example and explain
Fibonacci series... 阅读全帖 |
|
|
f*****w
发帖数: 2602 | 45
Fibonacci ?
没很明白 难道用两个stack 全倒出来一遍？
heuristic, 就number of different chars 好了 |
|
c******w
发帖数: 102 | 46 第一题就是Fibonacci数列。 比如你当前要求走到第n级楼梯的走法F(n), 那么你需要
完成知道走到n-1和n-2级的走法 F（n-1）和F（n-2）。 也就是F（n） = F（n-1） +
F（n-2）。 |
|
g*********s
发帖数: 1782 | 47
classical. Fibonacci.
classical
bfs + greedy as someone mentioned earlier. this is actually a*. |
|
e***l
发帖数: 710 | 48 这是从1开始的Fibonacci，F(n)可以直接算出来
F(n)=(a^(n+1)-b^(n+1))/sqrt(5)
where a=(1+sqrt(5))/2, b=(1-sqrt(5))/2 |
|
n********5
发帖数: 323 | 49 只有几个月工作经验 fresh graduate。。。骑驴找马一段时间了。。。
星期五的onsite，,,, 二三十人做web 的startup，，开放式的环境。。。感觉不错。
。。
面试分5个session，前面两个是两个面试官一组的technical session..后面分别是
product VP，engineering VP，CEO
简单说一下technical 的题目吧。
给一个string/stream,, 顺序是 [1,2,1,3,3,1,....]，不能放入memory，要求输出[1,
1,1..2,2...3,3....]，开始想歪了，，其实直接one way go through, count the
integer and print it out.
接着写个变形的fibonacci,只是if n ==0 , value = 2.
如何random shuffle 52 cards，如何做到random。open-end question. I try to do
the in place switch and get a the random number f... 阅读全帖 |
|
R***i
发帖数: 78 | 50 第一轮
1. 很多java概念和解释
2. 很简单的算法，具体忘了，任何一个CS大一学生都会写的那种，主要考察boundary
cases和exception handling
3. OOD, clothing store
第二轮
1. is binary tree BST，写两种解法，念code
2. efficient recursive way to compute Fibonacci number 念code
还没订好去西雅图的时间。。。虽然已有小公司的保底offer，但已被各大公司鄙视很
多次了，这次就让我成了吧。。。。 |
|
