狗家面经+吐槽

hot2346 发表于 2016-12-29 08:51
可能二面确实比较坑，遇到非要抓 code style的面试官， 真是运气问题。

然后problem 1 跟follow up1，  ...

层主好厉害...我就用的比较传统的方法，但我觉得应付面试应该够了...

hot2346 发表于 2016-12-29 10:13
我们能做的只能是尽力，然后剩下的交给运气。

真的感觉运气太重要了

在浙里 发表于 2016-12-29 09:10
狗狗还在招实习吗？

应该还在

请问楼主怎么用backtracking做的？

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

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

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

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

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

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

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

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

hot2346 发表于 2016-12-29 08:51
可能二面确实比较坑，遇到非要抓 code style的面试官， 真是运气问题。

然后problem 1 跟follow up1，  ...

分享我基于匈牙利法的代码~ 应该还挺清晰的，参考链接：http://blog.csdn.net/dark_scope/article/details/8880547

1. public class diceWords {
   
2.         interface find {
   
3.             boolean isAnyDice(int index);
   
4.         }
   
5.         public static boolean findWord(String[] words, String word){
   
6.                 char[] arr = word.toCharArray(); boolean bb = true;
   
7.                 int len = words.length;
   
8.                 int[] tried = new int[len]; int husband[] = new int[len];
   
9.                 int wife[] = new int[word.length()];
   
10.                 find f = new find(){
    
11.                         @Override
    
12.                         public boolean isAnyDice(int index) {
    
13.                                 for (int j=0;j<len;j++){    //扫描每个骰子
    
14.                                            if (words[j].indexOf(arr[index])!=-1 && tried[j]==-1)      
    
15.                                         //如果骰子j有包含index的char并且还没有标记过，那么我就@@@“试图”@@@拿j做我老婆；
    
16.                                     //这个试图是跟这轮绑定的，每一轮以后清零；
    
17.                                     //(这里标记的意思是这次查找曾试图改变过该骰子的归属问题，但是没有成功，所以就不用瞎费工夫了）
    
18.                                         {
    
19.                                                 tried[j]=1;
    
20.                                                 if (husband[j]==-1 || isAnyDice(husband[j])) {
    
21.                                                         //骰子j没被抢了当老婆（没老公），那j是我的了！
    
22.                                                         //或者index的char能占其他骰子（isAnyDice(husband[j])实际上是isAnyOtherDice），那我还是可以把j当老婆，这里使用递归
    
23.                                                         husband[j]=index;
    
24.                                                         wife[index] = j;
    
25.                                                         return true;
    
26.                                                 }
    
27.                                         }
    
28.                                 }
    
29.                                 return false;
    
30.                         }
    
31.                        
    
32.                 };                       
    
33.                 memset(husband,-1,len); memset(wife,-1,word.length());     
    
34.                 for (int i=0; i<arr.length; i++){
    
35.                         memset(tried,-1,len); //每一步清空tried；
    
36.                         bb = bb&&f.isAnyDice(i);
    
37.                 }
    
38.                 for(int i=0; i<word.length(); i++){
    
39.                         System.out.println(wife[i]);//print couple!
    
40.                 }
    
41.                 return bb;
    
42.         }
    
43. 
    
44.         private static void memset(int[] arr, int a, int len){
    
45.                 for(int i=0; i<len; i++){
    
46.                         arr[i] = a;
    
47.                 }
    
48.         }
    
49.         public static void main(String[] args){
    
50.                 String[] strarr = {"hewqed","doaefj","krelnv","fewqds"};
    
51.                 boolean ha = false;
    
52.                 ha = findWord(strarr,"khoq");
    
53.                 System.out.print(ha);
    
54.         }
    
55. }
    

复制代码

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

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