微软中国校招一二三面面经
===12.14更新===
获得了feedback，一面Hire，二面三面No Hire。
反而是感觉良好的两轮No Hire.
一面：尝试多次且没要提示(good)。
二面：花了太多时间且没要提示(bad)。
三面：问题分析和系统思维not good，CS背景not good，coding过于复杂且有bug。
feedback尖锐深刻，是秋招获得的最有价值的信息和资料，等价于一个北京28w的offer。
===原帖===
一面leetcode 297 准hard
二面leetcode 1358 准hard
三面leetcode 4 hard
三轮全是hard，无提示撕出。三面hard只20分钟，撕出最优解，依然被吐槽，第二天收到感谢信。
虽然败了，但我是败的一点都不服的！
===11.28更新===
有老哥觉得我有点过于纠结于最优解了。
所以在此贴一下代码，从而表达为何我过于纠结：
20分钟白板撕出，34行处加上 '||' 可AC leetcode第四题。
复杂度O(log(min(m,n))). 算法导论解。
public int getKth(int[] arr1, int[] arr2, int k) {
if (arr1 == null || arr2 == null) {
throw new RuntimeException("Invalid Input Arrays");
}
int [] longArr = arr1.length > arr2.length ? arr1 : arr2;
int [] shortArr = longArr == arr1 ? arr2 : arr1;
int longLen = longArr.length, shortLen = shortArr.length;
if (k < 1 || k > longLen + shortLen) {
throw new RuntimeException("Invalid k");
}
if (shortLen == 0) return longArr[k - 1];
if (k <= shortLen) {
return getUpMedianOfTwoSortedEqualLenArrays(shortArr, 0, k - 1, longArr, 0, k - 1);
} else if (k <= longLen) {
if (longArr[k - shortLen - 1] >= shortArr[shortLen - 1]) {
return longArr[k - shortLen - 1];
}
return getUpMedianOfTwoSortedEqualLenArrays(shortArr, 0, shortLen - 1, longArr, k - shortLen, k - 1);
}
// k > longLen && k < longLen + shortLen
if (shortArr[k - longLen - 1] >= longArr[longLen - 1]) {
return shortArr[k - longLen - 1];
}
if (longArr[k - shortLen - 1] >= shortArr[shortLen - 1]) {
return longArr[k - shortLen - 1];
}
return getUpMedianOfTwoSortedEqualLenArrays(shortArr, k - longLen, shortLen - 1, longArr, k - shortLen, longLen - 1);
}
private int getUpMedianOfTwoSortedEqualLenArrays(int[] arr1, int s1, int e1, int[] arr2, int s2, int e2) {
if (arr1 == null || arr2 == null) {
throw new RuntimeException("Invalid Input Arrays");
}
if (s1 < 0 || e1 >= arr1.length || s1 > e1
s2 < 0 || e2 >= arr2.length || s2 > e2) {
throw new RuntimeException("Invalid input start end");
}
if (e1 - s1 != e2 - s2){
throw new RuntimeException("Length not equal");
}
while (s1 < e1) {
int mid1 = s1 + ((e1 - s1) >> 1);
int mid2 = s2 + ((e2 - s2) >> 1);
int offset = ((e1 - s1 + 1) & 1) ^ 1;
if (arr1[mid1] == arr2[mid2]) {
return arr1[mid1];
} else if (arr1[mid1] > arr2[mid2]) {
e1 = mid1;
s2 = mid2 + offset;
} else { //arr1[mid1] < arr2[mid2]
s1 = mid1 + offset;
e2 = mid2;
}
}
return Math.min(arr1[s1], arr2[s2]);
} 