10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3402|回复: 18
收起左侧

Google电面水过经

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

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

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

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

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:

"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 {. Waral 鍗氬鏈夋洿澶氭枃绔,
        public boolean hasNextChar();
        public char getNextChar();
}. 鍥磋鎴戜滑@1point 3 acres


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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 48
 楼主| yalyka 发表于 2016-4-4 07:13:23 | 显示全部楼层
zdhzh05 发表于 2016-4-3 18:04. 鍥磋鎴戜滑@1point 3 acres
第二题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();
}

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

class Substring {
        Substring(long startpos, long endpos) {
                this.startpos = startpos; this.endpos = endpos;
        }
        …
}.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 鍥磋鎴戜滑@1point 3 acres
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;
                        }
                        int startIndex=Integer.MAX_VALUE;
                        Character removeC=null;
                        for(char startC:map.keySet()){
                                if(map.get(startC)<startIndex){-google 1point3acres
                                        startIndex=map.get(startC);
                                        removeC=startC;. From 1point 3acres bbs
                                }
                        }
                        start=startIndex;
                        map.remove(removeC);
                }
                end++;
        }
        if(finalStart==-1&&finalEnd==-1&&map.size()<m)throw Exception…
        return new SubString(finalStart,finalEnd);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}. visit 1point3acres.com for more.

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.鏈枃鍘熷垱鑷1point3acres璁哄潧
赞楼主!! 请教一下 如果不能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 ...
. visit 1point3acres.com for more.
原来如此,谢谢楼主!
回复 支持 反对

使用道具 举报

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吗?
. 鍥磋鎴戜滑@1point 3 acres
不是,提供了这样一个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())
        {
                res.push_back(curStr);
                return;
        }
        for (int i = step; i < (int)inStr.size(); i++)
        {
                if (inStr[i] == '?'). 鍥磋鎴戜滑@1point 3 acres
                {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        findCombination(inStr, i + 1, res, curStr + '1');
                        findCombination(inStr, i + 1, res, curStr + '0');. 鍥磋鎴戜滑@1point 3 acres
                }
                else
                {
                        findCombination(inStr, i + 1, res, curStr + inStr[i]);
                }
        }
}

void main()
{
        vector<string> res;
        string curStr;
        string inStr("1?1?0?");
        findCombination(inStr, 0, res, curStr);. 1point 3acres 璁哄潧
        for (int i = 0; i < res.size(); i++)
        {.1point3acres缃
                cout << res[i] << endl;
        }
        system("pause");
}.1point3acres缃
回复 支持 反对

使用道具 举报

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

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {. 1point3acres.com/bbs
        if (s == null || s.length() == 0 || k < 1) return 0;. from: 1point3acres.com/bbs
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();. 1point 3acres 璁哄潧
        int l = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        int ret = 0;
        BigStringIterator iter1 = new BigStringIterator(s), iter2 = new BigStringIterator(s);
        int i = 0;
        while (iter1.hasNextChar()) {
            char c = iter1.getNextChar();
            if (map.containsKey(c)) {. 鍥磋鎴戜滑@1point 3 acres
                int v = map.get(c);
                map.put(c, ++v);. From 1point 3acres bbs
            } else {
                map.put(c, 1);. Waral 鍗氬鏈夋洿澶氭枃绔,
            }
            if (map.size() > k) {
                while (iter2.hasNextChar()) {
                    c = iter2.getNextChar();. 1point3acres.com/bbs
                    l++;
                    int v = map.get(c);
                    if (v > 1) {
                        map.put(c, --v);
                    } else {.1point3acres缃
                        map.remove(c);
                        break;
                    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
            }
            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;
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
        public boolean hasNextChar() {
            return str.length() > 0 && i < str.length()-1;. 1point3acres.com/bbs
        }
        public char getNextChar() {
            if (!hasNextChar()) return '\0';
            return str.charAt(++i);
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
    }
    interface BigString {
        boolean hasNextChar();
        char getNextChar();
    }
}
回复 支持 反对

使用道具 举报

wzrthhj 发表于 2016-4-25 11:47:53 | 显示全部楼层
mingzhou1987 发表于 2016-4-4 05:42
祝楼主好运,第一题是phone combination letter的简单版
void findCombination(string inStr, int step, v ...
. from: 1point3acres.com/bbs
it's not right, some of the results are duplication. Waral 鍗氬鏈夋洿澶氭枃绔,
怎么把重复的结果给去掉呢?. visit 1point3acres.com for more.

1100
1110
1100
1110
1100. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1110. more info on 1point3acres.com
1100
. more info on 1point3acres.com1110
回复 支持 反对

使用道具 举报

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()) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        res.add(new String(cur));. Waral 鍗氬鏈夋洿澶氭枃绔,
                        return;
                }
               
                for(int i = step; i < input.length(); i++) {
                        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);. 1point3acres.com/bbs
                        }
                }
        }

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

使用道具 举报

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

. From 1point 3acres bbs
                              cur += input.charAt(i);.
                              helper(res, i+1, cur, input);
                        改成 helper(res, i + 1, cur + input.charAt(i), input); 另外 应该用string builder会好些。

补充内容 (2016-4-25 15:46):-google 1point3acres
其实 != '?' 的时候 不需要 进行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. From 1point 3acres bbs

                              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>();. 1point 3acres 璁哄潧
                helper(res, "", input);
                return res;
        }
       
        private void helper(ArrayList<String> res, String cur, String input) {. from: 1point3acres.com/bbs
                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));. more info on 1point3acres.com
                                }
                        } else {
                                helper(res, cur + "0", input);
                                helper(res, cur + "1", input);
                        }
                }-google 1point3acres
        }
       
}
回复 支持 反对

使用道具 举报

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. Waral 鍗氬鏈夋洿澶氭枃绔,
你可以帮我看一下,为什么我的代码结果会有重复的吗?
        public ArrayList findCombination(String input ...

this version is more close to correct answer.
but you still need to
change
if(input.charAt(i) != '?') {. 1point3acres.com/bbs
                                cur += input.charAt(i);
                                helper(res, i+1, cur, input);
to
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴 if(input.charAt(i) != '?') {
                                helper(res, i+1, cur + input.charAt(i), input);.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-21 05:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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