由一个面试题目想到的_求职面试_非技术区_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 非技术区 > 求职面试 > 由一个面试题目想到的

由一个面试题目想到的

 2010/12/2 10:22:43    程序员俱乐部  我要评论(0)
  • 摘要:今天看到一个特别简单的题目,就是说有两个数组A和B,假设都是整数类型的,而且都是从小到大排好序的,A里面,从下标0开始,有X个数;B里面有Y个数,A的长度是X+Y,B的长度是Y,就是说A里面能放下所有A和B的数。目标是设计一个算法,把所有这些数字都放到A里面去,当然结果要是排序的。这个题目再简单不过了,就是倒着做mergesort。具体说就是用两个下标,分别从A和B的数据尾巴开始,做合并。合并的结果从A的最后一个位置开始放,最后A里面就是A和B的合并的并且排序的结果了。说到这个题目
  • 标签:面试题

今天看到一个特别简单的题目,就是说有两个数组A和B,假设都是整数类型的,而且都是从小到大排好序的,A里面,从下标0开始,有X个数;B里面有Y个数,A的长度是X+Y,B的长度是Y,就是说A里面能放下所有A和B的数。目标是设计一个算法,把所有这些数字都放到A里面去,当然结果要是排序的。

这个题目再简单不过了,就是倒着做merge sort。具体说就是用两个下标,分别从A和B的数据尾巴开始,做合并。合并的结果从A的最后一个位置开始放,最后A里面就是A和B的合并的并且排序的结果了。

说到这个题目,想起另外一个比较难的题目来。不过还是用一个简单的题目开始吧:假如有一个很长的整数数组,要求用这个数组实现两个堆栈

这个题目很简单,就是用两个栈指针,然后分别从数组的两头开始,向中间生长。具体写程序的时候,检查一下两个指针是否相遇就可以了。

然后题目就难了一点:如何用一个数组实现三个堆栈?

答案其实是上面那个题目的一个挺巧妙的扩展:三个堆栈里面的两个,还是按照上面的办法做;然后第三个堆栈,从数组三分之一的地方开始,向三分之二的方向生长。具体说来:

假设数组是A,长度是L,那么三个堆栈分别从下标0,L,和1/3L的地方开始生长。假设三个堆栈的栈顶指针分别是x,y和z,那么当栈生长到一定时间的时候,空间会不够用,可能会有以下情况:

  1. x生长到了1/3L
  2. y和z相遇

这两种情况下,数组都会有一段空间空闲(如果三个栈一样长,那就结束了),或者是A[x,1/3L],或者是A[y,z]。那么把这个空间继续按照上面的办法分割,直到空间用完为止。

本文来自:http://www.meirendaddy.com/blog/?p=95

发表评论
用户名: 匿名