要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 5854|回复: 21
收起左侧

狗家面经

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

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

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

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

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


上一篇:uber电面
下一篇:Twitter 三藩onsite

本帖被以下淘专辑推荐:

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

public class Quad {
  private Quad[] children;
  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);
   
    Quad[] qs = new Quad[4];
    for (int i = 0; i < children.length; i++) {
       qs[i] = children[i].and(q.children[i]);. 1point 3acres 论坛
    }. 一亩-三分-地,独家发布
    return new Quad(size, qs);
  }
}

评分

1

查看全部评分

回复 支持 1 反对 2

使用道具 举报

我的人缘0
axings 发表于 2016-7-13 14:58:48 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
写了一下第一题:
public class QuadNode
{
        public QuadNode[] nodes;
        public int color;
        public boolean isFull; 来源一亩.三分地论坛.
       
        public static QuadNode And(QuadNode node1, QuadNode node2)
        {. From 1point 3acres bbs
                if(node1.isFull && node2.isFull)
                {
.留学论坛-一亩-三分地                        QuadNode node = new QuadNode();
                        node.isFull = true;
                        node.color = node1.color && node2.color;
                        return node;
                }
                . from: 1point3acres
                if(node2.isFull)
                {. 1point 3acres 论坛
                        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]);
                        node.isFull = false;. more info on 1point3acres
                        return node;
                }
        }
}
回复 支持 反对

使用道具 举报

我的人缘0
axings 发表于 2016-7-13 15:37:05 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
想了一下第二题不知道对不对,根据观察得出如下规律:

数字值的范围:该范围内数字的个数:该范围内每个数字所占的位数
1-9 : 9 : 1
10-99 : 90 : 2
100-999 : 900 : 3
1000-9999 : 9000 : 4
-google 1point3acres
那么比如我们要求第500个数是什么,就可以这么拆解问题:.1point3acres网
从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

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
peter_sqliu 发表于 2016-7-13 17:37:38 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
请问lz几年工作经验啊, 题好难啊
回复 支持 反对

使用道具 举报

我的人缘0
chen6145 发表于 2016-7-14 00:41:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
Design题楼主是咋作答的呀?
回复 支持 反对

使用道具 举报

我的人缘0
hxtang 发表于 2016-7-14 00:58:04 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
1 是说实现把方针里某个element 0->1, 1->0的功能吗?

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

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

使用道具 举报

我的人缘0
axings 发表于 2016-7-14 03:52:36 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
我觉得3b其实是考你知不知道google经典的Page Rank算法。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
crimsonfaith91 发表于 2016-7-14 04:57:59 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
axings 发表于 2016-7-13 15:37
想了一下第二题不知道对不对,根据观察得出如下规律:
来源一亩.三分地论坛.
数字值的范围:该范围内数字的个数:该范围内每个 ...

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

使用道具 举报

我的人缘0
axings 发表于 2016-7-14 07:36:39 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
. From 1point 3acres bbs
是的,之前写的是off by one mistake,应该是第103个数。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 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. 好像就是这个,不过我没敢碰证明,选了做生成矩阵。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| treee 发表于 2016-7-14 08:38:08 | 显示全部楼层

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

使用道具 举报

我的人缘0
adrian_yang84 发表于 2016-7-14 13:43:11 | 显示全部楼层
楼主好。第一题只要写And的逻辑就行了么?我试了一下写从matrix到tree的建立,再加上And操作,花了不少时间,面试时,时间恐怕不够。不知你面试的时候的要求是什么。

谢谢~
回复 支持 反对

使用道具 举报

我的人缘0
say543 发表于 2016-7-18 12:02:03 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
treee 发表于 2016-7-14 08:34
1. 方阵有3种情况,全是1,全是0,有1有0,两个方阵做与的时候要考虑这3种情况。比如一个全是0,那么不管 ...

-google 1point3acres
能分享一下LZ怎么简单ranking 的吗?
回复 支持 反对

使用道具 举报

我的人缘0
mkcing 发表于 2016-7-18 12:18:44 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
3b Toposort 吗? 但是有环的时候排不出来
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
readman 发表于 2016-7-18 20:07:12 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题面试官希望的时间复杂度是多少
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-27 21:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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