从校内转的，欢迎大家讨论

一、
1、设计一个栈的结构，要求实现一个min函数，返回栈中最小的元素。要求min、push和pop操作都必须是O(1)的时间复杂度，简单描述思想。
2.、(1)输出下面程序的前7行并且说明数列表示的含义
      (2)下面的程序是否存在安全隐患？原因是？
#include<stdio.h>
#include<string.h>
const int MAX = 128;
const int LEN = 20;
int main(){
char str[MAX]="1";
char tem_str[MAX]="";
char buf[MAX]="";
printf("%s\n",str);
int i;
for(int line=1;line<=LEN;line++){
  strcpy(tem_str,str);
  str[0]='\0';
  for(i=0;tem_str[i]!=0;++i){
   char ch=tem_str[i];
   int count = 1;
   for(;tem_str[i+1]==tem_str[i];++i)
    count++;
   sprintf(buf,"%d%c",count,ch);
   strcat(str,buf);
  }
  printf("%s\n",str);
}
return 0;
}
3、分析线性表、二叉平衡树和哈希表在存储数据的时候，各有什么优劣？
二、
1、有一串首尾相连的珠子，共有m个，每一个珠子有一种颜色，并且颜色的总数不超过n(n<=10)，求连续的珠子的颜色总数为n时，长度最小的区间。可简述思路或者给出伪代码，并且给出时间和空间复杂度分析。
2、实现函数strnumcmp，和strcmp类式，不过有一点区别是在字符串包含数字的地方，按照数字的大小进行排序。比如
abc<abc#<abc1<abc2<abc10<abcd
而正常的顺序为
abc<abc#<abc1<abc10<abc2<abcd
请实现strnumcmp，给出完整代码。要求简单、明确。
三、
           大规模的字典中，需要词与此中间的搭配关系。
（1）       字典中的项为辞与词之间的搭配，比如两个词“今天”和“晚上”有两个搭配，今天|晚上 和晚上|今天。
（2）       字典的规模为10W数量级。
（3）       每一个词，最多能和其他1W左右的词进行搭配。
（4）       这个系统中有大量的读操作，大约每秒1000次，但是很少有写操作。
设计一个字典服务系统，能够满足上述的要求，并且给出占用的资源，最后估算出需要的机器资源。

第一题不是很著名的google的面试题么。
百度现在连笔试题也开始抄google啦，真是好传统啊。。。

  请LZ应聘的是什么职位？

1、设计一个栈的结构，要求实现一个min函数，返回栈中最小的元素。要求min、push和pop操作都必须是O(1)的时间复杂度，简单描述思想。

public class MyStack {
	private int[] inArray = new int[10];

	private int[] minArray = new int[10];

	private int count = 0;

	public int min() {
		return minArray[count-1];
	}

	public void push(int i) {
		// 当count超出范围的时候自动扩充数组大小，不写了
		inArray[count] = i;
		if (count == 0 || minArray[count - 1] >= i)
			minArray[count] = i;
		else
			minArray[count] = minArray[count - 1];
		count++;
	}

	public int pop() {
		return inArray[count---1];
	}
}

用链表，再维护一个min变量

正解。

                    优                劣

线性表           遍历数据         不同内部结构的线性表优劣不同

二叉平衡树       搜索数据             增删元素耗时

哈希表           索引数据             耗费空间

1、有一串首尾相连的珠子，共有m个，每一个珠子有一种颜色，并且颜色的总数不超过n(n<=10)，求连续的珠子的颜色总数为n时，长度最小的区间。可简述思路或者给出伪代码，并且给出时间和空间复杂度分析。

public class Test {
	/**
	 * 思路（想象这是贪吃蛇，头部向前吃豆）： 
	 * 1.向右吃豆，直到豆的类型总数为n时，拉掉多余的豆，这是第一个解。
	 * 2.继续吃豆，每吃一颗，拉掉多余的豆，比较一下解，直到结束。 
	 * （一次遍历，时间复杂度O(n)，需要储存每一颗豆的颜色，空间复杂度O(n)）
	 */
	public Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	public int[] shake;
	public int index = 0;
	public int minSize = Integer.MAX_VALUE;

	public Test(int m, int n, int[] beans) {
		shake = new int[m];
		for (int i = 0; i < beans.length; i++) {
			eatBean(i, n, beans);
		}
	}

	// 吃豆子
	private void eatBean(int i, int n, int[] beans) {
		shake[i] = beans[i];
		map.put(shake[i], map.get(shake[i]) == null ? 1 : map.get(shake[i]) + 1);
		// 满足豆的种类总数为n
		if (map.size() == n) {
			while (map.get(shake[index]) > 1) {
				popBean();
			}
			minSize = i - index + 1 < minSize ? i - index + 1 : minSize;
		}
	}

	// 拉豆子
	private void popBean() {
		map.put(shake[index], map.get(shake[index]) - 1);
		index++;
	}

	public static void main(String[] args) {
		int[] ints = new int[] { 0, 1, 2, 3, 2, 1, 3, 3, 3, 4 };
		Test test = new Test(10, 5, ints);
		System.out.println(test.minSize);
	}
}

orz这不是商务部的java题吧。。
java题20多页呢-。-

我打酱油的，这是转自校内的

看示例代码，应该是考C的吧