巨硬OTS面经

3.23 的 hiring event。今天刚收到 OTS，想赶快给做了。

三道题。第一题很简单，找bug。

第二题，利口得 司令二，一个用string代表的数字，要remove n 个，求remove 后得到最小的数字

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

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

8 01:42):
有朋友问我是不是business application group的。我申请的应该是这个的。我没法发送／回复私信。级别太低 ==

1. public static int findMinStop(int g, int d, int[][] gasStations) {
   
2.         if (g >= d) return 0;
   
3.         if (gasStations == null || gasStations.length == 0) return -1;
   
4.         for (int i = 0; i < gasStations.length; i++) {
   
5.             gasStations[i][0] = d - gasStations[i][0];
   
6.         }
   
7.         int[] maxReach = new int[gasStations.length + 1];
   
8.         maxReach[0] = g;
   
9.         Arrays.sort(gasStations, new Comparator<int[]>() {
   
10.             @Override
    
11.             public int compare(int[] o1, int[] o2) {
    
12.                 return o1[0] - o2[0];
    
13.             }
    
14.         });
    
15.         int res = 0;
    
16.         HashSet<Integer> visited = new HashSet<>();
    
17.         while (res < maxReach.length - 1 && maxReach[res] < d) {
    
18.             maxReach[res + 1] = maxReach[res] + findLargestWithOutRepeat(gasStations, visited, maxReach[res]);
    
19.             res++;
    
20.         }
    
21.         System.out.println(visited);
    
22.         return maxReach[res] < d ? -1 : res;
    
23.     }
    
24. 
    
25.     //O(N)
    
26.     private static int findLargestWithOutRepeat(int[][] gasStations, Set<Integer> visited, int maxDis) {
    
27.         int max = 0;
    
28.         int maxIndex = -1;
    
29.         for (int i = 0; i < gasStations.length; i++) {
    
30.             if (gasStations[i][0] > maxDis) {
    
31.                 break;
    
32.             }
    
33.             if (visited.contains(i)) continue;
    
34.             if (gasStations[i][1] > max) {
    
35.                 max = gasStations[i][1];
    
36.                 maxIndex = i;
    
37.             }
    
38.         }
    
39.         visited.add(maxIndex);
    
40.         return max;
    
41.     }
    
42. 
    
43.     public static void main(String[] args) {
    
44.         int[][] test =  {{24,10},{25, 1},{26,12}};
    
45.         System.out.println(findMinStop(10, 34, test));
    
46.     }

复制代码

草草写了一下 抛砖引玉 希望同学能贡献标答

notturno 发表于 2018-3-7 15:04
greedy可以做

先对加油站按照地点排序。然后在当前的油够到大的加油站中，记录gas的最大值。

这种方法显然有bug,比如必须加当前油能到达的所有站的油才能到达目的地或者接下来的加油站，那么如果只记录所有能达到的加油站中最大的gas, 那么很可能导致达到不了目的地。

请问楼主如何拿到OTS的啊？谢谢

PJCS 发表于 2018-3-7 08:03
请问楼主如何拿到OTS的啊？谢谢

领英 recruiter 找的我。如果想要，我可以把 recruiter 联系方式发你。如果你是在职的话，比较好。

楼主可以分享一下hire event的报名链接吗，多谢！

谢谢，感觉是新题，不过难度还好

xdsb1989 发表于 2018-3-7 11:34
楼主可以分享一下hire event的报名链接吗，多谢！

你留个邮箱 我发你邮箱吧。

notturno 发表于 2018-3-7 14:09
谢谢，感觉是新题，不过难度还好

好吧。我感觉第三题不是很简单 == 想了挺久。
你有什么好的思路可以分享一下么。

fernando 发表于 2018-3-7 14:50
好吧。我感觉第三题不是很简单 == 想了挺久。
你有什么好的思路可以分享一下么。

greedy可以做

先对加油站按照地点排序。然后在当前的油够到大的加油站中，记录gas的最大值。