一亩三分地论坛

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

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

Google电面, 两轮, 尚未有结果

[复制链接] |试试Instant~ |关注本帖
maoyp 发表于 2014-4-11 22:16:32 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 全职@Google - Other - 技术电面 |Other

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

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

x
第一轮:
. 1point3acres.com/bbs
求array里unordered pair的数量(前一个数比后一个数大)

比如{1, 3, 2}里面有一个(3, 2), {1, 2, 3}里面没有, {3, 2, 1}里面有三个(3, 2) (3, 1) (2, 1).鏈枃鍘熷垱鑷1point3acres璁哄潧
. 1point 3acres 璁哄潧
我先写了最笨的方法, 每个pair都查一遍, 复杂度是O(n^2)

. Waral 鍗氬鏈夋洿澶氭枃绔,问能否优化, 我的第一反应是最多会有O(n^2)个unordered pair, 所以O(n^2)应该是最优了吧, 不过仔细想想还是有办法不用一个一个数, 我在merge sort里加了几行计算unordered pair的code, merge sort完成时就可以得出结果, 复杂度O(nlogn)



.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二轮:


binary tree serialization/deserialization
. more info on 1point3acres.com

每个node存放一个string. visit 1point3acres.com for more.


serialization之后返回一个string, deserialization这个string必须返回和原始tree一样结构的tree


我的方法是null node用#表示, 至于traversal嘛,


我的第一反应: 想要唯一确定一个tree, 必须有inorder在加上preorder和postorder中的一个 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

后来在网上看, 得知null node也存储的话, preorder或者postorder就可以唯一确定一个tree了
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我当时的做法是用level order, 虽然也对, 但是空间上需要一些额外的开销(BFS本身的需要)

这一轮至今没回复, 问HR, HR说仍然没有决定, 有可能再加一轮电面, 我水平还是不够哇, 唉...


. From 1point 3acres bbs我有个问题想问:

如果null node不存储的话, 那么想要唯一确定一个tree, 必须有inorder在加上preorder和postorder中的一个
null node存储的话, 那么想要唯一确定一个tree, preorder和postorder中的一个就够了

.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个说法究竟对不对?有没有什么严格一点的论述或者解释什么的?

评分

2

查看全部评分

本帖被以下淘专辑推荐:

zhujl1991 发表于 2014-4-12 01:18:46 | 显示全部楼层
第一题楼主的解答应该是标准解吧。这题是coursera上的斯坦福算法公开课分治那章的例题。
回复 支持 1 反对 0

使用道具 举报

北美农民 发表于 2014-4-11 23:57:59 | 显示全部楼层
你第一题能想到Merge Sort的模型挺棒的。 其实我猜测他希望的解是BST, 或者 树状数组。

第二题字符串和字符串之间要用个特殊的符号间隔开, null node用#表示就可以任意serialize/deserialize了, 不需要额外空间。
回复 支持 反对

使用道具 举报

 楼主| maoyp 发表于 2014-4-12 00:41:09 | 显示全部楼层

第一题用BST去解我还真没想过, 应该是往BST去想的, 我的想法可能有点奇葩了

第二题的话, 是的, 字符串和字符串之间要用个特殊的符号间隔开(我刚才忘了说), 我的意思是, 如果不保存null node信息的话, 需要inorder + preorder/postorder 才能唯一确定一个binary tree, 但是如果保存null node信息的话, 只需要preorder/postorder就可以了, 虽然我能通过举例子想通, 但是有没有一个更加系统的讲述? (保存null node信息怎么就消除了歧义了?)
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-4-12 00:46:43 | 显示全部楼层
maoyp 发表于 2014-4-11 11:41
第一题用BST去解我还真没想过, 应该是往BST去想的, 我的想法可能有点奇葩了
.鏈枃鍘熷垱鑷1point3acres璁哄潧. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题的话, 是的, 字符串 ...

因为保存null node能够让递归serialize/deserialize运算停止, 其实就是多了这个信息。

我还是不知道你为啥需要BFS。
回复 支持 反对

使用道具 举报

 楼主| maoyp 发表于 2014-4-12 00:52:23 | 显示全部楼层
北美农民 发表于 2014-4-12 00:46
因为保存null node能够让递归serialize/deserialize运算停止, 其实就是多了这个信息。

我还是不知道你 ...

当时第一反应是想要唯一确定一个BT, 需要inorder + preorder/postorder, 于是就想level order能不能traverse一遍就能确定

我就是一开始没想到存储null node信息能消除歧义, CC150书里写的唯一确定一个BT, 需要inorder + preorder/postorder这句话已经深深印在脑海里了, 刷题太死, 光背结论没有去想其原因和扩展, 我还是太弱
回复 支持 反对

使用道具 举报

veryblues 发表于 2014-4-12 01:00:58 | 显示全部楼层
lz请问每一面的题有多少道?
回复 支持 反对

使用道具 举报

 楼主| maoyp 发表于 2014-4-12 01:17:39 | 显示全部楼层
veryblues 发表于 2014-4-12 01:00 .鏈枃鍘熷垱鑷1point3acres璁哄潧
lz请问每一面的题有多少道?

都是一道
回复 支持 反对

使用道具 举报

discoveryi 发表于 2014-4-14 11:07:22 | 显示全部楼层
北美农民 发表于 2014-4-11 23:57
你第一题能想到Merge Sort的模型挺棒的。 其实我猜测他希望的解是BST, 或者 树状数组。

第二题字符串和 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
你好,请问能帮忙提供个JAVA版本的code吗? binary tree serialization/deserialization

谢谢!!!
回复 支持 反对

使用道具 举报

liyipui 发表于 2014-4-14 11:45:50 | 显示全部楼层
一般都会有2轮电面吗?
回复 支持 反对

使用道具 举报

rhozou 发表于 2014-4-16 12:28:21 | 显示全部楼层
请问lz第一题的merge sort具体思路是怎样的?thx
回复 支持 反对

使用道具 举报

 楼主| maoyp 发表于 2014-4-18 07:48:30 | 显示全部楼层
discoveryi 发表于 2014-4-14 11:07
你好,请问能帮忙提供个JAVA版本的code吗? binary tree serialization/deserialization

谢谢!!!

好的, 我这里就抛砖引玉了, 如果有错请大家指正, 我这里用#表示null node, | 表示分隔符
题意中, 每个node都有一个val, 装有string

public class TreeNode{
    TreeNode left;    //given
    TreeNode right;    //given. from: 1point3acres.com/bbs
    String val;            //given. 鍥磋鎴戜滑@1point 3 acres
    public String serialize(){
        String result = node.val + "|";
        if(this.left == null)     result += "#|";. Waral 鍗氬鏈夋洿澶氭枃绔,
        else    result += left.serialize();
        if(this.right == null)     result += "#|";
        else    result += right.serialize();
        return result;.1point3acres缃
    }
    public static TreeNode deserialize(String rep){. visit 1point3acres.com for more.
        if(rep == null || rep.length() == 0)    return null;
        String cur = rep.substring(0, rep.indexOf("|"));
鏉ユ簮涓浜.涓夊垎鍦拌鍧.         if(cur.equals("#"))    return null;
        TreeNode root = new TreeNode(cur);
        rep = rep.substring(rep.indexOf("|")+1);
        Stack<TreeNode> s = new Stack<TreeNode>();
        root.left = new TreeNode("");
        root.right = new TreeNode("");
        s.push(root.right);
        s.push(root.left);
        while(rep.length() > 0){.鐣欏璁哄潧-涓浜-涓夊垎鍦
            TreeNode curNode = s.pop();
            cur = rep.substring(0, rep.indexOf("|"));
            if(cur.equals("#"))    curNode == null;
            else{
                curNode.val = cur;. visit 1point3acres.com for more.
                curNode.left = new TreeNode("");
                curNode.right = new TreeNode("");
                s.push(curNode.right);
                s.push(curNode.left);
            }
            rep = rep.substring(rep.indexOf("|")+1);
        }
        return root;
    }
}

补充内容 (2014-4-27 23:20):
这个有错误, 请不要再作为参考
回复 支持 反对

使用道具 举报

 楼主| maoyp 发表于 2014-4-18 08:05:21 | 显示全部楼层
rhozou 发表于 2014-4-16 12:28
请问lz第一题的merge sort具体思路是怎样的?thx

就是在merge过程中, 每当取右边的element的时候, pair的数量增加当前剩余的左边的element的数量
回复 支持 反对

使用道具 举报

 楼主| maoyp 发表于 2014-4-18 09:37:07 | 显示全部楼层
rhozou 发表于 2014-4-16 12:28
请问lz第一题的merge sort具体思路是怎样的?thx

Java code 我也写下, 望大牛不吝赐教, 这里count就是mergesort的变形,

int count(int[] arr, int start, int end){
    if(start >= end)    return 0;
    else{. more info on 1point3acres.com
        int result = 0;
        int mid = start + (end-start)/2;  //interviewer indicate, avoid overflow. 鍥磋鎴戜滑@1point 3 acres
        result += count(arr, start, mid);
        result += count(arr, mid+1, end);
        result += merge(arr, start, mid, end);
        return result;
    }
}

int merge(int[] arr, int start, int mid, int end){.1point3acres缃
    int leftRem = mid - start + 1;
    int result = 0;
    int[] helper = Arrays.copyOf(arr);
    int cur = start, curLeft = start, curRight = mid+1;
    while(curLeft <= mid && curRight <= end){
        if(helper[curLeft] <= helper[curRight]){
            arr[cur++] = helper[curLeft++];
            leftRem--;
        }   
        else{
            arr[cur++] = helper[curRight++];
            result += leftRem;
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
    }. 1point 3acres 璁哄潧
    while(mid >= curLeft)    arr[cur++] = helper[curLeft++];
    return result;
}
回复 支持 反对

使用道具 举报

dandanliuqian 发表于 2014-5-1 18:04:54 | 显示全部楼层
第一题可以直接quick sort去swap pair 。。。。理解更直观些~
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-5-3 11:25:07 | 显示全部楼层
rhozou 发表于 2014-4-16 12:28
请问lz第一题的merge sort具体思路是怎样的?thx

在归并排序时,合并两个已经排序的数组时,可以通过当前的数字快速的计算出逆序对的个数
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-5-3 11:27:00 | 显示全部楼层
北美农民 发表于 2014-4-11 23:57
你第一题能想到Merge Sort的模型挺棒的。 其实我猜测他希望的解是BST, 或者 树状数组。
. 1point 3acres 璁哄潧
第二题字符串和 ...

用BST的话是每当往左子树插入,就要累加根节点和其右子树的个数吗?
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-5-3 16:07:38 | 显示全部楼层
pyemma 发表于 2014-5-3 11:27
用BST的话是每当往左子树插入,就要累加根节点和其右子树的个数吗?

恩恩,知道用merge sort的方法,BST的方法第一次听说,不过现在差不多弄明白了
回复 支持 反对

使用道具 举报

readman 发表于 2014-5-3 16:29:59 | 显示全部楼层
第一个还可以用merge的反向迭代形式,就是普林斯顿的公开课讲得那个.
只需要前边第一步的归并. 不过还是nlgn. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

zdcx 发表于 2016-5-7 17:59:42 | 显示全部楼层
顶顶顶顶顶顶顶顶顶顶达到
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 23:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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