Pocket Gems面经

电面1：

• strStr（）
• Top k frequent elements in an unsorted array
• FOLLOW UP: Top k frequent elements in a stream
• Kth most frequent number

Max Array

Input : An array of n numbers, and a number k

Output : An array of n numbers

where

output = MAX(input, input[i + 1]...... input[i + k - 1])
example：
[1, 3, 5, 7, 3, 4, 2, 9],  k = 3

[5, 7, 7, 7, 4, 9, 9, 9]

 

第三题，给出一个三角形三个顶点的坐标和一个新的点，问这个点是否在三角形内。当时没有准备这种几何题，上来有点萌，后来与小哥交流交流他还是会比较热心地给出一些hints，最后也没有要求把整个题目实现出来，我把思路和伪代码交给他，他说说得通OK。

 

都是面经原题。

1. StrStr()：

时间复杂度，worst case举例。

 

2. K most frequently occurring numbers：

时间复杂度。

follow-up：infinite stream of sorted numbers coming（用什么实现，伪代码，时间复杂度）。

 

补充内容 (2015-3-23 11:50):

第一题时间复杂度O(n)，worst case是在111111111112中找11112这种。

第二题时间复杂度O(n*log(n))；follow-up我用了一个heap，时间复杂度O(n*log(k))。

 

今天的新鲜面经：phone screen面试，一共问了两道题：

1. leetcode上的原题 strStr(). 然后问了时间复杂度（还问你这是最好，平均，还是最坏？），然后要给出一个能触发最坏运行时间的例子。以往的两篇面经中都能见到这个题，不多解释。

2. parse一个字符串表示的三元表达式，输出一个树结构。三元表达式中不含括号，每个变量名都是一个字母，并且保证合法。例如：

a?b:c	a?b?c:d:e	a?b:c?d:e
a / \ b   c	a   / \   b   e / \ c   d	a  / \, b   c     / \    d   e

其实一开始蒙圈了。。因为从没见过，所以很慌，总感觉跟上学期编译原理里讲的parser是一样的，努力回忆parser算法。。。。后来什么也没想起来，因为当初编程实现都是用yacc做的==

于是这才开始真正用心思考这个题目本身。很快想到得用递归了，然后有两个要点：

第一，字符串的开头一个字母一定是root。

第二，去掉root后，剩下的怎么切分成左子树和右子树呢？这里的关键是找到和第一个"?"相匹配的":"。后来发现其实就是很括号匹配一样的道理：见到"?"压栈；见到":"弹栈，弹出来的"?"和这个":"对应。

于是呼隆呼隆写完，然后interviewer要分析最坏时间复杂度。首先列出最坏情况：

a ? (...) : b

再列出最坏情况的递归表达式 T(n) = 2 * T(n - 4)，因为中间括号部分长度是n - 4，而且匹配":"时遍历了一遍，然后递归又遍历了一遍。这时 T(n) = O(2^n)。

然后问能不能优化，这才发现中间部分遍历了两次，所以应该一开始遍历就用hash table存下所有的 ? : 匹配关系，然后再遍历一遍，常数时间就能找到每个子树的起止点了。这样总复杂度是O(n)。这里就没让写代码，因为来不及了，只这样说了下思路。

 

最后一点时间介绍了一下公司情况。这家是做ios端手游的，一个游戏有一个team。然后还有一个team管后端服务器，虽然用python但是框架都是很老掉牙的，不是很有前途的样子。尽管我说没有ios开发经验，但是面试官还是鼓励说确实很多实习生没有Objective-C的经验，但是来学一学很容易上手的，我也顺势表示很喜欢学新东西（(⊙o⊙)…swift才是新版不是吗==）。

 

电面2：

• sort color，和lc的区别是sort的是对象数组，需要自己写comparator
• next node in BST
• 给出BST中某个节点，寻找下一个比它大的节点，有父节点。
• 有parent指针; 没有parent指针，但是有root

第一轮：

word break I

Sliding Window （给你一个数组和一个数k，k是滑动窗口的大小，滑动窗口每次向右移动一个index，输出是一个新的数组，记录每次窗口里的最小值）

example: [1, 2, 5, 10, 3, 4], output should be: [1, 2, 3, 3]

 

第二轮：

设计著名的Achievement 系统

 

第三轮：

著名的连接的房间问题。每个房间给你左下角点的坐标，长和宽，问是否所有的房间是一个连通的空间

那个房子的题就是每个房子给你(x, y)和房子的长宽。如果所有房间都是相连的，那么就是连通的空间。用bfs来做就可以了

• Top-down view of binary tree

example:

     1

   2  3

         4

       5

output should be: 2, 1, 3, 4

 

1. asian guy, 直接read code, 是String变成一个Tree， input: "   1     /   \    2       3"

  1

/ \

2   3

讨论了一下之后问如果String是

  1

/ \

2   3

\ /

  4 

 

2. asian girl, word break I, and find top k frequency number. 

3. american guy, achievenment的requirement设计游戏的achievement系统。requirement可以有很多种，给的例子一是拿到多少个金币，二是得到多少个某种动物，满足条件就可以完成一个achievement。

 

一共四轮

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=126289

第一轮俩题：

1. Maximum Product Subarray

2. Give a String array, return a minimum length String that satisfies the requirement that the relative orders between the chars in the output are consistent with the relative orders in every array element. Assume the output exists.

For example: { "cba", "bd", "ce", "ed" } -> "cbaed"     { "gcd", "jd", "fcj" } -> "fgcjd"

第二轮：

一个zoo的游戏，根据游戏中achievenment的requirement设计游戏的achievement系统。requirement可以有很多种，给的例子一是拿到多少个金币，二是得到多少个某种动物，满足条件就可以完成一个achievement。

第三轮：

讨论一份StringToTree的代码

 

第四轮：

You can go in four directions from the origin on a 2D surface. Given an int k, you can only reach the points where the sum of the coordinate digits is not greater than k. Return how many points you can reach..1

我当时用了Map<Integer, Set<Integer>>来存储访问过点的横纵坐标。讨论了一下如果用Set<Point>存储访问过的点需要怎么办，就是要重写hashCode()和equals()。

 

补充内容 (2015-3-24 21:47):

补充一下第三轮，代码是把

  1

/ \

2   3

这样的String变成一个Tree。讨论了一下之后问如果String是

  1

/ \. Waral 鍗氬鏈夋洿澶氭枃绔�,

2   3.1point3acres缃�

\ /. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷

  4

这样的这份代码还能不能构建出一个正确的Tree。

. From 1point 3acres bbs

补充内容 (2015-3-25 10:45):. fr

哦对了 第四轮还要求证明可达到的点的个数是有限个来着 以k=25为例证明

从(0, 0)向上走最多能够走到(0, 898)，到达这个点之后无论向上向左向右都走不通了，因此相当于在y=898上画了一条边界，其他方向同理。

补充内容 (2015-3-25 10:51):

第四轮的题还问到了时间复杂度

对于访问到的每个点判断是否满足小于k需要O(k)，所有访问到的点形成的图形最长半径为n的话则有O(n2)个点，所以总共是O(n2*k)。

 

http://www.1point3acres.com/bbs/thread-124517-1-1.html

1. leetcode 的word break，重要的是要写出时间复杂度（2^n）和worst case(如aaac, 字典是（"a", "aa", "aaa"）)

2. 给一个m*m的空间，一个房间的列表，证明所有房间是否相通的，这里面简化了很多，可以看成是一个二维数组然后搜索就可以了。其中还会问时间复杂度，不用写代码

3. 给一个stream，等概率抽出k个数，同时要证明是等概率的（reservoir sampling）cc150上也有讲的在hard那里, 这个也是shuffle card的算法

4. 输出一棵树从上往下看的节点，在geekforgeek上有，一开始用hashset说不好因为可能collision，然后先找最左和最右的距离然后用一个一维boolean数组就好了。

5. 一个机器人，在原点走，最远可以走多少个点，要求点的坐标数字之和不能大于k，然后证明机器人可以走的范围是有边界的。这个主要是证明，先一维，然后拓展就可以了，比如k = 14的话，一维最远可以走到68（虽然70可以，但是69就走不到了）。复杂度是nk/9，n可以走到的点的个数。这轮也不是很好需要三哥提醒才弄得出来证明的东西。另外visited table的话可以用hashset<string>，把“1，1”当作是key就好了。这个似乎挺好的。

6. 成就系统，估计是挂在这里了，把问题想的太复杂，然后基本没有说什么有价值的东西。三哥一问就有点紧张，注意不要冗余代码就好了，然后传参的时候用人物在成就中查询。三哥后来说oop和system design还是很重要的。

前几天面的，就是比如给你一些描述requirement, 比如金钱数，如果玩家身上的金钱数到达一定的数目的话就有奖励。玩家身上还有其它物品，然后有些成就是需要得到的物品达到一定的数目才有奖励，现在就是需要写一些类或者接口，使得当增加新的成就的时候不要修改或者增加代码。

 

面试题：

1．word break

2．给你n个棒子，每个棒子的长度不一，要把所有棒子连起来，每次连接两根，棒子的长度即为连接的cost, 求最小的cost.

解法：每次挑最短的两根棒子连接就好了。

3. 给你一组数，让你挑连续的几个数，使得它们乘积最大。　比如：　１，２，３，０，－１，－７，０，３，１，－９　

这组数里乘积最大的就是-1*-7 = 7,　注意要求是连续的数。　要求算法time complexity是O(n)

4. top-down view of binary tree.

解法：level order traversal + hashmap

5. achievement system

这题是设计题，achievement有requirement和reward, 玩家满足了requirement就可以拿到reward。　requirement 主要有coin, item等，　reward则不太清楚。　总之就建出来这些class, 把attribute还有constructor写写。　想想每次你增加一个achievement的时候怎么call你建的这些class等等。　这个设计的关键在于，每次如果设计方想增加一个achievement, 他应该只要给新的input就可以了，不用给写好的这些个class. 

 

补充内容 (2015-3-16 08:26):

最后一句应为：不用改写好的class.

 

补充内容 (2015-3-26 10:00):

连接棒子这题具体例子如下：四个棒子，长度为1,2,3,4. 

连接方法1：

3 + 4 = 7    

7 + 2 = 9     

9 + 1 = 10

total cost = 7+9+10 = 26

最佳顺序

1+2 = 3

3+3 = 6    

6+4 = 10

total cost = 3+6+10=19

 

面经如下：.

1. strStr()，之后问了什么样的情况会是worst case。lz刚开始举了一些在学kmp算法时看到过的例子；然后面试官说没有cover到所有的例子。在最后一秒想出了aaaaa, ac这样的worst case，只是面试官不让我写了= =.

2. （貌似是新题？？）设计一个数据结构，支持操作：插入元素、删除元素和随机获取一个元素（不考虑元素重复情况），要求三个操作的时间复杂度为O(1)，可以使用java的Math.random()。lz刚刚开始想到用linkedlist + hashmap，给每个元素一个单独的key，但是发现不知道在linkedlist里面存什么东西比较好。。。实在是很紧张。之后，又想到用了两个hashmap来存储，可是对于getRandom()，面试官说你这样可能会crash掉。。。然后，1个小时就到了。。。

 

其实和版上大多数同志遇到的题目差不多，只是LZ不幸被要求三轮面试，对这点感觉奇怪，在第三轮结束，自知铁定Fail的情况下，问了一下为什么给我三轮。得到的回答是：This is real uncommon. 

第一轮： strStr() ; find kth smallest number in a Array

第二轮：BST, find next node ; colors sort

第三轮： 成就系统设计

要求：

1. 界面支持： 成就列表，成就细节，完成情况

2. 成就系统能检测是否玩家完成成就要求， 每个成就之间是独立的（不用考虑是否有先后关系）

3. 系统要求简洁，新的内容可以增加（就是产生新的object），新的类型也可以添加，比如你可以添加一个int coin，新的integer 型。

总之LZ没有准备这个，所以挂了，仔细想想，并不是很难。希望对大家有帮助。

 

昨天去onsite的，感觉员工们都很年轻又是做游戏这一块的，所以感觉大家工作的很有激情，气氛很轻松。和所有面试官聊完以后，发现他们家招人其实不在乎你用什么语言，学过多少种，会不会什么特别流行的技术，基本上就是看你是不是善于分析思考，是不是能很快速学习一些新的东西，然后举一反三一类的。

一共面了四轮，真心感谢之前所有提供面经的人，
第一轮： 印度人. 
1. Max Product Subarray
2. Longest palindromic substring
3. Input String[] array = {"ab, bc, bz"} Output "abcz". 
    Input String[] array = {"fbz, jb, ebj"} Output "efbjz"
    要满足三个条件： 1. Output unique character
                                 2. output的string里，character相对顺序不变。Input不会有“bc ”，“cb”这种情况出现
                                 3.满足以上两个条件，按照lexicographical order, 输出最小的可能性.
   扯了很久这道题，一直没想到要怎么建立hashmap，三哥总是说接近了。。

第二轮: 印度人
Achievement System Design
其实这一轮很好准备，因为本身这个设计也不是很复杂。一共就是一些requirements，rewards， 满足requirements， 就给player reward。 之前的面经都很详细了，不过补充一点， 注意不要重复送reward，所以要有一个值去检查是不是已经发过reward了。这一轮其实算是面的最轻松的一轮了，主要是好好跟面试官交流，能很明白的让他知道你为什么这么设计就可以了。

第三轮： 亚裔MM
1. Word Break
2. Word BreakII改版，这次不需要返回所有的可能性，只要一种就可以，所以backtracking不是最优解。最后MM提示说继续用DP就可以了。

第四轮：白人GG.
1. 写一个mutable string。 里面有三个methods, charAt(int i), substring(int beginIndex, int endIndex), setcharAt(int i, char c); 只能是O（1） space complexity
第三问写的很辛苦，因为看过有人面过这道题，没记错的话当时楼主提出了自己的想法，用的是ArrayList of hashmap，所以我一开始也就朝这个方向在想，相差了。后来蹉跎了好久，突然发现用tree的结构更好。
然后面试官，终于说OK了。 因为没时间，所以就是在白板上画了图解释了一下子。
最后还跟HR聊了一下子，说SDE这个职位，目前他们还没有名额限制，所以录不录取，不受candidate影响。还有他们会连同phone interview的feedback一起考虑进来，所以phone interview还是要好好面。
HR说下周一给消息，不过回家以后收到邮件说，他们大概调查了一下子，感觉今天feedback不错， 让我发references 名单给他们。因为个人感觉每轮都还是答得没有那么好，真不知道这个是不是走流程还是真的有点戏。
求offe！！！！！
补充内容 (2015-4-4 14:56):
第一轮第三个道题的example给错了。“jb”和“ebj”这个是invalid input，请大家忽略

 

Pocket Gem电面题和地里朋友都差不多
第一轮电面：
1. Implement indexOf(strstr)，暴力解法OK...
2. Top K frequantly Number in array (提示：hashtable+minHeap)
    - Follow up: 输入是sorted stream，这个我回答的不好，说完idea写代码时候卡住了，但最后还是过了。

第二轮电：.
1. sort color objects (Leetcode). 
2. Find Next largest node in BST (parent pointer provided)
    - Follow up: No parent pointer, but provide the root pointer.. 

然后.....
刚刚收到第三轮电面通知..谁知道这是个什么东西..难道我第二轮面的不够好？.

 

 

第一轮电面是strstr 和 根据string建tree， 例如"a?b:c" 就是a是根节点 b，c是叶子节点。
第二轮电面是next node in BST 和  sort color
两轮电面之后，发了skype面，做了一道pocket gems之前没考过的题： evaluate an infix notation. 例如，输入“1+2*(4+5)-4”, 返回15. 不知道为啥两轮电面之后是skype，而不是onsite。

 

公司在sf downtown，出了电梯进公司满眼得游戏设施。。。 有台球有乒乓球，有桌上足球，还有各种游戏机，然后零食饮料之类得也是随便吃，感觉非常不错。
. Waral 鍗氬鏈夋洿澶氭枃绔,
4轮，每轮一个小时，连战。前一天飞5个小时过去，晚上睡得不好，面到后面都要跪下来了－ －
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一轮 3哥哥  
1. max product array，需要跟他讲清楚怎么做，然后复杂度什么得最后写代码。. 1point 3acres 璁哄潧
2.  给string array，输出包含所有字符并且顺序跟array里面一致得string 详情见http://www.1point3acres.com/bbs/ ... light=pocket%2Bgems

第二轮 3哥哥
1. word break， 先写了dp，说了复杂度，然后等着做word break ii 得时候，3哥让我用递归再做一个，然后又是复杂度，最差情况。
2. 给stream，设计策略，确保每一次取出来得数都是随机得，这里还要证明，不过这个三哥还是给了点提示，最后讨论出来了。

第三轮 不知道哪里来得高个白哥哥，说话很不清楚，而且我做得过程中给我讲注意点，也讲得不清不楚，相当于我连java都不会得时候，给我讲框架了. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
achievement，这轮感觉挺不好得，本来有些想法，白哥哥一直否定，后来就随便讲讲，也没写什么代码，如果要跪就是跪这里了。. Waral 鍗氬鏈夋洿澶氭枃绔,

第四轮 白大叔
string 设计，要求o(1)实现charat() substring() setcharAt()， setcharat想得方法不是很好，好在最后还是讲通了，后来问他，说用tree更好。
公司感觉还是不错，但是在sf市区，房租好吓人。。。.

 

发信人: unichen (greedyrouter), 信区: JobHunting 
标  题: pocket gems面经 
发信站: BBS 未名空间站 (Sat May 24 10:58:35 2014, 美东) 

总共有4轮。给的offer不是很好看，所以没去。他们家的阿三面完第三轮和我说你应该 
已经面完了，但是后来HR又给了我第4轮，我猜应该是前面两轮面的不错吧。他们家的 
面试题是最独特，也是我最喜欢的。 

第一轮： 
1‘  Shortest Manhattan distance. 有一个网格。在这个网格上有若干个人，如何在 
此网格上找出一个约会地点，使其到所有人的距离之和最短。 
2’  如何去serialize一棵树。 

第二轮： 
1‘  字符串分割。有一个字符串和一个字典，问此字符串是否可以分割成字典中的若 
干个词。时间复杂度为何？ 
2‘  random sampling。有一个infinite的stream，你想sample其中的k个元素。每次 
遇到新元素你可以选择加入它，同时放弃原有的一些元素。如何让每个元素被选到的概 
率一样，同时不使用多余的空间。 
3‘  你有一个棋盘。从原点出发，定义f(x,y)为其坐标所有数字之和。例如f(185,233 
) = 1+8+5+2+3+3。每次你都可以选择走任何8个方向。问：最后你能够到的点是有限个 
吗？试证明之。 

第三轮： 
设计一个游戏的scoreboard。假设每个人都有若干个任务。完成每个任务都会有相应的 
奖励。 

第四轮： 
设计一个mutable string，支持下列的功能： 
1' getCharAt   2' substring  3'setCharAt 
要求每个operation的space cost都是O(1) 

 

1 sliding windows (given an array of n numbers and a window width of k , return a new array with the minimum value in each window)

ex: a = 1,2,3,-1,5,6,7 k = 3 return : 1, -1,-1,-1,5,6,7;

follow up: O(n) complexity;

2. maximum product in an array

3. Neighboring classroom, given a map of m * m, and n classrooms, determine if every classroom belongs to one single component; 

bounds: (1)classroom is at most 3 * 3 in area (2) no overlapping classrooms (3) classrooms are at least 5% of m * m in total area (4) isConnected returns true only when two classroom shares a common EDGE

这轮完了的档口收到了一封"congratulations from amazon", 瞬间不想面了, 不过还是很负责任的继续面完了

Round 2 

Achievement System Design, requirement:

(1)no new codes should be added when adding similar achievements/requirements( 原来有个achievement 叫reachLVL2 , 新加一个reachLVL5 , 不能新写一个类)

(2) new codes can be added with minimum amount when adding brand new achivements(新加一个connectOnFB achievement , 类的借口不能被破坏) 

Round 3

1.  word search 1

2. given an array, return the starting and ending index of all subarrays that sums to 0;

ex: 1 , -2, 2, -1, 0 , 5

return (1,2)(0,3)(4,4)(0,4)-google 1point3acres

Round 4. 

design a string class , with implementation of charAt() and substring(b,e), with substring() requires O(1) time and O(1) space complexity

followup:

a new method setCharat(index, char) is added, a substring must keep the changes of parrent string that are made before its creation, but both the parrent string and the substring will not affect each other after the creation of the substring, requires O(1) space complexity

 

那题主要的design其实就是设计requirement 接口和reward 接口, 然后每个achievement 都有两个list, 一个存的是所有requirement 一个存的是所有reward. 有一个函数叫satisfied(), 每次调用就把requirement list 遍历一遍看是否都满足了, 都满足了就把所有reward 挨个给一遍. requirement和reward是相似的,这里只说requirement接口

interface Requirement{. Waral 鍗氬鏈夋洿澶氭枃绔�,

    public boolean isSatisfied(Player player);

}

接下来对player里的每个属性写一个requirement类就可以了, 比如lvl值

class ReachLvlReq implements Requirement{

   int lvl;

   public ReachLvlReq (int lvl){. 1point 3acres 璁哄潧

       this.lvl = lvl;-google 1point3acres

   }

   public boolean isSatisfied(Player player){

       return player.lvl >= this.lvl;. 1point 3acres 璁哄潧

   }

}. Waral 鍗氬鏈夋洿澶氭枃绔�,

这样写之后不管requirement是lvl2还是lvl5都不用改框架的code. 鍥磋鎴戜滑@1point 3 acres

假设多了一个connect on FB, 那自然player里会多一个boolean 属性叫 connectFB

自己新写一个requirement类就可以了. 鐗涗汉浜戦泦,涓€浜╀笁鍒

 

class connectOnFBReq implements Requirement{ 

  public connectOnFBReq  (){

   }

   public boolean isSatisfied(Player player){

       return player.connectOnFB;

   }

}

这样就保证即使出现了全新的req, 加的code也是minimum