Google校园招聘题: 程序员买房

Google的2011年校园招聘宣讲会分别在北大和清华举行,其中北大本来是350人的会场,去了大约600多人,爆满,那场面绝对是人山人海, 彩旗飘飘。经过了大约一个小时多的宣讲和问答,开始现场笔试环节,一共10个选择题和三个算法题,只有选择题答对了6个以上的人才有机会让面试官看你后面 的算法题。然后明天下午会通知笔试通过的人进行面试,Google的效率就像其搜索引擎一样迅速,效率可见一般。

其中前10个选择题中有一个特别雷人的,题如下:

现在北京有一套房子,价格200万,假设房价每年上涨10%,一个软件工程师每年固定能赚40万。如果他想买这套房子,不贷款,不涨工资,没有其他收入,每年不吃不喝不消费,那么他需要几年才能攒够钱买这套房子?

A, 5年

B, 7年

C, 8年

D, 9年

E, 永远买不起

Continue reading “Google校园招聘题: 程序员买房”

面试中常见的一些算法问题

Problem 1 : Is it a loop ? (判断链表是否有环?)

Assume that wehave a head pointer to a link-list. Also assumethat we know the list is single-linked. Can you come up an algorithm to checkwhether this link list includes a loop by using O(n) time and O(1) space wheren is the length of the list? Furthermore, can you do so with O(n) time and onlyone register?

方法:使用两个指针,从头开始,一个一次前进一个节点,一个前进2个节点,则最多2N,后两个指针可以重合;如果无环,则正常停止。同样的,可以找到链表的中间节点。同上。

Continue reading “面试中常见的一些算法问题”

将一个数组的元素顺序打乱

给定一个数组,要求把数组内元素的顺序随机打乱,然后输出,主要是要保证效率。

这个算法其实简单,首先从所有元素中随机选取一个与第一个元素进行交换,然后在第二个之后选择一个元素与第二个交换,直到最后一个元素。这样能确保每个元素在每个位置的概率都是1/n。代码如下:

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <time.h>  
  4.   
  5. // 随机打乱一个数组  
  6. void random(int a[], int n)  
  7. {  
  8.     int index, tmp, i;  
  9.     srand(time(NULL));  
  10.     for (i = 0; i <n; i++)  
  11.     {  
  12.         index = rand() % (n – i) + i;  
  13.         if (index != i)  
  14.         {  
  15.             tmp = a[i];  
  16.             a[i] = a[index];  
  17.             a[index] = tmp;  
  18.         }  
  19.     }  
  20. }  
  21. int main()  
  22. {  
  23.     int a[] = {1, 2, 3, 4, 5};  
  24.     int i;  
  25.     random(a, 5);  
  26.     for (i = 0; i < 5; i++)  
  27.         printf(“%d “, a[i]);  
  28.     printf(“\n”);  
  29.     system(“pause”);  
  30.     return 0;  

 

把一个数组的顺序打乱,很常用的算法,比如洗牌。

下面用Java实现:

  1. import java.util.Random;    
  2.     
  3. public class RandomSort {    
  4.     private Random random = new Random();    
  5.     //数组大小    
  6.     private static final int SIZE = 10;    
  7.     //要重排序的数组    
  8.     private int[] positions = new int[SIZE];    
  9.         
  10.     public RandomSort() {    
  11.         for(int index=0; index<SIZE; index++) {    
  12.             //初始化数组,以下标为元素值    
  13.             positions[index] = index;    
  14.         }    
  15.         //顺序打印出数组的值    
  16.         dwn();    
  17.     }    
  18.         
  19.     //重排序    
  20.     public void changePosition() {    
  21.         for(int index=SIZE-1; index>=0; index–) {    
  22.             //从0到index处之间随机取一个值,跟index处的元素交换    
  23.             exchange(random.nextInt(index+1), index);    
  24.         }    
  25.         dwn();    
  26.     }    
  27.         
  28.     //交换位置    
  29.     private void exchange(int p1, int p2) {    
  30.         int temp = positions[p1];    
  31.         positions[p1] = positions[p2];    
  32.         positions[p2] = temp;    
  33.     }    
  34.         
  35.     //打印数组的值    
  36.     private void dwn() {    
  37.         for(int index=0; index<SIZE; index++) {    
  38.             System.out.print(positions[index]+” “);             
  39.         }    
  40.         System.out.println();    
  41.     }    
  42.     
  43.     public static void main(String[] args) {    
  44.         RandomSort rs = new RandomSort();    
  45.         rs.changePosition();    
  46.         rs.changePosition();    
  47.         rs.changePosition();    
  48.     }    
  49. }   
 

不过由于随机数产生器产生的随机数不太随机,所以排序的结果页有很多相似的地方。换一个好的随机数产生器,会达到更好的效果,就能用于洗牌了。
 
 
 
 
 
 

利用数组索引进行排序

看到一道算法面试题,比较有趣,我自己用C做了一下。

题目:随机生成10个100以内的整数,把数据从小到大排序,而且算法复杂度只能是1。

这个算法比较有意思的地方是,首先建立一个数组B,其元素个数为数组A的最大元素值,然后用A的元素作为B的数组下标,然后给存在的B元素赋值,这样就可以用循环把下标输出出来。

C程序如下:

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <time.h>  
  4. #define random(x) (rand()%x)  
  5.   
  6. main()  
  7. {  
  8.     int lengthA, lengthB, i;  
  9.     int wait;  
  10.       
  11.     int arrayA[10]; // 定义一个数组  
  12.     int arrayB[101];  
  13.     srand(time(NULL)); // 让每次产生的随机数都不一样  
  14.   
  15.     lengthA = sizeof(arrayA) / sizeof(arrayA[0]);  
  16.     lengthB = sizeof(arrayB) / sizeof(arrayB[0]);  
  17.           
  18.     // 给数组赋值  
  19.     for(i = 0; i < 10; i++)  
  20.         arrayA[i] = random(100);  
  21.   
  22.     printf(“随机生成的数组A的元素为 \n”);  
  23.   
  24.     // 输出数组  
  25.     for(i = 0; i < 10; i++)  
  26.         printf(“%d\n”, arrayA[i]);  
  27.   
  28.     for (i = 0; i < lengthA; i++)  
  29.     {  
  30.         arrayB[arrayA[i]] = 101;  
  31.     }  
  32.   
  33.     printf(“排序后的结果为\n”);  
  34.   
  35.     for (i = 0; i < lengthB; i++)  
  36.     {  
  37.         if (arrayB[i] == 101)  
  38.             printf(“%d\n”, i);  
  39.     }  
  40.   
  41.     //printf(“%d”, lengthA);  
  42.     scanf(“%d”, &wait);  

 

程序运行结果:
随机生成的数组A的元素为
79
62
87
43
32
52
72
88
44
53
排序后的结果为
32
43
44
52
53
62
72
79
87
88

 

裴波那契数列

1, 1, 2, 3, 5, 8, 13, 21, 34, 55… 这个数列称为 fibonacci 数列。

当 n 大于1的时候,这个数列的第n项的值是它前面两项之和。

下面的程序用于打印出fibonacci 数列:

  1. <?php  
  2. for($i=0; $i<10; $i++)  
  3. {  
  4.     $result = fibonacci($i);  
  5.     echo $result.‘<br />’;  
  6. }  
  7.   
  8. function fibonacci($number)  
  9. {  
  10.     if($number <= 1)  
  11.     {  
  12.         return 1;  
  13.     }  
  14.     return fibonacci($number – 1) + fibonacci($number – 2);  
  15. }  
  16. ?> 

 

 

程序运行结果为:
1
1
2
3
5
8
13
21
34
55