一亩三分地论坛

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

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

Google电面水过经

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

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

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

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

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

补充内容 (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.. visit 1point3acres.com for more.
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.
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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 {
        public boolean hasNextChar();
        public char getNextChar();
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (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,当时的代码如下:

.鏈枃鍘熷垱鑷1point3acres璁哄潧
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();
}. From 1point 3acres bbs

Instead of returning a String, return the start index and end index of when the longest substring occurred..1point3acres缃
. more info on 1point3acres.com
class Substring {
        Substring(long startpos, long endpos) {
                this.startpos = startpos; this.endpos = endpos;
        }
        …
}. 1point3acres.com/bbs

So the new method signature is:
Substring getLongestSubstring(BigString s, int m){
        int finalStart=-1,int finalEnd=-1,maxLength=0;-google 1point3acres
        int start=0,end=0;. From 1point 3acres bbs
        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; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        int startIndex=Integer.MAX_VALUE;
                        Character removeC=null;
                        for(char startC:map.keySet()){
                                if(map.get(startC)<startIndex){
                                        startIndex=map.get(startC);. From 1point 3acres bbs
                                        removeC=startC;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                }
                        }
                        start=startIndex;. Waral 鍗氬鏈夋洿澶氭枃绔,
                        map.remove(removeC);
                }
                end++;
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷        }
        if(finalStart==-1&&finalEnd==-1&&map.size()<m)throw Exception…
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴        return new SubString(finalStart,finalEnd);
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

time O(N)
space O(M)

补充内容 (2016-4-3 18:14):. 鍥磋鎴戜滑@1point 3 acres
可能有小bug.....
回复 支持 2 反对 0

使用道具 举报

Alice0701 发表于 2016-4-4 04:28:45 | 显示全部楼层
赞楼主!! 请教一下 如果不能fit memory主要是啥变化啊?不能再用two pointer了吗?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| 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吗?

不是,提供了这样一个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;. From 1point 3acres bbs
        if (curStr.size() == inStr.size())
        {
                res.push_back(curStr);
                return;
        }
        for (int i = step; i < (int)inStr.size(); i++). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        {
                if (inStr[i] == '?')
                {
                        findCombination(inStr, i + 1, res, curStr + '1');. From 1point 3acres bbs
                        findCombination(inStr, i + 1, res, curStr + '0');
                }
                else
                {
                        findCombination(inStr, i + 1, res, curStr + inStr[i]);
                }
        }
}.鐣欏璁哄潧-涓浜-涓夊垎鍦

void main()
{
        vector<string> res;
        string curStr; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        string inStr("1?1?0?");. more info on 1point3acres.com
        findCombination(inStr, 0, res, curStr);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        for (int i = 0; i < res.size(); i++)
        {
                cout << res[i] << endl;
        }
        system("pause");. from: 1point3acres.com/bbs
}
回复 支持 反对

使用道具 举报

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;-google 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)) {. From 1point 3acres bbs
                int v = map.get(c);
                map.put(c, ++v);
            } else {
                map.put(c, 1);
.鏈枃鍘熷垱鑷1point3acres璁哄潧            }
            if (map.size() > k) {
                while (iter2.hasNextChar()) {
                    c = iter2.getNextChar(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                    l++;
                    int v = map.get(c);
                    if (v > 1) {
                        map.put(c, --v);
                    } else {
                        map.remove(c);
                        break;. visit 1point3acres.com for more.
                    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }. 1point 3acres 璁哄潧
            }.1point3acres缃
            ret = Math.max(ret, i-l+1);
            i++;
        }
        return ret;
    }
    class BigStringIterator implements BigString {
        String str;
        int i;
        BigStringIterator(String s) {
            str = s;.1point3acres缃
            i = -1;
        }
        public boolean hasNextChar() {
            return str.length() > 0 && i < str.length()-1;-google 1point3acres
        }
        public char getNextChar() {
            if (!hasNextChar()) return '\0';
            return str.charAt(++i);.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }
    }
    interface BigString {
        boolean hasNextChar();
        char getNextChar();-google 1point3acres
    }
}
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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. From 1point 3acres bbs
怎么把重复的结果给去掉呢?

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. from: 1point3acres.com/bbs
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));
                        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);. From 1point 3acres bbs
                        }
. From 1point 3acres bbs                }
        }

------输入11?0-----
------输出
1110
1100
1110(重复)
1100(重复)
1110(重复)
1100(重复)
1110(重复)
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

. from: 1point3acres.com/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):
其实 != '?' 的时候 不需要 进行recursion, 因为情况是确定的。 可以改成:
                cur += input.charAt(i);
. from: 1point3acres.com/bbs                 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 ...

你后来的补充内容是对的,我运行了,没有重复了,谢谢你,
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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;
        }
       
        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++) {. 1point 3acres 璁哄潧
                        if(input.charAt(i) != '?') {
                                cur += input.charAt(i);. 1point 3acres 璁哄潧
                                if(cur.length() == input.length()) {
                                        res.add(new String(cur));. from: 1point3acres.com/bbs
                                }
                        } else {
                                helper(res, cur + "0", input);
                                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. more info on 1point3acres.com
其实可以把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
你可以帮我看一下,为什么我的代码结果会有重复的吗?
        public ArrayList findCombination(String input ...
. from: 1point3acres.com/bbs
this version is more close to correct answer.. more info on 1point3acres.com
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
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-24 11:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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