周三晚上参加了一个interview，20分钟做了4道题目，由于时间不够，估计没戏了，现在把题目转给大家看看。我觉得题目出得还可以，并不刁难人，多给几分钟应该都能做出来的。

flying_snow(飞雪浮冰)

1. 给定一个 32bit 的长整型数，写一段程序计算其在二进制的模式下总共有多少个1？

2. Class A;
Class B: Class A;
Class C: Class B;
Class X: Class C;
Class Y;
Class Z: Class Y;
Class MI: Class X,Class Z
问：实例化MI的时候Constructor的先后次序是什么？

3.给定一个数组，内为连续整数{6，4，7，2，1，8，5，9}（未排序），请写出一段优化算法，找出其缺少的那个3。

4. （一些定义的判断，记不完全了，诸如 int i=3.14, char* p = &5 之类的是否正确）

我只做了1，2，4三题，如果再能有几分钟时间，第三道的算法我就可以写完了。可惜可惜！ :-(

(#578245@0)
Last Updated: 2002-6-14
This post has been archived. It cannot be replied.

再贴JAVA的试题 -flying_snow(飞雪浮冰); 2002-6-14 {373} (#578285@0)

1.名词解释
JDOM, ..........共6到7个

2. 实现一个 my.animal 基类，要求有成员函数feed(), walk(),成员变量int status , string name. 实现两个继承类 Dog, Cat, 要求Dog 有 Bark(), Cat 有 Bath(). 最后写一个实例 project, 可以是Cat, 也可以是Dog, 要求完成一个特有的动作Bath() or Bark，并最后打印出name。

3.最后一题是给定xml, dtd, xsl文件，要求找出其中那一段通不过 validation.

关于第三题的优化算法大家有什么好主意？ -flying_snow(飞雪浮冰); 2002-6-14 (#578301@0)

I think you should wait for a while since people are having dinner now. :) -birdswimming(feifei); 2002-6-14 (#578304@0)

yes, you are right, thanks :-) -flying_snow(飞雪浮冰); 2002-6-14 (#578308@0)
are you home? -peerless(红色修罗); 2002-6-14 (#578310@0)

从第一个数开始，在数组内找他的上下邻居，若发现某个上邻或下邻缺，即是。 -gjh(gjh); 2002-6-14 (#578311@0)

效率太低 -sunny_pen(闷的慌); 2002-6-14 (#578314@0)

how about this idea?--用快速冒泡法先排序，在排序过程中加判断，不连续的就是了。 -yfy_ca(老肯); 2002-6-14 (#578318@0)

效率还是不够高，我出考场的时候一下想出来一个算法，只要两个循环就可以了，不知道还有没有更好的。 -flying_snow(飞雪浮冰); 2002-6-14 (#578320@0)

check your email!! please -peerless(红色修罗); 2002-6-14 (#578324@0)
快速冒泡也就是一个嵌套loop而已。 -yfy_ca(老肯); 2002-6-14 (#578343@0)

我想到的是两个单循环，不嵌套的，但下面已经有了最佳答案了：x=(Min+Max)/2*Max - Sum(a(1),..,a(9)) ，我就不献丑了，呵呵：） -flying_snow(飞雪浮冰); 2002-6-14 (#578370@0)

高，不过20分钟想这个出来有难度吧。 -yfy_ca(老肯); 2002-6-14 (#578382@0)

20分钟不止要想出来，还要写出程序，不止这一题，还有其他3题。 :-( -flying_snow(飞雪浮冰); 2002-6-14 (#578385@0)

my idea -sunny_pen(闷的慌); 2002-6-14 {76} (#578328@0)
int s=0;
for (i=0; i<9; i++)
s |= (1<<a[i]);

s ^= 0x1ff;
n=log(s);

谢谢提醒：x=45-a[1]+a[2]+...+a[9]。不过是否太简单了？ -gjh(gjh); 2002-6-14 (#578341@0)

x=(Min+Max)/2*Max - Sum(a(1),..,a(9)) -weber(开悍马不喝酒的令狐冲); 2002-6-14 (#578352@0)

bingle !! :-)) -flying_snow(飞雪浮冰); 2002-6-14 (#578358@0)

多谢前面两位DX引导,有什么奖励:-p -weber(开悍马不喝酒的令狐冲); 2002-6-14 (#578373@0)

嘿嘿，我可没有什么奖励啊，我当时没有想出来，考试失败了，还得继续补习，继续找工作，呵呵:-P 倒是真的发现这个坛子里真是藏龙卧虎，佩服佩服啊！ -flying_snow(飞雪浮冰); 2002-6-14 (#578377@0)

说定了，一定来？^_^ -peerless(红色修罗); 2002-6-14 (#578379@0)

一定！ -flying_snow(飞雪浮冰); 2002-6-14 (#578383@0)

另外想问问你用了多少时间？我想估算一下是否当天考试的人都能在20分钟内完成。 -flying_snow(飞雪浮冰); 2002-6-14 (#578380@0)

用了一分钟确定一下从1加到10是否等于(1+10)/2*10 :-) -weber(开悍马不喝酒的令狐冲); 2002-6-14 (#578400@0)

呵呵，完蛋了，forget it，继续努力。 -flying_snow(飞雪浮冰); 2002-6-14 (#578406@0)

放心放心,前面两位DX还帮我想了20分钟呢. 对于做IT的DX说不定这是个trap,幸亏小弟我不是玩这门的. -weber(开悍马不喝酒的令狐冲); 2002-6-14 (#578414@0)

是啊，晚上5点半开始考的，饿得发晕，气氛又紧张，愣是没有想到这个公式，sigh，不过还是佩服上面几位......搞编程的就是要熟悉数学模型啊！ -flying_snow(飞雪浮冰); 2002-6-14 (#578421@0)

请教：第二题如何构造？ -gjh(gjh); 2002-6-14 (#578381@0)

从最基类开始构造，一层一层向下。但我还是有点吃不准Class X 和 Class Z 到底是否按照先后次序来构造。有谁可以给出正确的答案么？ -flying_snow(飞雪浮冰); 2002-6-14 (#578395@0)

构造的先后次序是A, B, C, X, Y, Z，个人认为啃腚没什么问题。 -xanada(㊣流水); 2002-6-14 (#578506@0)

绝对是ABCXYZ, 我刚验证了。 -ron2000(ron); 2002-6-18 {748} (#583894@0)
#include <iostream>
using namespace std;

class A
{
public:
A() {cout << "Call A constructor!" << endl;}
};

class B : public A
{
public:
B() {cout << "Call B constructor!" << endl;}
};

class C : public B
{
public:
C() {cout << "Call C constructor!" << endl;}
};

class X : public C
{
public:
X() {cout << "Call X constructor!" << endl;}
};

class Y
{
public:
Y() {cout << "Call Y constructor!" << endl;}
};

class Z : public Y
{
public:
Z() {cout << "Call Z constructor!" << endl;}
};

class MI : public X, public Z
{
};

main()
{
MI m;

}

OUTPUT:
Call A constructor!
Call B constructor!
Call C constructor!
Call X constructor!
Call Y constructor!
Call Z constructor!

谢谢！我这题答对了 :-)) -flying_snow(飞雪浮冰); 2002-6-18 (#583898@0)

问点别的... -linshell(shell); 2002-6-14 {84} (#578558@0)
请问浮冰： 1 你投简历后多久收到的面试通知？
2 你有加国经验是吗？
谢谢。

1.我投简历以后5个月这是第一个面试，2.我只有1年半的加拿大工作经验。 -flying_snow(飞雪浮冰); 2002-6-15 (#578963@0)

这个算法比我的好，只用了一个循环 -flying_snow(飞雪浮冰); 2002-6-14 (#578350@0)

其实只需要一个循环，找出了最小值(Min)后，最大值Max = Min + 8 (其中‘8’为数组中元素的个数). 或者先找最大值Max ，原理相同。 -naughtyfish(naughtyfish); 2002-6-20 (#589558@0)

log2(s)是log(s)吗?底是默认的吗？ -nnm(nnm); 2002-6-14 (#578565@0)
If there are more than 32 number, what will happen? -ron2000(ron); 2002-6-18 (#584593@0)

所有的数累加，然后拿45减去累加和，剩几就是少几。比如少3，那么1+2 +4+5+6+7+8+9=42。 -chenql26(不懂); 2002-6-15 (#578939@0)
可否用45（1+2+...+9）与数组的和比较差几就缺第几位数。 -chipshoot(天天向上); 2002-6-17 (#583680@0)
只用一个循环就可以,用55-SUM(ARRAY),得几缺的就是几,不知道这样行不吗? -bigwolf(大灰狼); 2002-6-19 (#588008@0)

咦？发现重大错误！x=(Min+Max)/2*Max - Sum(a(1),..,a(9)) 不对，试想如果数组从6开始到14怎么办？不过这个算法稍加修改就可以了，呵呵 :-)) -flying_snow(飞雪浮冰); 2002-6-14 (#578438@0)

是啊是啊, x=(Min+Max)*2/(Max-Min+1) - Sum (a(1)...a(8)) 惭愧惭愧 -weber(开悍马不喝酒的令狐冲); 2002-6-14 (#578464@0)

x=(Min+Max)*2/(Max-Min+1) - Sum 就可以了呀，不用太复杂的 -hugefox(长得象熊的狐狸); 2002-6-14 (#578465@0)

我说的Sum(a(1)...a(8))就是你说的Sum. :-pp -weber(开悍马不喝酒的令狐冲); 2002-6-14 (#578480@0)
是不是(min+max)/2*(max-min+1)-sum,前面的公式我不懂啊；还有log2(s)是n=log(s)吗 -nnm(nnm); 2002-6-14 (#578559@0)

看不懂,min, max 怎么来,还不是要扫一个循环.还是用45减SUM最简单. -eggplant(老茄子); 2002-6-15 (#578969@0)

可首先你得知道不通过最大，最小值怎么得到45？ -naughtyfish(naughtyfish); 2002-6-20 (#589569@0)

大家都这么厉害呀，我还在想第一题了。惨。应该有优化算法吧，我是把它转为16进制后再判断。我记得好像可以用与或来算似的。 -happy_life(happy_life); 2002-6-14 (#578490@0)

The answer of number 1. -ron2000(ron); 2002-6-18 {265} (#584004@0)
//IN: the number want to be checked
//RET: the number of the 1
GetTheNumber(unsigned int nData)
{
int lnNum = 0;
unsigned lnData = nData;

for (int i = 0; i < 32; i ++)
{
if (lnData & 0x00000001L)
lnNum ++;
lnData >>= 1;
}
return lnNum;
}

easy for question 3. you should sort it first, then binary search. that's it. -jami(jami); 2002-6-18 (#584283@0)

That's not the best, you may lose points if you do like this. -yuanzidan(原子弹); 2002-6-18 (#584448@0)

No, but simple way is better. don't make it complicated. -jami(jami); 2002-6-18 (#584611@0)

Well, 优化算法 means making the complexity of your algorithm as low as possible. There are some more SIMPLE ways than Sorting+Binary search, but they are bad. -yuanzidan(原子弹); 2002-6-18 {76} (#584824@0)
The complexcity is the critical point for this question, and is the purpose.

as for question 1, you need to do two steps: bit-check and shift -jami(jami); 2002-6-18 {388} (#584631@0)

if you are not familiar with the bit operation and bit test, the simple way can be:
int bitOneCount( int x)
{
int bitOneCounter = 0;
while (x)
{
/* check if if the bit0 is '1' */
if (x%2)
bitOneCounter ++;
/* shift right for checking next bit*/
x = x/2;
}
return bitOneCounter;
}

fogive me to speak frankly, flying_snow is not likely a programmer graduated from computer science. -jami(jami); 2002-6-18 (#584641@0)

我是转行自学的C++。 -flying_snow(飞雪浮冰); 2002-6-18 (#584961@0)

Recomend a good book: effective C++, perhap you're know it. -jami(jami); 2002-6-18 (#585181@0)

Counting Sort can do it within linear time -goodbody(good_body); 2002-6-19 (#586623@0)

问一句，您这是面试什么职位？ C++ programmer? 什么样的公司？谢谢。 -whatrudoing(whatIamdoing?); 2002-6-19 (#588119@0)

C++ programmer, 大型软件公司，5000 employees globle -flying_snow(飞雪浮冰); 2002-6-19 (#588124@0)

多谢。 -whatrudoing(whatIamdoing?); 2002-6-19 (#588139@0)

my code for question 3 -newtale(newtale); 2002-6-22 {328} (#594410@0)

总结大家的想法，写一小段程序, 请看看对不对？

int check(int length, int *a)
{
int min=*a;
int sum=*a;

for(int i=1; i<length; i++){
sum += a[i];
if (a[i]<min) min = a[i];
}

return ( (min+min+length-1)*length/2 - sum );
}

return((min+min+length-1)*length/2

延伸一下: 如果你并不知道1..100中缺少的几个数字呢?? -gugu(GuGu); 2002-6-22 (#594436@0)

@Las Vegas

周三晚上参加了一个interview，20分钟做了4道题目，由于时间不够，估计没戏了，现在把题目转给大家看看。我觉得题目出得还可以，并不刁难人，多给几分钟应该都能做出来的。

Replies, comments and Discussions:

More Topics