楼主: frank11118
跳转到指定楼层
上一主题 下一主题
收起左侧

Google 面經求問

🔗
jy_121 2016-7-22 14:18:36 | 只看该作者
全局:
hxtang 发表于 2016-7-21 19:38
树规模大了以后hashmap的key会越来越长。虽然hit到对应的hashkey可能还是O(1)的,但是应该还是得比较两个 ...

有道理,多谢
回复

使用道具 举报

🔗
greentrail 2016-7-24 12:02:19 | 只看该作者
全局:
本帖最后由 greentrail 于 2016-7-24 19:37 编辑

第一题,返回相同最大相同子树的节点数。简单测了一下。
int identicalSubtree(TreeNode * root) {
        unordered_map<int, int> map;
        string out;
        int num = 0, n = 0;
        
        search(root, out, map, n, num);
        return num;
}

void search(TreeNode * root, string & out, unordered_map<int, int> & map, int & n, int & maxnodes) {
        if (!root) {            out.append("# ");
            return;
        }
        string seq;
        int leftn = 0, rightn = 0;
        search(root->left, seq, map, leftn, maxnodes);
        search(root->right, seq, map, rightn, maxnodes);

        n = leftn + rightn + 1;
        seq.append(to_string(root->val) + " ");
        out.append(seq);

        int h = hash<string>()(seq);
        if (map.count(h) == 0) {
                map[h] = n;
        }
        else maxnodes = max(maxnodes, map[h]);
}

Update:
有个小bug,fix了。
回复

使用道具 举报

🔗
jefferyy 2016-8-13 02:22:54 | 只看该作者
全局:
Input a matrix, where every number is greater or equal to the numbers on its right and bottom. Output a sorted array   
这个题和leetcode的Kth Smallest Element in a Sorted Matrix 很相似
回复

使用道具 举报

🔗
mnmunknown 2016-8-13 02:37:27 | 只看该作者
全局:
burself 发表于 2016-8-11 23:22
握手。我也是这么想的。参考pre-order遍历序列化一棵二叉树。然后build这个字符串的失败函数。假设某字 ...

应该不行,只靠 pre-order 不能定义一个独立的 tree,至少需要加上 in-order.

比如,          1         和             1
                  /                         /   \
                2                         2     3
              /
            3

的 pre-order 都是 1-2-3,但是树的结构不同。
回复

使用道具 举报

🔗
pushazhiniao 2016-8-13 04:19:36 | 只看该作者
全局:
本帖最后由 pushazhiniao 于 2016-8-13 04:22 编辑

第二题参考这题做法建heap
https://leetcode.com/problems/kt ... in-a-sorted-matrix/

评分

参与人数 1大米 +3 收起 理由
frank11118 + 3 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
pushazhiniao 2016-8-13 04:25:42 | 只看该作者
全局:
本帖最后由 pushazhiniao 于 2016-8-13 04:39 编辑

dfs或者bfs都可以定义一棵树,参考这题
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/只需要none节点用#或者什么特别字符表示即可,如果不表示none节点才不能只用preorder(也就是dfs)


1,2,3,#,#,#,#和
1,2,#,#,3,#,#是不一样的

感觉第一题就是set加树serialization
后序遍历的过程中,对于每个根节点做serialization(利用其左右已经序列好的来省时间),以serialized string为id,如果遇到相同的就返回True,不需要hashmap,set就够了
回复

使用道具 举报

🔗
pushazhiniao 2016-8-13 04:34:37 | 只看该作者
全局:
mnmunknown 发表于 2016-8-13 02:37
应该不行,只靠 pre-order 不能定义一个独立的 tree,至少需要加上 in-order.

比如,          1      ...

可以,参考https://leetcode.com/problems/se ... ialize-binary-tree/
回复

使用道具 举报

🔗
 楼主| frank11118 2016-8-13 04:46:39 | 只看该作者
全局:
pushazhiniao 发表于 2016-8-13 04:19
第二题参考这题做法建heap
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

感謝!
但建 heap 的複雜度也是 O(nlgn)
複雜度跟 merge k sorted list 應該是一樣的吧?
回复

使用道具 举报

🔗
pushazhiniao 2016-8-13 08:52:30 | 只看该作者
全局:
frank11118 发表于 2016-8-13 04:46
感謝!
但建 heap 的複雜度也是 O(nlgn)
複雜度跟 merge k sorted list 應該是一樣的吧?

worst case是一样的 但是average case 总左上角跑到右下角还是不一样

merge k sorted list:n一直都是matrix的边长
而从matrix左上角跑到右下角每次pop并放入下一个,heap只在正中间的时候是matrix的边长,其他时候都小于

你可以想象从matrix的左边横着跑到右边heap里放的元素个数,再想从matrix的左上跑到右下heap里的元素个数变化
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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