Amazon OA 面试经验

Utilization Checks :
其中一个测试案例是：[46, 73, 77, 53, 75, 22, 55, 84, 45, 40, 80, 66, 54, 39, 68, 23, 54, 22, 11, 91, 47, 56, 91, 97, 5, 44, 62, 73, 26, 99, 96, 74, 4

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

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

单的那些外，马上上到500个长度的startIndices，要确保你的代码是O(n+m)的复杂度。我考完后修改的代码：

1.     public static List<Integer> numberOfItems(String s, List<Integer> startIndices, List<Integer> endIndices) {
   
2.         List<Integer> result = new ArrayList<>();
   
3.         
   
4.         if (s == null || s.isEmpty()) {
   
5.             return result;
   
6.         }
   
7.         
   
8.         char[] charArray = s.toCharArray();
   
9.         List<Integer> pipePositions = new ArrayList<>();
   
10.         int[] nextIndexInPipePositions = new int[charArray.length]; //for each character in the string, the valid counting point will be from the position indicated by the index of pipePositions. for example, "**|**|" the pipePositions will be [2,5] and nextIndexInPipePositions will be [0,0,0,1,1,1] indicating [2,2,2,5,5,5]
    
11.         for (int i = 0; i < charArray.length; i++) {
    
12.             nextIndexInPipePositions[i] = pipePositions.size();
    
13.             if (charArray[i] == '|') {
    
14.                 pipePositions.add(i);
    
15.             }
    
16.         }
    
17.         
    
18.         int indicesSize = Math.min(startIndices.size(), endIndices.size());
    
19.         for (int i = 0; i < indicesSize; i++) {
    
20.             int firstPipePositionIndex = nextIndexInPipePositions[startIndices.get(i) - 1];
    
21.             int lastPipePositionIndex = nextIndexInPipePositions[endIndices.get(i) - 1];
    
22.             if (charArray[endIndices.get(i) - 1] != '|') { //the next pipe is after the endIndex - should count to the previous pipe
    
23.                 lastPipePositionIndex--;
    
24.             }
    
25.             if (lastPipePositionIndex > firstPipePositionIndex) {
    
26.                 // count of *s = the total distance between the first pipe and the last pipe - the pipe count between the fist piple and the last pipe
    
27.                 result.add(pipePositions.get(lastPipePositionIndex) - pipePositions.get(firstPipePositionIndex) - lastPipePositionIndex + firstPipePositionIndex);
    
28.             } else { // no pipe or only one pipe between
    
29.                 result.add(0);
    
30.             }
    
31.         }
    
32.         
    
33.         return result;
    
34.     }

复制代码

楼主能贴一下starting instance 和最后expected output instances# 么？

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

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

谢谢楼主， 可能我没说清楚， 我问的是你的第一题 Utility check 的  long case [46, 73, 77, 53, 75, 22,  ....
starting number of instance 是多少， expected output instance 是多少？

楼主可以讲讲第二题的思路吗 可以binary search做吗