一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1370|回复: 25
收起左侧

g家实习电面跪经

[复制链接] |试试Instant~ |关注本帖
tjnkzll 发表于 2016-2-18 03:26:03 | 显示全部楼层 |阅读模式

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

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

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

x
昨天的实习电面
第一个看名字是个白人,目是这样
Given a class IntSetIter with mothods “hasNext()” and“next()”, implement a class UnionSetIter that takes into two IntSetIter’s andproduce a new IntSetIter
我看看了挺久的,然后可以 一开始把两个set合并成一个set,然后返回iterator
不要一开始就合并,如果两个set很大的 construct个新set时间太久,要求在hasNext()和next()里直接用两个定的iterator返回。又想了挺久,感最后写出来是有bug
要跪了,面完都不想面第二个了。
第二个国人小哥,目是小哥口述的。
一个string和一个character set,要求出所有的可能的string,把在character set 里的string里的char成大写或者保持小写
比如airplane a,p} {airpalne,Airplane, AirPlane,AirplAne, airPlane, ...}
然后第二followup是如果把A大写,所有的A都要大写
我用backtracking写的,小哥人很nice,提示下修了不少bug,还问了时间复杂度。followup写完,小哥说还可以优化,但是没时间了,就结束了。

目测已跪,发面经攒rp吧

xiaozhuxiaozhu 发表于 2016-2-18 09:58:27 | 显示全部楼层
写了个代码,应该还能优化。

  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. . 鍥磋鎴戜滑@1point 3 acres

  13. . visit 1point3acres.com for more.
  14.                         Iterator<Character> itr = set.iterator();
  15.                        
  16.                         while(itr.hasNext())
  17.                         {
  18.                                 char temp = itr.next();-google 1point3acres

  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.         }

复制代码
回复 支持 1 反对 0

使用道具 举报

christy.zhang 发表于 2016-2-18 06:08:29 | 显示全部楼层
lz, set 是排好序的么?

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

使用道具 举报

 楼主| tjnkzll 发表于 2016-2-18 06:39:50 | 显示全部楼层
set是无序的,可随意返回值,但是不能有duplicate
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-2-18 06:53:46 | 显示全部楼层
请问一下楼主第一题,可以拿一个HashSet把输出过的都加进去么....不然真想不到别的办法去重了......
回复 支持 反对

使用道具 举报

joana92 发表于 2016-2-18 06:56:34 | 显示全部楼层
谢谢楼主面经。楼主答的还不错啊。第二题 follow up 怎么优化呢?
回复 支持 反对

使用道具 举报

echo33 发表于 2016-2-18 07:36:02 | 显示全部楼层
第一题除非是sorted 否则不看整个set怎么可能判断?
回复 支持 反对

使用道具 举报

echo33 发表于 2016-2-18 07:39:29 | 显示全部楼层
echo33 发表于 2016-2-18 07:36
第一题除非是sorted 否则不看整个set怎么可能判断?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
或者是不允许你construct new set但是可以读完其中一个set存储到hash table里?
回复 支持 反对

使用道具 举报

 楼主| tjnkzll 发表于 2016-2-18 07:48:56 | 显示全部楼层
echo33 发表于 2016-2-18 07:39
或者是不允许你construct new set但是可以读完其中一个set存储到hash table里?

可以construct new set,但是不能一次都读完
回复 支持 反对

使用道具 举报

 楼主| tjnkzll 发表于 2016-2-18 07:49:31 | 显示全部楼层
lxxxxxxx 发表于 2016-2-18 06:53
请问一下楼主第一题,可以拿一个HashSet把输出过的都加进去么....不然真想不到别的办法去重了......

可以的



.1point3acres缃

回复 支持 反对

使用道具 举报

 楼主| tjnkzll 发表于 2016-2-18 07:54:36 | 显示全部楼层
joana92 发表于 2016-2-18 06:56
谢谢楼主面经。楼主答的还不错啊。第二题 follow up 怎么优化呢?

我是用一个set纪录已经visit过的set里有的char,下次再遇到就跳过。我估计小哥是想让我判断下这个set的大小和原string里所有char的个数,如果相等就break。不过没来及想出这个来,时间就到了。
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-2-18 09:26:45 | 显示全部楼层
tjnkzll 发表于 2016-2-18 07:54
我是用一个set纪录已经visit过的set里有的char,下次再遇到就跳过。我估计小哥是想让我判断下这个set的大 ...

跪求下什么叫 判断下这个set的大小和原string里所有char的个数

不是iterator嘛,没法遍历到底的话没法判断原string的chr个数吧
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-18 10:00:49 | 显示全部楼层
第2题,大概花了将近40分钟,我一开始想要string builder 去加result的,结果发现stringbuilder在recursive call里面,操作有点麻烦。有换成了string.  如果面试考,做到bug free最少 25分钟。 我还不确定,我的code对不对
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-18 10:05:11 | 显示全部楼层
tjnkzll 发表于 2016-2-18 07:54. Waral 鍗氬鏈夋洿澶氭枃绔,
我是用一个set纪录已经visit过的set里有的char,下次再遇到就跳过。我估计小哥是想让我判断下这个set的大 ...
. from: 1point3acres.com/bbs
你如果是判断该不该call recursion function.那我觉的你这个方法,可能有问题
如果一个char,出现了mutiple times, 那么当前即使有重复,你还是需要继续call recursion的。
回复 支持 反对

使用道具 举报

 楼主| tjnkzll 发表于 2016-2-18 10:21:24 | 显示全部楼层
lxxxxxxx 发表于 2016-2-18 09:26
跪求下什么叫 判断下这个set的大小和原string里所有char的个数. 1point3acres.com/bbs

不是iterator嘛,没法遍历到底的话没法 ...

同学你是不是吧第二题和第一题搞混了?这个我说的是第二题
回复 支持 反对

使用道具 举报

 楼主| tjnkzll 发表于 2016-2-18 10:23:52 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-18 10:05
你如果是判断该不该call recursion function.那我觉的你这个方法,可能有问题
如果一个char,出现了mutip ...

followuo的要求是一个字母变大写,这个string里的所有的这个字母都要大写。
所以,如果第一次碰到A,要么不变,要么把a都变大写了,第二次碰到a的时候,就不用再考虑了,所以可以跳过了。
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-2-18 10:31:57 | 显示全部楼层
tjnkzll 发表于 2016-2-18 10:23
followuo的要求是一个字母变大写,这个string里的所有的这个字母都要大写。
所以,如果第一次碰到A,要 ...

哦哦我看错了我以为你是再说第一题。。。谢啦!
回复 支持 反对

使用道具 举报

echo33 发表于 2016-2-19 02:22:17 | 显示全部楼层
tjnkzll 发表于 2016-2-18 07:54
我是用一个set纪录已经visit过的set里有的char,下次再遇到就跳过。我估计小哥是想让我判断下这个set的大 ...

get~~~谢啦
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-2-19 13:34:02 | 显示全部楼层
tjnkzll 发表于 2016-2-18 10:23 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
followuo的要求是一个字母变大写,这个string里的所有的这个字母都要大写。
所以,如果第一次碰到A,要 ...

follow up 写了一会,还是不对,
有参考代码么。。。
回复 支持 反对

使用道具 举报

Morphy 发表于 2016-2-19 14:45:21 | 显示全部楼层
houqingniao 发表于 2016-2-19 13:34
follow up 写了一会,还是不对,
有参考代码么。。。

刚看了下,感觉是回溯,三个hash表,一个hash表存需要转换的字符,一个hash表存要大写的字符,另一个hash表存要小写的字符。
c++写了个,不知道还有没其他bug,大概这个意思。
void dfs(vector<string>& res, string& str, string& cur, int pos, unordered_set<char>& change, unordered_set<char>& upper, unordered_set<char>& lower)
{   
   
    if(pos == str.length())
    {
        res.emplace_back(cur);
        return ;
    }
    if(change.find(str[pos]) == change.end())
    {
        cur += str[pos];
        dfs(res,str,cur,pos+1,change,upper,lower);. Waral 鍗氬鏈夋洿澶氭枃绔,
        cur.pop_back();
        return ;
    }
    else if(change.find(str[pos]) != change.end())
    {
        if(upper.find(str[pos]) == upper.end() && lower.find(str[pos]) == lower.end())-google 1point3acres
        {-google 1point3acres
            upper.insert(str[pos]);
            cur += toupper(str[pos]);
            dfs(res,str,cur,pos+1,change,upper,lower);
            cur.pop_back();
-google 1point3acres            upper.erase(str[pos]);

            lower.insert(str[pos]);
            cur += tolower(str[pos]);. visit 1point3acres.com for more.
            dfs(res,str,cur,pos+1,change,upper,lower);
            cur.pop_back();
            lower.erase(str[pos]);
        }
        else if(upper.find(str[pos]) != upper.end())
        {. 1point3acres.com/bbs
            cur += toupper(str[pos]);
            dfs(res,str,cur,pos+1,change,upper,lower);
            cur.pop_back();
        }. 1point3acres.com/bbs
        else
        {
            cur += tolower(str[pos]);. 鍥磋鎴戜滑@1point 3 acres
            dfs(res,str,cur,pos+1,change,upper,lower);
            cur.pop_back();
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
    }. 1point 3acres 璁哄潧
}

2个set变为1个map也行。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 04:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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