热带雨林在线作业 Amazon OA

运气比较好拿到了两个最难的oa题

第一题
Product Suggestions
Runtime: 11 ms, faster than 92.26% of Java online submissions for Search Suggestions System.

1. class Solution {
   
2.     public List<List<String>> suggestedProducts(String[] products, String searchWord) {
   
3.         List<List<String>> ans = new ArrayList<>();
   
4.         
   
5.         if (products.length == 0 || searchWord.length() == 0) {
   
6.             return ans;
   
7.         }
   
8.         
   
9.         Arrays.sort(products);
   
10.         char[] arr = searchWord.toCharArray();
    
11.         
    
12.         // first
    
13.         List<String> lastMatched = new ArrayList<>();
    
14.         for (String str : products) {
    
15.             if (str.charAt(0) == arr[0]) {
    
16.                 lastMatched.add(str);
    
17.             }
    
18.         }
    
19.         ans.add(getFirstThree(lastMatched));
    
20.         
    
21.         //O(m)
    
22.         for (int i = 1; i < arr.length; i++) {
    
23.             List<String> matched = getMatchedStrings(lastMatched, i, arr[i]); // O(n)
    
24.             lastMatched = matched;
    
25.             ans.add(getFirstThree(matched));
    
26.         }
    
27.         
    
28.         return ans; //O(m*n)  m 是搜索字符串的长度 n是总共的products个数
    
29.     }
    
30.    
    
31.     private List<String> getFirstThree(List<String> products) { //O(3)
    
32.         List<String> ans = new ArrayList<>();
    
33.         for (int i = 0; i < 3 && i < products.size(); i++) {
    
34.             ans.add(products.get(i));
    
35.         }
    
36.         return ans;
    
37.     }
    
38.    
    
39.     //O(n)
    
40.     private List<String> getMatchedStrings(List<String> products, int index, char c) {
    
41.         List<String> ans = new ArrayList<>();
    
42.         for (String str : products) {
    
43.             // 这里默认如果搜索字串长于当前产品名字， 那么我们就认为没有产品匹配
    
44.             if (index < str.length() && str.charAt(index) == c) {
    
45.                 ans.add(str);
    
46.             }
    
47.         }
    
48.         return ans;
    
49.     }
    
50. }

复制代码

第二题
Critical Routers[/i]
无向图里找相连点, 我这里的答案是看过Tarjan教程之后写的

正常人的想法应该是用bfs / dfs 把相邻点去掉一个一个试能不能联通

You are given a

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

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

Input: numNodes = 7, numEdges = 7, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 5], [5, 6], [3, 4]]

1. public class CriticalRouters {
   
2.     public static void main(String[] args) {
   
3.         /**
   
4.          * numNodes = 7, numEdges = 7, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 5], [5, 6], [3, 4]]
   
5.          */
   
6.         int numNodes = 7, numEdges = 7;
   
7.         List<List<Integer>> edges = StringTransformHelper.to2DList("[[0, 1], [0, 2], [1, 3], [2, 3], [2, 5], [5, 6], [3, 4]]");
   
8.         /**
   
9.          * out put [2, 3, 5]
   
10.          */
    
11.         CriticalRouters cr = new CriticalRouters();
    
12. 
    
13.         List<Integer> ans = new ArrayList<>();
    
14.         int[] ids = new int[numNodes];
    
15.         int[] lowLink = new int[numNodes];
    
16.         int[] outGoingEdgeCount = new int[numNodes];
    
17.         boolean[] visited = new boolean[numNodes];
    
18. 
    
19.         List<Integer>[] graph = cr.getGraph(numNodes, edges);
    
20.         int startNode = 5;
    
21.         cr.getCriticalRouters(ans, ids, lowLink, outGoingEdgeCount, visited, -1, startNode, 0, startNode, graph);
    
22.         System.out.println(ans);
    
23. 
    
24.     }
    
25. 
    
26.     private void getCriticalRouters(List<Integer> ans,
    
27.                                     int[] ids,
    
28.                                     int[] lowLink,
    
29.                                     int[] outGoingEdgeCount,
    
30.                                     boolean[] visited,
    
31.                                     int prevNode,
    
32.                                     int currNode,
    
33.                                     Integer currentId,
    
34.                                     int startNode,
    
35.                                     List<Integer>[] graph) {
    
36. 
    
37.         ids[currNode] = lowLink[currNode] = currentId++;
    
38.         visited[currNode] = true;
    
39.         if (prevNode == startNode) {
    
40.             outGoingEdgeCount[prevNode]++;
    
41.         }
    
42. 
    
43.         for (Integer neib : graph[currNode]) {
    
44.             if (neib == prevNode) {
    
45.                 continue;    // ensure single directional
    
46.             }
    
47.             if (!visited[neib]) {
    
48.                 getCriticalRouters(ans, ids, lowLink, outGoingEdgeCount, visited, currNode, neib, currentId, startNode, graph);
    
49.                 lowLink[currNode] = Math.min(lowLink[currNode], lowLink[neib]);
    
50.                 if (ids[currNode] <= lowLink[neib]) {               // == -> circle      < -> bridge
    
51.                     if (currNode == startNode) {
    
52.                         if (outGoingEdgeCount[startNode] > 1) {
    
53.                             ans.add(currNode);
    
54.                         }
    
55. 
    
56.                     } else {
    
57.                         ans.add(currNode);
    
58.                     }
    
59.                 }
    
60. 
    
61.             } else {
    
62.                 lowLink[currNode] = Math.min(lowLink[currNode], ids[neib]);
    
63.             }
    
64.         }
    
65.     }
    
66. 
    
67.     private List<Integer>[] getGraph(int n, List<List<Integer>> connections) {
    
68.         List<Integer>[] graph = new List[n];
    
69.         for (int i = 0; i < n; i++) {
    
70.             graph[i] = new ArrayList<>();
    
71.         }
    
72.         for (int i = 0; i < connections.size(); i++) {
    
73.             List<Integer> edge = connections.get(i);
    
74.             int prev = edge.get(0);
    
75.             int next = edge.get(1);
    
76.             graph[prev].add(next);
    
77.             graph[next].add(prev);
    
78.         }
    
79.         return graph;
    
80.     }
    
81. }

复制代码

当时两个题都没做好，然而还是被recruiter捞起来了 1.10 onsite，求各位加点米
[/i]

恭喜楼主，我做完OA结果recruiter放假到2月份，看来我完全没希望参加1月的hiring event了

请问你是全职还是实习OA2?

请问这是 full time OA 还是 intern OA 啊

请问这是 full time OA 还是 intern OA 啊

chb123 发表于 2020-1-7 07:43
请问你是全职还是实习OA2?

sde 1 experienced

好像只要是oa2 题库都一样的

Neo333 发表于 2020-1-7 12:30
请问这是 full time OA 还是 intern OA 啊

fulltime

请问楼主你是社招吗？是什么职位呀？SDE2？

KHNOGG 发表于 2020-2-9 12:56
请问楼主你是社招吗？是什么职位呀？SDE2？

SDE 1 社招 NYC 但是我蛮怪的考了两个设计题