一亩三分地论坛

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

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

Google电面水过经

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

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

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

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

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
-->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:. visit 1point3acres.com for more.
. Waral 鍗氬鏈夋洿澶氭枃绔,
"ABACAAAB" M=2 -> "ACAAA"

补充内容 (2016-4-3 12:26):
. From 1point 3acres bbs There are now new requirements for getLongestSubstring! The string doesn't fit into memory. Instead you get an object of type BigString:. Waral 鍗氬鏈夋洿澶氭枃绔,
.1point3acres缃
补充内容 (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, 订阅: 45
 楼主| yalyka 发表于 2016-4-4 07:13:23 | 显示全部楼层
zdhzh05 发表于 2016-4-3 18:04
第二题follow up,用BigString

public class Solution {

这个不太对,parameter只传进来一个BigString,不能用两个iter,当时的代码如下:


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();
        public char getNextChar();
}. 鍥磋鎴戜滑@1point 3 acres
.鐣欏璁哄潧-涓浜-涓夊垎鍦
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>();. From 1point 3acres bbs
        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;
                        }
                        int startIndex=Integer.MAX_VALUE;
                        Character removeC=null;
                        for(char startC:map.keySet()){. more info on 1point3acres.com
                                if(map.get(startC)<startIndex){
                                        startIndex=map.get(startC);
                                        removeC=startC;
                                }
                        }
                        start=startIndex;
                        map.remove(removeC);
                }
                end++;
        }
        if(finalStart==-1&&finalEnd==-1&&map.size()<m)throw Exception…
        return new SubString(finalStart,finalEnd);
}
. From 1point 3acres bbs
time O(N)
space O(M)

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

使用道具 举报

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

使用道具 举报

 楼主| yalyka 发表于 2016-4-4 04:34:32 | 显示全部楼层
Alice0701 发表于 2016-4-3 15:28
赞楼主!! 请教一下 如果不能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吗?
. From 1point 3acres bbs
不是,提供了这样一个interface~直接用就可以
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-4-4 05:42:32 | 显示全部楼层
祝楼主好运,第一题是phone combination letter的简单版
void findCombination(string inStr, int step, vector<string> &res, string curStr)
{.1point3acres缃
        if (inStr.empty())return;
        if (curStr.size() == inStr.size())
        {
                res.push_back(curStr);
                return;
        }
        for (int i = step; i < (int)inStr.size(); i++). Waral 鍗氬鏈夋洿澶氭枃绔,
        {
                if (inStr[i] == '?')
                {
                        findCombination(inStr, i + 1, res, curStr + '1');
                        findCombination(inStr, i + 1, res, curStr + '0');
                }
                else. 1point 3acres 璁哄潧
                {. from: 1point3acres.com/bbs
                        findCombination(inStr, i + 1, res, curStr + inStr[i]);
                }
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
}

void main()-google 1point3acres
{
        vector<string> res;
        string curStr;
        string inStr("1?1?0?");. 鍥磋鎴戜滑@1point 3 acres
        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璁哄潧
        int ret = 0;
        BigStringIterator iter1 = new BigStringIterator(s), iter2 = new BigStringIterator(s);. visit 1point3acres.com for more.
        int i = 0;
        while (iter1.hasNextChar()) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            char c = iter1.getNextChar();
            if (map.containsKey(c)) {
                int v = map.get(c);
                map.put(c, ++v);
            } else {
                map.put(c, 1);
            }
            if (map.size() > k) {
                while (iter2.hasNextChar()) {
                    c = iter2.getNextChar();
                    l++;
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴                    int v = map.get(c);
                    if (v > 1) {. more info on 1point3acres.com
                        map.put(c, --v);
                    } else {
                        map.remove(c);
                        break;
                    }
                }
            }
            ret = Math.max(ret, i-l+1);
            i++;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
        return ret;
    }
    class BigStringIterator implements BigString {. more info on 1point3acres.com
        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);. 1point 3acres 璁哄潧
        }
. 鍥磋鎴戜滑@1point 3 acres    }
    interface BigString {
        boolean hasNextChar();
        char getNextChar();
    }. 鍥磋鎴戜滑@1point 3 acres
}
回复 支持 反对

使用道具 举报

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
. From 1point 3acres bbs1110
回复 支持 反对

使用道具 举报

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.
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) {
                if(cur.length() == input.length()) {.1point3acres缃
                        res.add(new String(cur));.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        return;
                }
               
                for(int i = step; i < input.length(); i++) {
                        if(input.charAt(i) != '?') {
                                cur += input.charAt(i);
                                helper(res, i+1, cur, input);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        } else {
                                helper(res, i+1, cur + "0", input);
                                helper(res, i+1, cur + "1", input);
                        }
                }
        }

------输入11?0-----
------输出
1110
1100
1110(重复)
1100(重复)
1110(重复)
1100(重复)
1110(重复)
回复 支持 反对

使用道具 举报

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


                              cur += input.charAt(i);.
                              helper(res, i+1, cur, input);
                        改成 helper(res, i + 1, cur + input.charAt(i), input); 另外 应该用string builder会好些。
. 1point 3acres 璁哄潧
补充内容 (2016-4-25 15:46):
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴其实 != '?' 的时候 不需要 进行recursion, 因为情况是确定的。 可以改成:
                cur += input.charAt(i);
                if (cur.length() == input.length()) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                    res.add(cur...
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-4-25 22:29:11 | 显示全部楼层
wzrthhj 发表于 2016-4-25 13:32
你可以帮我看一下,为什么我的代码结果会有重复的吗?
        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 {. 1point3acres.com/bbs
        public ArrayList<String> findCombination(String input) {
                ArrayList<String> res = new ArrayList<String>();
                helper(res, "", input);
                return res;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }
       
        private void helper(ArrayList<String> res, String cur, String input) {
                if(cur.length() == input.length()) {. from: 1point3acres.com/bbs
                        res.add(new String(cur));
                        return;
                }
               
                for(int i = cur.length(); i < input.length(); i++) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        if(input.charAt(i) != '?') {
                                cur += input.charAt(i);. Waral 鍗氬鏈夋洿澶氭枃绔,
                                if(cur.length() == input.length()) {.1point3acres缃
                                        res.add(new String(cur));
                                }
                        } else {
                                helper(res, cur + "0", input);
. more info on 1point3acres.com                                helper(res, cur + "1", input);
                        }
                }
        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
       
}
回复 支持 反对

使用道具 举报

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已经记录了这是哪步了,最后贴上代码. Waral 鍗氬鏈夋洿澶氭枃绔,
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.鏈枃鍘熷垱鑷1point3acres璁哄潧
你可以帮我看一下,为什么我的代码结果会有重复的吗?
        public ArrayList findCombination(String input ...

this version is more close to correct answer.
but you still need to . visit 1point3acres.com for more.
change. from: 1point3acres.com/bbs
if(input.charAt(i) != '?') {
                                cur += input.charAt(i);
                                helper(res, i+1, cur, input);
to. 1point3acres.com/bbs
if(input.charAt(i) != '?') {
                                helper(res, i+1, cur + input.charAt(i), input);

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 00:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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