g家实习电面跪经

昨天的实习电面

第一个看名字是个白人，题目是这样的

Given a class IntSetIter with mothods “hasNext()” and“next()”, implement a class UnionSetIter that takes into two IntSetIter’s andproduce a new IntSetIter

我看题看了挺久的，然后说可以 一开始把两个<

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

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

e="宋体">题follow－up是如果把A变大写，所有的A都要大写

我用backtracking写的，小哥人很nice，提示下修了不少bug，还问了时间复杂度。followup写完，小哥说还可以优化，但是没时间了，就结束了。

目测已跪，发面经攒rp吧

写了个代码，应该还能优化。

1.         public static Set<String> generateBig(String input,Set<Character> set)
   
2.         {
   
3.                 Set<String> st = new HashSet<String>();
   
4.                 String tempStr = input;
   
5.                 helperGenerator(st, tempStr,input,0,set);
   
6.                
   
7.                  return st;
   
8.         }
   
9.        
   
10.         public static void helperGenerator(Set<String> res, String sb, String word, int index,Set<Character> set)
    
11.         {   
    
12. 
    
13. 
    
14.                         Iterator<Character> itr = set.iterator();
    
15.                        
    
16.                         while(itr.hasNext())
    
17.                         {
    
18.                                 char temp = itr.next();
    
19. 
    
20.                                 //"airplane"
    
21.                                 for(int i = index; i < word.length();i++)
    
22.                                 {
    
23.                                 if(word.charAt(i)==temp)
    
24.                                 {   
    
25.                                     res.add(sb);
    
26.                                         helperGenerator(res,sb,word,i+1,set);
    
27.                                         StringBuilder sb1 = new StringBuilder(sb);
    
28.                                         sb1.setCharAt(i,Character.toUpperCase(word.charAt(i)));
    
29.                                     res.add(sb1.toString());
    
30.                                         helperGenerator(res,sb1.toString(),word,i+1,set);
    
31.                                        
    
32.                                 }       
    
33.                         }       
    
34.                 }
    
35.                 //sb.setLength(lengthTemp);
    
36.         }
    
37. 
    

复制代码

lz, set 是排好序的么？

补充内容 (2016-2-18 06:12):
搞错了 不是说要返回两个set一样的值哈？ 那道题的考点是什么？ 需要顺序返回set的element么？

muybienw 发表于 2016-3-6 03:52
第一题现在能想到的就是先不断next()第一个iterator，然后把读取过的数据记下来，然后在next()第二个iterat ...

follow up, 可以加一个map,来记录，

1. public class CapitalAndLowercaseStringsII {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 Set<Character> set = new HashSet<Character>();
   
5.                 set.add('a');
   
6.                 set.add('p');
   
7.                 List<String> res = generataAllStringFollowUp("airpalne", set);
   
8.                 for (String s : res) {
   
9.                         System.out.println(s);
   
10.                 }
    
11.         }
    
12. 
    
13.         public static List<String> generataAllStringFollowUp(String input,
    
14.                         Set<Character> set) {
    
15.                 List<String> res = new ArrayList<String>();
    
16.                 if (input == null || input.length() == 0) {
    
17.                         return res;
    
18.                 }
    
19.                 HashMap<Character, Character> map = new HashMap<Character, Character>();
    
20.                 helper(res, new StringBuilder(), set, input, 0, map);
    
21.                 return res;
    
22.         }
    
23. 
    
24.         public static void helper(List<String> res, StringBuilder sb,
    
25.                         Set<Character> set, String input, int pos,
    
26.                         HashMap<Character, Character> map) {
    
27.                 if (pos == input.length()) {
    
28.                         res.add(sb.toString());
    
29.                         return;
    
30.                 }
    
31.                 char c = input.charAt(pos);
    
32.                 if (!set.contains(c)) {
    
33.                         sb.append(c);
    
34.                         helper(res, sb, set, input, pos + 1, map);
    
35.                         sb.deleteCharAt(sb.length() - 1);
    
36.                 } else {
    
37.                         if (map.containsKey(c)) {
    
38.                                 char ch = map.get(c);
    
39.                                 sb.append(ch);
    
40.                                 helper(res, sb, set, input, pos + 1, map);
    
41.                                 sb.deleteCharAt(sb.length() - 1);
    
42.                         } else {
    
43.                                 sb.append(c);
    
44.                                 map.put(c, c);
    
45.                                 helper(res, sb, set, input, pos + 1, map);
    
46.                                 sb.deleteCharAt(sb.length() - 1);
    
47.                                 map.remove(c);
    
48.                                 char capital = (char) (c - 'a' + 'A');
    
49.                                 map.put(c, capital);
    
50.                                 sb.append(capital);
    
51.                                 helper(res, sb, set, input, pos + 1, map);
    
52.                                 sb.deleteCharAt(sb.length() - 1);
    
53.                                 map.remove(c);
    
54.                         }
    
55.                 }
    
56.         }
    
57. }
    

复制代码

set是无序的，可随意返回值，但是不能有duplicate

请问一下楼主第一题，可以拿一个HashSet把输出过的都加进去么....不然真想不到别的办法去重了......

谢谢楼主面经。楼主答的还不错啊。第二题 follow up 怎么优化呢？

第一题除非是sorted 否则不看整个set怎么可能判断？

echo33 发表于 2016-2-18 07:36
第一题除非是sorted 否则不看整个set怎么可能判断？

或者是不允许你construct new set但是可以读完其中一个set存储到hash table里？

echo33 发表于 2016-2-18 07:39
或者是不允许你construct new set但是可以读完其中一个set存储到hash table里？

可以construct new set，但是不能一次都读完

lxxxxxxx 发表于 2016-2-18 06:53
请问一下楼主第一题，可以拿一个HashSet把输出过的都加进去么....不然真想不到别的办法去重了......

可以的

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

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