|
B*****t 发帖数: 335 | 2 1. O(nlgn) can be achieved by using FFT under some conditions. But generally
the best algorithm to find a subset of 3 elements sum up
to a given value T is O(n^2). The relationship is like radix sort vs quick
sort. But I doubt the interviewers from MS would ask such kind of questions.
2. I don't think there is such kind of algorithms with O(m+n) complexity. |
|
r****o 发帖数: 1950 | 3 多谢,竟然还用到了fft。
在 Stigmata (Stigmata) 的大作中提到: 】 |
|
x****k 发帖数: 2932 | 4 并行运算绝对是fpge优于软件,例如fft和3G里面的rake多径搜索算法。
这还是取决于具体算法需求。 |
|
h**6 发帖数: 4160 | 5 四流学校Fresh EE PhD年底毕业,找了半年的工作终于有着落了。
微软Windows Live 59级SDE,给的是master的价:
8.1w + 0-20%bonus + $5w stock/4 years + 0.5w搬家费
网上投的简历,三周后网上测试,四周后hr电面,六周后onsite面试,七周后offer。
onsite面了五个人,第三人包括吃午饭共90分钟,其余每人60分钟。
1.C语言字符串相关问题。
1)写出strstr函数,准备好的BM算法没有用上,用的最土的O(nm)算法。
注意两点:a.不要用strlen(防止某个字符串很长),b.只检查长度许可的部分(起始位
置为0到n-m+1)
2)在长度未知的文件中查找字符串。
2.定义无符号可变长度长整数类并实现加减乘除。
1)加法因为内存分配研究了半天,定义了分配和使用两个size而搞定;
3)乘法提到可以使用FFT,但仍然用普通方法实现。
4)除法的试商函数没有时间写了,但我说用二分法实现,面试官表示满意。
3.吃饭时未必需要参考版上的建议什么可以吃,什么不能吃。我的饮食一向比较独特,
选自己熟悉的吃就行了。吃... 阅读全帖 |
|
d**u 发帖数: 1065 | 6 来自主题: JobHunting版 - 经典面试题 FFT |
|
d********w 发帖数: 363 | 7 First, we can consider 2 numbers, which is O(n) time. We can use 2 two
pointers to process the sorted array or use hashtable to find whether T-cur
in it.
If k = 3, the running time is O(n^2), wiki describes the algorithm http://en.wikipedia.org/wiki/3SUM, it also mentions an optimization
"When the integers are in the range [−u ... u], 3SUM can be solved in
time O(n + u lg u) by representing S as a bit vector and performing a
convolution using FFT." but it is hard to follow.
How about numb... 阅读全帖 |
|
i**********e 发帖数: 1145 | 8 看了看 topcoder 的讨论,第三题似乎是用 inclusion-exclusion principle 来排除
多余的组合,看来关系还是比较棘手的。出的题目也真是太难了,说要派 300 件
tshirt 给前 300 名,结果只有 150 人答对至少一题...
这轮看来是专门针对那些专做 topcoder 的选手,看看第一题的讨论就知道,听说要用
FFT 或者 Karatsuba algorithm 来做快速乘法。看了排第一名大牛级别的代码,还真
不是一般的复杂...
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
l********n 发帖数: 9 | 9 Problem 1 seems asking for FFT, the O(N^1.5) algorithms is too slow. In fact
, I tested Petr's solution and it takes around 8m to finish. He must have
other tricks like running testcases in parallel to finish it within 6min.
Problem 3 asks for Mobius function which I have no idea before.
Among over 2700 participants, only 150 have solved at least one problem. It
is hard, especially compared to previous rounds that most problems are
trivial. |
|
b****y 发帖数: 169 | 10 【 以下文字转载自 Programming 讨论区 】
发信人: binary (erazer), 信区: Programming
标 题: 有人参加hacker cup吗?
发信站: BBS 未名空间站 (Tue Feb 8 18:25:01 2011, 美东)
这round2的题很有意思啊。
可惜我一道也没做出来。
第一题居然要用FFT。
后两道都是DP,我连高手们的源代码都看不懂。
有高人能解释下吗? |
|
h******8 发帖数: 55 | 11 快速傅里叶变换
int * multiplication(int a[], int b[], int size_a, int size_b)
{
int i, j;
for (i = 0; i < size_a + size_b; ++ i) c[i] = 0;
for (i = 0; i < size_a; ++ i)
for (j = 0; j < size_b; ++ j)
c[i+j] += a[i]*b[j]
return c;
}
It will take n^2 operations.
♥ To reduce that, we can transform the coefficient representation to
sample representation. Then do the multiplication, then transform back.
Sample representation: given {(x_0, y_0), ..., (x_n, y_n)}, there is exactly
on... 阅读全帖 |
|
s****n 发帖数: 199 | 12 What is graphic fundamental? FFT, DCT and etc? |
|
f******t 发帖数: 7283 | 13 呵呵尝试想了一下:
1. 当年上抽象代数的时候,老教授第一堂课上就说,抽代四个重要概念:群、环、模
、域;结果期末考试第一道大题四个小题分别是默写这四个概念的定义。这里俄罗斯老
头问的是其中“环”的定义
2. 黎曼几何......也是当年,上完微分流形那门课之后有一门后继的选修课就是黎曼
几何,我打死都不愿去选。所以不懂......
3. FFT,wiki上有很多不同的implementation
4. 泰勒展开,关键是如何高效准确算高阶导数
5. 特征值和特征向量,假如是在矩阵空间里面的话好办,直接解特征多项式得到特征
值,有了特征值之后解对应的线性方程组得到所属特征子空间的一组基;或者用数值计
算里面那些方法(海森堡矩阵、QR分解等等);假如是对抽象的算子求特征值、向量,
可以用迭代法(Krylov space、Lanczos之类的那些),当然迭代法也适用于矩阵的情形
6. 解线性系统是数值代数里最终极的目的,数不尽的解法,不过大致分为这2类:直接
求解(高斯消去、QR分解等等);迭代求解(把AX=B转化为求min ||(AX-B)||这类形式
,等价于解一个优化问题) |
|
c****p 发帖数: 6474 | 14 没有。。。。可能要利用圆周卷积的性质,然后转化成类似于FFT的做法。 |
|
b*******y 发帖数: 232 | 15 qualcomm的职位有各种不同领域的,看你申请什么了
如果申请PHY/MAC的system engineer,当然需要好好准备:
简单随机过程,概率,signal processing(FT,DTFT,FFT,功率谱,频谱变换,频域信号
分析),以及简单的detection,包括ml,MMSE,MAP,Zero Forcing, matched filter,还
有简单状态机等等,以及准备一些小的puzzle,以前精华区都有。
如果是networking的职位,好好准备计算机网络,TCP-reno阿,AIMD,routing,
scheduling等等,以及很多灵活应用的知识。反正都需要平时的积累。
software的话不知道,估计也面一些编程吧。
讨论CS的,请问qualcomm这样的公 |
|
g***i 发帖数: 4272 | 16 EE的master,转码工不易啊。。
问的东西很杂,算法问题倒是不多,
问了quick sort,count sort具体实现
然后就问static variable和global 的区别, extern的用法
malloc和calloc的区别
问我是否知道把string变为int的函数(应该是atoi)
++n和n++具体实现,效率比较
解释眼图和BER
markov chain是啥
heap是啥,创建max heap的算法
QPSK和4QAM的区别
信号空间和向量啥的
香农定理
fft和dft区别
QPSK解调方式
wcdma是否支持mimo
wcdma和gsm区别
LTE对语音通话的解决方案
还有UE register umts网络步骤,详细说出来。这个完全没说出来
能记住的就这么多了。。是一个态度非常好的老印,投了无数了,拿到的电面没几个,
又screw up了一个 |
|
i******r 发帖数: 793 | 17 1. FFT
2. 两两比较一遍,有更快的做法么 |
|
g*********e 发帖数: 14401 | 18 第一题不用FFT吧,反而复杂了。直接用公式不就得了。结果长度 n+m-1
第二题也不用sort啊,直接找个对字母顺序不敏感的hash function |
|
H****r 发帖数: 2801 | 19 arrays的convolution 不是指FFT吧
感觉是说 sequence of tuples? |
|
l***m 发帖数: 339 | 20 想请教版上的大侠们,google 的intern 现在team match还有戏吗?因为听说三周
要是没有match上,就要被拒了。 我现在过了google的技术面试,hr通知让我等team来
match我,可是一周多了也没人理我,好着急啊,别的公司offer要deadline了。
小女子求求大家帮帮我,急死了都。如果有在google工作的兄弟姐妹们,你们组招
intern的话,求推荐一下,请联系我,小女子感激不尽!!
我的方向是machine learning, data mining, large data processing。
更新面经:
问了问我简历上的project 和一些相关的算法。
题目:
1。 给定输入这样的字符串
fft, fcp, aac, act, acd, atp, tbk, tdf, …
这些都是按照字母排序好的,但是字母顺序改了,比如 f 在 a之前,t在d之前等等,给定一些这样的rule,问怎么rebuild
the alphabet?
拓扑排序。
2。 停车场调度问题
3。 给定一个很长的string, 切分字典里的词。输出。
例如举个短的例子 ... 阅读全帖 |
|
g*********e 发帖数: 14401 | 21 最近onsite了两家公司,没有签NDA,今天把面经回忆整理下献上。很长,希望对大家
有所帮助。特别是EE的同学。
Qualcomm QCT HW
先是去QCOM candidate caring center。这里会见到HR,然后问些何时毕业,VISA的问
题。还会告诉你如何打车在不同building之间走。不爽的是HR会在这里问SALARY
expectation,我说expect market price,a competitive number blabla。
HR非要问what it means? 我没办法:you want a number? HR:yes. 我想了5秒:
10w?
HR 脸色一变,开始压价:10w是非常高的数字,这样对其他老员工不公平。
我说这个数字很reasonable啊?HR问你真的不想改了吗?反复问is it a make or a
break? 我最后说9w5。然后说是flexible的,Q的福利好也是优势blabla.
之后HR态度就很冷淡了,问问题也不怎么responsive。
之后是technical面经,有些问题记不起来了
亚裔MM:
... 阅读全帖 |
|
a****g 发帖数: 3027 | 22 电磁场全是数学计算.没觉得难,考试分数也不错.但是学偏了,当年只会计算,现在一点
点都不知道是个啥东西了.微波上来就是方程式,方程太难解了,而且只是几种特殊情形.
没有学懂过.天线更不知道学的是啥东西了.
国内的课程太偏计算了,学偏了,也就是没有学会.有时和老师的水平也有点关系.比如快
速FFT,本科只是死记硬背那个蝶形,上研究生时老师从相似的例子,1+x+x2+x3+x4+x5+x6
+x7,讲出了实质,反而很容易理解,觉得真的懂了,反而不关心的那个蝶形了.
不过学懂了,用处也不大,除非你想当教授. |
|
P**********c 发帖数: 3417 | 23 取决于你以后做什么,我觉得不管什么专业,应该都是只有一两门课比较有用。象我本
科是EE, PhD读了EDA, 基本上本科用得上的就非常之少了。除了编程以外,可能数学,
矩阵那些还用上了一些。本科学的常微,偏微解法也不是numerical的,虽然EDA很多时
候是在解常微,但是都是numerical的,本科那些也没用上多少。电路的东西全都没用
上,因为本科学的电路基本上都是经验解法,跟EDA的思路正好相反。
象那些做电路的,我觉得基本就是电路那几门课和简单的FFT比较有用,很多数学课,
比较复杂的信号处理那些就用不上。 |
|
H****r 发帖数: 2801 | 24 现场写啊? 30分钟的话能写定简单版本不错了吧?如果是课后题方式那Toom-Cook还是
说的过去的。 FFT就复杂了... |
|
f*********d 发帖数: 140 | 25 补上一份详细的g家店面面经,或许对即将要面的,准备面的都有帮助, 我也顺便搞点
包子!
===============================================
Oct.19th ,东部时间1:30, 一面,印度a3
1,为什么基于比较的排序问题复杂度下界是O(nlogn)
回答出来了,他表示赞同
2,分析下面递归算法的复杂度
Alg(array, size)
split -> A1, A2, A3.... O(n)
Alg(A1, size/3)
Alg(A2, size/3)
这个题目是硬伤,他push我快快快,我一紧张,递归函数没有写好, 写出来之后
说用主定理,再一紧张把 a 和 b搞反了。。。
F(n) = a * F(1/b n) + O(n)
总的来说这题做错了
3, 大数据的平方 X^2 X很长 不能用int long 之内的表示
一开始就反应时Divide and Conque, 他表示赞同, 但是我始终没有到NlogN, 只
到了N... 阅读全帖 |
|
j*****y 发帖数: 1071 | 26 一面的第三题一般是可以做到 n^(log3) 吧?
比如 算 A * A where A is n digits number
A = B * 10^(n / 2) + C
A * A = B * B * 10^n + 2 * B*C * 10(n / 2) + C * C
need to compute B * B, B * C and C * C
So we compute three items below:
(B+C) * (B+ C) = B*B + 2*B*C + C*C
B*B
C*C
from which we can get 2*B*C = (B+C) * (B + C) - B*B - C*C
let the time for A^2 is T(n)
so we have T(n) = 3 T(n/2) + O(n)
and T(n) = O(n^(log3)
这里假设两个 n digits number的求和需要 O(n)的时间
补上一份详细的g家店面面经,或许对即将要面的,准备面的都有帮助, 我也顺便搞点
包子!
=======================... 阅读全帖 |
|
l*****i 发帖数: 136 | 27 第一面问的真是多啊,FFT都出来了,要我估计也是挂
LZ能做到这样已经很不错了 |
|
d**e 发帖数: 6098 | 28 ☆─────────────────────────────────────☆
marius (youyou) 于 (Fri May 25 17:57:14 2012, 美东) 提到:
amfgl的中的两个onsite 在即, 一直觉得自己不笨,算法很来势,可今天看了网上的题库,都
快哭出来了。没几个会的, 更别提在5分钟内做出来了。感觉自己的脑子,已近被
wired成 EE了, 什么变换,去燥,自适应。。。什么问题都能很有得心应手, 但一碰
到permutation, sort, heap, tree, 一点思路都没有,绝对一个低智商的学生。
数学, 信号处理多学了没用, 最重要的就是那门离散数学只当了选修, 编译原理没
有深入。
啊, 很郁闷。。
☆─────────────────────────────────────☆
lclclclc (home) 于 (Fri May 25 18:13:58 2012, 美东) 提到:
amfgl like smart elementary school level candidates, you are over q... 阅读全帖 |
|
f******n 发帖数: 198 | 29 这个以前学Image Processing的时候都是用Fast Fourier Transform做的。当然除非刚
上完课,否则面试的时候用FFT基本是找死。。。 |
|
l*******b 发帖数: 2586 | 30 ? FFT也不可能比O(n^2)快呀???为什么 |
|
g****x 发帖数: 223 | 31 DP的一个小小的应用是HMM。楼主不妨一试,即考了DP,编成,又考了概率,如果对方
答不出,楼主又可以显示自己高深的理论数学功底,让他崇拜吧。这年头,想考倒一个
人还不容易?DP不成,咱们可以来LP,LP不成,再来数论或FFT,。。。MIT的大白书上
有的是这样的题。再不成,自己读读SODA/STOC上的文章,然后去考人,让他30分钟
内提出个大概想法,如果想不出,证明此人"CANNOT THINK LOUDLY"。 |
|
d**********x 发帖数: 4083 | 32 我大三的时候作为一个外系的,跟着二手数据结构课一学期把这本书从头到尾做下来,
跳过了FFT、数论、NP这三章,以及网络流的习题。
这几个topic再用一个学期怎么也做下来了。这真的只是一本introduction而已。 |
|
h**********7 发帖数: 218 | 33 职位是硬件测试组的,非码农,所以职位具体内容就省略了,lz背景其实只能算沾边,
偏软件一点,加上刚毕业工作不到一年,所以抱着好奇和试一试又不会怀孕的心态去打
了回酱油:
最初是apple的recruiter在linkedin上联系我,山寨到木有job description,俺还是
很贱的发了resume过去。省略其中一些磨唧的过程,然后hr开始setup电面
电面两轮,
1 hiring manger,问了一些我现在的工作内容,为什么感兴趣这个position,和一些
本科水平的专业问题,比如做FFT是基于对时域信号的什么假设,Nyquist thereom,
Green's frunction之类
2. 招人组的一个engineer,还是问你为什么要apply这个position,问了一些c编程的
问题,也是那种网上可以搜到的常见问题 比如static和constant区别,如果要在无限
循环中 allocate heap memory如何防止crush(lz脑残的没有答出来),另外还有一些
物理方面的问题,内容过于暴露此处省略
两个电面都是四十分钟左右
onsite 在cuper... 阅读全帖 |
|
A*****i 发帖数: 3587 | 34 看到FFT瞬间内牛满面,曾经的EE屌看到这个真是倍感亲切~~~ |
|
s********k 发帖数: 6180 | 35 面的是Sunnyvale的wifi做底层SW和FW的。题目都是C以及操作系统和DSP的内容,比较
有特色的是不需要math的库计算signal strength到dbm的转换,上了最简单的之后要求
优化再优化(我用的是最简单val/10开始,然后转换成shift bit,然后转换成BST类型
),其他都是指针,memory或者bitvector的东西,系统层面考察RTOS的context
swtich触发条件,ARM的IRQ和FIQ区别,怎么决定stack的size,等等。DSP主要是FFT,
OFDM,frequency reuse,最后还有一些比如float point的计算之类的。
想请教PHD+2 yr能拿到SR staff吗?大概工资能什么范围?
多谢 |
|
z****x 发帖数: 49 | 36 wiki上说的是:When the integers are in the range [−u ... u], 3SUM can
be solved in time O(n + u lg u) by representing S as a bit vector,
determining S + S by performing a discrete convolution using FFT, and then
comparing to -S.
http://erikdemaine.org/papers/3SUM_Algorithmica/paper.pdf |
|
|
b********a 发帖数: 300 | 38 收到一封烙印来信。。。
Dear Professor,
I am Ashish Ganta , a pre-final year undergraduate student of Electrical
Engineering Department at Indian Institute of Technology, Bhubaneswar (Link)
,one of the premier institutes in India for study of Technology and Applied
Sciences.
As a part of research study I recently read your article"<> " on
Science Direct and I was highly impressed by the research work going on at
your institute. I would like to pursue a summer internship under your
guidance in orde... 阅读全帖 |
|
s*w 发帖数: 729 | 39 FFT 居然都列出来了,这东西太经典了,有啥做头? |
|
g*********e 发帖数: 14401 | 40 来自主题: JobHunting版 - CS真难学 其实说白了 CS工作的人 大多只懂工作需要的那部分就够了 比如写JAVA的可以不懂OS
CPU设计
内存分配 做网页的可以不懂C++ 短平快。
数学物理EE这种都必须从最低懂到应用,比如信号系统,不会算积分就算不了拉普拉斯
变换,推不出FFT 也搞不了滤波 环环相扣 |
|
H**r 发帖数: 10015 | 41 来自主题: JobHunting版 - CS真难学 FFT不就是个divide and conquer算法么,在CS面前有啥了不起的。
一般的积分,CS专业的也会,CS的数学又不差。
当然可能有人说了,实际工作上CS的码工又不用算微积分。问题是EE毕业的每天都用微
积分?也许毕业找不到工作转行做了几年当auto dealer,连啥是CMOS都忘了。EE这么
大一坨东西,full stack前后通吃的人几乎都不存在了。
OS |
|
c******3 发帖数: 5 | 42 本人有个非美国的ece phd。phd做的是fft算法方面的。现在cmu读金融工程master.之
前有个it consulting说可以帮我办h1b。需要两万美元。我是打算毕业去硅谷做
software engineer。请问我是让ccc办h1b然后十月生效去硅谷找it工作还是读完
master用opt找cs工作。不想读有几个原因 学费比两万贵,金融工程比较难,毕业工资
待遇不如it.或者有什么其他想法可以告诉我,谢谢! |
|
g******y 发帖数: 143 | 43 你想怎么处理?无非就是采样,FFT,filtering,IFT这几个步骤。 |
|
x******1 发帖数: 155 | 44 周一google电面,现在还在等消息,发发面经,攒攒RP,也希望得到大家的Bless!
第一题,水题,数组加一操作,for example, 输入[2, 7, 8, 9] 数组,加一后变成 [
2, 7, 9, 0]
第二题,给定输入这样的字符串
fft, fcp, aac, act, acd, atp, tbk, tdf, …
这些都是按照字母排序好的,但是字母顺序改了,比如 f 在 a之前,t在d之前等等,
给定一些这样的rule,问怎么rebuild the alphabet? |
|
y*****9 发帖数: 149 | 45 弱问拓扑排序咋用的。是说比如fft就弄一个f到t的edge,一个directed graph,然后
从没有incoming edge的node开始delete,delete完node delete edge?
这应该用啥data structure啊,一般graph不用linked list,感觉复杂度很高啊。 |
|
f*******w 发帖数: 1243 | 46 Sampling
Quantization
Low-pass/high-pass/notch/comb filters
DFT/FFT
Estimation and detection
Fundamental probability questions |
|
c******n 发帖数: 4965 | 47 向量相乘难道要考你 fft 乘法? 这都是工业界熟知的办法, 不过要考就实在无聊 |
|
发帖数: 1 | 48 刷的在FLG的工作中用的到吗?
我觉得能想出quick sort的就是算法大牛了,EE领域的就是FFT。 那都是世纪牛算法。
没想到本版大牛各种dynamic programming信手拈来, 这水平比楼教主也不差了吧。 |
|
c******3 发帖数: 6509 | 49 试试FFT分解,固定周期的和中间的很容易找到,单峰值是固定的,次峰值是specially |
|
|