一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1787|回复: 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吧

评分

1

查看全部评分

xiaozhuxiaozhu 发表于 2016-2-18 09:58:27 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
写了个代码,应该还能优化。

  1.         public static Set<String> generateBig(String input,Set<Character> set)-google 1point3acres
  2.         {. visit 1point3acres.com for more.
  3.                 Set<String> st = new HashSet<String>();
  4.                 String tempStr = input;. 1point3acres.com/bbs
  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.                         Iterator<Character> itr = set.iterator();
  13.                        
  14.                         while(itr.hasNext()) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.                         {. From 1point 3acres bbs
  16.                                 char temp = itr.next();.鏈枃鍘熷垱鑷1point3acres璁哄潧

  17.                                 //"airplane"
  18.                                 for(int i = index; i < word.length();i++)
  19.                                 {
  20.                                 if(word.charAt(i)==temp). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.                                 {   
  22.                                     res.add(sb);
  23.                                         helperGenerator(res,sb,word,i+1,set);
  24.                                         StringBuilder sb1 = new StringBuilder(sb);
  25.                                         sb1.setCharAt(i,Character.toUpperCase(word.charAt(i)));
  26.                                     res.add(sb1.toString());
  27.                                         helperGenerator(res,sb1.toString(),word,i+1,set);
  28.                                        
  29.                                 }        . Waral 鍗氬鏈夋洿澶氭枃绔,
  30.                         }       
  31.                 }.1point3acres缃
  32.                 //sb.setLength(lengthTemp);
  33.         }

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

使用道具 举报

christy.zhang 发表于 2016-2-18 06:08:29 | 显示全部楼层
关注一亩三分地微博:
Warald
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怎么可能判断?
. From 1point 3acres bbs
或者是不允许你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里?
. From 1point 3acres bbs
可以construct new set,但是不能一次都读完
回复 支持 反对

使用道具 举报

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

.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的大 ...
. From 1point 3acres bbs
跪求下什么叫 判断下这个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
我是用一个set纪录已经visit过的set里有的char,下次再遇到就跳过。我估计小哥是想让我判断下这个set的大 ...

你如果是判断该不该call recursion function.那我觉的你这个方法,可能有问题
如果一个char,出现了mutiple times, 那么当前即使有重复,你还是需要继续call recursion的。
回复 支持 反对

使用道具 举报

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

不是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. visit 1point3acres.com for more.
followuo的要求是一个字母变大写,这个string里的所有的这个字母都要大写。
所以,如果第一次碰到A,要 ...

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

使用道具 举报

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

刚看了下,感觉是回溯,三个hash表,一个hash表存需要转换的字符,一个hash表存要大写的字符,另一个hash表存要小写的字符。. 1point3acres.com/bbs
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);
        cur.pop_back();. 1point 3acres 璁哄潧
        return ;
    }. From 1point 3acres bbs
    else if(change.find(str[pos]) != change.end())
    {
        if(upper.find(str[pos]) == upper.end() && lower.find(str[pos]) == lower.end())
        {
            upper.insert(str[pos]);
            cur += toupper(str[pos]);. visit 1point3acres.com for more.
            dfs(res,str,cur,pos+1,change,upper,lower);
            cur.pop_back();
            upper.erase(str[pos]);

            lower.insert(str[pos]);
            cur += tolower(str[pos]);
            dfs(res,str,cur,pos+1,change,upper,lower);
            cur.pop_back();
            lower.erase(str[pos]);
        }. from: 1point3acres.com/bbs
        else if(upper.find(str[pos]) != upper.end())
        {
            cur += toupper(str[pos]);
            dfs(res,str,cur,pos+1,change,upper,lower);
            cur.pop_back();
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        else 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            cur += tolower(str[pos]);
            dfs(res,str,cur,pos+1,change,upper,lower);
            cur.pop_back();
        }. 1point 3acres 璁哄潧
    }
}

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-29 16:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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