i**********e
发帖数: 1145 | 1 呵呵，先赞一个.
该叫你 Tracy 吗？呵呵
昨天我忙着 update 在 blog 里新的面试题，还没看你的代码.
现在头脑有点晕，我现在去看看哈 :)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
b***d
发帖数: 186 | 2 【 以下文字转载自 Linux 讨论区 】
发信人: beerd (beerd), 信区: Linux
标 题: 一道面试题求解
发信站: BBS 未名空间站 (Sat Sep 3 01:22:56 2011, 美东)
一道面试题
我抓脑袋想不出来，帮我想想
家里一台电脑A ip 11.22.33.44
公司一台电脑B ip 55.66.77.88 这电脑还有另外一个interface，可以连到公司内部
100台电脑10.1.1.100～10.1.1.199
A可以ssh到B，但是不能直接ssh到公司内部电脑10
问做了什么操作后，可以在A和B直接建立某种连接，使得在家里A电脑上直接访问10.1.
1.100:123 或一百台电脑中任一台的任一端口都可以直接访问。
所有server均运行Linux
已知答案不是在AB间建VPN
也不能用 ssh tunnel with -w option
也不能用 iptables
据说还是特别简单的办法，不需要特别的软件支持。 |
|
r********d
发帖数: 7742 | 3 我完全不反对通过面试题来考察解决问题的能力，我反对的是那种通过看面经，背答案
，通过面试，回过头来再来贬低计算机专业难度的行为。
如果所有的面试题都是自己一道一道独立解决的，恰恰说明了面试人解决问题的能力很
强。这也其实是面试设计的初衷。
Anyway，不管大家最后怎么复习，怎么拿到offer，我都真心祝贺。只是这个道理还是
要说明白的。
的。 |
|
r*****s
发帖数: 262 | 4 大家好，
我想建一个小网站，专门收集Analog IC Design面试题。
以提高面试技巧。
如果你有兴趣，请把你知道的和亲身经历的Analog IC Design面试题
email给我。我会综合并发布到网站上。同时试着给出答案。
我会通知你网址。
这样大家就可以提高面食技巧，同时扩宽思路。
我的email address
d******[email protected] |
|
kx
发帖数: 16384 | 5 2011年3月21日陈皓发表评论阅读评论 68 次点击
有时候，有些面试题是很是无厘头，这不，又有一个，还记得小时候玩的的“火柴棍游
戏”吗，就是移动一根火柴棍改变一个图或字的游戏。程序面试居然也可以这么玩，看
看下面这个火柴棍式的程序面试题吧。
下面是一个C程序，其想要输出20个减号，不过，粗心的程序员把代码写错了，你需要把
下面的代码修改正确，不过，你只能增加或是修改其中的一个字符，请你给出三种答案
。
1
2
3
4
5
int n = -20;
for(int i = 0; i < n; i--){
printf("-");
} |
|
c********d
发帖数: 26 | 6 一份罕见试卷引出一个沉重话题
——点评上海交通大学科学史系2000年硕士研究生复试试题
□命题：江晓原 □点评：刘兵
点评
考试的问题历来是教育中的一个重要问题。只要有教育，就会有
考试，只是在不同的情况下考试的内容和形式会有所不同而已。一般
来说，考试的内容和题目的出法，是很能够反映出出题者的学识、风
格以及所供职单位的教育传统甚至于对不同观念的宽容程度的。
经常有人提到过去著名学者陈寅恪的各种轶事，提到他在清华大
学的考题中用“孙行者”作对子的上联这一著名的例子，他心目中的
标准答案是“胡适之”，这件事至今仍被人们作为掌故而津津乐道。
只是，在如今从小学到中学再到大学的各种考试题中，我们已经很难
再见到这样风格别样且大胆的试题了。在这当中，或许除了出题者的
因素之外，与当下各教育单位新的考试传统的形成和宽容程度的下降
均不无关系。
不久前，非常高兴地看到了上海交通大学科学史系对其硕士研究
生进行复试的一份考题。这份考题与现在我们常见的考题确有很大的
不同，所以愿在此对之做些评论，以期引起相关的讨论，并相信这种
讨论对于科学史等相关学科的建设，对于人文修养的强调，甚至对于
教育改革 |
|
i**********e
发帖数: 1145 | 7 【 以下文字转载自 JobHunting 讨论区 】
发信人: ihasleetcode (1337coder), 信区: JobHunting
标 题: 一道热门的 Google 面试题
发信站: BBS 未名空间站 (Thu Jan 27 21:06:18 2011, 美东)
最近非常热门的一道 google 题，大家讨论讨论.
Two reverse sorted arrays A and B have been given.
such that size of A is m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n
本版又讨论过，但是好像没什么结果。
http://www.mitbbs.com/article_t/JobHunting/31684697.html
这题其实可以转换成另外以下的题目（杨式矩阵）：
Given a N*N Matrix.
All rows... 阅读全帖 |
|
i**********e
发帖数: 1145 | 8 【 以下文字转载自 JobHunting 讨论区 】
发信人: ihasleetcode (1337coder), 信区: JobHunting
标 题: 一道热门的 Google 面试题
发信站: BBS 未名空间站 (Thu Jan 27 21:06:18 2011, 美东)
最近非常热门的一道 google 题，大家讨论讨论.
Two reverse sorted arrays A and B have been given.
such that size of A is m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n
本版又讨论过，但是好像没什么结果。
http://www.mitbbs.com/article_t/JobHunting/31684697.html
这题其实可以转换成另外以下的题目（杨式矩阵）：
Given a N*N Matrix.
All rows... 阅读全帖 |
|
|
c***s
发帖数: 70028 | 10 如何拿到一个“国家级”大奖？非常简单，抄份答案，再交20元钱。
近日，永康一所学校的400名学生，参加了一个竞赛，其中，163名学生获奖。只要他们再交20元，就能拿到一个国家级协会颁发的奖状。
有家长质疑，这种比赛有什么意思，这种奖状又有多少含金量，“学校能不搞这些虚的吗？”
家长：
孩子兴冲冲说他得奖了，但领奖要交钱
林先生的孩子在永康城区一所学校上学，半个月前，孩子放学回家，兴冲冲地对他说，自己中奖了。
林先生一问，原来前段时间，老师组织他们参加了第七届“环保之星”全国小学生科技大赛，最近结果出来，孩子获得了一等奖。
不过，孩子又告诉他，为了拿到获奖证书，要先交20元钱。“他说，老师对他们说，这是个国家级的奖，对升学有好处。”
经过了解，林先生发现，这个比赛由中国地理学会主办，奖状也由他们颁发。
比赛过程很简单，老师给学生发了一套试题，并提供答案，之前并没有任何专门的培训或训练。
获奖概率也很高，据了解，这次约400名学生参加了比赛，其中163名学生拿到了一、二、三等奖。
了解情况后，林先生有点气愤，决定不交这钱。“20元钱谁都出得起，关键是学校是教书育人的地方，不要搞这些虚的东西... 阅读全帖 |
|
|
u*****E
发帖数: 2476 | 12 多选题不好答，是存在一个或更多的正确答案，而不是两个或更多的正确答案，这就不
好答了。
做了一遍，单选得了8分，错在第1题和第8题
多选得了18分，
1. 没选A
2. 多选了D
6. 没选C 人们只能老老实实地服从规律？
7. 选D而没选B
8. 多选了A和D
10.多选了A,B,D
第三部分填空，当年如果多看记忆材料，应该不难回答。
我记得我舅舅曾拿给我一本1987-1989年高考试题及解析，我过些天找到了再看看答案
如何。
今年的考研政治多选题也不好答的。参见：http://news.koolearn.com/kaoyan/20130108/725958.html |
|
n*****n
发帖数: 1634 | 13 时间：12小时，
考试形式： 开卷，跟帖
评判标准：选答案最接近实际的。如果两个答案很接近，选时间早的
公布答案时间： 72小时以后
荣誉即奖励：授予买买提菌斑最强大脑名誉称号，在菌斑享有智商永远不被怀疑的待遇 |
|
b******v
发帖数: 1493 | 14 来自主题: JobHunting版 - 一道面试题 假设第一个被选数字前有a个数字，最后一个被选数字后有b个数字
则这a+b个数字可以看成是被浪费掉了
中间这X个数字一起形成了X-1个间隔，依照题意，每个间隔至少包含一个数字(不含两
端)
我们的任务是把N-(a+b)-X个数字放进这X-1个间隔里去，使得每个间隔至少包含一个数字
这可以归结为把n个不可分辨的球放入k个容器，使得每个容器至少一个元素的问题
这样的问题的解是C(n-k+k-1,k-1) = C(n-1,k-1)
从而我们的任务有C(N-X-(a+b)-1, X-2)种选择
接下来，设a+b=k, 那么k的取值范围是多少呢？k最小可以是0，最大必须使得
N-(a+b)-X >= X-1，从而k <= N+1-2*X
对于每个这样的k，(a,b)组合有(k+1)种取法(a可以是0,1,2,...,k)
从而问题的答案是\sum_{k=0,N+1-2*X} (k+1)*C(N-X-k-1, X-2)
当然，上面假设了X>=2，否则组合数没有意义
如果X=1，则易得答案是N
可以用X=2来验证上述公式对不对：
当X=2时，易得答案是C(N,2)-(N-1) = (N-1)(N-2) |
|
s*******d
发帖数: 17566 | 15 大卡车和后面车保持距离的原因是卡车后面一块是盲点（Blind Spot）。
答案1，别的车要出高速了，当然不用再管了。答案3，后车减速，距离增加，离开盲点
更远了，当然更加安全了。这样只有答案2。
啊。 |
|
|
B*********r
发帖数: 267 | 17 一共一百题
很多都已经见过了
可入题库
－－－－
1为什么下水道的井盖是圆的？
这是网上流传最广的问题，答案有很多，比如：便于推着行走。
2美国有多少辆车？（一个常见的类似问题是：美国有多少家加油站？）
3美国有多少个下水道井盖？
4你让某些人为你工作了七天，你要用一根金条作为报酬。这根金条要被分成七块。你
必须在每天的活干完后交给他们一块。如果你只能将这根金条切割两次，你怎样给这些
工人分？
答案：分别是1、2、4三份。
5一列火车以每小时15英里的速度离开洛杉矶，朝纽约进发。另外一列火车以每小时20
英里的速度离开纽约，朝洛杉矶进发。如果一只每小时飞行25英里的鸟同时离开洛杉矶
，在两列火车之间往返飞行，请问当两列火车相遇时，鸟飞了多远？
答案：两地之间的距离*25/(15+20)
6假设一张圆盘像唱机上的唱盘那样转动。这张盘一半是黑色，一半是白色。假设你有
数量不限的一些颜色传感器。要想确定圆盘转动的方向，你需要在它周围摆多少个颜色
传感器？它们应该被摆放在什么位置？
7假设时钟到了12点。注意时针和分针重叠在一起。在一天之中，时针和分针共重叠多
少次？你知道它们重叠时的具体时间 |
|
f*********5
发帖数: 367 | 18 已知X和Y都是N(0,1)分布的随机变量，但不知道他们俩是否独立还是有怎么的相关性，
连是否bivariate normal distribution都不知道，问能否确定
E[X|X+Y=1]？
我自己简单验证当X=Y或者X和Y独立的时候答案是0.5，但是能否证明无论他俩满足什么
相关性答案都是0.5？或者有没有大牛给个答案不是0.5的反例？
百思不得其解，求解惑 |
|
r**a
发帖数: 536 | 19 虽然你不是回我的帖子。但是请原谅，我还是想啰嗦几句。如果我是interviewer，如
果candidate的答案是stock price/upper barrier, 我肯定会让她过。如果他能说出一
个更全面的答案，那么我会mark him as extraordinary。毕竟在工作中，我们需要全
面的思维，要尽可能避免思维死角。zero vol是有点极端，但是非零vol的bounded
positive process还是很常见的，甚至在工作中也能经常遇到（具体的请自行做
research如果你有兴趣的话）。当然是不是能被用来当做stock price的dynamics，是
有待进一步考察的（我不知道答案，也许行，也许不行）。
另外，就像你说的，我们没有必要convince对方。面试标准这种东西是personal style.
result
reasonable
case |
|
c*******r
发帖数: 323 | 20 都从哪方面说？最后两问的标准答案是什么？
发信人: windwine (fly), 信区: Statistics
标 题: 今天的capital one statistician面试细节及抱怨，呵呵
关键字: capital one,statistician
发信站: BBS 未名空间站 (Thu Dec 2 16:29:52 2010, 美东)
第３个是role play.分析如何把航空公司晚点的概率降低。给了一个regression的数据
和图表，从correlation matrix看里面有些东西有strong correlation,然后他们直接
去fit regression，然后你自己我去看这个东西有没有问题以及如何用它来指导
business ｕｎｉｔ，我分析的问题有。１，它把day of the week(mon,tue...)当成
了continuous variable,肯定不行，改成categorical,２。公司只关心delay<8分钟与
否，不ｃａｒｅ具体时间，所以这个就把ｒｅｇｒｅｓｓｉｏｎ改为了logistic
regression.３。它把温度作为c... 阅读全帖 |
|
o***s
发帖数: 42149 | 21 不久前张悟本骗局的曝光令中国学者和百姓再次感到失望。现在，弄虚作假的行为已经渗透到中国社会的各个角落：学生高考作弊、学者假造或抄袭科研成果、乳业公司经销“毒奶粉”……
最近的一连串事件令人触目惊心。8月份伊春发生空难后，有关人员发现这家航空公司约100名飞行员的飞行记录不实。还有唐骏的“学历门”事件——这位原微软中国区总裁曾吹牛说自己获得了加州理工学院的博士学位。
古今中外，浮夸卖弄并不罕见。而在中国，教育和科研方面弄虚作假的问题已极为严重，许多中国人不由担心这会阻碍中国下一阶段的经济发展。
国内外的学者纷纷表示，科研人员缺乏诚信不但令中国的发展潜力无法充分发挥，也阻碍了中国与其他国家的科研合作。中国人民大学政治学系教授张鸣说，如果不改变现状，（中国人）就会被淘汰出世界学术圈。
中国的大学管理者以发表论文的数量作为科研人员自主创新的衡量标准，受到压力的科研人员便制造了一大堆抄袭、伪造的科研成果应付。去年12月份，英国《晶体学学报》宣布，撤销刊载中国学者发表的70篇论文。理由是这些论文或涉嫌剽窃，或不够严谨。
今年早些时候，英国医学刊物《柳叶刀》发表社论警告说，假造或抄袭科研成果的现象将... 阅读全帖 |
|
o***s
发帖数: 42149 | 22 西工大选修课出了这样的考题，有人说这是纯洁的爱情，有人说出题者有失偏颇
“某大学女生与本校某男确定恋爱关系之后，经常在一起学习、娱乐、约会，可是八个月过去了，男生对女生没有任何亲昵举动，甚至连女生的手都没碰过。您认为该女生下一步应该咋办?”
这是西北工业大学选修课程《大学生心理健康》考试试卷的压轴题。该微博昨日上午11时1分发布，截至昨晚8时许，该微博被转发200多次，相关评论达到200多条。有网友还在百度贴吧中发帖讨论。
调查的确是西工大选修课考题
昨日，记者来到西北工业大学长安校区，采访了二十多名大一大二的学生，了解到该大学2011至2012学年“大学生健康教育”课程第二学期考试试题一共有五道，都是论述题。考试时间为6月9日上午。
考试题中的第五道压轴题，正是网友微博上所发的：恋爱8个月，大学男生对女生没有任何亲昵动作，女生该咋办?
观点有支持也有怀疑
在这条微博的转发和评论中，网友的观点分为三种。
第一种，支持题中男大学生。
网友“西安微博道德管委会”：一个纯情的男生被你们说成什么了?真正的爱情并不需要性来证明。
网友“没有信仰的”：这种爱情才是值得推崇的!有些男的接近女的就是为... 阅读全帖 |
|
i***s
发帖数: 39120 | 23 “某大学女生与本校某男确定恋爱关系之后，经常在一起学习、娱乐、约会，可是八个月过去了，男生对女生没有任何亲昵举动，甚至连女生的手都没碰过。您认为该女生下一步应该咋办?”
《华商报》报道，这是西北工业大学选修课程《大学生心理健康》考试试卷的压轴题。该微博昨日上午11时1分发布，截至昨晚8时许，该微博被转发200多次，相关评论达到200多条。有网友还在百度贴吧中发帖讨论。
调查的确是西工大选修课考题
昨日，记者来到西北工业大学长安校区，采访了二十多名大一大二的学生，了解到该大学2011至2012学年“大学生健康教育”课程第二学期考试试题一共有五道，都是论述题。考试时间为6月9日上午。
考试题中的第五道压轴题，正是网友微博上所发的：恋爱8个月，大学男生对女生没有任何亲昵动作，女生该咋办?
观点有支持也有怀疑
在这条微博的转发和评论中，网友的观点分为三种。
第一种，支持题中男大学生。
网友“西安微博道德管委会”：一个纯情的男生被你们说成什么了?真正的爱情并不需要性来证明。
网友“没有信仰的”：这种爱情才是值得推崇的!有些男的接近女的就是为了性，毕业后一拍两散。
第二种，觉得这名男大学生的性取向... 阅读全帖 |
|
i***s
发帖数: 39120 | 24 题都没看懂
最让考生感觉棘手的，是5道用英文表述的“IQ题”，12位考生接受记者采访，10名称“连题都没有读懂”。
一针见血
"你觉得你有什么地方值得炫耀，好让四川大学愿意录取你？"一位考生就遭遇了一个一针见血的问题。还好他真想起了一个闪光点：“我在11个月之内，从对信息学完全零认识到拿到了信息学全国联赛一等奖。”
88888888。这不是电话号码，而是昨日举行的四川大学保送生考试的一道笔试题。给你八个“8”，要如何加减乘除，才能得出“1000”这个结果？考生告诉记者，昨日笔试一共遭遇了5道这样的IQ题，和这5道题相比，有些考生感觉其他笔试和面试都弱爆了―――“做不来”、“题都没看懂！”
IQ题 考生题都没看懂
保送生笔试要求在3个小时内，完成语文、数学和英语3个科目考试，中间无休息时间。这样的连轴转让许多考生应接不暇。“我数学只做了选择题，解答题一道都没做。”一名考生一出门就猛叹气。
而最让考生感觉棘手的，是5道用英文表述的“IQ题”，12位考生接受记者采访，10名称“连题都没有读懂”。
只有一位广西考生清楚记得，并完成了其中一道题，“给你8个‘8’，问如何才能得出1000这个结果。... 阅读全帖 |
|
o***s
发帖数: 42149 | 25 题都没看懂
最让考生感觉棘手的，是5道用英文表述的“IQ题”，12位考生接受记者采访，10名称“连题都没有读懂”。
一针见血
"你觉得你有什么地方值得炫耀，好让四川大学愿意录取你？"一位考生就遭遇了一个一针见血的问题。还好他真想起了一个闪光点：“我在11个月之内，从对信息学完全零认识到拿到了信息学全国联赛一等奖。”
88888888。这不是电话号码，而是昨日举行的四川大学保送生考试的一道笔试题。给你八个“8”，要如何加减乘除，才能得出“1000”这个结果？考生告诉记者，昨日笔试一共遭遇了5道这样的IQ题，和这5道题相比，有些考生感觉其他笔试和面试都弱爆了―――“做不来”、“题都没看懂！”
IQ题 考生题都没看懂
保送生笔试要求在3个小时内，完成语文、数学和英语3个科目考试，中间无休息时间。这样的连轴转让许多考生应接不暇。“我数学只做了选择题，解答题一道都没做。”一名考生一出门就猛叹气。
而最让考生感觉棘手的，是5道用英文表述的“IQ题”，12位考生接受记者采访，10名称“连题都没有读懂”。
只有一位广西考生清楚记得，并完成了其中一道题，“给你8个‘8’，问如何才能得出1000这个结果。... 阅读全帖 |
|
c*********d
发帖数: 9770 | 26 http://cn.nytimes.com/opinion/20150901/c01iht-edgao29/dual/
New York Times ChinaWhy Parrot Beijing’s Line?
By HELEN GAO September 1, 2015
鹦鹉学舌的中国式教育
高雨莘 BEIJING — In the spring of 1999, when I was in fifth grade, my
teacher at my Beijing elementary school gave me an assignment one day after
class. A week earlier, the North Atlantic Treaty Organization had bombed the
Chinese Embassy in Belgrade during the war in Kosovo, killing three Chinese
reporters. Washington called the attack an accident, wh... 阅读全帖 |
|
z**********e
发帖数: 22064 | 27 Why Parrot Beijing’s Line?
By HELEN GAO September 1, 2015
鹦鹉学舌的中国式教育
高雨莘
BEIJING — In the spring of 1999, when I was in fifth grade, my teacher at
my Beijing
elementary school gave me an assignment one day after class. A week earlier,
the North
Atlantic Treaty Organization had bombed the Chinese Embassy in Belgrade
during the war
in Kosovo, killing three Chinese reporters. Washington called the attack an
accident, while
the Chinese public believed it to be a deliberate provocation. I was to
writ... 阅读全帖 |
|
s********g
发帖数: 176 | 28 这个学校20刀啊 太贵 任何一个网上驾校都一样 你可以考无数次直到通过为止 所以公
布这些试题没什么意义 挑个便宜的直接上去考就好了 反正都是选择题 不会的题目错
个几次自然就知道正确答案了 |
|
L*******a
发帖数: 1693 | 29 最新的面试试题是：
如果Switch出问题的不是GM，是TOYOTA，你如何应对？
回答啥的都有，但是只有一个人被当场录用，他的答案待会揭晓。。。 |
|
c********d
发帖数: 11593 | 30 面试结果——我拿到了offer。但是这个面试题一直让我很摸不着头脑，到现在我也不
知道面试官到底想要从我这里得到什么答案。我猜想我和他的思路一定是有些脱节了。
所以发在这里，也请大家帮我参谋一下。
面试官：现在，你要做一个app，读入一个文件名，该文件可以是xml、excel表格、
blah blah（他一共举了四种不同的文件名），然后把它显示在一个窗口里。画出你需
要的模块来。
我：好的，我需要一个parse文件的模块，一个显示文件的模块……
面试官：假设这些你都已经有了。你有了四个API，可以分别读入并且parse我说的这四
种文件，你也有了一个API可以用来显示被parse好的文件。
（到这里我彻底糊涂了，这些假如都已经有了，那么还需要我做什么？）
我：假如这些都已经有了，貌似我就没啥事儿了……只需要一个有switch/case的函数
就好了啊。
面试官：一个函数……假如用C++来写这个app，你需要几个class？
我：（只好胡诌，因为我的思路明显跟面试官有些错位的地方）一个。既然那些API都
有了，一个就应该可以把它们都整合起来。
面试官：一个？你确定？假如用polymorp |
|
b**********7
发帖数: 103 | 31 [更新Google Intern Interview 过程解释]
感谢很多朋友来信。鉴于大家都很关心Google Intern的过程，我来详细的说说吧。Google intern interview的过程好像和以前不太一样了，目前在发正式offer前，需要经历2轮电话interview，然后会进入一个candidate pool，由manager来挑选，这个过程叫host bidding.
1. 电话interview: 都是google的开发人员来面的，所以比MS的HR难。当然从另一个方面来说，因为开发人员更容易理解你的code，你更容易和他们沟通。每个人大约2道题。其中一个人两个都是算法。另一个就会问一道概念题（当然，是很多小概念），一道算法。面完后，他们把feedback发给HR，如果两个人对你的评价都是positive，那么恭喜，你进入candidate pool 了。一般这个要等待1天到几周不等。
2.我电面是用google doc, 每次写一点儿要保存，有些麻烦。尤其是你要加个外层循环，需要把每一行都缩进，很麻烦。我个人不建议先在IDE里写，因为这是个interactive... 阅读全帖 |
|
i**********e
发帖数: 1145 | 32 Your argument doesn't sound convincing to me.
Assuming we are finding the 7th largest element, which is in the first
partition according to your example. To apply QuickSelect, you are assuming
you know the order of the elements in that partition... ie, how could you
tell for sure that the 7th largest element is not in [1,2] or [2,1]???
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 33 恩，听你这样说就挺有道理。
QuickSelect 的确不用排好序。
虽然我还是不很信服你这方法能 O(log M + log N) 运行，
但是你这方法的确开启了很好的思路。
我稍候再研究研究，并且顺便啃啃书，理解下 QuickSelect 这玩意。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 34 对了，听你的解说，似乎要 O(M) 来寻找一个 partition 的边界。
这样达不到你所说的 O( log M + log N ) 复杂度吧.(感觉上是 O(M*N)).
这样挺费时的吧，你能展开说说吗？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 35 paul 的方法是 O(N)吗？我怎么觉得像 O(MN）？这是因为每次为了计算字串长度，必须寻找 minimum，所以要遍历 M 次。有人可以解释一下吗？
我想到最直接的优化方法就是保持一个 min heap，能 O(1) 索取 minimum，但是代价就是 insert 和 delete 需要 O(lg M)。总复杂度为 O(N lg M)。
还有值得一提的是，以上的例子小串里没有重复的字母。万一小串是 "AABC" 怎么办呢？以上的方法都不能解决这个情况，只有 han6 的方法似乎比较对的，就是利用两个指针。但是解释得有点复杂，建议看 stormrage 的精简解法（在第9楼）。
http://mitbbs.com/article_t/JobHunting/31731763.html
楼上有人说如果 M 相对 N 很小，可以直接忽略，万一面试官不觉得是这么回事那就完蛋啦。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 36 paul 的方法是 O(N)吗？我怎么觉得像 O(MN）？这是因为每次为了计算字串长度，必须寻找 minimum，所以要遍历 M 次。有人可以解释一下吗？
我想到最直接的优化方法就是保持一个 min heap，能 O(1) 索取 minimum，但是代价就是 insert 和 delete 需要 O(lg M)。总复杂度为 O(N lg M)。
还有值得一提的是，以上的例子小串里没有重复的字母。万一小串是 "AABC" 怎么办呢？以上的方法都不能解决这个情况，只有 han6 的方法似乎比较对的，就是利用两个指针。但是解释得有点复杂，建议看 stormrage 的精简解法（在第9楼）。
http://mitbbs.com/article_t/JobHunting/31731763.html
楼上有人说如果 M 相对 N 很小，可以直接忽略，万一面试官不觉得是这么回事那就完蛋啦。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
|
i**********e
发帖数: 1145 | 39 给定一个方形矩阵, 有正整数组成, 每一行按升序排列, 每一列也按升序排列, 已
经给定整数N （N是矩阵维数）, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear time的solution.
这题O(N)的解相信大家都知道了，就是从左下角或者右上角开始搜索（很多人已经讨论过了），可以参考原帖：
http://www.mitbbs.com/article_t/JobHunting/31562567.html
我尝试了另一个解法，思路是利用binary search + divide and conquer。
给个例子：
假设我们所要找的是10。先看中间那列（请参考以下图片，灰色的那列），然后利用binary search的变种找到10是9与14之间。那么，我们可以将矩阵给分成两个（请参考图片，黄色与橙色部分），然后分别在那两个小矩阵以再进行同样的搜索。
我可以证明一个case，就是假设每次矩阵被分成两个同样大小的矩阵，那么复杂度就是:
T(n) = 2T(n/2) + c lg n
= O(N) <== 这里我省略了一些证明步骤。
注：... 阅读全帖 |
|
i**********e
发帖数: 1145 | 40 Thanks for your answer.
However, you have made an assumption that each divide is only eliminating
one row/column, which is not true.
Since we always choose the center column, each divide will eliminate half of
the columns (If the partition point is at the top most row/bottom most row)
. Therefore, we only need to perform at most log N divisions, but in your
case, it seems to be doing M+N divisions. How can that be possible?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
is |
|
i**********e
发帖数: 1145 | 41 Thanks again for your post.
Sorry I didn't make it clear in my question. If I am understand correctly,
you are trying to eliminate one row/column each time, therefore getting a lg
(N!) or N lg N solution.
I am asking for the worst case of the approach I mentioned in my first post.
This approach partitions the matrix to two sub-matrices each time, but the
problem is the two sub-matrices could be of different sizes.
There might be a case where each time it partitions the matrix to one sub-matrix
o... 阅读全帖 |
|
i**********e
发帖数: 1145 | 42 谢谢你们的尝试，我又尝试了一个方案，但还是不能证明worst case的upper bound是O
(N).
思路是这样的：
假设矩阵的大小是 NxM，那么总共有 NxM 个元素。每一次划分可以保证去除正好 NM/2
个元素。第二层的划分又可以保证去除 NM/4 个元素。那么最坏的情况我们可以保证
划分的层数绝对不会超过 lg (NM)。这也表示 recursion 的深度不会超过 lg (NM)。
第一层我们总共用了 lg N 的时间来去除 NM/2 个元素，剩下 NM/2 个元素来搜索。
第二层我们总共用了 lg(i1) + lg(N-i1) 的时间来去除 NM/4 个元素，剩下 NM/4 个
元素。（i1 是第二层选择的划分点）
Complexity:
1st level = lg (N), NM/2 items left
2nd level = lg(i1) + lg(N-i1), NM/4 items left
3rd level = lg(i2) + lg(i1-i2) + lg(i3) + lg(N-i1-i3), NM/8 items left... 阅读全帖 |
|
i**********e
发帖数: 1145 | 43 我也尝试解一解这题，不知道是不是跟各位大侠的解法一样，欢迎讨论。
假设定义：
4A 为 连敲 4 次 A，
2D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V,将之前的 A X 2，
3D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V,将之前的 A X 3.
f(N) 为最优解.
n <= 7, 那么 f(n) = n.
n = 8, f(n) = 3A3D = 9.
n = 9, f(n) = 3A4D = 12.
n = 10, f(n) = 4A4D = 16.
n = 11, f(n) = 4A5D = 20.
n = 12, f(n) = 5A5D = 25.
n = 13, f(n) = 5A6D = 30.
n = 14, f(n) = 6A6D = 36.
思路很明显，就是要求 a*b = n-2, 并且 a 和 b 相乘为最大值。
注意了，
n = 15, f(n) = 6A7D = 42？
这是错的，因为当 n = 15,
f(n) = 3A4D4D = 48.
n = 16, f(n) = 4A4D4D = ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 44 n = 13, f(n) = 5A6D = 30. ( a = 5, b = 6, f(n) = a*b = 5*6 = 30 )
n = 14, f(n) = 6A6D = 36. ( a = 6, b = 6, f(n) = a*b = 6*6 = 36 )
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
i**********e
发帖数: 1145 | 46 这不一定。
if n = 19,
x=y=z= 19/4 = 4
4*4*4*7 = 448
But the max should be
4*5*5*5 = 500
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 47 不是大侠，贴一贴我的代码，代码如果不好看 请多多包涵
恐怕只能 handle 以上的 sample test case。
基本思路就是递归，如果有更复杂的情况可以再慢慢改进。
#include
#include
#include
using namespace std;
const int TAB_SPACE = 4;
void outputJSon(istream &in, int indentLevel) {
bool firstChar = true;
bool inBracket = false;
while (in) {
char c = in.get();
if (firstChar) {
cout << endl << setw(indentLevel) << c;
firstChar = false;
}
else {
cout << c;
}
if (c == '{') {
outputJSon(in... 阅读全帖 |
|
i**********e
发帖数: 1145 | 48 其实不递归 代码或许会更简单些
void outputJSon(istream &in) {
bool newLine = false;
bool inBracket = false;
int indentLevel = 0;
while (in) {
char c = in.get();
if (newLine) {
cout << endl << setw(indentLevel) << c;
newLine = false;
}
else {
cout << c;
}
if (c == '{') {
indentLevel += TAB_SPACE;
newLine = true;
} else if (!inBracket && c == ',') {
newLine = true;
} else if (c == '}') {
newLine = true;
} else if (c == '[') {
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 49 The idea is simple but subtle. This trick is discussed in Programming Pearls.
Reverse the entire string.
Then reverse the characters for each individual word.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 50 最近非常热门的一道 google 题，大家讨论讨论.
Two reverse sorted arrays A and B have been given.
such that size of A is m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n
本版又讨论过，但是好像没什么结果。
http://www.mitbbs.com/article_t/JobHunting/31684697.html
这题其实可以转换成另外以下的题目（杨式矩阵）：
Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.
我想到一个利用堆的解法，可以达到 O(k log min(m, n)).
但看网上 google 要求的最优解法好... 阅读全帖 |
|
