发几道面试题
几道AMAZON的面试题
1. 数组有N+M个数字, 数字的范围为1 ... N, 打印重复的元素, 要求O(M + N), 不可以用额外的空间。
2. 数组有N-2个数字，数字的范围为1 ... N，没有重复的元素，要求打印缺少的2个数字，不可以用额外的空间。
3. 输入上百万个行星的位置， 求距离第K近的两个行星。
4. 一个int 的数组, 有些数字只出现一次， 有些数字出现两次， 只有一个数字出现了3次， 求出现3次的这个数字， 不可以用额外的空间（用位操作）。
5. 打印字符串中最大的回文子串。
6. 判断一个二叉树是否为二叉查找树
7. 打印int 数组中 和为给定值的 组合
[解决办法]
先贴2个简单的
static void Problem01()
{
int[] A = new int[] { 1, 3, 4, 2, 8, 7, 3, 2, 5, 6, 9, 10, 1, 1 };
for (int i = 0; i < A.Length; i++)
{
while (A[i] != i + 1 && A[i] != -1)
{
int index = A[i] - 1;
if (A[index] == A[i])
{
A[i] = -1;
Console.WriteLine(A[index]);
}
else
{
A[i] = A[index];
A[index] = index + 1;
}
}
}
}
static void Problem02()
{
int[] A = new int[] { 1, 3, 4, 8, 7, 5, 6, 10, 11, 12 };
int n = A.Length + 2;
int sum = (n * (n + 1)) >> 1;
int squareSum = sum * (2 * n + 1) / 3;
for (int i = 0; i < A.Length; i++)
{
sum -= A[i];
squareSum -= A[i] * A[i];
}
int k = squareSum / sum;
Console.WriteLine("{0} {1}", (sum + k) >> 1, (sum - k) >> 1);
}
[解决办法]
6. 判断一个二叉树是否为二叉查找树
中序遍历一下，有序就是BST。
[解决办法]
和litaoye的差不多
1. 数组有N+M个数字, 数字的范围为1 ... N, 打印重复的元素, 要求O(M + N), 不可以用额外的空间。
设数组为a[N+M],
从a[0] 到 a[N+M-1]，
对每个数字 a[i] , 如果 a[i]==a[a[i]-1], 则continue
如果 a[i]!=a[a[i]-1],则交换两者。
输入a[N]到a[N+M-1] //这就是结果。
一共有N+M个数字，就把这N+M个数字放到a[o]~a[N-1]里，1 就放在 a[0]里，2就放在a[1]里，a[i]就放在a[a[i]-1]里，遍历一遍后，a[N]~a[N+M-1]放的就是重复的。
N=5, M=3
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
5 5 3 4 4 1 2 5 //原始
第一个数字a[0]=5要放到a[4]里，a[4]!=5,所以和a[4]交换。如果和a[4]相等就不用换了。
4 5 3 4 5 1 2 5
第二个数字a[1]=5要放到a[4]里，a[4]==5,所以不用和a[4]交换。
4 5 3 4 5 1 2 5
第三个数字a[2]=3,要放在a[2]里，所以不用换了。
4 5 3 4 5 1 2 5
第四个数字，a[3]=4,要放在a[3]里，也不用换了。
4 5 3 4 5 1 2 5
第五个数字，a[4]=5.不用换了
4 5 3 4 5 1 2 5
第六个数字，a[5]=1, 要放在a[0]里，交换。
1 5 3 4 5 4 2 5
第七个数字，a[6]=2, 要放在a[1]里，交换。
1 2 3 4 5 4 5 5
第八个数字，a[7]=5, 要放在a[4]里，不用交换了，因为a[4]已经是5了。
输出 a[N] 到 a[N+M-1] 即 ： 4 5 5 这还可以改进一下，如果一个数i已输出，就把a[i]置为0.防止重复
[解决办法]
可以递归 但是需要
left child.max < current node < right child.min
[解决办法]
第一题，可以考虑用负号来标识一个数已经存在了。
第二题，litaoye的方法很好了
第三题、先聚类。再对每个聚类够一棵最小支撑树就行。当然如果只是第K，可以考虑怎么剪枝啦
第四题、期待高人
第五题、litaoye方法好
第六题、中序遍历一下，排好序的就是
第七题、利用Hash，最多额外O(n)的空间咯
[解决办法]
做出第一题：
int main()
{
//assume N = 10, M = 5
int num[15] = {1, 7, 5, 7, 9, 1, 4, 8, 6, 0, 4, 2, 5, 2, 3};
int temp;
int i = 14;
while(i != 9)
{
temp = num[num[i]];
if(num[i] == temp)
{
cout << num[i] << '\n';
i --;
}
else
{
num[num[i]] = num[i];
num[i] = temp;
}
}
return 0;
}