《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 5408|回复: 21
收起左侧

狗家面经

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

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

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

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

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

本帖被以下淘专辑推荐:

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

public class Quad {. 鍥磋鎴戜滑@1point 3 acres
  private Quad[] children;
  private int size;
  private int value = -1;. more info on 1point3acres.com

  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);. visit 1point3acres.com for more.
    if (q.value == 1) return new Quad(this);
    . from: 1point3acres.com/bbs
    Quad[] qs = new Quad[4];
    for (int i = 0; i < children.length; i++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
       qs[i] = children[i].and(q.children[i]);
    }
    return new Quad(size, qs);
  }. 1point 3acres 璁哄潧
}

评分

1

查看全部评分

回复 支持 1 反对 2

使用道具 举报

axings 发表于 2016-7-13 14:58:48 | 显示全部楼层
写了一下第一题:
public class QuadNode
{
        public QuadNode[] nodes;
        public int color;
        public boolean isFull;-google 1point3acres
       
        public static QuadNode And(QuadNode node1, QuadNode node2)
        {.1point3acres缃
                if(node1.isFull && node2.isFull)
                {
                        QuadNode node = new QuadNode();
.1point3acres缃                        node.isFull = true;. From 1point 3acres bbs
                        node.color = node1.color && node2.color;
                        return node;
                }
               
                if(node2.isFull)
                {
                        return QuadNode(node2, node1);
                }
               
                if(node1.isFull)
                {
                        if(node1.color == 1)
. visit 1point3acres.com for more.                        {
                                return node2;
                        }
                        else
                        {
                                return node1;
                        }
                }
                else. from: 1point3acres.com/bbs
                {.1point3acres缃
                        QuadNode node = new QuadNode(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        node.nodes = new QuadNode[4];. 1point 3acres 璁哄潧
                        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]);
                        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
. more info on 1point3acres.com
那么比如我们要求第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怎么处理?. 鍥磋鎴戜滑@1point 3 acres

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
想了一下第二题不知道对不对,根据观察得出如下规律:

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

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

使用道具 举报

axings 发表于 2016-7-14 07:36:39 | 显示全部楼层
.鐣欏璁哄潧-涓浜-涓夊垎鍦
是的,之前写的是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. from: 1point3acres.com/bbs
我觉得3b其实是考你知不知道google经典的Page Rank算法。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
哈哈我也问了面试官能否用page rank, 但是不行。
回复 支持 反对

使用道具 举报

 楼主| treee 发表于 2016-7-14 08:38:08 | 显示全部楼层
. 1point3acres.com/bbs
我当时也是这么做的,注意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
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个 ...
. 1point 3acres 璁哄潧
好的,感谢回复。我觉得我面试的时候得看着表,盯紧时间。自己练的时候,是在vim上写完整的能运行的程序,写很长的一坨,特别费时间。
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-25 16:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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