一个google intern的面试题

Edengundam

原帖由 ArXoR 于 2006-12-15 12:15 发表


。。。还是不行，取完最值还得维护堆性质。。。还要O(logn)...^_^

恩, heap..看过一次, 现在已经忘记差不多了...名字都记不住了....刚才想了至少半个小时才....太丢人了

emacsnw

原帖由 frog_skywalker 于 2006-12-13 18:18 发表
正整数集合s={a1,a2...an}
存在ai*aj=ak, i!=j!=k
求最大的ak


想不到什么好的办法，加法还好办点
现在我是排序，从最大的开始找。
要找的数开根号，以此分成高列，低列。从中间开始乘，往两边移动。

...

加法也不好办吧。由于都是正数，所有数取个log后等价与于对应加法的问题。

dzbjet

原帖由 frog_skywalker 于 2006-12-14 10:18 发表
正整数集合s={a1,a2...an}
存在ai*aj=ak, i!=j!=k
求最大的ak


想不到什么好的办法，加法还好办点
现在我是排序，从最大的开始找。
要找的数开根号，以此分成高列，低列。从中间开始乘，往两边移动。

...

每次相乘的结果，例如n1 * n2 = n， 查找 n 是否与 a(i)  ( 1 <= i <= n ) 匹配，匹配，做做个记号。

从最大开始找，找到做了记号的a(i)，算法结束。

crspo

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <math.h>
   
5. 
   
6. void inline swap(int *x,int *y)
   
7. {
   
8.   int tmp;
   
9.   tmp=*x;
   
10.   *x=*y;
    
11.   *y=tmp;
    
12. }
    
13. 
    
14. 
    
15. void max_heapify(int a[],int i,int j)
    
16. {
    
17.   int k=i;
    
18.   int ind;
    
19.   while(2*k+1<=j){
    
20.     ind=2*k+1;
    
21.     if(ind+1<=j && a[ind+1]>a[ind])
    
22.         ind++;
    
23.     if(a[k]<a[ind])
    
24.       swap(a+k,a+ind);
    
25.     k=ind;
    
26.   }
    
27. }
    
28. 
    
29. void build_heap(int a[],int i,int j)
    
30. {
    
31.   int k;
    
32.   for(k=(j-1)/2;k>=0;k--)
    
33.     max_heapify(a,k,j);
    
34. }
    
35. 
    
36. void heap_sort(int a[],int n)
    
37. {
    
38.   int k;
    
39.   build_heap(a,0,n);
    
40.   for(k=n;k>=1;k--){
    
41.     swap(a,a+k);
    
42.     max_heapify(a,0,k-1);
    
43.   }
    
44. }
    
45. 
    
46. int bin_search(int a[],int key,int i,int j)
    
47. {
    
48.   int low=i;
    
49.   int high=j;
    
50.   int mid;
    
51.   while(low<=high){
    
52.     mid=(low+high)/2;
    
53.     if(key==a[mid])
    
54.       return mid;
    
55.     else if(key<a[mid])
    
56.       high=mid-1;
    
57.     else
    
58.       low=mid+1;
    
59.   }
    
60.   return -1;   
    
61. }
    
62. 
    
63. int bin_locate(int a[],int key,int i,int j)
    
64. {
    
65.   int low=i;
    
66.   int high=j;
    
67.   int mid;
    
68.   while(high-low>1){
    
69.     mid=(low+high)/2;
    
70.     if(key==a[mid])
    
71.       return mid;
    
72.     else if(key<a[mid])
    
73.       high=mid-1;
    
74.     else
    
75.       low=mid+1;
    
76.   }
    
77.   return low;
    
78. }
    
79. 
    
80. int gog(int a[],int n)
    
81. {
    
82.   int i,j;
    
83.   int ind1,ind2;
    
84.   heap_sort(a,n);
    
85.   for(i=n;i>=0;i--){
    
86.     if(sqrt(a[i])<a[0]) continue;
    
87.     ind1=bin_locate(a,sqrt(a[i]),0,n);
    
88.     for(j=0;j<=ind1;j++){
    
89.       if(a[i]%a[j]==0){
    
90.         ind2=bin_search(a,a[i]/a[j],ind1+1,i-1);
    
91.         if(ind2>=0){
    
92.           printf("%d*%d=%d\n",a[j],a[i]/a[j],a[i]);
    
93.           return 0;
    
94.         }
    
95.       }
    
96.     }
    
97.   }
    
98.   return -1;
    
99. }
    
100. 
     
101. int main(void)
     
102. {
     
103.   int i;
     
104.   int test[10]={13,13,12,11,10,9,8,7,4,1};
     
105.   gog(test,9);
     
106.   system("pause");
     
107.   return 0;
     
108. }
     
109. 
     

复制代码

写了个n(3/2)*logn的程序，不知道对错

ArXoR

原帖由 crspo 于 12/17/06 11:32 发表
[code]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void inline swap(int *x,int *y)
{
  int tmp;
  tmp=*x;
  *x=*y;
  *y=tmp;
}


void max_heapify(int a ...

hash表就好了，不用最内层的二分，省掉O(logn)

ArXoR

原帖由 crspo 于 12/17/06 11:32 发表
[code]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void inline swap(int *x,int *y)
{
  int tmp;
  tmp=*x;
  *x=*y;
  *y=tmp;
}


void max_heapify(int a ...

而且只是复杂度期望是O(n^(3/2))，不是理论最坏界
开方不一定能到达sqrt(n)
比如
2,2^2,2^4,2^8...

crspo

原帖由 ArXoR 于 2006-12-17 12:09 发表


而且只是复杂度期望是O(n^(3/2))，不是理论最坏界
开方不一定能到达sqrt(n)
比如
2,2^2,2^4,2^8...

谢谢，我也发现这个问题了，有点大意了。没有比O(n^2)更好的算法吗？