O******i
发帖数: 269 | 1 和一个美国人吧。给一个矩阵和一个数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, 只是递归方程比一维情形稍微复杂些，是两个矩阵相加，减去相
交部分... 阅读全帖 |
|
h*******e
发帖数: 1377 | 2 caiwu pku本科， 数学phd cs master 6年毕业，老婆当时在nyc, 放弃实习机会，面
了3家 fulltime游戏公司全挂，拿到一个intern 实习没去，后来进了google 就不怎么
来了 |
|
d**e
发帖数: 6098 | 3 ☆─────────────────────────────────────☆
CAIWU (Cai) 于 (Mon Jul 16 01:46:48 2012, 美东) 提到:
看了c++complete reference 那本书
☆─────────────────────────────────────☆
mxf (mxf) 于 (Mon Jul 16 01:59:30 2012, 美东) 提到:
继续写code
☆─────────────────────────────────────☆
CAIWU (Cai) 于 (Mon Jul 16 03:07:17 2012, 美东) 提到:
有些理论光写小程序学不来
想找点进阶的书看看
练习code就那些leetcode上的
基本只用到c的东西
☆─────────────────────────────────────☆
bokertov (早上好) 于 (Mon Jul 16 05:39:35 2012, 美东) 提到:
effective C++讲得比较深入
☆────────────... 阅读全帖 |
|
y***g
发帖数: 10422 | 4 CAIWU应该说的是在飞机上打炮。所以是一日2000迈。
不过2000迈飞机也得飞4个多小时。CAIWU保持的时间够长的。估计没少吃伟哥。。。 |
|
m*********k
发帖数: 10521 | 5 本次统计截止时间为：2012-10-23 02:01:00 （美东时间）
成功奖励 20 伪币的用户: alexlovedove, Arashi, awaydream, CAIWU, cat117,
chatman, csbao, dasha1900, earlybirdie, father, feifeiyang, hejingke,
KillUncleSan, LNN2011, luciferegg, lxingbo, maiziex, Math1978, mijian,
Qingzhou, qwxqwsean, rotatezh, STM, swjtuer, tencups, thread23, valleybear,
wh, yuxuxin
奖励版面:(Apple)20伪币成功
奖励版面:(Biology)20伪币成功
奖励版面:(CS)20伪币成功
奖励版面:(Family)20伪币成功
奖励版面:(Fishing)20伪币成功
奖励版面:(Food)20伪币成功
奖励版面:(Heart)20伪币成功
奖励版面:(History)20伪币成功
奖励版面:(Immigratio... 阅读全帖 |
|
m*********k
发帖数: 10521 | 6 本次统计截止时间为：2012-11-15 01:01:00 （美东时间）
成功奖励 20 伪币的用户: aegeanboat, Benbenxu, bmwcar, CAIWU, CMNIU, csbao,
drtao, eightmile, Evora, gogotora, going395, hcxy, helix, jachy,
jpostsildavi, jsolomon, juzbox, kaka814, kickok, kinkkink, laivlys, LeftEye,
LynnCA, MaSaiKe, meask, milaso, mitbbsshare, miyamama, monkeyface,
OverCloud, patfatcat, semenov, simenking, summer28, theislander5, url, VitD,
wang370112, wyx1014, xuejian68, yingtaoxiaop, zijins
奖励版面:(Automobile)20伪币成功
奖励版面:(ChinaNews2)20伪币成功
奖励版面:(EB23... 阅读全帖 |
|
m*********k
发帖数: 10521 | 7 本次统计截止时间为：2012-12-19 01:01:00 （美东时间）
成功奖励 20 伪币的用户: airdragon77, amberLL, CAIWU, chanceway, chatman,
chendeyun, cjcup, Cklein, Conehammer, diandianxin, eua, farewell, fckdsb,
frombeijing, go88, grady, havetomajia, hcxy, hgao1, jnyn, kickok, kingcw,
koalakoala, ksnow, leaflying, Loadrunner, luoyiyi107, lynnez, NECPED, perfec
, Playmygame, poolman, qwxqwsean, Sandra27, shaoshuminzu, sheshui,
ShuaigeUSA, SpringMay, Subbus, suddl, Taraxacum, Tianma, vagabond, yakexi,
zerobama
奖励版面:(astrology)20伪币成功
... 阅读全帖 |
|
m*********k
发帖数: 10521 | 8 本次统计截止时间为：2012-12-26 01:01:00 （美东时间）
成功奖励 20 伪币的用户: ahotmail, anyme, belle, biliantian, binjiang,
bolixin, cactustian, CAIWU, cc0000, chanceway, cyberholic, digua, dodofat,
fuleyou, huskymm, iamtheretoo, iepetrinet, jiaming, joyjoy, kayaker, laomamj
, leaflee, lianxin, Little7, lovelyfish, Mercury2008, monkeyface, newday,
nirvana21, OZdreamer, Peasant61, qiaqiafeng, ShuaigeUSA, sonofagun, sunop,
tingtingliu, triest, weiweiya, woa, xiaan, yeguoer, yinian, Yobi
奖励版面:(Arizona)20伪币成功
奖励版面:(astrology... 阅读全帖 |
|
g********d
发帖数: 19244 | 9 ☆─────────────────────────────────────☆
guoguo914 (guoguo914) 于 (Fri Sep 20 16:15:53 2013, 美东) 提到:
背景：电影院停车场。我倒车，直行道上的车突然也往后一倒，当时就撞了。有点t-
bone的意思，其实就是擦了一下，我的右后bumper kiss了她的右后轮后的车身。完全
没人受伤，双方的车上留下的痕迹可以忽略不计。。我下车道了歉，当时那个女的想走
人了之，走之前还是留下了我的保险。
Geico处理结果：昨天接到geico电话，说那个女的claim了，estimate是$1436，geico
已支付。
开始吐槽：
1. 我把当时情况跟geico讲，他们说只要是我当时那种情况（倒车到直行道撞上）都是
我的责任，无论直行道上的车有没有倒车。
2. 尼玛那个女的那辆车是1994 Toyota Celica, mileage 220,975. KBB的估价才$1346
（good condition）。。。
3. 那份inspector出具的报告上，估价的是一个local的修车铺。也太黑了点... 阅读全帖 |
|
t********g
发帖数: 145 | 10 谢谢大家的热情啊，收到对方邮件，说是把我的resume forward到一个和我背景match
的hire manager那里，什么情况这是？【 在 CAIWU (Cai) 的大作中提到: 】 |
|
|
C***U
发帖数: 2406 | 12 需要2爷来认证啊
CAIWU是对的吧？
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite |
|
g***s
发帖数: 3811 | 13 CAIWU在3楼就给了解法，那就是正解啊。
换i到a[i-1]位置上,最坏情况负责度也就是O(n). |
|
A**u
发帖数: 2458 | 14 CAIWU大牛啊
quant面试机会少啊
公司网页 |
|
e***s
发帖数: 799 | 15 CAIWU， 你什么时候的G onsite 啊？ |
|
e***s
发帖数: 799 | 16 CAIWU， 你什么时候的G onsite 啊？ |
|
d**e
发帖数: 6098 | 17 ☆─────────────────────────────────────☆
fuckthrust (...) 于 (Sat Mar 3 20:04:35 2012, 美东) 提到:
这段时间真是倒霉。面试了三家，一共有5个印度人，3个中国人（2女1男），一个美国
人分别面试我。
印度人的态度简直太差了，问我的时候很不耐烦的样子，而且问的都是非常刁钻古怪
tricky的问题。还有的在我回答问题中间突然粗暴的打断我的话，有的中途打电话，明
显是想让我心理压力大自己放弃。最后3家公司都拒了我，后来听公司里的人告诉我，
最后的3个职位都给了印度人！
那个美国人真的很nice，还很细心的跟我解释他表述的问题。中国男对我还不错，挺客
气的，他问的问题比较难。但我回答得很好，期间他还一直鼓励我。那两个中国女人（
分别属于不同公司）不知道为什么，好像很排斥我，很offensive。问的问题一般难度
，但是动不动就操着中国英语说 "you should know this before!", "you really
should know this theory in your high... 阅读全帖 |
|
e***s
发帖数: 799 | 18 CAIWU，有没有经验介绍一下，明天电面G，不想被秒杀啊～ |
|
k****r
发帖数: 807 | 19 觉得你和CAIWU是一个水平的，应该offer不远了才对，一起加油吧 |
|
p*****2
发帖数: 21240 | 20 两个人可能碰到的题目难度完全不在一个层次上。看来大家要积极攒人品呀。感觉
CAIWU的人品就攒的非常好。要好好像他学习。 |
|
t*******2
发帖数: 292 | 21 同意你说的关于G的
caiwu的背景还是很牛的，不光是人品 |
|
|
O******i
发帖数: 269 | 23 那思路对么？不过具体写代码也不容易写对，边界和下标处理挺麻烦的。 |
|
O******i
发帖数: 269 | 24 如果边长为k的矩阵有部分在界外是怎么处理的？是对界外的元素补0? 还是只考虑在界
内的情形(有部分在界外就不去求平均数，中心保留原值)? |
|
|
C***U
发帖数: 2406 | 26 思路应该对的吧
就是矩阵(i,j)可以通过(i-1,j),(i,j-1),(i-1,j-1)通过常数时间得到
看来我做的题还是太少了。。。主要只做了leetcode
cc 150上的题目 我竟然不知道。。。。 |
|
l*******b
发帖数: 2586 | 27 哈哈，这个题我也这样想的。不过，超过边界了怎么处理，例如p=10，(0,0)取谁的平
均呀？(5,5)又怎么取. 感觉有点麻烦 |
|
|
O******i
发帖数: 269 | 29 CC 150 5th edition 18.12, 解法二，属于hard部分章节，解答还很详细。
我也是后来才发现和这题有点关联。 |
|
|
O******i
发帖数: 269 | 31 大牛你不用第五版，都直接白板前现想出来了。面试官想，这么smart的人，不hire真
是没天理呀。话说面试官其实不喜欢我们有撞题痕迹的说。 |
|
w****a
发帖数: 186 | 32 这是二维矩阵卷积的特例，这种情况下，可以先算小矩阵的和，再除以k*k。计算小矩
阵的和，可以用summed area table(也叫integral image)，跟楼主说到的辅助数组是
一样的：
http://en.wikipedia.org/wiki/Summed_area_table
算法是O(N)的，其实非常简单，就是利用A(i-1, j-1), A(i-1, j), A(i, j-1)来算A(i
, j)。应该用不到DP。
楼主很强！ |
|
o*********r
发帖数: 446 | 33 请教一下，这个问题本身是不是也是CG里面一种Blur的实现？ |
|
w****a
发帖数: 186 | 34 Yes, it is one of the simple blurring technique, called box filters. It is
simpler and faster than the Gaussian blur and other blurring technique. |
|
f******n
发帖数: 198 | 35 这个以前学Image Processing的时候都是用Fast Fourier Transform做的。当然除非刚
上完课，否则面试的时候用FFT基本是找死。。。 |
|
l*******b
发帖数: 2586 | 36 ? FFT也不可能比O(n^2)快呀？？？为什么 |
|
f******n
发帖数: 198 | 37 FFT是比n^2慢，我是对上面那个说CG处理的说的。Box filter的特殊性质决定了你可以
用较小的运算量从相邻的点算出当前的点的数值，所以可以做到n^2。如果是一个不规
则的filter，就要FFT了。 |
|
l*******b
发帖数: 2586 | 38 嗯能不能举个不规则的例子，看看有有什么实际用途，学习下 |
|
a********m
发帖数: 15480 | 39 比如低通滤波一类的（包括前面提到的高斯铝箔）也是一个k*k矩阵，但是每个元素不
一样（数组对称），不象box这种每个元素都是1/(k*k)，所以以前的结果不能用来计算
当前结果，变换以后简单乘法
就可以了。 |
|
|
a********m
发帖数: 15480 | 41 恩。。。。不知道钻风把dp理解成啥了。。。。毒品？ |
|
d**e
发帖数: 6098 | 42 ☆─────────────────────────────────────☆
bufangqi ( 不放弃) 于 (Fri Jun 15 11:51:54 2012, 美东) 提到:
女，国内TOP2 CS PHD，H4身份在这边
请问1，今年H1B已经完了，明年直接找到工作难么，还是需要读个master或者做个
postdoc。有什么比较可行的
途径呢
2. 有没有不是太累的码农工作，但也是大公司，或者偏research一点的？总之比较适
合女生的
诚心请教
☆─────────────────────────────────────☆
redpearl (redpearl) 于 (Fri Jun 15 12:33:35 2012, 美东) 提到:
今年的H1B已经没了，不太可能有公司愿意现在给你offer，2013年4月帮你申请H1B，但
是一直等到2013年10月你才去上班吧。
所以要么自己上EB1A，要么找到大学或非营利机构（H1B没有名额限制）。另外如果有
公司肯给你申请O1的话也可以。
读个Master的好处是可以用OPT，将来申H1B名额多一点，但是... 阅读全帖 |
|
e***s
发帖数: 799 | 43 再CAIWU的面经上看到的，有没有大牛给个IDEA？ |
|
e***s
发帖数: 799 | 44 再CAIWU的面经上看到的，有没有大牛给个IDEA？ |
|
O******i
发帖数: 269 | 45 这题在CAIWU的G面经也有？
和一个老美。先上来DP问题。说给一个字符串，是通过一些单词没有空格隔开的。让我
如果把他们分成最少的单词数。用了DP做出来。不过不知道他听懂没有。然后让设计一
个数据结构，使得一个人输入几个字母以后，会弹出来推荐的词。我用了prefix tree
。然后他问怎么能最小化打字。我就说可以根据概率来弹出后面3个的推荐，然后一次
继续。然后在这个上面纠缠了很多，然后考虑了很多情况。然后算了一下期望可以减少
的打字数。 |
|
d**e
发帖数: 6098 | 46 ☆─────────────────────────────────────☆
lvhemi (驴和咪) 于 (Mon Jul 16 20:09:00 2012, 美东) 提到:
面试中的辛苦按下不表，直接上数字(按我个人的偏好排序)，还没有谈价钱
个人背景：计算机专业新鲜出炉的屁爱着地，编程一般，研究尚可
1.推特(科学家头衔的码农，湾区)：13万基本工资+2万五千股(目前二手市场上是15美
元一股)+1万签字费
2.非死不可(科学家头衔的码农，湾区)：12万5千基本工资+价值18万美元的股票+3万5
千签字费
3.微软(产品部门和研究院联合聘用的研究员，核心组，西雅图)：12万基本工资+价值6
万美元的股票(分三年)+可能的签字费
4.亚马逊(科学家头衔的码农，西雅图)：12万基本工资+价值6万美元的股票+4万美元签
字费
5.雅虎研究院(科学家):14万基本工资+价值6万美元的股票+1万5千美元签字费
Google面试感觉不好，面试后主动发信给recruiter取消了我的申请
☆─────────────────────────────────────☆
hunt... 阅读全帖 |
|
|
r*****e
发帖数: 146 | 48 版上很多非cs的，照样去大公司啊。
随便列几个牛人吧，
小尾羊，（物理），去了G,
CAIWU，（数学），去了G, |
|
f*****e
发帖数: 2992 | 49 别吵了，求最小周期，n久之前，caiwu出过类似题，我给答案就是O(N)，我找找。 |
|
f*****e
发帖数: 2992 | 50 想想又好像是对的，caiwu的那个题比这个难，最小周期只是其中一部分。 |
|
