IXL电面已跪

面试官人很好，上来先介绍公司。然后讲一个自己的project。接着做题。
题目：Given target word, and a list of stick

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

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

00">
刚收到邮件，已跪。之前在地里的面经中并没见过这题。希望能对以后的同学有帮助。

之前的代码有Bug.
这个代码应该可以了

1. static int result = Integer.MAX_VALUE;
   
2. 
   
3.     static void minSourceWords(String[] words, String target) {
   
4.         search(words, target, 0, new ArrayList<>());
   
5.     }
   
6. 
   
7.     static void search(String[] words, String target, int start, List<String> source) {
   
8. 
   
9.         if (valid(target,source)) {
   
10.             result = Math.min(result, source.size());
    
11.             return;
    
12.         }
    
13. 
    
14.         if (start == words.length) {
    
15.             return;
    
16.         }
    
17. 
    
18.         for (int i = start; i < words.length; i++) {
    
19.             source.add(words[i]);
    
20.             search(words,target,i+1,source);
    
21.             source.remove(source.size()-1);
    
22.         }
    
23. 
    
24.     }
    
25. 
    
26.     static boolean valid(String target, List<String> source) {
    
27.         int[] map = new int[256];
    
28.         for (String s : source) {
    
29.             for (char c : s.toCharArray()) {
    
30.                 map[c] += 1;
    
31.             }
    
32.         }
    
33.         for (char c : target.toCharArray()) {
    
34.             if(--map[c] < 0) {
    
35.                 return false;
    
36.             }
    
37.         }
    
38.         return true;
    
39.     }

复制代码

看着可以用动态规划，其实是背包问题的变种

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

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

pat pat...那这个题的就应该返回2吗？  h i + story ?

每一个sticker里面的字母顺序可以打乱吗？

可以的，对顺序没有要求，结果要求用最少的sticker拼出来target就好

wendaomumu 发表于 2017-9-28 08:25
求问楼主什么时候做的OA？

很早了，大概八月份的时候。

想问楼主什么时候电面的？多谢~

09/25 周一刚面的

DFS和用current result做domain reduction? 请问一下有polynomial time的解法么？

fledgling 发表于 2017-9-28 09:22
DFS和用current result做domain reduction? 请问一下有polynomial time的解法么？

额这我也不知道了。。。