一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 5583|回复: 31
收起左侧

01/20 Google intern phone screen

[复制链接] |试试Instant~ |关注本帖
Tsien 发表于 2016-1-21 14:19:11 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
动作比较晚,到寒假才开始找实习,结果Google差不多成了我的处女面,之前都没面试经验(我知道要先拿小公司试水,但小公司网投都没回音==!),所以没抱太大希望,权当积累经验了。. 1point 3acres 璁哄潧
.鐣欏璁哄潧-涓浜-涓夊垎鍦
一面:国男.1point3acres缃
上来先谈简历,做过的一些项目,大概扯了十分钟左右。
然后做题:encoder and decoder
Example: aaaabbbbcc5555->4xa4xbcc4x5->aaaabbbbcc5555
我直接用naive方法做了,Two Pointers。这个方法的局限是只能做连续字母个数小于10的那种,比如21a,decoder就不知道是21a还是21个a。
写程序后,让跑个test case,像debug一样一步步讲,途中问了一个pointer的问题。
然后让分析算法复杂度。
接着是一堆OOD的问题: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
什么是virtual function,什么时候用?
什么时候用virtual deconstrutor ?
这些都在cc150中有。
最后还有时间,就让我提问,我就问了intern都干些什么,小公司还是大公司对个人发展更有帮助,还有就是对于interview有什么建议?
他最后说我除了边界条件没处理,其他都做的挺好的,他会给我good feedback。(这里真的很感谢这些前辈!!!给了我很大信心!)

. from: 1point3acres.com/bbs
二面:白男
上来直接问我做过的一个Android项目,问的挺细致的,让我讲扫描二维码登陆的具体实现原理。。。
然后做题:
A: 34567
B: 45678. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
C: 67345
交换A中的数字位置,得到一个新的数C,使得C大于B。
我的想法是,每次挑出最大的那个digit跟前面的swap,直到找大于B的,时间复杂度是O(n*n);corner case:当A、B的digits个数不等时,直接返回结果。
这时候小哥给了hint说这本质上是一个sort问题,那么sort问题你ideal复杂度应该是多少呢?sort我就直接想到了quicksort,我就说找最大digit的那个过程可以用quick select,这样就是O(nlogn)了。然后让用test case跑一边quick select,让分析复杂度。. 1point3acres.com/bbs

Follow up: 存在很多这样的C,返回其中最小的那个。
因为要把integer的digits一个个拿出来,弄成array,比较麻烦,就只让讲了下想法,然后用test case跑一边
最小的就是离B最近的那个,所以我的想法是,从B开始找。因为B中可能存在A没有digits,所以先作差集A-B={3},把B中的8替换成3,得到45673.. 1point 3acres 璁哄潧
然后从B的尾巴开始,保持一个递减的序列B[i - 1] > B[i],直到碰到一个B[i - 1] < B[i], 则B[i - 1]跟B[i...n]中第一个比B[i - 1]大的那个交换,得到45763,然后使B[i...n]递增,得到45736。
感觉我是弄的太复杂,消耗了很多时间,最后小哥感觉不耐烦了,到了45分钟,就直接说了thanks for your time就挂了,我都还没缓过神了。


总体来说,一面encoder、deconder之前见过,但没有去实现,OOD问题CC150中见过;二面的题目没见过,所以感觉很虚。。。. more info on 1point3acres.com
Anyway,权当积累经验,攒RP了!



评分

4

查看全部评分

本帖被以下淘专辑推荐:

韦斯特大人 发表于 2016-1-22 04:49:00 | 显示全部楼层
第二题follow up我觉得可以先scan一遍B,把A中的digits当做一个bag,尽可能地匹配B
. 鍥磋鎴戜滑@1point 3 acres
例如
A: 34567. more info on 1point3acres.com
B: 45678
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
然后我们匹配成了 A' 4567  (3)剩余没有用     B 4567 | 8

然后我们的目标就是从剩余没用的数字里,找到比 第一个不匹配值 大的 最小值,如果找不到,就往前移一位,再把A‘的前一位算在没用的里面继续重复上面的运算

例如   A' 4567  (3)          B 4567 | 8   找不到比8大的数,我们就往前移一位
         A' 456  (7, 3)          B 456 | 7 8  找不到比7大的数,再往前移一位
         A' 45  (6, 7, 3)          B 45 | 6 7 8  找到了比6大的最小的数为7,所以我就设没用的数字里最高位为7, 其他剩余数字就按升序使用就好了,结果就是45736了,不过算法复杂度感觉也需要 n^2
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


回复 支持 3 反对 0

使用道具 举报

wtcupup 发表于 2016-1-21 14:44:43 | 显示全部楼层
楼主准备下半年直接开始找full time ?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-21 14:54:56 | 显示全部楼层
写了个第一题。
  1.        
  2.         public static String encode(String input)
  3.         {
  4.                 StringBuilder sb = new StringBuilder();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.                 int times;
  6.                 for(int i =0; i < input.length();i++)
  7.                 {
  8.                         times =1;
  9.                         while(i+1<input.length()&&input.charAt(i)==input.charAt(i+1))
  10.                         {. 1point3acres.com/bbs
  11.                                 times++;
  12.                                 i++;
  13.                         }. From 1point 3acres bbs
  14.                         sb.append(times);
  15.                         sb.append("#");
  16.                         sb.append(input.charAt(i));
  17.                        
  18.                 }
  19.                 . From 1point 3acres bbs
  20.                 return sb.toString();
  21.         }
  22.        
  23.         public static String decode(String input)-google 1point3acres
  24.         {
  25.                 StringBuilder sb = new StringBuilder();
  26.                 int i =0;
  27.        
  28.                 while(i<input.length())
  29.                 {. more info on 1point3acres.com
  30.                         int index = input.indexOf('#',i);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  31.                         System.out.println("#" + index);
  32. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33.                         int wordLength = Integer.parseInt(input.substring(i, index));
  34.                         char word = input.charAt(index+1);
  35.                         for(int j =0; j < wordLength;j++).1point3acres缃
  36.                         {
  37.                                 sb.append(word);
  38.                         }
  39.                         i = index+2;
  40. -google 1point3acres
  41.                         System.out.println(sb.toString());
  42.                 }
  43.                
  44.                 return sb.toString();
  45.                
  46.         }
  47.        
  48.         public static void main(String[] args)
  49.         {
  50.                 String test ="aaaaaaaaaaaaaaaaabbcde";
  51.                 String en = encode(test);
  52.                 System.out.println(en);
  53.                 String de = decode(en);. visit 1point3acres.com for more.
  54.                 System.out.println(de);
  55.                 System.out.println(de.equalsIgnoreCase(test));
  56.                         . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  57.         }
复制代码

. From 1point 3acres bbs

补充内容 (2016-1-21 14:57):
有错误,没看到你能input int。我改下。

补充内容 (2016-1-21 20:09):
这道题无解吧。。4xa4xbcc4x5,如果把cc换成33,你怎么知道是33还是335的5呢。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-21 15:01:18 | 显示全部楼层

这个代码是对的。。可以handle你那个情况。。

补充内容 (2016-1-21 15:04):
3333333333333333334444444444444444cd55555555555555e
这个情况可以handle

补充内容 (2016-1-21 15:07):
把 #换成x,不受任何影响。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-21 15:02:58 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-21 15:01
这个代码是对的。。可以handle你那个情况。。

要不把第二个也写下?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-21 15:05:10 | 显示全部楼层
wtcupup 发表于 2016-1-21 15:02. 1point3acres.com/bbs
要不把第二个也写下?

行,我现在写。
回复 支持 反对

使用道具 举报

 楼主| Tsien 发表于 2016-1-21 15:18:39 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-21 15:01
这个代码是对的。。可以handle你那个情况。。

补充内容 (2016-1-21 15:04):

赞!&#128077;我之前看到这题时要是也像你一样实现一遍就好了。。。.1point3acres缃
不过有个问题:5x--decode--> 'xxxxx' or '5x' . visit 1point3acres.com for more.
怎么处理这种case?
回复 支持 反对

使用道具 举报

 楼主| Tsien 发表于 2016-1-21 15:19:38 | 显示全部楼层
wtcupup 发表于 2016-1-21 14:44
楼主准备下半年直接开始找full time ?

不。。。先再找找实习
回复 支持 反对

使用道具 举报

MCwong 发表于 2016-1-21 15:24:53 | 显示全部楼层
感谢lz分享,第一轮面试官有没有要求encode后字符串的长度一定要比之前短?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-21 15:28:29 | 显示全部楼层
Tsien 发表于 2016-1-21 15:18
赞!&#128077;我之前看到这题时要是也像你一样实现一遍就好了。。。
不过有个问题:5x--decode--> 'xxxx ...

我的代码可以跑这个coner case的。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-21 15:29:10 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-21 15:05 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
行,我现在写。

我觉得第二题的第一小问就是先把B给从大到小sort了,sort的值肯定大于A,但是follow up不太会求指导
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-21 15:40:35 | 显示全部楼层
wtcupup 发表于 2016-1-21 15:29
. visit 1point3acres.com for more.我觉得第二题的第一小问就是先把B给从大到小sort了,sort的值肯定大于A,但是follow up不太会求指导

我是用permutation做的。。组成所有可能,然后比较,但是这么太麻烦了。我正在想,有没有简单的方法。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-21 15:55:36 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-21 15:40
我是用permutation做的。。组成所有可能,然后比较,但是这么太麻烦了。我正在想,有没有简单的方法。

我倒是有个办法 ,假设当前是A,在A[i+1....n-1]中挑出一个>= B的元素交换,(比如说A:34567, B:45678,交换4和3因为4>=4,每次交换后用一个function比较B和C,如果还是小,继续swapA中的下一个: 34567->43567->45367->45637->45673, reset 到45367,然后45763->45736 45736是最后答案 要用backtracking做,但是我真正要把它转换成代码有点难,你看看呢?
回复 支持 反对

使用道具 举报

 楼主| Tsien 发表于 2016-1-21 16:07:52 | 显示全部楼层
MCwong 发表于 2016-1-21 15:24
感谢lz分享,第一轮面试官有没有要求encode后字符串的长度一定要比之前短?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
面试官没说。
不过,我觉得题目里已经隐含了这个要求。从给的例子看,encode的时候,如果重复字符个数小于3,那就leave it。所以encode以后的字符串肯定小于等于原字符串吧
回复 支持 反对

使用道具 举报

 楼主| Tsien 发表于 2016-1-21 16:09:50 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-21 15:28
我的代码可以跑这个coner case的。

打错了。。。
应该是:'5xx' decode之后,should be 'xxxxx' or '5xx',因为这两个字符串encode结果都是'5xx'。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我是觉得这种编码方法本身就有问题==!

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-21 16:25:53 | 显示全部楼层
你的follow up我做出了。。泪留满面阿。。
  1.         public static ArrayList<Integer> covertIntToIntListHelper(int input). 鍥磋鎴戜滑@1point 3 acres
  2.         {
  3.                 ArrayList<Integer> nums = new ArrayList<Integer>();
  4.                
  5.                 for(int i =0; i < Integer.toString(input).length();i++)
  6.                 {. more info on 1point3acres.com
  7.                         nums.add((int) Integer.toString(input).charAt(i));
  8.                 }
  9.                
  10.                 return nums;
  11.         }. from: 1point3acres.com/bbs
  12.         .1point3acres缃
  13.         public static ArrayList<Integer> covertIntToIntListSortedHelper(int input)
  14.         {
  15.                 ArrayList<Integer> nums = new ArrayList<Integer>();
  16.                 . visit 1point3acres.com for more.
  17.                 for(int i =0; i < Integer.toString(input).length();i++)
  18.                 {
  19.                         nums.add((int) (Integer.toString(input).charAt(i)-'0'));
  20.                 }
  21.                
  22.                 Collections.sort(nums);. 1point 3acres 璁哄潧
  23.                 return nums;
  24.         }
  25.        
  26.         public static int followUPusingNaturalComparaing(int A,int B)
  27.         {. 鍥磋鎴戜滑@1point 3 acres
  28.                 . Waral 鍗氬鏈夋洿澶氭枃绔,
  29.                 ArrayList<Integer> Aarray = covertIntToIntListHelper(A);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  30.                 ArrayList<Integer> Barray = covertIntToIntListSortedHelper(B);-google 1point3acres
  31.                 System.out.println(Barray);
    .1point3acres缃
  32.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  33.                 ArrayList<Integer> newArr = new ArrayList<Integer>();
  34.                 boolean goOut = false;
  35.                
  36.                 for(int i =0; i < Aarray.size();i++). From 1point 3acres bbs
  37.                 {
  38.                         for(int j=0; j < Barray.size();j++)
  39.                         {
  40.                                 if(Barray.get(j)==Aarray.get(i))
  41.                                 {
  42.                                         newArr.add(Barray.get(j));
  43.                                         Barray.remove(j);
  44.                                 }
  45.                                 else if(Barray.get(j)>Aarray.get(i)). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  46.                                 {
  47.                                         newArr.add(Barray.get(j));
  48.                                         Barray.remove(j);
  49. . Waral 鍗氬鏈夋洿澶氭枃绔,

  50.                                         goOut = true;
  51.                                         break;
  52.                                 }
  53.                         }
  54.                         if(goOut==true)
  55.                         {
  56.                                 break;
  57.                         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  58.                 }.1point3acres缃
  59.                 .鐣欏璁哄潧-涓浜-涓夊垎鍦
  60.                 List<Integer> result = new ArrayList<Integer>(newArr);
  61.                 result.addAll(Barray);
  62.                 StringBuilder sb = new StringBuilder();
  63.                
  64.                 for(int i =0; i < result.size();i++)
  65.                 {
  66.                         sb.append(result.get(i));
  67.                        
  68.                 }
  69.                 return Integer.parseInt(sb.toString());
  70. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  71.                
  72.         }
复制代码

鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2016-1-21 16:57):
有个corner case不能handle.
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-21 16:32:46 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-21 16:25
你的follow up我做出了。。泪留满面阿。。

我的算法是. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
比如我们有2个数
a=3423 b=3524.鐣欏璁哄潧-涓浜-涓夊垎鍦
我们现在要重新组成a,得到一个比b大的数,条件是比b大的最小数。. 1point 3acres 璁哄潧
我的思路是,我重组a,变成a为最小的数, 现在a = 2334.
然后走2个for loop,a的第1个char是2,比b的第1个char 3小,我们继续扫,发现a的第2个char和b的第1个char一样,我们加进新的result里面并且从原本的a里面删除,继续扫,知道找到第1个a的char比当前b的char大的时候,我们break 2个for loops。. From 1point 3acres bbs
然后把加进result里面的数和剩下在result里面的数,组成新的结果。。

补充内容 (2016-1-21 16:35):
剩下在a里面的数。。不是剩下在result里面的数。

补充内容 (2016-1-21 16:57):
有个corner case不能handle.
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-21 18:05:21 | 显示全部楼层
有其他人,有最优解法么。
我改了改代码,这次应该ok了。。
  1.        
  2.         public static int findLargestFirstQuestion(int input). From 1point 3acres bbs
  3.         { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4.                 int[] nums = new int[Integer.toString(input).length()];
  5.                
  6.                 for(int i =0; i < Integer.toString(input).length();i++)
  7.                 {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.                         nums[i] = Integer.toString(input).charAt(i);
  9.                 }
  10.                
  11.                 Arrays.sort(nums);
  12.                
  13.                 StringBuilder sb = new StringBuilder();
  14.                 for(int i =nums.length-1; i>=0;i--)
  15.                 { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  16.                         sb.append(nums[i]);
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17.                 }
  18.                
  19.                 return Integer.parseInt(sb.toString());

  20.                
  21.         }
  22.        
  23.         public static int largestCurrent(List<Integer> input)
  24.         {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  25.                 int[] nums = new int[input.size()];
  26.                
  27.                 for(int i =0; i < input.size();i++)
  28.                 {
    . 1point3acres.com/bbs
  29.                         nums[i] = input.get(i);. from: 1point3acres.com/bbs
  30.                 }
  31.                
  32.                 Arrays.sort(nums);
  33.                
  34.                 StringBuilder sb = new StringBuilder();. Waral 鍗氬鏈夋洿澶氭枃绔,
  35.                 for(int i =nums.length-1; i>=0;i--)
  36.                 {. more info on 1point3acres.com
  37.                         sb.append(nums[i]);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  38.                 }
  39.                
  40.                 return Integer.parseInt(sb.toString());
  41.                 . visit 1point3acres.com for more.
  42.         }
  43.         public static ArrayList<Integer> covertIntToIntListHelper(int input)
  44.         {
  45.                 ArrayList<Integer> nums = new ArrayList<Integer>();
  46.                
  47.                 for(int i =0; i < Integer.toString(input).length();i++)
  48.                 {
  49.                         nums.add((int) (Integer.toString(input).charAt(i)-'0'));
  50.                 }
  51.                
  52.                 return nums;
  53.         }
  54.         . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  55.         public static ArrayList<Integer> covertIntToIntListSortedHelper(int input).1point3acres缃
  56.         {
  57.                 ArrayList<Integer> nums = new ArrayList<Integer>();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  58.                
  59.                 for(int i =0; i < Integer.toString(input).length();i++)
  60.                 {
  61.                         nums.add((int) (Integer.toString(input).charAt(i)-'0'));
  62.                 }. more info on 1point3acres.com
  63.                
  64.                 Collections.sort(nums);
  65.                 return nums;
  66.         }
  67.         .鐣欏璁哄潧-涓浜-涓夊垎鍦
  68.         public static int covertListToInteger(List<Integer> input). more info on 1point3acres.com
  69.         {
  70.                 StringBuilder sb = new StringBuilder();

  71.                 for(int i =0; i < input.size();i++)
  72.                 {
  73.                         sb.append(input.get(i));. from: 1point3acres.com/bbs
  74.                 }
  75.                        
  76.                 return Integer.parseInt(sb.toString());.鏈枃鍘熷垱鑷1point3acres璁哄潧
  77.         }
  78.         .1point3acres缃
  79.         public static int followUPusingNaturalComparaing(int A,int B)
  80.         {
  81.                
  82.                 ArrayList<Integer> Aarray = covertIntToIntListHelper(A);
  83.                 ArrayList<Integer> Barray = covertIntToIntListSortedHelper(B);
  84.         //        ArrayList<Integer> indexToRemove = new ArrayList<Integer>();
  85.                
  86.                 ArrayList<Integer> newArr = new ArrayList<Integer>();
  87.                 boolean goOut = false;
  88.                 boolean breakInside;

  89.                 for(int i =0; i < Aarray.size();i++)
  90.                 {
  91.                         breakInside = false;
  92.                         for(int j=0; j < Barray.size();j++)
  93.                         {
  94.                                 ArrayList<Integer> currentBarray = new ArrayList<Integer>(Barray);
  95.                                 ArrayList<Integer> currentAarray = new ArrayList<Integer>(Aarray);
  96.                                 for(int remove =0; remove <=j;remove++). 1point 3acres 璁哄潧
  97.                                 {
  98.                                         currentAarray.remove(remove);. 鍥磋鎴戜滑@1point 3 acres
  99.                                 }-google 1point3acres
  100.                                 currentBarray.remove(j);
  101.                                 System.out.println(newArr);
  102.                                 if(Barray.get(j)==Aarray.get(i)&&largestCurrent(currentBarray)>covertListToInteger(currentAarray))
  103.                                 {. 1point 3acres 璁哄潧

  104.                                         newArr.add(Barray.get(j));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  105.                                         Barray.remove(j);
  106.                                         breakInside = true;
  107.                                         j--;
  108.                                 }
  109.                                 else if(Barray.get(j)==Aarray.get(i)&&largestCurrent(currentBarray)<=covertListToInteger(currentAarray))
  110.                                 {
  111.                                         System.out.println("convert" +covertListToInteger(currentAarray));. more info on 1point3acres.com
  112.                                         System.out.println("largest" +largestCurrent(currentBarray));
  113.                                         //System.out.println(Barray.get(j));. 1point 3acres 璁哄潧
  114.                                         while(Barray.get(j)<=Aarray.get(i))
  115.                                         {. Waral 鍗氬鏈夋洿澶氭枃绔,
  116.                                                 j++;
  117.                                         }
  118.                                         //45678
  119.                
  120.                                         //34567
  121.                                         newArr.add(Barray.get(j));
  122.                                         Barray.remove(j);
  123.                                         List<Integer> result = new ArrayList<Integer>(newArr);
  124.                                         result.addAll(Barray);
  125.                                         StringBuilder sb = new StringBuilder();
  126.                                        
  127.                                         for(int ii =0; ii < result.size();ii++)
  128.                                         {
  129.                                                 sb.append(result.get(ii));
  130.                                                
  131.                                         }
  132.                                         return Integer.parseInt(sb.toString());

  133.                                 }
  134.                                 else if(Barray.get(j)>Aarray.get(i))
  135.                                 {. 鍥磋鎴戜滑@1point 3 acres
  136.                                         newArr.add(Barray.get(j));
  137.                                         Barray.remove(j);
  138.                                         j--;


  139.                                         goOut = true;
  140.                                         break;
  141.                                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  142.                                 if(breakInside==true)
  143.                                 {
  144.                                         break;
  145.                                 }
  146.                         }. 鍥磋鎴戜滑@1point 3 acres
  147.                         if(goOut==true)
  148.                         {
  149.                                 break;
  150.                         }
  151.                 }
  152.                
  153.                 List<Integer> result = new ArrayList<Integer>(newArr);
  154.                 System.out.println(newArr);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  155.                 result.addAll(Barray);
  156.                 StringBuilder sb = new StringBuilder();
  157.                 .1point3acres缃
  158.                 for(int i =0; i < result.size();i++). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  159.                 {
  160.                         sb.append(result.get(i));
  161.                        
  162.                 }. visit 1point3acres.com for more.
  163.                 return Integer.parseInt(sb.toString());

  164.                
  165.         }
  166.        
  167.         public static void main(String[] args)
  168.         {
  169.                 int test = followUPusingNaturalComparaing(3567,7643);//4778
  170.                 System.out.println(test);
    . 1point 3acres 璁哄潧
  171.         }
复制代码
回复 支持 反对

使用道具 举报

snooze 发表于 2016-1-21 18:12:09 | 显示全部楼层
第二问follow up我觉得可以用回溯+剪枝来做。

混合了多种风格的伪代码,结合注释看吧。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
int small = INT_MAX;

int findLarger(vector<int> A, vector<int> B){
        search(A, B);
        return small;
}
. Waral 鍗氬鏈夋洿澶氭枃绔,
search(vector<int> A, vector<int> B, vector<int> current){
        for(int a : A){                                                                     //对于A中的每一个数字a
                if(a > B[0])                                                                //如果a大于B的第一个数字
                        small = min(small, current '+' a '+' sort(A-a) )   //  small在这俩中取小的一个:1. small, 2. (current放在最前,a当成之后的一个数字,然后A去掉a的部分从小到大排列)这样构造成的数字

                if(a == B[0]){                                                             //如果a等于B的第一个数字
                        current.push_back(a);               
                        search(A-a, B[1:]);                                            //递归地搜,A变成了A去掉a的新数字,B变成了B去掉第一个数字的新数字
                        current.pop_back();
                }
        }
}

只有满足if(a == B[0])的时候才会递归地搜索,平均时间复杂度应该还好。有问题请帮忙指出。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-21 18:23:11 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-21 18:05. 1point3acres.com/bbs
有其他人,有最优解法么。
我改了改代码,这次应该ok了。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
思路,
a, b。我们要把a重组成一个数,大于b,且为a的最小可能。
我把a变成了a能组成的最小数。比如,a=34567, b = 45678
走2个for loops.. from: 1point3acres.com/bbs
a是inner loop。
b是out loop.
我们比较的时候分成3种情况,
如果当前a比当前的b,小,我们继续走。
如果当前a和当前的相等,是最复杂的情况。
这个情况又分为2种情况,如果当a = b,那么,a后面的数,能不能组成一个比b后面的数大的情况,如果是,我们把当前a加入result里面。
如果不能,我们停止所有for loops, 在a里面找到一个大于b当前的数,这个数且为a大于b的最小数。
第3种情况,当前a之前大于b,加入a进result.
这是我们把a分成2部分,一部分已经append result里面了么。我们只需要把剩下的a,继续append 进result即可。

code flow:
A=34567, B = 45678-google 1point3acres
a的第1个char 比b的第1个char小。我们继续扫,发现a的第2个char和b的第1个char相同。如果,我们要看,a剩下的 567 能否组成一个数比b剩下的678大呢?我们发现可以,如果result.add(4)进来,并从a里面remove 4。a还剩下3567.
然后继续扫,发现a的第2个char 5和b的第2个char 5相同,我们继续看,a剩下的367能否组成一个数,比b剩下的678大呢。我们发现,可以,继续result.add(5),并从a里面减去5。我们继续扫,发现a的第2个char和b的第3个char 6相同,我们发现a剩下的37不能组成一个比b剩下的78大,如果我们从a里面找到第1个比6大的数,是7. result.add(7), 并从a里面减去7。 这是result 是 457. a剩下了36. 我们组合,成45736.
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-19 09:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表