一亩三分地论坛

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

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

Google二面

[复制链接] |试试Instant~ |关注本帖
hj867955629 发表于 2015-10-27 02:52:08 | 显示全部楼层 |阅读模式

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

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

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

x
刚面完google,一面被面试官坑了,迟到十分钟,然后问了两个简单的问题,和地里一个人题目一模一样,两题都答出来了,最后时间也没延长,然后还feedback说水平一般,今天给了二面。求onsite!

Verify that for each node in a binary tree, the sum of values in the left sub-tree equals the sum of the values in the right sub-tree -- it’s balanced.  The input to the function is the root node of an existing tree.



                               
登录/注册后可看大图

class TreeNode {
        int val, sum;
        TreeNode left, right;
        public TreeNode(int val) {
                this.val = val;
                sum = 0;
                left = right = null;
        }
}

public boolean isBalanced(TreeNode root) {
        if (root == null) {
                return true;
        }
        if (root.left == null && root.right == null) {
                root.sum = root.val;
                return true;
        }
        if (root.left == null || root.right == null) {
                return false;
        }
        if (isBalanced(root.left) && isBalanced(root.right)) {
                root.sum = root.val + root.left.sum + root.right.sum;
                if (root.left.sum == root.right.sum) {
                        return true;
                }
        }
        return false;
}




Problem 2:
Develop a function that returns the longest substring which contains at most M distinct characters.  Characters are allowed to repeat within the substring.  For example, given ABCDEBABA and M=4, the function should return DEBABA.
. from: 1point3acres.com/bbs
O(n)
. from: 1point3acres.com/bbs
public String getLongestSubstringWithMDistinctCha(String s, M) {
        if (M <= s.length()) {
                return s;
        }
        if (M <= 0) {
                return “”;
        }
        HashMap<Character, Integer> stas = new HashMap<>();
        int start = 0, maxStart = -1, maxEnd = -1, maxLen = 0;
        for (int pos = 0; pos < s.length(); pos++) {
                char curCha = s.charAt(pos);
                if (stas.containsKey(curCha)) {
                        stas.put(curCha, stas.get(curCha)+1);
                        continue;
                }
                stas.put(curCha, 1);
                if (stas.size() > M) {
                        if (pos-start > maxLen) {
                                maxStart = start;
                                maxEnd = pos-1;
                                maxLen = pos-start;
                        }
                }
                while (stas.size() > M) {
                        char startCha = s.charAt(start);
                        if (stas.get(startCha) == 1) {
                                stas.remove(startCha);
                        }
                        else {
                                stas.put(startCha, stas.get(startCha)-1);
                        }
                        start++;
                }
        }
        if (maxStart == -1) {
                return s;
        }
        return s.substring(maxStart, maxEnd+1);
}


test case: ABCDEBABA and M=4

public String getLongestSubstringWithMDistinctCha(Iterator<Character> iter, M) {
             Queue<Character> queue = new LinkedList<>();
        if (M <= 0) {
                return “”;
        }
        HashMap<Character, Integer> stas = new HashMap<>();
        String maxLenSubstring = “”;
        StringBuilder candidate = new StringBuilder();
        while (iter.hasNext()) {
                char curCha = iter.next();
                queue.offer(curCha);
                if (stas.containsKey(curCha)) {
                        stas.put(curCha, stas.get(curCha)+1);
                        candidate.append(curCha);
                        continue;
                }
                stas.put(curCha, 1);
                if (stas.size() > M) {
                        if (candidate.length() > maxLenSubstring.length()) {
                                maxLenSubstring =candidate.toString();
                        }
                }
                while (stas.size() > M) {
                        char startCha = queue.poll();
                        if (stas.get(startCha) == 1) {
                                stas.remove(startCha);
                        }
                        else {
                                stas.put(startCha, stas.get(startCha)-1);
                        }
                        candidate.deleteCharAt(0);
                }
                candidate.append(curCha);
        }
        if (maxLenSubstring.length() == 0) {
                return candidate.toString();
        }
        return maxLenSubstring;
}





. from: 1point3acres.com/bbs


补充内容 (2015-10-27 03:00):
一面题目跟这个一样:http://www.1point3acres.com/bbs/ ... 2%26searchoption...

补充内容 (2015-10-27 03:59):.1point3acres缃
一小时后拿到onsite

评分

1

查看全部评分

本帖被以下淘专辑推荐:

marthew777 发表于 2015-10-27 15:14:40 | 显示全部楼层
同学,你打代码好快啊! 好奇第二题为啥用iterator和queue有做了一次?是面试官要求的么?
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-10-27 15:15:07 | 显示全部楼层
预祝onsite顺利噢!
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-10-27 15:30:43 | 显示全部楼层
marthew777 发表于 2015-10-27 15:14
同学,你打代码好快啊! 好奇第二题为啥用iterator和queue有做了一次?是面试官要求的么?

follow up嘛,多谢祝福 :)
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-10-27 15:30:51 | 显示全部楼层
marthew777 发表于 2015-10-27 15:14
同学,你打代码好快啊! 好奇第二题为啥用iterator和queue有做了一次?是面试官要求的么?

follow up嘛,多谢祝福 :)
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-10-27 15:31:16 | 显示全部楼层
marthew777 发表于 2015-10-27 15:14
同学,你打代码好快啊! 好奇第二题为啥用iterator和queue有做了一次?是面试官要求的么?

follow up嘛,多谢祝福!. visit 1point3acres.com for more.

补充内容 (2015-10-27 15:32):
Sorry,论坛抽了。。连续出来三个。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 16:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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