一亩三分地论坛

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

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

8/31 Google电面

[复制链接] |试试Instant~ |关注本帖
Williamslg 发表于 2015-9-1 03:28:50 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
上午的电面,国人大叔:
1. leetcode原题 distinct subsequence.
好久没刷leetcode了,一上来紧张,代码敲的很快,但是我解释的挺差的,不知道有没有影响

2. leetcode的变型,Given a stream, find thelongest substring with exact M distinct characters.
例如,M = 3, S = "abcddd", 那longest substring = "bcddd",我用的sliding window方法

评分

8

查看全部评分

本帖被以下淘专辑推荐:

alucardzhou 发表于 2015-9-1 11:32:40 | 显示全部楼层
Leetcode上的解答稍稍改下就能用了。
  1.         public static String solution(String s, int k){
  2.                 int maxLen = 0, maxStartIndex = 0;
  3.             int start = 0; // start index of this substring of interest
  4.             HashMap<Character, Integer> map = new HashMap(); // map a char to its # of appearance

  5.             for (int i = 0; i < s.length(); i++) {
  6.                 char c = s.charAt(i);. 1point3acres.com/bbs
  7.                 if (map.containsKey(c)) {. 1point3acres.com/bbs
  8.                     map.put(c, map.get(c) + 1);
  9.                 } else {
  10.                     if (map.size() < k) {
  11.                         map.put(c, 1);. From 1point 3acres bbs
  12.                     } else {
  13.                         // need to delete a char from map; update start index along the way
  14.                         while (true) {
  15.                             char startChar = s.charAt(start++);
  16.                             if (map.get(startChar) == 1) {
  17.                                 map.remove(startChar);
  18.                                 break;
  19.                             } else {
  20.                                 map.put(startChar, map.get(startChar) - 1);
  21.                             }
  22.                         }
  23.                         map.put(c, 1);. visit 1point3acres.com for more.
  24.                     }
  25.                 }

  26.                 //maxLen = Math.max(maxLen, i - start + 1);
  27.                 if(maxLen < i - start + 1){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  28.                         maxLen = i - start + 1;
  29.                         maxStartIndex = start;
  30.                 }
  31.             }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  32.             return s.substring(maxStartIndex,maxStartIndex+maxLen);
  33.         }
复制代码

补充内容 (2015-8-31 22:33):
https://leetcode.com/discuss/22980/java-solution-for-k-unique-characters
回复 支持 0 反对 2

使用道具 举报

hulahu 发表于 2015-9-1 03:38:33 | 显示全部楼层
blessed and good luck
回复 支持 反对

使用道具 举报

zchang3 发表于 2015-9-1 04:53:27 | 显示全部楼层
感谢分享,楼主好运
回复 支持 反对

使用道具 举报

flamen 发表于 2015-9-1 05:18:46 | 显示全部楼层
感谢lz!请问下第二题,"given a stream",所以input不是string而是考虑一个string stream吗?那岂不是只能走一遍怎么sliding window吖?
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-9-1 05:23:30 | 显示全部楼层
楼主new gard么?
回复 支持 反对

使用道具 举报

hello2pig 发表于 2015-9-1 10:26:11 | 显示全部楼层
好难啊 楼主厉害
回复 支持 反对

使用道具 举报

discoveryi 发表于 2015-9-1 11:34:01 | 显示全部楼层
像sliding window这种题,面试前2小时,是不是要死背下来啊!!否则面试忘记解法,立马挂了!
回复 支持 反对

使用道具 举报

manman1990 发表于 2015-9-1 11:41:59 | 显示全部楼层
alucardzhou 发表于 2015-9-1 11:32
Leetcode上的解答稍稍改下就能用了。

补充内容 (2015-8-31 22:33):

你这个写法有问题吧,给的是一个字符流,没有说可以把s给存下来吧?
回复 支持 反对

使用道具 举报

manman1990 发表于 2015-9-1 11:43:41 | 显示全部楼层
第二题,EPI上有一道类似的题,12.14,主要思想是使用hashmap+双向链表,类似于LRU的思想。
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-1 12:27:07 | 显示全部楼层
flamen 发表于 2015-9-1 05:18
感谢lz!请问下第二题,"given a stream",所以input不是string而是考虑一个string stream吗?那岂不是只能 ...

LZ有同样的问题? 如果不是stream sliding window 自己coding 因该差不多虽然也蛮难bug free. 不知道string 要怎么做?
回复 支持 反对

使用道具 举报

 楼主| Williamslg 发表于 2015-9-1 13:03:09 | 显示全部楼层
flamen 发表于 2015-9-1 05:18
感谢lz!请问下第二题,"given a stream",所以input不是string而是考虑一个string stream吗?那岂不是只能 ...

是stream,长度未知,所以只能走一遍。所以我没有通过记录起始点的index来确定最终的结果。
回复 支持 反对

使用道具 举报

 楼主| Williamslg 发表于 2015-9-1 13:04:55 | 显示全部楼层
manman1990 发表于 2015-9-1 11:41
你这个写法有问题吧,给的是一个字符流,没有说可以把s给存下来吧?

你说的对,是stream,不是string
回复 支持 反对

使用道具 举报

 楼主| Williamslg 发表于 2015-9-1 13:08:20 | 显示全部楼层
补充一下,第二题是 Stream,长度未知
回复 支持 反对

使用道具 举报

 楼主| Williamslg 发表于 2015-9-1 13:09:13 | 显示全部楼层

是的,new grad,努力找工作ing
回复 支持 反对

使用道具 举报

hello2pig 发表于 2015-9-1 13:39:49 | 显示全部楼层
楼主能说一下stream该怎么做么? 对stream不熟悉
回复 支持 反对

使用道具 举报

jkl51310 发表于 2015-9-1 16:10:46 | 显示全部楼层
第二题:用一个int[26],记录每个字母在当前遍历到的字符串中最后出现的位置,当出现字符种数为m+1时,就要把int[26]中值最小的值min抛弃,这时计算新的子串长度为(当前下标 - min)。用双向队列来保存int[26]的值,使得更新操作为O(1),最终只需遍历一遍string。

补充内容 (2015-9-1 16:55):
对于某个字符c,为了在双向队列中找到对应的node,需要用一个Node *[26]来进行查找。
回复 支持 反对

使用道具 举报

manman1990 发表于 2015-9-1 16:38:26 | 显示全部楼层
jkl51310 发表于 2015-9-1 16:10. more info on 1point3acres.com
第二题:用一个int[26],记录每个字母在当前遍历到的字符串中最后出现的位置,当出现字符种数为m+1时,就要 ...

如果字符不是ascii编码的呢?
回复 支持 反对

使用道具 举报

jkl51310 发表于 2015-9-1 16:53:44 | 显示全部楼层
manman1990 发表于 2015-9-1 16:38
如果字符不是ascii编码的呢?

把数组开大点。。。
回复 支持 反对

使用道具 举报

manman1990 发表于 2015-9-1 18:24:08 | 显示全部楼层
jkl51310 发表于 2015-9-1 16:53. 1point 3acres 璁哄潧
把数组开大点。。。

你并不知道字符流里面的字符有多少个,所以开大点是没用的。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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