一亩三分地论坛

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

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

狗家面经

[复制链接] |试试Instant~ |关注本帖
treee 发表于 2016-7-13 14:35:40 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 猎头 - Onsite |Other在职跳槽

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

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

x
1. 给一个方阵,里面是1或者0,有2^n行或者列,写个四分树,实现-与-的功能
2. 设计一个日志系统,给不同的组件使用
3a. 整数从1开始连着写,12345678910111213...找到第n个数字.
3b. 有很多视频,每两个视频给一个人评价选哪个好,比如a>b, c<d, c < b, 设计一个系统给视频排序。
4. 设计一个迷宫,要求difficult to solve。讨论一番以后,要求写程序生成迷宫,或者证明解迷宫np complete.

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
 楼主| treee 发表于 2016-7-20 10:52:56 | 显示全部楼层
当时写的大致是这样,没要求写constructor

public class Quad {
  private Quad[] children;. more info on 1point3acres.com
  private int size;
  private int value = -1;

  public Quad and(Quad q) {
    if (size != q.size) throw new IllegalArgumentException();

    if (value == 0) return new Quad(this);
    if (q.value == 0) return new Quad(q);
    if (value == 1) return new Quad(q);
    if (q.value == 1) return new Quad(this);
    . Waral 鍗氬鏈夋洿澶氭枃绔,
    Quad[] qs = new Quad[4];
    for (int i = 0; i < children.length; i++) {
       qs[i] = children[i].and(q.children[i]);. From 1point 3acres bbs
    }
    return new Quad(size, qs);
  }
}

评分

1

查看全部评分

回复 支持 1 反对 2

使用道具 举报

axings 发表于 2016-7-13 14:58:48 | 显示全部楼层
写了一下第一题:. From 1point 3acres bbs
public class QuadNode. 1point3acres.com/bbs
{
        public QuadNode[] nodes;
        public int color;. more info on 1point3acres.com
        public boolean isFull;
       
        public static QuadNode And(QuadNode node1, QuadNode node2)
        {.1point3acres缃
                if(node1.isFull && node2.isFull)
                {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        QuadNode node = new QuadNode();
                        node.isFull = true;
                        node.color = node1.color && node2.color;
                        return node;
                }
               
                if(node2.isFull)
                {
                        return QuadNode(node2, node1);
                }
               
                if(node1.isFull)
                {
                        if(node1.color == 1)
                        {
                                return node2;
                        }
                        else.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        {
                                return node1;
                        }
                }
                else
                {
                        QuadNode node = new QuadNode();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        node.nodes = new QuadNode[4];
                        node.nodes[0] = And(node1.nodes[0], node2.nodes[0]);
                        node.nodes[1] = And(node1.nodes[1], node2.nodes[1]);
                        node.nodes[2] = And(node1.nodes[2], node2.nodes[2]);
                        node.nodes[3] = And(node1.nodes[3], node2.nodes[3]);. From 1point 3acres bbs
                        node.isFull = false;
                        return node;
                }
        }
}
回复 支持 反对

使用道具 举报

axings 发表于 2016-7-13 15:37:05 | 显示全部楼层
想了一下第二题不知道对不对,根据观察得出如下规律:

数字值的范围:该范围内数字的个数:该范围内每个数字所占的位数
1-9 : 9 : 1. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
10-99 : 90 : 2
100-999 : 900 : 3
1000-9999 : 9000 : 4. Waral 鍗氬鏈夋洿澶氭枃绔,

那么比如我们要求第500个数是什么,就可以这么拆解问题:
从0算起的第 500 位数
从9算起的第 500 - 9 * 1 = 491 位数
从99算起的第 491 - 90 * 2 = 311 位数
在这里因为 311 - 900 * 3 < 0 所以区别对待,问题转换为从99算起的311位数是什么。
我们知道从99以后每个数字占3位,所以第311位即是 311 / 3 = 109 个数的第 311 % 3 = 2位,99 + 109 = 208, 208的第二位是0, 所以答案为0.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

peter_sqliu 发表于 2016-7-13 17:37:38 | 显示全部楼层
请问lz几年工作经验啊, 题好难啊
回复 支持 反对

使用道具 举报

chen6145 发表于 2016-7-14 00:41:32 | 显示全部楼层
Design题楼主是咋作答的呀?
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-7-14 00:58:04 | 显示全部楼层
1 是说实现把方针里某个element 0->1, 1->0的功能吗?

3b 如果只有a>b, c>d,是返回abcd和cdba都可以吗?如果有a>b, b>c, c>a怎么处理?-google 1point3acres

4 可以定义一下difficult to solve吗?
另外不会问的是下面这个问题吧...如果是的话也太黑了
https://www.mat.unical.it/~alvia ... -mazegeneration.pdf
回复 支持 反对

使用道具 举报

axings 发表于 2016-7-14 03:52:36 | 显示全部楼层
我觉得3b其实是考你知不知道google经典的Page Rank算法。
回复 支持 反对

使用道具 举报

crimsonfaith91 发表于 2016-7-14 04:57:59 | 显示全部楼层
axings 发表于 2016-7-13 15:37. visit 1point3acres.com for more.
想了一下第二题不知道对不对,根据观察得出如下规律:

数字值的范围:该范围内数字的个数:该范围内每个 ...

311/3 = 103个数?
回复 支持 反对

使用道具 举报

axings 发表于 2016-7-14 07:36:39 | 显示全部楼层
crimsonfaith91 发表于 2016-7-14 04:57. 1point 3acres 璁哄潧
311/3 = 103个数?

是的,之前写的是off by one mistake,应该是第103个数。
回复 支持 反对

使用道具 举报

 楼主| treee 发表于 2016-7-14 08:34:31 | 显示全部楼层
hxtang 发表于 2016-7-14 00:58
1 是说实现把方针里某个element 0->1, 1->0的功能吗?

3b 如果只有a>b, c>d,是返回abcd和cdba都可以吗 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
1. 方阵有3种情况,全是1,全是0,有1有0,两个方阵做与的时候要考虑这3种情况。比如一个全是0,那么不管另外一个是什么,与完还是0。注意一下全是1和全0的情况是不需要子树的。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
3b 这个从头到尾得自己设计,有循环怎么办,我当时的设计是做个有向图,然后按某种ranking算法来计算视频的分数。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

4. 好像就是这个,不过我没敢碰证明,选了做生成矩阵。
回复 支持 反对

使用道具 举报

 楼主| treee 发表于 2016-7-14 08:36:09 | 显示全部楼层
axings 发表于 2016-7-14 03:52
我觉得3b其实是考你知不知道google经典的Page Rank算法。

哈哈我也问了面试官能否用page rank, 但是不行。
回复 支持 反对

使用道具 举报

 楼主| treee 发表于 2016-7-14 08:38:08 | 显示全部楼层

我当时也是这么做的,注意edge case就好,这道题就是考数组操作。
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-14 13:43:11 | 显示全部楼层
楼主好。第一题只要写And的逻辑就行了么?我试了一下写从matrix到tree的建立,再加上And操作,花了不少时间,面试时,时间恐怕不够。不知你面试的时候的要求是什么。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
谢谢~
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-18 12:02:03 | 显示全部楼层
treee 发表于 2016-7-14 08:34. 1point3acres.com/bbs
1. 方阵有3种情况,全是1,全是0,有1有0,两个方阵做与的时候要考虑这3种情况。比如一个全是0,那么不管 ...

.鐣欏璁哄潧-涓浜-涓夊垎鍦
能分享一下LZ怎么简单ranking 的吗?
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-7-18 12:18:44 | 显示全部楼层
3b Toposort 吗? 但是有环的时候排不出来
回复 支持 反对

使用道具 举报

 楼主| treee 发表于 2016-7-18 13:58:00 | 显示全部楼层
adrian_yang84 发表于 2016-7-14 13:43
楼主好。第一题只要写And的逻辑就行了么?我试了一下写从matrix到tree的建立,再加上And操作,花了不少时间 ...

只要and就可以,不过数据结构自己定义。要求就是我上面说的,但是注意如果一个子方阵都是1,就不需要4个子方阵了。程序不长,我有时间的时间写一下我的。。
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-18 20:07:12 | 显示全部楼层
第一题面试官希望的时间复杂度是多少
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-19 15:22:41 | 显示全部楼层
treee 发表于 2016-7-18 13:58
只要and就可以,不过数据结构自己定义。要求就是我上面说的,但是注意如果一个子方阵都是1,就不需要4个 ...

好的,感谢回复。我觉得我面试的时候得看着表,盯紧时间。自己练的时候,是在vim上写完整的能运行的程序,写很长的一坨,特别费时间。
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-22 12:20:21 | 显示全部楼层
迷宫那题,如果常规bfs或dfs的话,最多把每个点走一遍,就知道出口了,所以是O(V^2)的,不是指数复杂度。如果游戏规则设定走过的点不能计入visited,还可以再走若干次或者无穷次的话,那么就是一颗完全4叉树了,没有剪枝,是指数复杂度。

这是我的理解。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 01:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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