近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3329|回复: 16
收起左侧

2016.3.11. google一轮电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

现成给一个character stream的class instance implements以下interface
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
}

写一个function, 在这个stream中找出一个连续的最长substring只包含最多m个不同的character, 返回这个substring
private StreamInstance s;
String find(int m) {. 1point3acres.com/bbs
    ....
.1point3acres缃}

eg: stream                       m      return. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
"ababcbcbaaabbdef"         2         "baaabb"
"ababc"                           2         "abab"
"abab"                            3         "abab"
. more info on 1point3acres.com
自己表现不好。move on...

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 48
bobzhang2004 发表于 2016-3-12 22:05:00 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
用deque存,用hashmap计数吧?
回复 支持 反对

使用道具 举报

 楼主| WayneBit 发表于 2016-3-13 03:03:08 | 显示全部楼层
关注一亩三分地微博:
Warald
local存局部最长子串,global存至今最长子串。hashmap存local中出现的字符和其数量,size不大于m。. 鍥磋鎴戜滑@1point 3 acres
每来一个字符,加到local末尾,加到hashmap中。hashmap size若大于m, 从local开始向后扫同时更新hashmap至size重新不大于m。-google 1point3acres
更新local和global。继续处理下个字符直至没有字符。时间复杂度o(n). from: 1point3acres.com/bbs
这样看local用queue存就好。
回复 支持 反对

使用道具 举报

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

. From 1point 3acres 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/

这道题吧

两根同向指针
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. from: 1point3acres.com/bbs
觉得楼主这个做法挺合理的,怎么就表现不好呢,是面试官想要另外的解法?

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

使用道具 举报

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
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,更新每个字符的下标。

这个是stream, 得存下从start开始的数据吧
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-26 04:45:53 | 显示全部楼层
写了下code, 感觉应该是要记录下部分string的
  1. public class LongestSubstringWithAtMostKDistinctCharactersStream {
  2. . Waral 鍗氬鏈夋洿澶氭枃绔,
  3.         static class StreamReader {
  4.                 int pos = 0;
  5.                 String str;

  6.                 public StreamReader(String str) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.                         this.str = str;
  8.                 }

  9.                 char next() {// return next character
  10.                         return str.charAt(pos++);.1point3acres缃
  11.                 }
  12. . 1point 3acres 璁哄潧
  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 "";
  20.                 }
  21.                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
  22.                 int max = 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.                 StringBuilder sb = new StringBuilder();-google 1point3acres
  24.                 String res = "";
  25.                 while (s.hasNext()) {
  26.                         char c = s.next();
  27.                         sb.append(c);. 1point 3acres 璁哄潧
  28.                         if (!map.containsKey(c)) {
  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) {. from: 1point3acres.com/bbs
  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.                         }
  45.                 }-google 1point3acres

  46.                 return res;
  47.         }
  48.         . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  49.         public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  50.                 StreamReader sr = new StreamReader("ababcbcbaaabbdef");. 1point 3acres 璁哄潧
  51.                 System.out.println(lengthOfLongestSubstringKDistinct(sr, 2));
  52.                 StreamReader sr1 = new StreamReader("ababc");
  53.                 System.out.println(lengthOfLongestSubstringKDistinct(sr1, 2));
  54.                
  55.         }
  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

请问现在都没消息吗?
回复 支持 反对

使用道具 举报

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
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-28 15:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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