|
s*w
发帖数: 729 | 2 那个所谓的解析表达也是要算 raised to the power of n, 不是 O(1) |
|
|
r*********n
发帖数: 4553 | 4 不行，因为你要考虑到表达式里面的irrational number，只能用floating number来近
似，然后还要求n此幂，各种over flow，最后还要cut off回整形，很难得到正确的答
案。 |
|
|
h**6
发帖数: 4160 | 6 全都跑题了，我来说一下吧。
楼主没有给num数组赋初值，循环内第一行continue应该删除。 |
|
l*****t
发帖数: 2019 | 7 什么意思？
数学表达是不就是什么根号5还是黄金分割什么的。根本不用loop,一个expression搞定。 |
|
g****o
发帖数: 547 | 8 需要计算什么根号5的n次方啊
问题在于这个运算的复杂度是o(lgn)还是o(1)
定。 |
|
c********p
发帖数: 1969 | 9 这题目到底有多少解法啊。。。
请教一下这个非recursion非iteration的解法是神马啊！ |
|
x***4
发帖数: 1815 | 10 http://en.wikipedia.org/wiki/Fibonacci_number
Under the section of Matrix Form:
F_n = .....
Of course, I do not think a code farmer interview will ask for this formula.
Maybe the interviewer is looking for something else.
Good luck with your interview. |
|
c********p
发帖数: 1969 | 11 就是前几天在版上看谁的面经里提到的。。
formula. |
|
k**********y
发帖数: 20 | 12 用那个根号的公式，但是计算大数字时候有问题的。因为IEEE的浮点就是狗啊！！！！
！！ |
|
|
|
i******t
发帖数: 22541 | 15 f(n) = f(n-1)+f(n-2)
所以总共树的高度是 n , 每i层的节点数 2^i
所以总共节点数 2^0 + 2^1 +... +2^n >2^n
所以
错略复杂度是 THETA(2^n)
？
所以是 np-hard 问题？ |
|
a*****u
发帖数: 1712 | 16 复杂度是O(n)
念order of，不是theta
Np-hard好像也不是你说的那样定义的
★ 发自iPhone App: ChineseWeb 7.8 |
|
i******t
发帖数: 22541 | 17 O(n) 是 big O啊 还有个 Theta啊 |
|
a*****u
发帖数: 1712 | 18 theta是什么？上下限吗？一般面试big O就行了吧，不需要上下限吧
★ 发自iPhone App: ChineseWeb 7.8 |
|
i******t
发帖数: 22541 | 19 一个是 big O 还有个 sigma 还有个 theta
。。。
theta 和 O正好相反
sigma 是 加中间。。。 |
|
|
i******t
发帖数: 22541 | 21 我说错了
我应该说的是 这种用原始递归做的时候的复杂度 是 大约 2^n
用 DP 是可以o(n)的
还有个方法是 logn
easy |
|
|
L********e
发帖数: 159 | 23 [fn+1]=[1, 1][fn ]
[fn ] [1, 0][fn-1]
然后参考矩阵乘积的logn解法。 |
|
w**s
发帖数: 339 | 24 别搞什么O(logN)了。你要是较真的话，既然写成矩阵，还可以算矩阵的特征值和特征
向量，然后可以可以写出通项公式，那就是O(1)了。有兴趣可以翻翻组合数学的书。方
法我还记得，但特征值不记得了。好像跟黄金分割有关。所以我们写程序O(N)就可以了
。 |
|
|
c********p
发帖数: 1969 | 26 我太笨了，不得不用一个数来试了一下，发现是2^n |
|
s******7
发帖数: 1758 | 27 要求不用recursion和iterative求fibonacci
听完就放弃了说数学没那么好，后来忘了问答案
求这里高人求解 |
|
B********r
发帖数: 397 | 28 类似于算一个范围内的Fibonacci，不过要小心integer overflow。 |
|
s********u
发帖数: 1109 | 29 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
前言：
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
所以这个原则应该是“适合用dp”，而不是“可以用dp”
另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
是有重复的，但是
subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7），bool cover( root, p )本身是
单纯的DFS访问，subproblem不存在overlap；但对整个问题而言，cover不停的调用，
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS，递归函数中调用了递归... 阅读全帖 |
|
|
|
|
r*****d
发帖数: 727 | 33 来自主题: JobHunting版 - CS真难学 I am taking graduate CS classes too. (I am not CS major)
Algorithm , data structure is not that easy. I am kind of lost when talking
about UNION/FIND, Fibonacci Heap...So I did not do well in the Midterm.
Is this important for interview?
But the other course I am taking, AI, I am doing much much better..... |
|
a***m
发帖数: 5037 | 34 phone coding questions :
1 - Write a function that takes an integer N and returns the Nth number of a
Fibonacci suite.
2 - Given a list of Integer. Write a function that takes an integer and
returns all the pair of integers included in the given list that sum up with
this integer.
Face to face coding questions :
1 - Write a function that takes an integer and return a string of this
integer in Roman number format.
2 - Go game. Write a function that takes a position (x,y) in a go game graph
and re... 阅读全帖 |
|
a**********0
发帖数: 422 | 35 请问怎么做？ 我看了一篇小文 会做了 觉得挺有意思的 |
|
a**********0
发帖数: 422 | 36 更正 说错了 仍然不是constant time |
|
|
d**********x
发帖数: 4083 | 38 impossible. best running time is O(logn). |
|
s*********o
发帖数: 14 | 39 there is a formula to calculate nth element, is that what you mean? |
|
d**********x
发帖数: 4083 | 40 put aside these math tricks...
we can actually make a lookup table... because Fn is same order as 2^n, so..
.. |
|
|
d**********x
发帖数: 4083 | 42 well. the idea is, formula with irrational number is not accurate when you
calculate it in computer. (which is not that true. for F1-F30, it is
accurate enough)
and, with the 'n' parameter in the formula, it still needs O(logN) time to
evaluate.
I think OP was talking about the matrix solution in fact. |
|
|
a**********0
发帖数: 422 | 44 对 可以使用类似公式的东西 可以用矩阵的SVD乘方的方法计算
但问题是需要计算常数的乘方 所以不算constant time |
|
|
a**********0
发帖数: 422 | 46 wiki上说DP是把大问题变成小问题 但我觉得这不能体现DP的特点 难道recursion不是
把大问题变小问题吗？ 我觉得差别是 DP一般从base case 到complicate case
递归反之 比如Fibonacci如果用递归 则指数复杂度 如果用循环 就是多项式 循环当然
也需要从简单到复杂而不是反之 DP相比递归就是减少了重复的计算
其实dp有点像随机过程里的马克夫过程或者martingale一样的 就是一点一点的算 |
|
c*******2
发帖数: 60 | 47 那个繁殖的, 应该是Fibonacci数列吧, 不是等比数列 |
|
G*****n
发帖数: 11 | 48 这家很奇怪。我是collabedit 上面做题，题很简单，2 sum, 4 sum,然后求fibonacci
数的和。我有同学则是直接给题，然后说思路。已拿到onsite，因为回国推的很后面。
一句话,完全up to面试官。 |
|
G*****n
发帖数: 11 | 49 这家很奇怪。我是collabedit 上面做题，题很简单，2 sum, 4 sum,然后求fibonacci
数的和。我有同学则是直接给题，然后说思路。已拿到onsite，因为回国推的很后面。
一句话,完全up to面试官。 |
|
u*****o
发帖数: 1224 | 50 面试公司：tower research capital, 职位: quantitative trader, 地点：NYC曼哈顿
这家公司做high frequency trading的，大概就是抄短线的意思。本人对金融业一无所
知，炒过一点股票还高买低卖，但拿到onsite后，还是想着应该锻炼一下自己，面试虽
然痛苦，但肯定是有好处的，何况还可以看看华尔街和金融精英们，都长得啥样。。用
心良苦的把面试安排在感恩节后，想着好好复习，结果跳deal跳的天昏地暗，题也没做
几道。在西雅图候机的时候心情别提多沉重了，onsite丢脸那可是无处遁形啊。怕了一
路，最后还是没躲过。
转机的时候，去纽约的飞机又因为天气问题被cancel了，在芝加哥机场等了3个多小时
。到了纽约已经晚上8点多了。宾馆屋里那叫一个黑呀，根本不是学习的地方，我把所
有的灯源都集中到书桌前，困的已经睁不开眼了，但还是咬着牙把markov chain,
martingale, 各种integration的trick都过了一遍才睡的。。后来证明这番努力完全没
有用 T_T…
第一轮是做卷子，10道题两个小时，一道题就是12分钟... 阅读全帖 |
|
