亚麻Onsite

来写个A家的面经吧, 最近刚面的, 一共四轮:
1. 一个大叔(看不出是哪里的)和一个shadow(三哥), 问了我有关项目的事情, 题目是经典的拓扑排序

2. 白人小哥, 问了如果你和队友意见不统一但是你还是坚持你的意见最后胜出, 问了一道我之前没见过的题目, 不是很难:
给定一堆硬币, 硬币的两面分别印着不同的字母, 问你用这些硬币能不能拼出给定的单词, 每个硬币只能用一次, 比如
硬币: ["A,B", "B,C"], 单词: AB => true
硬币: [&

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

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

er. 就是一堆locker, 然后让你设计一个控制系统, 来选择哪些是空的, 哪些可以放, 用户怎么知道东西放哪, 快递员怎么知道东西放哪, 怎么通知用户之类的.


feedback是interview positive, 但是组里面headcount满了, 所以正在team match. 有了消息再update吧

楼主能讲下第二轮你用的循环是怎样的么？我只能想到O(nlogn)的做法。已加米！！！

[quote]害群之蚂蚁 发表于 2019-5-14 05:30

1. public class Coin_Word_Backtracking {
   
2.     public boolean find(String[] coins ...[/quote]
4. 嗯，我也感觉第二轮用backtrack毕竟靠谱。下面是我写的，大概看了一下，似乎思路差不多？
   
5. 
   
6. [code]  public boolean formLetter(char[][] list, String word) {
   
7.     // for every char character from A to Z, create a Set to store all the indices of coins where a char exists in the list
   
8.     ArrayList<Set<Integer>> coinsForletter = new ArrayList<>();
   
9.     for (int i = 0; i < 26; i++) {
   
10.       coinsForletter.add(i, new HashSet<>());
    
11.     }
    
12.     for (int i = 0; i < list.length; i++) {
    
13.       coinsForletter.get(list[i][0] - 'A').add(i);
    
14.       coinsForletter.get(list[i][1] - 'A').add(i);
    
15.     }
    
16.     return backtrack(coinsForletter, word.toCharArray(), new HashSet<Integer>(),  0);
    
17.   }
    
18.   
    
19.   // visited: a set of indices of coins that have already used one side (so we cannot use the other side anymore
    
20.   private boolean backtrack(ArrayList<Set<Integer>> coinsForletter, char[] letters, Set<Integer> visited, int start) {
    
21.     if (start >= letters.length) return true;
    
22.    
    
23.     char c = letters[start];
    
24.     for (Integer coin : coinsForletter.get(c - 'A')) {
    
25.       if (!visited.contains(coin)) {
    
26.         visited.add(coin);
    
27.         // if can continue all the way to the end, then it means we can return true for index `start`
    
28.         if (backtrack(coinsForletter, letters, visited, start + 1)) return true;
    
29.         // if backtrack() returns false above, it means that path cannot go through, so we backtrack
    
30.         visited.remove(coin);
    
31.       }
    
32.     }
    
33.     return false;
    
34.   }

复制代码

补充内容 (2019-6-10 13:48):
这里假设所有字母都是大写字母。如果是任意unix code，那就换成Map<Character, Set<Integer>>就行了

1. public class Coin_Word_Backtracking {
   
2.     public boolean find(String[] coins, String word){
   
3.         HashMap<String, List<Integer>> hm = new HashMap<>();
   
4.         for (int i = 0; i < coins.length; i++){
   
5.             String coin = coins[i];
   
6.             String[] co = coin.split(",");
   
7.             for (String c : co){
   
8.                 hm.putIfAbsent(c, new ArrayList<>());
   
9.                 hm.get(c).add(i);
   
10.             }
    
11.         }
    
12. 
    
13.         return backtrack(0, word.toCharArray(), hm, new HashSet<>());
    
14. 
    
15.     }
    
16.     public boolean backtrack(int idx, char[] word, HashMap<String, List<Integer>> hm, HashSet<Integer> set){
    
17.         if (idx >= word.length)
    
18.             return true;
    
19.         String cur = String.valueOf(word[idx]);
    
20.         for (int i : hm.get(cur)){
    
21.             if (set.add(i)){
    
22.                 if (backtrack(idx + 1, word, hm, set))
    
23.                     return true;
    
24.                 else
    
25.                     set.remove(i);
    
26.             }
    
27.         }
    
28.         return false;
    
29.     }
    
30. }

复制代码

第二题 我觉得用backtracking

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

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

请问是投的社招吗 具体哪个职位呢

请问楼主，第三个打印节点的问题，解法中有没有用到额外的空间？

mengxy2004 发表于 2019-5-3 00:02
请问是投的社招吗 具体哪个职位呢

社招, 猎头主动找的我, 其实具体啥职位我也不是很清楚

leaftree2013 发表于 2019-5-3 00:34
请问楼主，第三个打印节点的问题，解法中有没有用到额外的空间？

用了, 用了一个hashmap

问一下，第三题，横向index怎么定义的？

第三轮是利扣散要肆变体吧

请问楼主面的是什么组呀？