一亩三分地论坛

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

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

Palantir新鲜电面

[复制链接] |试试Instant~ |关注本帖
andr_ 发表于 2015-9-5 10:12:53 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Palantir - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
面的是NY office
.鏈枃鍘熷垱鑷1point3acres璁哄潧题目是求两个grid的overlay,二维grid内部用黑白二色涂色,然后黑+黑=黑,白+黑=黑,白+白=白,求两个grid重叠之后的结果
grid是用四叉树而不是矩阵来表示的,如果某一个区域全部都是同一个颜色,则该节点就变成叶子节点,因此这个树每个分支的深度不一定一样
在国内半夜面的,脑子有点转不动,反应略慢,一开始写不对,后面自己想想改对了但是时间也快到了,拿了一个中等的分数,所以后面hr通知电面加面一轮

评分

4

查看全部评分

baobozo 发表于 2015-9-5 11:05:11 | 显示全部楼层
这grid怎么用四叉树表示不是很明白, lz能不能详细说一下。
回复 支持 反对

使用道具 举报

 楼主| andr_ 发表于 2015-9-6 10:45:38 | 显示全部楼层
baobozo 发表于 2015-9-5 11:05
这grid怎么用四叉树表示不是很明白, lz能不能详细说一下。
.1point3acres缃
Node: color; child[]
如果这片区域都是同一个颜色则child为空数组,否则color就是undefined
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-9-6 11:31:31 | 显示全部楼层
LZ,还是不太明白呀,能否给了例子呀. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2015-9-6 11:37):
明白题目意思啦,这题有点意思呀,LZ是用什么办法来做的呀
回复 支持 反对

使用道具 举报

 楼主| andr_ 发表于 2015-9-7 01:48:49 | 显示全部楼层
直接traverse就好啦~有简化的方法,不难想的
回复 支持 反对

使用道具 举报

 楼主| andr_ 发表于 2015-9-7 01:49:01 | 显示全部楼层
f1371342385 发表于 2015-9-6 11:31 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
LZ,还是不太明白呀,能否给了例子呀

补充内容 (2015-9-6 11:37):

直接traverse就好啦~有简化的方法,不难想的
回复 支持 反对

使用道具 举报

shanni 发表于 2015-9-7 03:05:53 | 显示全部楼层
很想问traverse的话 root从哪里开始。。。
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-9-7 03:21:39 | 显示全部楼层
andr_ 发表于 2015-9-7 01:49
直接traverse就好啦~有简化的方法,不难想的

对 我也是这么想的 直接BFS判断好啦
回复 支持 反对

使用道具 举报

On_the_way 发表于 2015-9-7 04:46:23 | 显示全部楼层
嗯。。想问下比较的这两个grid的size和对应两个grid的树的结构是一样的吗?如果不一样就比较难办了。。还没想出来好的办法
如果一样的话,我感觉这里应该用DFS。大概想法是搞个递归然后比较4个返回值是不是一样颜色的,如果是就合并并且把这个颜色返回给上一级。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-7 05:25:27 | 显示全部楼层
楼主是海投的吗?
回复 支持 反对

使用道具 举报

 楼主| andr_ 发表于 2015-9-7 07:39:58 | 显示全部楼层
On_the_way 发表于 2015-9-7 04:46
嗯。。想问下比较的这两个grid的size和对应两个grid的树的结构是一样的吗?如果不一样就比较难办了。。还没 ...
. more info on 1point3acres.com
可以不一样啊。你可以举个例子试试就看出来啦
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-9-16 10:16:47 | 显示全部楼层
请问楼主怎么找到内推的?
回复 支持 反对

使用道具 举报

krist 发表于 2015-10-24 10:34:13 | 显示全部楼层
andr_ 发表于 2015-9-6 10:45
Node: color; child[]
如果这片区域都是同一个颜色则child为空数组,否则color就是undefined

小弟愚钝。。还是没明白。。能不能简单举个例子
回复 支持 反对

使用道具 举报

krist 发表于 2015-10-24 10:34:49 | 显示全部楼层
f1371342385 发表于 2015-9-6 11:31
LZ,还是不太明白呀,能否给了例子呀

补充内容 (2015-9-6 11:37):
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
小弟愚钝。。还是没明白。。能不能简单举个例子
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-1-27 07:23:05 | 显示全部楼层
楼主这题目挺麻烦的。。。楼主方便pose code么~
回复 支持 反对

使用道具 举报

Teness 发表于 2016-2-6 03:10:05 | 显示全部楼层
大概写了下逻辑,没DEBUG没测试没编译,随便看看就好. from: 1point3acres.com/bbs

    public void BuildOverlay(Node a, Node b, Node c)
    {
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴        if(a == null && b == null) return;. from: 1point3acres.com/bbs
        
        if(a.color != '' && b.color != '')
            c = new Node((a.color == 'W' && b.color == 'W') ? 'W' : 'B', null);
        else if(a.color != '' && b.color == '')
        {
            if  (a.color == 'B') c = new Node('B', null);
            else                 c = b.Clone(); // deep copy of B, skip the code..
        }
        else if(a.color == '' && b.color != '')
        {
            if  (b.color == 'B') c = new Node('B', null);
            else                 c = a.Clone(); // deep copy of A, skip the code..
        }
        else
        {
            // a.color == '' && b.color == '' : both has chilren.
            // if we draw a graph we can conclude that they should have equal number of childs.
            Node child = null;
            c = new Node('', new List<Node>());
            for(int i = 0; i < a.childs.Count; i++)
            {
                BuildOverlay(a[i], b[i], child);
                if(child != null) c.childs.Add(child);
. From 1point 3acres bbs            }
            
            // exam if we need to combine childs
            bool flag = false;
            for(int i = 0; i < c.childs.Count - 1; i++)
            {
                // if any child has more children, or any of the two have different color, set flag to true
                flag |= (c.child[i].color == '') || (c.child[i+1].color == '') || (c.child[i].color != child[i+1].color);
            }. more info on 1point3acres.com
            
            if(!flag) { c.color = c.childs[0].color; c.childs = null;}
        }
    }
   
    public class Node
    {
        public char color;
        public List<Node> childs;
    }
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-2-6 03:40:00 | 显示全部楼层
Teness 发表于 2016-2-6 03:10
大概写了下逻辑,没DEBUG没测试没编译,随便看看就好

    public void BuildOverlay(Node a, Node b, No ...

谢楼主!楼主好人啊!代码我觉得很对哈!!
回复 支持 反对

使用道具 举报

Allenping 发表于 2016-3-18 04:00:01 | 显示全部楼层
请问LZ有没有 一轮HR 30分钟的电面 ?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 02:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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