注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

众里寻他千百度,名师成就满分路

AP 微积分 AP 计算机 腾飞的博客

 
 
 

日志

 
 
关于我

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献!

网易考拉推荐

AP 计算机 微软,谷歌,雅虎,华为,百度,网易,创新工场面试题目 转载  

2015-11-03 16:46:00|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转载博客http://blog.csdn.net/v_july_v/article/details/6870251

3.求子数组的最大和
题目:
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。
ANSWER: 
A traditional greedy approach.
Keep current sum, slide from left to right, when sum < 0, reset sum to 0.

int maxSubarray(int a[], int size) {
  if (size<=0) error(“error array size”);
  int sum = 0;
  int max = - (1 << 31);
  int cur = 0;
  while (cur < size) {
    sum += a[cur++];
    if (sum > max) {
      max = sum;
    } else if (sum < 0) {
      sum = 0;
    }
  }
  return max;
}

5.查找最小的k 个元素
题目:输入n 个整数,输出其中最小的k 个。
例如输入1,2,3,4,5,6,7 和8 这8 个数字,则最小的4 个数字为1,2,3 和4。
ANSWER:
This is a very traditional question...
O(nlogn): cat I_FILE | sort -n | head -n K
O(kn): do insertion sort until k elements are retrieved.
O(n+klogn): Take O(n) time to bottom-up build a min-heap. Then sift-down k-1 times.
So traditional that I don’t want to write the codes...
Only gives the siftup and siftdown function.

/**
 *@param i the index of the element in heap a[0...n-1] to be sifted up
void siftup(int a[], int i, int n) {
  while (i>0) {
    int j=(i&1==0 ? i-1 : i+1);
    int p=(i-1)>>1;
    if (j<n && a[j]<a[i]) i = j;
    if (a[i] < a[p]) swap(a, i, p);
    i = p;
  }  
}
void siftdown(int a[], int i, int n) {  
  while (2*i+1<n){
    int l=2*i+1;
    if (l+1<n && a[l+1] < a[l]) l++;
    if (a[l] < a[i]) swap(a, i, l);
    i=l;
  }
}

第14 题:
题目:输入一个已经按升序排序过的数组和一个数字,
在数组中查找两个数,使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
例如输入数组1、2、4、7、11、15 和数字15。由于4+11=15,因此输出4 和11。
ANSWER:
Use two cursors. One at front and the other at the end. Keep track of the sum by moving the cursors.
void find2Number(int a[], int n, int dest) {
  int *f = a, *e=a+n-1;
  int sum = *f + *e;
  while (sum != dest && f < e) {
    if (sum < dest) sum = *(++f);
    else sum = *(--e);
  }
  if (sum == dest) printf(“%d, %d\n”, *f, *e);
}

第17 题:
题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。
分析:这道题是2006 年google 的一道笔试题。
ANSWER:
Again, this depends on what is “char”. Let’s assume it as ASCII.
char firstSingle(char * str) {
  int a[255];
  memset(a, 0, 255*sizeof(int));
  char *p=str;
  while (*p!=’\0’) {
    a[*p] ++;
    p++;
  }
  p = str;
  while (*p!=’\0’) {
    if (a[*p] == 1) return *p;

p++;
  }

  return ‘\0’; // this must the one that occurs exact 1 time.
}

第18 题:
题目:n 个数字(0,1,…,n-1)形成一个圆圈,从数字0 开始,
每次从这个圆圈中删除第m 个数字(第一个为当前数字本身,第二个为当前数字的下一个数
字)。
当一个数字删除后,从被删除数字的下一个继续删除第m 个数字。
求出在这个圆圈中剩下的最后一个数字。
July:我想,这个题目,不少人已经见识过了。
ANSWER:
Actually, although this is a so traditional problem, I was always to lazy to think about this or even to search for the answer.(What a shame...). Finally, by google I found the elegant solution for it.
The keys are:
1) if we shift the ids by k, namely, start from k instead of 0, we should add the result by k%n
2) after the first round, we start from k+1 ( possibly % n) with n-1 elements, that is equal to an (n-1) problem while start from (k+1)th element instead of 0, so the answer is (f(n-1, m)+k+1)%n
3) k = m-1, so f(n,m)=(f(n-1,m)+m)%n. 
finally, f(1, m) = 0;
Now this is a O(n) solution.
int joseph(int n, int m) {
  int fn=0;
  for (int i=2; i<=n; i++) {
    fn = (fn+m)%i;  }
  return fn;
}
hu...长出一口气。。。

第19 题:
题目:定义Fibonacci 数列如下:
/ 0 n=0
f(n)= 1 n=1
\ f(n-1)+f(n-2) n=2
输入n,用最快的方法求该数列的第n 项。
分析:在很多C 语言教科书中讲到递归函数的时候,都会用Fibonacci 作为例子。
因此很多程序员对这道题的递归解法非常熟悉,但....呵呵,你知道的。。
ANSWER:
This is the traditional problem of application of mathematics...
let A=
{1 1}
{1 0}
f(n) = A^(n-1)[0,0]
this gives a O(log n) solution.
int f(int n) {
  int A[4] = {1,1,1,0};
  int result[4];
  power(A, n, result);
  return result[0];
}

void multiply(int[] A, int[] B, int _r) {
  _r[0] = A[0]*B[0] + A[1]*B[2];
  _r[1] = A[0]*B[1] + A[1]*B[3];
  _r[2] = A[2]*B[0] + A[3]*B[2];
  _r[3] = A[2]*B[1] + A[3]*B[3];
}

void power(int[] A, int n, int _r) {
  if (n==1) { memcpy(A, _r, 4*sizeof(int)); return; }
  int tmp[4];
  power(A, n>>1, _r);
  multiply(_r, _r, tmp);
  if (n & 1 == 1) {
    multiply(tmp, A, _r);
  } else {
    memcpy(_r, tmp, 4*sizeof(int));
  }
}

27.跳台阶问题
题目:一个台阶总共有n 级,如果一次可以跳1 级,也可以跳2 级。
求总共有多少总跳法,并分析算法的时间复杂度。
这道题最近经常出现,包括MicroStrategy 等比较重视算法的公司
都曾先后选用过个这道题作为面试题或者笔试题。
ANSWER
f(n)=f(n-1)+f(n-2), f(1)=1, f(2)=2, let f(0) = 1, then f(n) = fibo(n-1);

45.雅虎:
1.对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)
某一个元素也加一,现给出一正数矩阵,判断其是否能够由一个全零矩阵经过上述运算得到。
ANSWER
A assignment problem. Two ways to solve. 1: duplicate each cell to as many as its value, do Hungarian algorithm. Denote the sum of the matrix as M, the edge number is 2M, so the complexity is 2*M*M; 2: standard maximum flow. If the size of matrix is NxN, then the algorithm using Ford Fulkerson algorithm is M*N*N.
too complex... I will do this when I have time...

2.一个整数数组,长度为n,将其分为m 份,使各份的和相等,求m 的最大值
比如{3,2,4,3,6} 可以分成{3,2,4,3,6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m 的最大值为3
ANSWER
Two restrictions on m, 1) 1 <= m <= n; 2) Sum(array) mod m = 0
NOTE: no hint that a[i]>0, so m could be larger than sum/max;
So firstly prepare the candidates, then do a brute force search on possible m’s.
In the search , a DP is available, since if f(array, m) = OR_i( f(array-subset(i), m) ), where Sum(subset(i)) = m.

int maxShares(int a[], int n) {
  int sum = 0;
  int i, m;
  for (i=0; i<n; i++) sum += a[i];
  for (m=n; m>=2; m--) {
    if (sum mod m != 0) continue;
    int aux[n]; for (i=0; i<n; i++) aux[i] = 0;
    if (testShares(a, n, m, sum, sum/m, aux, sum/m, 1)) return m;
  }
  return 1;
}

int testShares(int a[], int n, int m, int sum, int groupsum, int[] aux, int goal, int groupId) {
  if (goal == 0) {
    groupId++;
    if (groupId == m+1) return 1;
  }
  for (int i=0; i<n; i++) {
    if (aux[i] != 0) continue;
    aux[i] = groupId;
    if (testShares(a, n, m, sum, groupsum, aux, goal-a[i], groupId)) {
      return 1;
    }
    aux[i] = 0;
  }
}

Please do edge cutting yourself, I’m quite enough of this...

47.创新工场:
求一个数组的最长递减子序列比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,
4,3,2}
ANSWER:
Scan from left to right, maintain a decreasing sequence. For each number, binary search in the decreasing sequence to see whether it can be substituted.

int[] findDecreasing(int[] a) {
  int[] ds = new int[a.length];
  Arrays.fill(ds, 0);
  int dsl = 0;
  int lastdsl = 0;
  for (int i=0; i<a.length; i++) {
    // binary search in ds to find the first element ds[j] smaller than a[i]. set ds[j] = a[i], or append a[i] at the end of ds
    int s=0, t=dsl-1;
    while (s<=t) {
      int m = s+(t-s)/2;
      if (ds[m] < a[i]) {
        t = m - 1;
      } else {
        s = m + 1;
      }
    }
    // now s must be at the first ds[j]<a[i], or at the end of ds[]
    ds[s] = a[i];
    if (s > dsl) { dsl = s; lastdsl = i; }
  }
  // now trace back.
  for (int i=lastdsl-1, j=dsl-1; i>=0 && j >= 0; i--) {
    if (a[i] == ds[j]) { j --; }
    else if (a[i] < ds[j]) { ds[j--] = a[i]; }
  }  
  return Arrays.copyOfRange(ds, 0, dsl+1);
}

48.微软:
一个数组是由一个递减数列左移若干位形成的,比如{4,3,2,1,6,5}
是由{6,5,4,3,2,1}左移两位形成的,在这种数组中查找某一个数。
ANSWER:
The key is that, from the middle point of the array, half of the array is sorted, and the other half is a half-size shifted sorted array. So this can also be done recursively like a binary search.

int shiftedBinarySearch(int a[], int k) {
  return helper(a, k, 0, n-1);
}

int helper(int a[], int k, int s, int t) {
  if (s>t) return -1;
  int m = s + (t-s)/2;
  if (a[m] == k) return m;
  else if (a[s] >= k && k > a[m]) return helper(a, k, s, m-1);
  else return helper(a, k, m+1, e);
}

51.和为n 连续正数序列。
题目:输入一个正数n,输出所有和为n 连续正数序列。
例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3 个连续序列1-5、4-6 和7-8。
分析:这是网易的一道面试题。
ANSWER:
It seems that this can be solved by factorization. However, factorization of large n is impractical!

Suppose n=i+(i+1)+...+(j-1)+j, then n = (i+j)(j-i+1)/2 = (j*j - i*i + i + j)/2
=> j^2 + j + (i-i^2-2n) = 0 => j=sqrt(i^2-i+1/4+2n) - 1/2
We know  1 <= i < j <= n/2 + 1
So for each i in [1, n/2], do this arithmetic to check if there is a integer answer.

int findConsecutiveSequence(int n) {
  int count = 0;
  for (int i=1; i<=n/2; i++) {
    int sqroot = calcSqrt(4*i*i+8*n-4*i+1);
    if (sqroot == -1) continue;
    if ((sqroot & 1) == 1) {
      System.out.println(i+”-” + ((sqroot-1)/2));
      count ++;
    }
  }
  return count;
}
Use binary search to calculate sqrt, or just use math functions.

53.字符串的排列(字符串)。
题目:输入一个字符串,打印出该字符串中字符的所有排列。
例如输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串
abc、acb、bac、bca、cab和cba。

分析:这是一道很好的考查对递归理解的编程题,
因此在过去一年中频繁出现在各大公司的面试、笔试题中。

74.数组中超过出现次数超过一半的数字(数组)

题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。

分析:这是一道广为流传的面试题,包括百度、微软和Google在内的多家公司都
曾经采用过这个题目。要几十分钟的时间里很好地解答这道题,
除了较好的编程能力之外,还需要较快的反应和较强的逻辑思维能力。

68.把数组排成最小的数。
题目:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的
一个。
例如输入数组{32, 321},则输出这两个能排成的最小数字32132。
请给出解决问题的算法,并证明该算法。
分析:这是09 年6 月份百度的一道面试题,
从这道题我们可以看出百度对应聘者在算法方面有很高的要求。
ANSWER:
Actually this problem has little to do with algorithm...
The concern is, you must figure out how to arrange to achieve a smaller figure.
The answer is, if ab < ba, then a < b, and this is a total order.

String smallestDigit(int a[]) {
  Integer aux[] = new Integer[a.length];
  for (int i=0; i<a.length; a++) aux[i] = a[i];
  Arrays.sort(aux, new Comparator<Integer>(){
    int compareTo(Integer i1, Integer i2) {
      return (“”+i1+i2).compare(“”+i2+i1);
    }
  });
  StringBuffer sb = new StringBuffer();
  for (int i=0; i<aux.length, i++) {
    sb.append(aux[i]);
  }
  return sb.toString();
}

69.旋转数组中的最小元素。
题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个
排好序的数组的一个旋转,
输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数
组的最小值为1。
分析:这道题最直观的解法并不难。从头到尾遍历数组一次,就能找出最小的元素,时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性,我们应该能找到更好的解法。
ANSWER
This is like the shifted array binary search problem. One blind point is that you may miss the part that the array is shifted by 0(or kN), that is not shifted.

int shiftedMinimum(int a[], int n) {
  return helper(a, 0, n-1);
}

int helper(int a[], int s, int t) {
  if (s == t || a[s] < a[t]) return a[s];
  int m = s + (t-s)/2;
  if (a[s]>a[m]) return helper(a, s, m);
  else return helper(a, m+1, t);
}

  评论这张
 
阅读(226)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017