2015唯品会技术岗笔试真题（含答案）

1、现有n个小于100000的整数，写一个算法将这些数从小到大排序，要求时间复杂度O(n)，空间复杂度O(1)。

2、有一个整数数组，请用你熟悉的编程语言写一个算法将这个数组变成奇数在前偶数在后。并给出你的算法的空间复杂度和时间复杂度。

3、有两个目录a、b的绝对路径(字符串)，用你熟悉的语言实现一个算法，求出b相对于a的相对路径。

4、仓库中有100颗金豆，拣货员在拣货的时候无意中把一颗外观一摸一样但重量不同的假豆掉了进去。仓库主管发现后给了他一架天平，并说如果他能通过最多两次称量得出假豆比真豆重还是轻，就不对他进行惩罚。你如果你是拣货员，你能让自己免于惩罚吗?

网友A：个人想法，有错请指出。

第一题：快排。
第二题：从中间开始往两边扫描。
第三题：个人觉得应该是字符串匹配算法。
第四题：不会，以前见过多种类似的题，但是忘了。

网友B：
1、快排的时间复杂度是nlog2(n)，我觉得题目可能记得有问题。
2、从中间肯定不对，应该和快排一样，从两边往中间扫。
3、类似于最小父节点的查找，但更简单，因为A和B的深度是已知的。可以直接看A和B开头目录有多少一样的。然后再在B到父节点的相对深度前加一堆上线目录（../）。
4、第一次： 1-33   VS 34 - 66
                    1.1 平      1-35 VS 67-101  --〉      67-101的轻重，就是假球的轻重 
                    1.2 左重  1-33 VS 67-99    --〉       左重：则假重；左轻，则假轻：平，则假轻
                    1.3 右重   同理1.2

网友C：
第一题没研究
第二题
private static void cata(int[] s, int[] r) {
if (s.length != r.length) {
throw new RuntimeException();
}
int jxIdx = 0;
int oxIdx = 0;
for (int i = 0; i < s.length; i++) {
if (s[i] % 2 != 0) {
r[jxIdx++] = s[i];
} else {
r[s.length - (++oxIdx)] = s[i];
}
}
}
第三题
private static String getPath(String fPath, String sPath) {
String ret = "";
String fs[] = fPath.split("\\\\");
String ss[] = sPath.split("\\\\");
int idx = getSameFolderIdx(fs, ss);
for (int i = idx; i < ss.length; i++) {
ret += "../";
}
for (int i = idx; i < fs.length; i++) {
ret += fs[i] + "/";
}
return ret;
}

private static int getSameFolderIdx(String fs[], String ss[]) {
int i = 0;
for (; i < fs.length; i++) {
if (i == ss.length || !fs[i].equals(ss[i])) {
break;
}
}
return i;
}
来源于 CSDN