May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

Google电面水过经

[复制链接] |试试Instant~ |关注本帖
yalyka 发表于 2016-4-4 01:23:26 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Passfresh grad应届毕业生

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

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

x
面试官也不知道是个东欧人还是印度人,叫做桑杰,在map组工作了五年。一上来先是介绍最有意思的proj,基本没有问问题。接下来接下来就是在gg doc上做题。我的gg doc上还存着,直接贴上来给大家

补充内容 (2016-4-3 12:24):
题1. A string consists of ‘0’, ‘1’ and '?'. The question mark can be either '0' or '1'. Find all possible combinations for a string.
01?0. 1point3acres.com/bbs
-->0100, 0110


补充内容 (2016-4-3 12:26):
题2 2) Suppose we have a method "getLongestSubstring(String s, int m)" which finds the longest substring with exactly M distinct characters.

Examples:. 1point 3acres 璁哄潧

"ABACAAAB" M=2 -> "ACAAA"

补充内容 (2016-4-3 12:26):
There are now new requirements for getLongestSubstring! The string doesn't fit into memory. Instead you get an object of type BigString:

补充内容 (2016-4-3 12:27):
interface 补充如下:
interface BigString {
        public boolean hasNextChar();
        public char getNextChar();
}


补充内容 (2016-4-3 12:28):
onsite求人品TAT....虽然拿到onsite就已经是赚了....

评分

2

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 47
 楼主| yalyka 发表于 2016-4-4 07:13:23 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
zdhzh05 发表于 2016-4-3 18:04. visit 1point3acres.com for more.
第二题follow up,用BigString

public class Solution {

这个不太对,parameter只传进来一个BigString,不能用两个iter,当时的代码如下:
. from: 1point3acres.com/bbs

3) There are now new requirements for getLongestSubstring! The string doesn't fit into memory. Instead you get an object of type BigString:

interface BigString {
        public boolean hasNextChar();. From 1point 3acres bbs
        public char getNextChar();
}. 1point 3acres 璁哄潧

Instead of returning a String, return the start index and end index of when the longest substring occurred..1point3acres缃

class Substring {
        Substring(long startpos, long endpos) {
                this.startpos = startpos; this.endpos = endpos;
        }
        …
}

So the new method signature is:
Substring getLongestSubstring(BigString s, int m){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        int finalStart=-1,int finalEnd=-1,maxLength=0;
        int start=0,end=0;
        Map<Character,Integer> map=new HashMap<Character,Integer>();
        while(s.hasNextChar()){
                char endC=s.getNextChar();
                if(map.containsKey(endC)){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        map.put(endC,end);
                }else if(map.size()<m){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        map.put(endC,end)
                }else if(map.size()==m){
                        if(end-start>maxLength){
                                maxLength=end-start;
                                finalStart=start;
                                finalEnd=end;
                        }. Waral 鍗氬鏈夋洿澶氭枃绔,
                        int startIndex=Integer.MAX_VALUE;. 鍥磋鎴戜滑@1point 3 acres
                        Character removeC=null;
                        for(char startC:map.keySet()){
                                if(map.get(startC)<startIndex){
                                        startIndex=map.get(startC);
                                        removeC=startC;
                                }
                        }
                        start=startIndex;
                        map.remove(removeC);
                }
                end++;. From 1point 3acres bbs
        }
        if(finalStart==-1&&finalEnd==-1&&map.size()<m)throw Exception…. from: 1point3acres.com/bbs
        return new SubString(finalStart,finalEnd);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}
. 1point3acres.com/bbs
time O(N)
space O(M). visit 1point3acres.com for more.

补充内容 (2016-4-3 18:14):
可能有小bug.....
回复 支持 2 反对 0

使用道具 举报

Alice0701 发表于 2016-4-4 04:28:45 | 显示全部楼层
关注一亩三分地微博:
Warald
赞楼主!! 请教一下 如果不能fit memory主要是啥变化啊?不能再用two pointer了吗?
回复 支持 反对

使用道具 举报

 楼主| yalyka 发表于 2016-4-4 04:34:32 | 显示全部楼层
Alice0701 发表于 2016-4-3 15:28. from: 1point3acres.com/bbs
赞楼主!! 请教一下 如果不能fit memory主要是啥变化啊?不能再用two pointer了吗?

可以用two pointer, 不能fit memory的意思是string过大,只能用bigstring类遍历,且只能遍历一次。把hashmap<Character,count(也就是interger)>改成<Character,lastPosOfThisChar(也是int)>就可以
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-4 05:07:30 | 显示全部楼层
yalyka 发表于 2016-4-4 04:34
可以用two pointer, 不能fit memory的意思是string过大,只能用bigstring类遍历,且只能遍历一次。把hash ...

原来如此,谢谢楼主!
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-4-4 05:38:35 | 显示全部楼层
用big string 累遍历是要自己用interface里的两个方法写个iterator吗?
回复 支持 反对

使用道具 举报

 楼主| yalyka 发表于 2016-4-4 05:39:27 | 显示全部楼层
wtcupup 发表于 2016-4-3 16:38
用big string 累遍历是要自己用interface里的两个方法写个iterator吗?

不是,提供了这样一个interface~直接用就可以
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-4-4 05:42:32 | 显示全部楼层
祝楼主好运,第一题是phone combination letter的简单版
void findCombination(string inStr, int step, vector<string> &res, string curStr)
{
        if (inStr.empty())return;
        if (curStr.size() == inStr.size()). From 1point 3acres bbs
        {
                res.push_back(curStr);
                return;
        }
        for (int i = step; i < (int)inStr.size(); i++)
        {
                if (inStr[i] == '?') 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                {
                        findCombination(inStr, i + 1, res, curStr + '1');. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        findCombination(inStr, i + 1, res, curStr + '0');
                }
                else
                {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        findCombination(inStr, i + 1, res, curStr + inStr[i]);
                }. From 1point 3acres bbs
        }
}. more info on 1point3acres.com

void main()
{
        vector<string> res;
        string curStr;
        string inStr("1?1?0?");
        findCombination(inStr, 0, res, curStr);
        for (int i = 0; i < res.size(); i++)
        {
                cout << res[i] << endl;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        system("pause");
}
回复 支持 反对

使用道具 举报

zdhzh05 发表于 2016-4-4 07:04:38 | 显示全部楼层
第二题follow up,用BigString

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k < 1) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int l = 0;. 1point3acres.com/bbs
        int ret = 0;
        BigStringIterator iter1 = new BigStringIterator(s), iter2 = new BigStringIterator(s);. from: 1point3acres.com/bbs
        int i = 0;
        while (iter1.hasNextChar()) {
            char c = iter1.getNextChar();
            if (map.containsKey(c)) {
                int v = map.get(c);
                map.put(c, ++v);.鐣欏璁哄潧-涓浜-涓夊垎鍦
            } else {. more info on 1point3acres.com
                map.put(c, 1);
            }-google 1point3acres
            if (map.size() > k) {
                while (iter2.hasNextChar()) {
                    c = iter2.getNextChar();
                    l++;
. From 1point 3acres bbs                    int v = map.get(c);. 1point 3acres 璁哄潧
                    if (v > 1) {
                        map.put(c, --v);
                    } else {
                        map.remove(c);
                        break;.1point3acres缃
                    }
                }-google 1point3acres
            }
            ret = Math.max(ret, i-l+1);
            i++;
        }
        return ret;
    }
    class BigStringIterator implements BigString {
        String str;
        int i;
        BigStringIterator(String s) {
            str = s;
            i = -1;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        public boolean hasNextChar() {
            return str.length() > 0 && i < str.length()-1;
        }
        public char getNextChar() {
            if (!hasNextChar()) return '\0';
            return str.charAt(++i);
. From 1point 3acres bbs        }
    }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    interface BigString {
        boolean hasNextChar();
        char getNextChar();
    }. 1point3acres.com/bbs
}
回复 支持 反对

使用道具 举报

wzrthhj 发表于 2016-4-25 11:47:53 | 显示全部楼层
mingzhou1987 发表于 2016-4-4 05:42
祝楼主好运,第一题是phone combination letter的简单版
void findCombination(string inStr, int step, v ...

it's not right, some of the results are duplication
怎么把重复的结果给去掉呢?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

1100
1110
1100
1110
1100
1110
1100
1110
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-4-25 12:13:57 | 显示全部楼层
wzrthhj 发表于 2016-4-25 11:47
it's not right, some of the results are duplication
怎么把重复的结果给去掉呢?

There is no repetition... can you your code in testing the DFS? Suppose the input is 0?1? only ? can be changed..1point3acres缃
thus, 4 results only. from the math points, the DFS is correct and no repeat at all. Sorry, this computer has no pinyin.
回复 支持 反对

使用道具 举报

wzrthhj 发表于 2016-4-25 13:32:00 | 显示全部楼层
blackrose 发表于 2016-4-25 12:13
There is no repetition... can you your code in testing the DFS? Suppose the input is 0?1? only ? c ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
你可以帮我看一下,为什么我的代码结果会有重复的吗?
        public ArrayList<String> findCombination(String input) {
                ArrayList<String> res = new ArrayList<String>();
                helper(res, 0, "", input);
                return res;
        }
        . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        private void helper(ArrayList<String> res, int step, String cur, String input) {. 1point3acres.com/bbs
                if(cur.length() == input.length()) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        res.add(new String(cur));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        return;
                }
                .鐣欏璁哄潧-涓浜-涓夊垎鍦
                for(int i = step; i < input.length(); i++) {. 鍥磋鎴戜滑@1point 3 acres
                        if(input.charAt(i) != '?') {
                                cur += input.charAt(i);
                                helper(res, i+1, cur, input);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        } else {
                                helper(res, i+1, cur + "0", input);
                                helper(res, i+1, cur + "1", input);
                        }
                }
        }

------输入11?0-----
------输出
1110
1100
1110(重复)
1100(重复)
1110(重复)
1100(重复). visit 1point3acres.com for more.
1110(重复)
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-25 15:32:02 | 显示全部楼层
wzrthhj 发表于 2016-4-25 13:32
你可以帮我看一下,为什么我的代码结果会有重复的吗?
        public ArrayList findCombination(String input ...

. visit 1point3acres.com for more.
                              cur += input.charAt(i);.-google 1point3acres
                              helper(res, i+1, cur, input);
                        改成 helper(res, i + 1, cur + input.charAt(i), input); 另外 应该用string builder会好些。. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2016-4-25 15:46):.鐣欏璁哄潧-涓浜-涓夊垎鍦
其实 != '?' 的时候 不需要 进行recursion, 因为情况是确定的。 可以改成:
                cur += input.charAt(i);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                if (cur.length() == input.length()) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                    res.add(cur...
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-4-25 22:29:11 | 显示全部楼层
wzrthhj 发表于 2016-4-25 13:32. visit 1point3acres.com for more.
你可以帮我看一下,为什么我的代码结果会有重复的吗?
        public ArrayList findCombination(String input ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
it is because "cur += input.charAt(i);" curr was changed and will be carried into next else loop.
回复 支持 反对

使用道具 举报

wzrthhj 发表于 2016-4-26 00:46:08 | 显示全部楼层
adiggo 发表于 2016-4-25 15:32

                              cur += input.charAt(i);..鐣欏璁哄潧-涓浜-涓夊垎鍦
                              helper(r ...

你后来的补充内容是对的,我运行了,没有重复了,谢谢你,
回复 支持 反对

使用道具 举报

wzrthhj 发表于 2016-4-26 00:49:10 | 显示全部楼层
其实可以把step的入参也拿掉,因为cur已经记录了这是哪步了,最后贴上代码
public class FindCombination {
        public ArrayList<String> findCombination(String input) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                ArrayList<String> res = new ArrayList<String>();
                helper(res, "", input);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                return res;
        }. 1point3acres.com/bbs
       
        private void helper(ArrayList<String> res, String cur, String input) {
                if(cur.length() == input.length()) {
                        res.add(new String(cur));
                        return;
                }
                . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                for(int i = cur.length(); i < input.length(); i++) {
                        if(input.charAt(i) != '?') {
                                cur += input.charAt(i);
                                if(cur.length() == input.length()) {
                                        res.add(new String(cur));
                                }
                        } else {
                                helper(res, cur + "0", input);
                                helper(res, cur + "1", input);
                        }.1point3acres缃
                }. From 1point 3acres bbs
        }
       
}
回复 支持 反对

使用道具 举报

tellmethough 发表于 2016-4-26 01:04:54 | 显示全部楼层
aiya  thanks fo r your sharing
回复 支持 反对

使用道具 举报

此用户无名 发表于 2016-5-1 12:36:28 | 显示全部楼层
wzrthhj 发表于 2016-4-25 11:49
其实可以把step的入参也拿掉,因为cur已经记录了这是哪步了,最后贴上代码
public class FindCombination  ...

this version of dfs can't pass the test case like 1??1
回复 支持 反对

使用道具 举报

此用户无名 发表于 2016-5-1 12:39:02 | 显示全部楼层
wzrthhj 发表于 2016-4-25 00:32. more info on 1point3acres.com
你可以帮我看一下,为什么我的代码结果会有重复的吗?. 鍥磋鎴戜滑@1point 3 acres
        public ArrayList findCombination(String input ...

this version is more close to correct answer.
but you still need to
change. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
if(input.charAt(i) != '?') {
                                cur += input.charAt(i);
                                helper(res, i+1, cur, input);
to
if(input.charAt(i) != '?') {
                                helper(res, i+1, cur + input.charAt(i), input);

then it's correct and the same as mingzhou1987's code
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-25 10:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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