onsite experience

发信人: tu (土死了), 信区: JobHunting
标 题: onsite experience
发信站: BBS 未名空间站 (Mon Jun 12 04:01:13 2006), 转信

第一次面试，出师未捷。只有经历，没什么经验。programmer position，写出来请大家
指点。

我比预期提前了接近一个小时到的，因为那天下雨，我也不知道hotel离公司多远（事先
被告知大概15分钟，但秘书特意提醒过不要迟到了）。在公司library看了一会儿书，
group manager（#1）来了，然后去他办公室，听他介绍了公司的几个group和他的几个
subgroup，也问了他一些简单的问题。被再一次问到了为什么要申请这个公司我说朋友推
荐的。然后我说上周的NY Times报道你看了吗他笑说当然了。然后就被领到下一个，#2。
电话邀请里#1已经提到了这次会被问到很多programming。

-------------------
进去后#2已经站在office里的小黑板边上，上面已经写好题目了。架势一看不小我心里就
咯噔了一下。开始做题：
two strings: 1 = text, 2 = command.
a cursor (pointer) to the "text"
command is composed with '+', '-', 'a', 'd':
'+': move forward the cursor to next character of "text".
'-': move backward ...
'a': insert a "character" to "text" at current cursor position. "character"
is decided by a letter followed after 'a'. e.g.: if "commmand" = "+-++ap-",
then insert 'p'.
'd': delete the chracter at current position.

题目不难。答案我就先不写了。
问到用memcpy(newstr+i, newstr+i+1, newstrlen-i)效率高还是直接用循环高。这个取
决于memcpy的memory块大小，我认为是直接循环快，#2也说是。

问到了new分配内存和alloc。void *。具体内容忘了。简单问题。


-------------------
然后#3，subgroup manager
为什么要用virtual destructor。这个问题在第二轮电话面试的时候被问过类似的。感觉
virtual function, abstract base class之类的这个公司很喜欢问。我一开始回答不是
很坚决，只是说i think it should be b/c the derived class will change some
memory part allocated/detroyed by the base class. 后来提醒之后反应过来是因为有
些base class pointer是指向derived class，比如
B *b = new D; ( B = base, D = derived )
delete b;
这时候需要用到virtual destructor for base class。

>>>>
另外关于virtual的问题还有（包括电话面试）
为什么要用virtual？直接在derived class中override行不行？有何区别？
abstract virtual class不可以instantiate，但是有一种情形是必须instantiate的
，是哪种？（这个是电话面试问题，我没答出来但问了答案，但是现在又忘了而且查不到
。哪个高手告诉一下吧，多谢了）。
（没被问过但我觉得有意思的问题：virtual在multiple inheritance中有时候很有用
，比如B->D1, B->D2, 然后DD从D1和D2继承，这时候如果D1 & D2定义了同一个函数，可
能会造成multiple definition。需要用到virtual。具体的参见C++ faq lite－－网址我
放在最后部分）

>>>>>
继续#3：
数组，99元素，如果unique，1-100中miss了一个，怎么办。这个很简单就是求和了。
如果98元素，miss了两个，怎么办？
我想了一会儿没想出来（当然hash table之类可解，但不是他要的答案）。
后来他说用求平方和。这样可以得到两个方程，两个未知数，就可解。
（但是其实这样的运算量并不减少，而且是增加了乘法）。
>>>>>
提问：我请他介绍了一下他的日常工作。

---------------------
#4，subgroup manager

先一个class问题，data member包括int和char*，设计copy constructor和destructor。
>>>>>>

然后写一个abbreviation问题（和上面class无关），比如给了usa，验证是否是
unitedstateofamerica的缩写，条件就是usa这三个字母都出现在后面长串中而且顺序相
同。这个也简单。做之前我问了一下是否需要第一个字母必须相同，得到了赞许。因为这
是abbreviation的常识。

最后是一个简单的金融问题。
比如股票价格走势，x轴时间t，y轴价格p。在t=t1是一股分为两股，这时候单价突然就变
为1/2。但是这个下降并不表示单价下跌了。而在另一个时间比如t=t2，价格确实是贬值
了一半。现在给的图上只有每个时刻的单价走势，how to renormalize the graph such
that you can easily check whether the price is increase or decrease。我一开始
就想到也说了在t=t1把这之后的包括t1的价格乘以2放到图上。然后被问在图上怎么表示
。我就犯了一个很弱的，开始换答案告诉他用derivative可以很直接地看出趋势来，比如
正是升负是降那些拆股点是奇点。很失败，他说你是我面试到的第二个用数学方法的数学
dr了。我的第一个做法是对的。（教训：用对方的语言和简单的语言解答问题）

---------------------
#5
int, char之类的bit大小
这个问题电话面试两轮都问到。第一次我没回答对。很简单可以查到（char=1byte=8bits
, short int=2bytes, int, float, double...和机器有关）。
float的精度？这个我没答出来。谁知道答案的帮忙这里说一下。我自己也会再查。

>>>>
接着，写个算黄金分割数的程序，用Frobenius序列，要求精确到小数点后8位精度。
这个程序简单，记住Frobenius的迭代公式是f(n) = f(n-1) + f(n-2), f(1) = 2, f(2)
= 3。但是精度上我不知道怎么做。我用fabs(f(n) - f(n-1))<1.0e-8，但是我认为不对
，就问他，他说他也不知道该怎么判断才对。

>>>>
统计问题：
[0,1], random generator gives even distributed number (x).
how to get a linear distributed series (y), such that the probability of 0
is 1, and the probability of 1 is 0. (that is, p(y) = 1-y)。
这道题我没有做好。
#5给的答案是用even distributed generator先生成x1，然后生成x2，如果1-x1>x2就
保留x1，否则继续找x1和x2。
我的想法是 dp(y)/dy = -1 = -p(x)，然后用这个来找y应该是x的积分。但是没解出来
。请问谁有这道题的好解法？

>>>>
(int)&((short int*)0->8) = ?
就是在memory里平移之后变成什么。
答案是16，因为每个short int占2 bytes，那么移动8之后就成了16。
我请教后他给了另一个例子
#define offsetof(s, m) (int)&(s*0)->m)
我对位操作memory操作不熟。哪个高手给解释一下？
（另外以前看过一道题：如何判断一个数是2的power？用位操作最快。具体的我又给忘了
，待查）。

然后午饭。感觉这个人还是很nice也对我很满意的。

------------------
#6
简单介绍了一下我的work。然后听他先讲他的work。不停问因此时间消耗了一些。
这个的记忆不是很清楚讲了哪些东西。但是有一个问题我回答很弱。包括他和manager
大概有三个人问到。
-- how do you know about this position/company?
-- i have just graduated and am looking for a job. then my friend introduced
your company to me. i found that it is very strong and its founder is ... who
i heard about long time ago ...
-- did you know about our company before?
-- no.
-- why do you want to work here?
-- i think my .... and programming skills are a good match for this position
and i believe i can do well here.
回答不好。我平时也是有一说一类型，但是对面试这样就不大好了。以后还是一定要准备
一下。（其实这公司是行业no1我怎么吹我如何久仰久仰它都可以的）

>>>>
然后编程题
一组关系表，比如
a ce --> 表示 a depends on c, e
b cdf --> 表示 b depends on c, d, f
c af
d egh
写一个程序表示出这些关联。
这个问题我没做好，不知道该用哪种数据结果最合适。我当时想的是chained linked
list。谁帮忙一下？

-------------------
#7 subgroup manager
先问了一下how often do you programm（还有几个也问了这问题。daily），哪种语言，
怎么学的（我不是cs的我说了刚开始上过c，然后自学c++，news group + books），还学
过哪些课程。然后开始。
max_number_repeat( const char* s, char c )
{
....
}

>>>>
接着一到binary tree。print all nodes。
我用recursion。这是正确答案。然后他问我知道stack吗（我说了我学过数据结构。－－
实话，但现在很多忘了）。知道。用stack可以去掉recursion，重写一个答案。我没想出
来。binary tree是很经典的。在后面一个interviewer问binary search时我就把stack
version想出来了。（教训－－不要轻易说不，多想一下也许就做出来了）

>>>>
sort问题
股票代码都是四字母，比如
ABAD
CFDD
BCWQ
...
如何快速地字母排序？
没有内存限制。我给的答案是先分组然后排序：按第一个字母分组，所有A的在一组，B的
在一组，....，然后在A组里按第二个字母分组，...。内存是2n，速度是4n，线性。
他说对。然后说还可以按最后一个字母先分组。但是这个我现在也没想出来为什么从最后
一个字母先分组也可以（甚至更好？）。谁帮忙解答一下？

--------------------
#8
一个很年轻看起来很友好的小伙子。说没面试过。问了电话面试之后是谁之后说那基本上
不用再考编程了（我当时全部面试完之后出来感觉也很好，但是现在回顾一下才发现其实
很多地方我犯了错误，因此说冤也不冤了）。还是做题。先一个简单的。问了一下
computational cost。

一个数组，N个元素。范围是1-K。
一个random generator。生成0到N-1的数字i，然后print the i-th in array。要求：每
个元素只能被print一次，比如这次生成一个数字6，但是array[6]已经被打印过了，就不
能再打印了。

这也是一个经典问题。但是我没答好。其实这个问题我已经编过很多次了，我用的是如果
array[i] was printed, then check next array[i+1], array[i+2] until find one.
next of array[N-1] is set to be the first array[0]. then u must be able to
find one.
但是这样就不是random了。
他给的答案是：比如第一次，after printing array[i], then move the last element
of the array: array[N-1] to i-th position. then u have a 'full' array with
length = N-1. now call the random generator RG(0,N-2)生成0到N-2的数。以此类推
。
（但是我还是觉得这样的话也不是random的。谁有更好的答案吗？）

---------------------
#9
这是个某组的head。午饭的时候已经遇见过了简单聊过，当时他带另一个interviewee吃
饭（另一个position，没有竞争关系），我还不知道他也要面试我。他先问了一下phd
work，因为之前向一个人解释过，因此比较简单。然后他问你有没有遇到什么challenge
，我。。。。说没有。。。我看过101问也知道这个问题可能被问到。但是我没有准备那
些答案，一个原因是前一阵太忙了要准备很多东西，面试准备的主要时间放在了c++和
perl复习上，另一个原因是过于轻敌了觉得这些问题我会回答好的。而且那天面试到这里
已经比较疲惫但又比较满足（总觉得自己发挥不错），因此在这里就走神了一下。
我想这是致命的错误之一。加上他是Head因此分量太重了。可惜错误不可挽回。

没问题那就开始编程了。
char * replaceSubstring(const char *str, const char *pattern, const char *
replace)
{
...
}
就是找到某个字符串然后替换。
不难但是第一遍我有一个小错误，我前阵子看KMP算法看多了因此在找不到匹配之后指针
就一下跳移了几个（看过Knuth-Morris-Pratt的应该知道我说什么）。他很快提醒然后我
纠正了。然后讨论了一下复杂度。我忘了算strlen(str)需要用到的O(L)。

--------------------
#10
最后一个。
先问了简历上的research部分的一些问题。我解释了一下，但是现在看来回答得不够精练
。
（和#9问题类似。教训：要做好准备，用简单易懂的语言，而且是突出自己这些
experience和求职职位的联系。我回答不好的地方就是没有重点突出一下有啥联系。）他
用荧光笔把简历其中一点重点标示出来。我当时看到了，但没有重点说/吹一下这部分。
唉，现在想来当时真是很木的。

>>>>
然后编程，二叉树的搜索。先写了recursion answer，然后他要non-recursion version
，我说我得回想一下，他说好就是要看看我怎么解答的。我多嘴了一下说i forgot this,
i didn't prepare for it. 他说oh so you have prepared others for interview。我
感觉像是在问我没有真才实学只是背书来考的，赶紧否认。anyway，我不该乱说没必要的
话。然后做出来了。实在是不难，因此后悔前面那个print binary tree的没做出来。

>>>>
最后他说要问一个math question。
a sequence of doors, from 1 to N
1st step: from 1st door to the end, touch all doors -> all open;
2st step: from the 2nd door to the end, touch each other doors (2nd, 4th,
6th, ...) --> odd unchanged (open), even touched and changed (open->closed);
3rd step: from the 3rd door to the end, touch every three doors (3rd, 6rd,
9th, ...), all these 3k-th doors changed (open->closed, closed->open);
4th step: from the 4th door to the end, touch every four doors (4th, 8th,
12th, ...), ...

after N steps: which doors are opened?

这个我想不出来。后来也没时间了因此我问了他答案，好像是看什么约数（或者分解数吧
，比如8 = 2*2*2有三个分解数），具体我再想想。谁有答案的帮忙一下吧。

------------------
最后回到manager。说第二天会开会然后给我消息。然后也提醒了我他们是很picky的。我
说了一下我已经拿到opt了因此随时可以上班。然后提问时间我问了一下这是否新
position（书上的老套问题），上班时间之外大家干啥，他提到了有时候需要work from
home for emergency。我又聊到了research publication问题因为以前看到一个文章是他
们公司的人发的（这是瞎聊了）。然后车快到了就告别了。

-----------------
感觉manager人和大部分interviewers还是很nice的。公司各方面条件都很好。看到这里
大家也许大约能猜到公司类型和我的背景。我学应数的，公司是一个financial的，职位
programmer，不要求financial背景（这也是我觉得fail了很可惜的地方因为不需要准备
financial知识可以省去很多时间精力）。公司的名字我就不说了，去过那公司的从问题
上应该一下子就能看出来。这次申请中几个朋友给我的帮助非常大，虽然他们事先都没见
过我。这让我很感动。这次技术问题实在没有什么难度，其实只要我再细心一点，绝大多
数都是可以做的很好的。我害怕的brain teaser questions没有考到（如果最后一个不算
的话）。因此那天出来之后我对自己很满意也很有信心。失败后打击很大。但是现在看来
犯的错误还是不少。而且那些behavial questions回答实在糟糕。这些都是需要改进的了
。刚开始找工作，以后多向大家学习请教，也请大家对我的这些经历点评指点一下。谢谢
。

电话面试两轮，问到的技术问题有基本的也有刁钻一点的。但除了STL，基本上我以前都
看过，只是有些很久没用了想不起来。我建议大家可以看看C++ FAQ Lite，是news group
上comp.lang.c++的一些常见问题解答集：www.parashift.com/c++-faq-lite/

前面我问了很多问题，哪些高手有时间的话帮忙解答一下吧。多谢了。

--


※ 修改:·tu 于 Jun 12 14:55:14 修改本文·[FROM: 128.97.]
※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 24.127.]