|
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上的文章，然后去考人，让他３０分钟
内提出个大概想法，如果想不出，证明此人＂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 |
|
|
