一亩三分地论坛

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

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

2016.3.11. google一轮电面

[复制链接] |试试Instant~ |关注本帖
WayneBit 发表于 2016-3-12 08:52:51 | 显示全部楼层 |阅读模式

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

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

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

x
朋友内推的google, 做了oa后约了今天第一轮电面。三哥声音,口齿不太清楚。上来问了interesting project,上题。

现成给一个character stream的class instance implements以下interface.鏈枃鍘熷垱鑷1point3acres璁哄潧
interface StreamReader {
    char next(); // return next character
    bool done(); // check if there is more character
    // as long as done() returns true, it will never return false later.鏈枃鍘熷垱鑷1point3acres璁哄潧
}

写一个function, 在这个stream中找出一个连续的最长substring只包含最多m个不同的character, 返回这个substring
private StreamInstance s;.鐣欏璁哄潧-涓浜-涓夊垎鍦
String find(int m) {
    ..... visit 1point3acres.com for more.
}

eg: stream                       m      return
"ababcbcbaaabbdef"         2         "baaabb". 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
"ababc"                           2         "abab"
"abab"                            3         "abab"

自己表现不好。move on.... 1point 3acres 璁哄潧

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
bobzhang2004 发表于 2016-3-12 22:05:00 | 显示全部楼层
用deque存,用hashmap计数吧?
回复 支持 反对

使用道具 举报

 楼主| WayneBit 发表于 2016-3-13 03:03:08 | 显示全部楼层
local存局部最长子串,global存至今最长子串。hashmap存local中出现的字符和其数量,size不大于m。.鐣欏璁哄潧-涓浜-涓夊垎鍦
每来一个字符,加到local末尾,加到hashmap中。hashmap size若大于m, 从local开始向后扫同时更新hashmap至size重新不大于m。
更新local和global。继续处理下个字符直至没有字符。时间复杂度o(n). 1point 3acres 璁哄潧
这样看local用queue存就好。
回复 支持 反对

使用道具 举报

 楼主| WayneBit 发表于 2016-3-13 03:04:18 | 显示全部楼层
bobzhang2004 发表于 2016-3-12 22:05
用deque存,用hashmap计数吧?

. from: 1point3acres.com/bbs
local存局部最长子串,global存至今最长子串。hashmap存local中出现的字符和其数量,size不大于m。
每来一个字符,加到local末尾,加到hashmap中。hashmap size若大于m, 从local开始向后扫同时更新hashmap至size重新不大于m。
更新local和global。继续处理下个字符直至没有字符。时间复杂度o(n)
这样看local用queue存就好。
回复 支持 反对

使用道具 举报

wrf91324 发表于 2016-3-16 00:33:27 | 显示全部楼层
http://www.lintcode.com/en/problem/longest-substring-with-at-most-k-distinct-characters/. 1point 3acres 璁哄潧
. 鍥磋鎴戜滑@1point 3 acres
这道题吧

两根同向指针
O(n)
回复 支持 反对

使用道具 举报

lby1989825 发表于 2016-3-16 12:04:54 | 显示全部楼层
这题leetcode上有非常相似的啊,楼主!two pointer的问题
回复 支持 反对

使用道具 举报

mrhohn 发表于 2016-3-16 12:30:05 | 显示全部楼层
WayneBit 发表于 2016-3-13 03:03
local存局部最长子串,global存至今最长子串。hashmap存local中出现的字符和其数量,size不大于m。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
每来一 ...

觉得楼主这个做法挺合理的,怎么就表现不好呢,是面试官想要另外的解法?
回复 支持 反对

使用道具 举报

 楼主| WayneBit 发表于 2016-3-16 13:34:33 | 显示全部楼层
mrhohn 发表于 2016-3-16 12:30
觉得楼主这个做法挺合理的,怎么就表现不好呢,是面试官想要另外的解法?

当场没给这个解法,之后自己再想的。。。
回复 支持 反对

使用道具 举报

slashGu 发表于 2016-3-19 05:05:14 | 显示全部楼层
hash table 加双指针,维持hash table的尺寸小于等于2,更新每个字符的下标。
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-3-20 15:06:46 | 显示全部楼层
WayneBit 发表于 2016-3-13 03:04
local存局部最长子串,global存至今最长子串。hashmap存local中出现的字符和其数量,size不大于m。
每 ...

lz这样好像不行啊

现在给的是 iterator的接口,一旦访问过某个char,没法再访问一次的。

换句话 "从local开始向后扫同时更新hashmap“,hashmap里面存的是什么呢?
回复 支持 反对

使用道具 举报

 楼主| WayneBit 发表于 2016-3-21 00:40:07 | 显示全部楼层
guixi107 发表于 2016-3-20 15:06. from: 1point3acres.com/bbs
lz这样好像不行啊

现在给的是 iterator的接口,一旦访问过某个char,没法再访问一次的。

存local中存在的char和其对应出现的次数
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-25 22:56:51 | 显示全部楼层
请问楼主面完几天后出的结果?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-25 23:36:59 | 显示全部楼层
slashGu 发表于 2016-3-19 05:05
hash table 加双指针,维持hash table的尺寸小于等于2,更新每个字符的下标。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这个是stream, 得存下从start开始的数据吧
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-26 04:45:53 | 显示全部楼层
写了下code, 感觉应该是要记录下部分string的
  1. public class LongestSubstringWithAtMostKDistinctCharactersStream {

  2.         static class StreamReader {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.                 int pos = 0;. 鍥磋鎴戜滑@1point 3 acres
  4.                 String str;
  5. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.                 public StreamReader(String str) {
  7.                         this.str = str;
  8.                 }

  9.                 char next() {// return next character
  10.                         return str.charAt(pos++);
  11.                 }
  12. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  13.                 boolean hasNext() {
  14.                         return pos < str.length();
  15.                 }
  16.         }

  17.         public static String lengthOfLongestSubstringKDistinct(StreamReader s, int k) {
  18.                 if (s == null || !s.hasNext()) {
  19.                         return "";. From 1point 3acres bbs
  20.                 }. from: 1point3acres.com/bbs
  21.                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();. 1point 3acres 璁哄潧
  22.                 int max = 0;
  23.                 StringBuilder sb = new StringBuilder();
  24.                 String res = "";
  25.                 while (s.hasNext()) {
  26.                         char c = s.next();
  27.                         sb.append(c);
  28.                         if (!map.containsKey(c)) {. From 1point 3acres bbs
  29.                                 map.put(c, 1);
  30.                                 while (sb.length() > 0 && map.size() > k) {
  31.                                         char ch = sb.charAt(0);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  32.                                         sb.deleteCharAt(0);
  33.                                         map.put(ch, map.get(ch) - 1);
  34.                                         if (map.get(ch) == 0) {
  35.                                                 map.remove(ch);
  36.                                         }
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  37.                                 }
  38.                         } else {
  39.                                 map.put(c, map.get(c) + 1);
  40.                         }
  41.                         if (sb.length() > max) {
  42.                                 max = sb.length();
  43.                                 res = sb.toString();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  44.                         }.1point3acres缃
  45.                 }

  46.                 return res;
  47.         }
  48.         . From 1point 3acres bbs
  49.         public static void main(String[] args) {
  50.                 StreamReader sr = new StreamReader("ababcbcbaaabbdef");
  51.                 System.out.println(lengthOfLongestSubstringKDistinct(sr, 2));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  52.                 StreamReader sr1 = new StreamReader("ababc");
  53.                 System.out.println(lengthOfLongestSubstringKDistinct(sr1, 2));
  54.                
  55.         }. 1point 3acres 璁哄潧
  56. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| WayneBit 发表于 2016-3-26 12:04:05 | 显示全部楼层
bobzhang2004 发表于 2016-3-25 22:56
请问楼主面完几天后出的结果?

面完一周催了一下,没有回复。估计默剧了。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-26 20:40:24 | 显示全部楼层
[quote][url=forum.php?mod=redirect
. From 1point 3acres bbs
请问现在都没消息吗?
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-14 13:13:59 | 显示全部楼层
出题出成streamReader这个样子,估计是给不用java的人吧。。。anyway, 如果需要return substring,那就queue+map<char, count>, 如果不需要substring,只需要size,就可以two point+map<char, lastIdx>,另外如果想更快的找到最小lastIdx,可以加个minHeap
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 20:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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