Chinaunix

标题: 看看这两个面试题 [打印本页]
作者: _mystic    时间: 2009-08-05 14:06
标题: 看看这两个面试题
昨天去了的笔试题，这是最后两个题。


1.
void func0(void);
void func1(void);
void func2(void);
void func3(void);
void func4(void);
void func5(void);

int MAIN(int N)
{
    if(N == 0) 执行func0;
    if(N == 1) 执行func1;
    if(N == 2) 执行func2;
    if(N == 3) 执行func3;
    if(N == 4) 执行func4;
    if(N == 5) 执行func5;
}



不使用 if 或是 switch 判断语句。

2.
void func0(void);
void func1(void);
void func2(void);
void func3(void);
void func4(void);
void func5(void);

int MAIN(int N)
{
    if(N == 33) 执行func0;
    if(N == 67) 执行func1;
    if(N == 150) 执行func2;
    if(N == 274) 执行func3;
    if(N == 331) 执行func4;
    if(N == 556) 执行func5;
}

问用什么方法能使得，执行的速度最快。

第一个题，我用的是 条件语句。
出来后想到了用函数指针数组更好。人家考的本意应该也是用函数指针数组吧！！

void func0(void);
void func1(void);
void func2(void);
void func3(void);
void func4(void);
void func5(void);

/* An array of 6 pointers to functions that take an void argument and return void */
void (*fun[6])(void)

int MAIN(int N)
{
    fun[0] = func0;
    fun[1] = func1;
    fun[2] = func2;
    fun[3] = func3;
    fun[4] = func4;
    fun[5] = func5;

    fun[N];
}


第二个问题， 想了想没有什么思路，大家有什么高见啊?
其中N== 33 N==67 后面的值是我自己瞎编的！！！忘了。
但我想和这个值应该没什么关系。 我搞不懂他要考的是什么？
有什么东西可以不用判断，就可以选择执行的，而且效率还高？

[ 本帖最后由 _mystic 于 2009-8-5 14:15 编辑 ]
作者: 青菜吃蟲    时间: 2009-08-05 14:11
提示: 作者被禁止或删除 内容自动屏蔽
作者: _mystic    时间: 2009-08-05 14:16
标题: 回复 #2 青菜吃蟲 的帖子
啊！！ 建立一个500多的数组？？
作者: epegasus    时间: 2009-08-05 14:22
原帖由 _mystic 于 2009-8-5 14:16 发表
啊！！ 建立一个500多的数组？？

33=32+1
67=64+3
也许后面的值都比较特殊呢?
作者: DQP    时间: 2009-08-05 14:23
第二个问题， 想了想没有什么思路，大家有什么高见啊?
其中N== 33 N==67 后面的值是我自己瞎编的！！！忘了。
但我想和这个值应该没什么关系。 我搞不懂他要考的是什么？
有什么东西可以不用判断，就可以选择执行的，而且效率还高？

很有可能是跟数字有关的
33 % 33 == 0
67 % 33 == 1
估计题目是让你建立一个简单的hash
作者: hellioncu    时间: 2009-08-05 14:30
原帖由 _mystic 于 2009-8-5 14:16 发表
啊！！ 建立一个500多的数组？？



也未尝不可呀，简单明了
作者: _mystic    时间: 2009-08-05 15:17
标题: 回复 #4 epegasus 的帖子
嗯 有可能！ 呵呵 不过这样的话，这个公司够无聊的了！等于前面的问题再加个小学数学！~
不过，我想他应该想问的不单单是这个~  C语言里有没有一个执行这种判断时效率很高的方法哪？
作者: _mystic    时间: 2009-08-05 15:18
原帖由 DQP 于 2009-8-5 14:23 发表

很有可能是跟数字有关的
33 % 33 == 0
67 % 33 == 1
估计题目是让你建立一个简单的hash



这样的效率会高吗，比起用函数指针数组？
作者: DQP    时间: 2009-08-05 15:22
标题: 回复 #8 _mystic 的帖子
就是多了一步

  2.     fun[0] = func0;
  3.     fun[1] = func1;
  4.     fun[n % 33];
复制代码
作者: aaaaa5aa    时间: 2009-08-05 15:32
大家想得太简单了，如果是N＝＝99呢，那执行哪一个？
作者: aaaaa5aa    时间: 2009-08-05 15:34
第一题 我也没看懂LZ的意思，那样就效率高？

你的判断又在哪呢
作者: DQP    时间: 2009-08-05 15:50
原帖由 aaaaa5aa 于 2009-8-5 15:32 发表
大家想得太简单了，如果是N＝＝99呢，那执行哪一个？

我没看到题目 我是猜得
如果有99肯定不这么做
作者: baopbird2005    时间: 2009-08-05 15:50
作者: DQP    时间: 2009-08-05 15:51
原帖由 aaaaa5aa 于 2009-8-5 15:34 发表
第一题 我也没看懂LZ的意思，那样就效率高？

你的判断又在哪呢

没啥高效的就是省去 if 或 switch了
作者: _mystic    时间: 2009-08-05 15:56
呵呵 不过函数指针确实要比if去一个个判断要来的快啊
作者: 虑而后能得    时间: 2009-08-05 16:19
main函数中可以有参数int n 吗 第一次见到啊

曾尝试使用枚举来做 发现对常量不管用

[ 本帖最后由 虑而后能得 于 2009-8-7 22:03 编辑 ]
作者: _mystic    时间: 2009-08-05 16:20
原帖由 虑而后能得 于 2009-8-5 16:19 发表
main函数中可以有参数int n 吗 第一次见到啊


呵呵 你看错了~ 是MAIN函数, 不是mian....
作者: whoami2003    时间: 2009-08-05 19:25
使用hashmap搞。
作者: lxdiyun    时间: 2009-08-05 21:05
void (*fun[8])(void);

fun[0] = func2;
fun[1] = func4;
fun[2] = NULL;
fun[3] = func0;
fun[4] = func3;
fun[5] = NULL;
fun[6] = func6;
fun[7] = func1;

fun[N & 0x7]();

位操作时间最短
作者: mjus    时间: 2009-08-05 22:30
void (*fun[8])(void);
index=hash=N%10;
set fun[2]=fun[5]=NULL

done !
作者: 网鬼    时间: 2009-08-05 22:44
函数指针数组
作者: _mystic    时间: 2009-08-06 00:35
原帖由 mjus 于 2009-8-5 22:30 发表
void (*fun[8])(void);
index=hash=N%10;
set fun[2]=fun[5]=NULL

done !


我看的有点晕。。。解释一下，可以吗？
作者: mjus    时间: 2009-08-06 02:56
OK. see
N=33,   index=hash=33%10=3
N=67,   index=hash=67%10=7
N=150  index=hash=150%10=0
N=274  index=hash=274%10=4
N=331  index=hash=331%10=1
N=556  index=hash=556%10=6


fun[0]=[150%10]=func2;
fun[1]=[331%10]=func4;
fun[2]=NULL;
fun[3]=[33%10]=func0;
fun[4]=[274%10]=func3;
fun[5]=NULL;
fun[6]=[556%10]=func5;
fun[7]=[67%10]=func1;

Basically, it is just a hash mapping !

Strictly speaking, given a set of data, using perfect hashing is better. Of course,
this can't be done in a limited time in a test.
作者: zphjita    时间: 2009-08-06 17:44
原帖由 mjus 于 2009-8-6 02:56 发表
OK. see
N=33,   index=hash=33%10=3
N=67,   index=hash=67%10=7
N=150  index=hash=150%10=0
N=274  index=hash=274%10=4
N=331  index=hash=331%10=1
N=556  index=hash=556%10=6


fun[0]=[150%10 ...


Are you a 外国人？
作者: _mystic    时间: 2009-08-07 16:50
原帖由 mjus 于 2009-8-6 02:56 发表
OK. see
N=33,   index=hash=33%10=3
N=67,   index=hash=67%10=7
N=150  index=hash=150%10=0
N=274  index=hash=274%10=4
N=331  index=hash=331%10=1
N=556  index=hash=556%10=6


fun[0]=[150%10 ...


嗯 好像明白了~~
要是对10取余后，有两个一样的怎么办？
33%10 = 3
要是还有有93哪？ 93 % 10 = 3
作者: snyh    时间: 2009-08-07 17:08
第二题大家想多了吧？

你再建立一个数组 a[] = { 63, 41, 145,..};
fun[0] = func0;
fun[1] = func1;
.........
以上内容在函数外面初始化  否则谈不上效率。。。每次都执行。。。如果只执行一次 应该可以不算时间的。。。

for (i = 0; a［i] != N; i++);
fun［i];


不过 我不觉得函数指针会比直接用if else快  （除非你是把我说的那些初始化代码放到外面。。否则还不如直接if else)
因为函数指针要2次 * 才能找到函数入口地址。。。。

[ 本帖最后由 snyh 于 2009-8-7 17:10 编辑 ]
作者: snyh    时间: 2009-08-07 17:15
不过这个还是O(n) ...
hash 是O(1)
只是 几个数还好 。多了找一个合适的哈西函数 似乎比较难。。。。少了的话。。。我觉得这个n就跟1差不多了
作者: lgqss    时间: 2009-08-08 20:03
为什么执行不是(*fun[N])()这样的指针放那边就会执行吗？
作者: folklore    时间: 2009-08-08 21:14
原帖由 _mystic 于 2009-8-5 14:06 发表
昨天去了的笔试题，这是最后两个题。


1.
void func0(void);
void func1(void);
void func2(void);
void func3(void);
void func4(void);
void func5(void);

int MAIN(int N)
{
  &nb ...


1.

  2. int MAIN(int N){
  3. typedef void(*DispatchFun)(void);
  4. static DispatchFun funarray[]={
  5.   fun0,fun1,fun2,fun3,fun4,fun5
  6. };
  7. if(N>=0&&N<sizeof(funarray)/sizeof(funarray[0])) funarray[N]();
  8. else return -1;
  9. returun 0;
  10. }
复制代码


2.

  2. void nop(void){}
  3. int MAIN(int N){
  4. typedef void(*DispatchFun)(void);
  5. static DispatchFun funarray[]={
  6.   func2, //150%10
  7.   func4, //331%10
  8.   nop,   //none
  9.   func0, //33%10
  10.   func3, //274%10
  11.   nop,   //none
  12.   func5 //556%10
  13.   func1 //67%10
  14. };
  15. if(N>=0&&N<sizeof(funarray)/sizeof(funarray[0])) funarray[N]();
  16. else return -1;
  17. returun 0;
  18. }
复制代码
作者: folklore    时间: 2009-08-08 21:19
标题: 没有
但你可以自已做一个~~
作者: zjzfb    时间: 2009-08-08 23:13
不用if/else，不检查参数吗？
作者: starwing83    时间: 2009-08-08 23:24
那个，GNU不是有个prefect hash的程序么？叫啥名字来着？
作者: mymsnzxw    时间: 2009-08-09 09:35
第一个用数组，第二个用二分法，，
作者: jallyx    时间: 2009-08-10 08:30
这种题目出得可真够无聊的，想必出题的人纯属NC
突然想起，要是偶也遇到这种题目了的话，那就笑了
作者: yaoaiguo    时间: 2009-08-10 09:56
用switch就行了，效率能低到哪里去？
作者: yylogo    时间: 2009-08-10 18:09
不检查参数啊`就和前面一个人说的一样...
如果数据是99怎么办呢?



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2