狗家新鲜出炉电面面筋

狗家面试官挺nice，人也不拽哈哈，就是不指名道姓地鄙视某某公司动不动炒人，说实话我也不知道某某是哪一家。
anyways。随便chitchat一下就说来咱做道题，毫无行为面试。（英文无口音，估计是老外）

第一道：

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

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

第二道：

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

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

Good luck！

PS：
老外的特点是英文无口音好懂，但是，同时他们的英文讲起来特别溜，特别快，遣词造句信手拈来，句句不重样，也有他独特的挑战性。
反正不懂就问，说i could quite follow you。再不行就在doc上打例子。。。哈哈，八仙过海吧。

Random note 写了一下 没有跑可能有runtime error 请教一下思路是不是对的?

1. Map<String, boolean> seen = new HashMap<>();
   
2. Set<Integer> used = new HashSet<>();
   
3. Map<Integer, List<Integer>> map = new HashMap<>();
   
4. boolean[] checked;
   
5. int[] tar;
   
6. public boolean randomNote(List<String> l, String target) {
   
7.         if (target.length() > l.size()) return false;
   
8.         checked = new boolean[target.length()];
   
9.         int tari = 0;
   
10.         for (char c : target.toCharArray()) {
    
11.         int dif = c - ‘a’;
    
12.         if (!map.containsKey(dif)) map.put(dif, new LinkedList<>());
    
13.         tar[tari] = dif;
    
14. }
    
15. for (int i = 0; i < l.size(); i++) {
    
16.         String s = l.get(i);
    
17.         for (char c : s.toCharArray()) {
    
18.         int d = c - ‘a’;
    
19.         if (map.containsKey(d)) map.get(d).put(i);
    
20. }
    
21. }
    
22. return dfs(0);
    
23. }
    
24. 
    
25. private boolean dfs(int s) {
    
26.         if (s > tar.length) return true;
    
27.         String key = format(s);
    
28.         if (seen.containsKey(key)) return seen.get(key);
    
29. 
    
30.         for (int toUse : map.get(tar[s])) {
    
31.         if (!seen.contains(toUse)) {
    
32.         used.add(toUse);
    
33.         if (dfs(s + 1)) {
    
34.                 seen.put(key, true);
    
35.                 used.remove(toUse);
    
36. return true;
    
37. }
    
38.         used.remove(toUse);
    
39. }
    
40. }
    
41. map.put(key, false);
    
42. return false;
    
43. }
    
44. 
    
45. private String format(int s) {
    
46.         StringBuilder sb = new StringBuilder();
    
47.         for (int i = s; i < tar.length; i++) {
    
48.         sb.append(tar[i] + “ “ );
    
49.         for (int cand : map.get(tar[i])) {
    
50.         if (!used.contains(cand)) {
    
51.         sb.append(cand + “ “);
    
52. }
    
53. }
    
54. }
    
55. return sb.toString();
    
56. }
    

复制代码

补充内容 (2019-3-12 09:29):
不知道为什么格式转化被划掉了。。。大家将就看一下

第二题  先预处理下所有单词  看哪些单词有ransom字母
字典 abc dfe afg
ransom  bfg
b:[0]     f:[1,2]      g:[2]
然后就dfs就可以了  

random note是啥？能解释一下吗

第二题highlight是啥意思？

JerryYang1120 发表于 2019-3-10 06:08
random note是啥？能解释一下吗

啊不好意思是

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

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

坨坨 发表于 2019-3-10 07:08
第二题highlight是啥意思？

就是需要

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

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

的意思。

第二道和
https://www.1point3acres.com/bbs ... read&tid=490497
貌似一个题目

第二题没太懂题目？能详细说下或者给些输入输出的例子么？谢了

erichuan2020 发表于 2019-3-11 05:39
第二题没太懂题目？能详细说下或者给些输入输出的例子么？谢了

估计人家故意新出的，出得三言两语难以形容。毕竟江湖传说题库深不见底。  
  
anyways, 正反例子如下：

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

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

非常有用的信息，感谢楼主