Niantic电面 + Onsite面经

面经检索
年份: 2019
月份: 11
公司: 其他公司
其他公司名称: -
面试阶段: OA 电面 Onsite 
职位类型: Intern
职位名称: General SDE
hr电话聊天+一轮电面+onsite(两轮)
基本电面,onsite都没有怎么问简历,大多数都是先介绍一下自己,面试官大致介绍一下Niantic,然后就开始做题。

Phone Interview:
中国工程师,Gang Liu. Max Tree Sum Path. Given a binary tree, find max path sum from root node to any node.
Follow up: find max path sum from any node to any node.
大班课的题。不是很难。不过面试官对code质量要求较高,不允许用global variable,最好也不要用argument传参数,用return type解决问题(包括follow up)

Onsite 1:
Steve
run length encoding
given a decoder, work like this:
input: “2a4xc”
ouput: “2acccc”

保持decoder的工作机理不变,如何设计encoder,可以使所有情况下的原string被decoder正确编译。(encode str要尽量短)
这个题我发挥的不是很好。看起来很简单,但其实Corner case特别多。最简单的情况下encoder遇到一个连续的重复字母(就是一个run),就将他encode成num X char的pattern。(注意如果run的长度是4以下,是没有必要encode的)
其次是一些Corner case:
input:”4xa”
这个题要求decoder的工作机理不变,所以encoder需要对这种情况特殊处理。解决方法是:“4xa”--> “1x4xa”

解决了上一个问题还要考虑:
input:”14xa”
这个要encode成“1x11x4xa”才能保证正确性
如果input是“122244xa”, → “1x13x22x4xa”保证最短

input:“123aaaa”
这个要encode成“1x11x21x34xa”才能保证正确性

我当时没有想到这么多test case,一直被challenge,直接有点懵了。最后代码没有写完,只写了主框架,没有写helper function。不过以上应该是需要考虑的所有Corner case了。再把它structure成代码,需要一些思考时间。

onsite2:
Jane 在sunnyvale办公室的小姐姐
人很好,上来自我介绍后做题。str addition 给两个str of digits 要求返回他们的和,存在str里。
很简单,注意Corner case就好

unit test刚才的代码,要加什么test case

然后一个讨论题,不需要写代码:
给一个api: getParent() 输入一个personid,返回两个personid(父母)。
设计: areRelated(), 输入两个personid,判断其是不是related
我的回答是recursively不断往上call getparent,用hashset记录两个path,不断check


Pingyuan Yue Phone
tree max path sum root to any node,any node to any node
run length encoding/decoding,  3xa --> aaa


Yi Wen onsite

1. Given two interfaces:

interface Tape {
        long read();
        void write(long value);
        boolean atEnd();
}

interface Network {
        void write(long value);
}

There are in total T tapes, each has N long integers stored. All the tapes are connected to one machine and that machine can store N long integers only. Design the algorithm to write global ascending data into the network.

2. Design an algorithm to search for pokemons whose names start with String p. The search should be conducted in your own pokemon inventory (will be given as List<Pokemon>).



标签: 暂无标签

写了 8 篇文章,拥有财富 0,被 0 人关注

回复

使用道具

您需要登录后才可以回帖 登录 | 立即注册
B Color Link Quote Code Smilies

成为第一个吐槽的人

返回顶部