论坛首页 招聘求职论坛

Nortel一道笔试题

浏览 3763 次
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2006-11-10  
  我没有参加Software Engineer的考试,错投了Product Test Engineer,搞得面试的时候没什么优势,不然说不定也有二面的机会给我。

   这道题目是同学基本表述出来的,大意是从一堆人中找出明星,明星的条件是其他人都认识他,但他不认识其他人。题目的一个限制是效率要在O(n2)之下。短短时间之内,好象基本没有同学搞定。今天早上,花了将近一个小时的时间把这个问题解决了。其间想到很多概念,回溯,分治好象不可行哈,呵呵还是挺有意思的。

   由此而看,就是一个行列式,可以定义如下,二阶数组a[n][n];

  
int query(int[4][4] a,int size);

   int main(){
     int a[4][4]={{1,1,0,1},{0,1,0,0},{0,1,1,0},{0,1,1,1}};
     cput<<query(a,4);
   }
   //这里需要的一个前提就是行列式必须是符合题目要求的
   int query(int[4][4] a,int size){
     int i=0;
     for(int j=i+1;j<n;j++)
   //对称位置不等才符合要求,且要求是明星潜质才行哦(a[j][i]==0)
       if(a[i][j]!=a[j][i]&&a[j][i]==0)
         i=j;
     return i;
   }


  
   涉及到的主要思想就是避免不必要的扫描啦,从前往后扫描,前面的不符合要求就直接往后跳,写的时候还记起kmp,开始的时候还以为需要象八皇后那样需要回溯呢,后发现no,他的内容是已经给定的。
   发表时间:2006-11-15  
算法效率最重要
0 请登录后投票
论坛首页 招聘求职版

跳转论坛:
Global site tag (gtag.js) - Google Analytics