10月23日onsite面试

queeniejing 发表于 2015-11-18 15:13
谢谢LZ 只要走到出口就行了吗？ 还是要求最短路径或者其他的什么？

我不大记得了 应该是要求出最短路径的 要把路径返回的

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

queeniejing 发表于 2015-11-18 15:13
谢谢LZ 只要走到出口就行了吗？ 还是要求最短路径或者其他的什么？

哦哦，明白了，题目是要输出最多overlap的时间段是吧？我以为要输出所有overlap的时间段。。。。那上面的例子就应该输出[3,7]?

hj867955629 发表于 2015-11-18 15:33
这种题也可以把所有start看成正数，所有end看成负数，然后绝对值排序，这里就是 1 2 3 －7 －10 －11, 顺 ...

嗯嗯，知道啦！

请问楼主 那题迷宫是求最小的步数走到出口么 还是只是找到一个路径走到出口？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

queeniejing 发表于 2015-11-19 05:14
我有个问题不太理解： “就是 1 2 3 －7 －10 －11, 顺序扫一遍，遇到正的次数加1，负得次数减1，次数大 ...

中间会大于1呀。。比如扫到2，遇到两个正数1和2，所以次数为2，说明从2开始的部分是重叠两次

请问楼主第三轮是求最多overlap的个数吗？

写了下sort array a*x^2 + bx + c的代码，这题代码量也不少啊。。。

1. public class SortSortedArray {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] arr = {-5, -3, -1, 0, 4, 9, 11, 13};
   
5.                 int[] res = sortSortedArray(arr, -1, 2, 0);
   
6.                 for (int i : res) {
   
7.                         System.out.print(i + " ");
   
8.                 }
   
9.         }
   
10.         public static int[] sortSortedArray(int[] arr, int a, int b, int c) {
    
11.                 int pivot = -b / (2 * a);
    
12.                 int[] res = new int[arr.length];
    
13.                 int index = findPivot(arr, pivot);
    
14.                 int left = index;
    
15.                 int right = index + 1;
    
16.                 boolean faceUp = true;
    
17.                 if (a < 0) {
    
18.                         faceUp = false;
    
19.                 }
    
20.                 int pos = 0;
    
21.                 if (faceUp) {
    
22.                         while (left >= 0 && right < arr.length) {
    
23.                                 if (getResult(arr[left], a, b, c) > getResult(arr[right], a, b, c)) {
    
24.                                         res[pos++] = getResult(arr[right], a, b, c);
    
25.                                         right++;
    
26.                                 } else {
    
27.                                         res[pos++] = getResult(arr[left], a, b, c);
    
28.                                         left--;
    
29.                                 }
    
30.                         }
    
31.                         while (left >= 0) {
    
32.                                 res[pos++] = getResult(arr[left], a, b, c);
    
33.                                 left--;
    
34.                         }
    
35.                         while (right < arr.length) {
    
36.                                 res[pos++] = getResult(arr[right], a, b, c);
    
37.                                 right++;
    
38.                         }
    
39.                 } else {
    
40.                         pos = res.length - 1;
    
41.                         while (left >= 0 && right < arr.length) {
    
42.                                 if (getResult(arr[left], a, b, c) > getResult(arr[right], a, b, c)) {
    
43.                                         res[pos--] = getResult(arr[left], a, b, c);
    
44.                                         left--;
    
45.                                 } else {
    
46.                                         res[pos--] = getResult(arr[right], a, b, c);
    
47.                                         right++;
    
48.                                 }
    
49.                         }
    
50.                         while (left >= 0) {
    
51.                                 res[pos--] = getResult(arr[left], a, b, c);
    
52.                                 left--;
    
53.                         }
    
54.                         while (right < arr.length) {
    
55.                                 res[pos--] = getResult(arr[right], a, b, c);
    
56.                                 right++;
    
57.                         }
    
58.                 }
    
59.                 return res;
    
60.         }
    
61. 
    
62.         private static int getResult(int i, int a, int b, int c) {
    
63.                 return a * i * i + b * i + c;
    
64.         }
    
65. 
    
66.         private static int findPivot(int[] arr, int pivot) {
    
67.                 int start = 0;
    
68.                 int end = arr.length - 1;
    
69.                 while (start + 1 < end) {
    
70.                         int mid = (end - start) / 2 + start;
    
71.                         if (arr[mid] == pivot) {
    
72.                                 return mid;
    
73.                         } else if (arr[mid] > pivot) {
    
74.                                 end = mid;
    
75.                         } else {
    
76.                                 start = mid;
    
77.                         }
    
78.                 }
    
79.                 if (arr[end] <= pivot) {
    
80.                         return end;
    
81.                 } else {
    
82.                         return start;
    
83.                 }
    
84.         }
    
85. }
    

复制代码

hhllryslh 发表于 2015-11-18 09:52
就是
得定义一个 Point struct
struct Point{

请问这么做和一次走1步2步没什么关系啊，2步不就是走两次吗？是要求最小的走得次数吗？