Palantir面经 | shawnlincoding
1. 给你一个棋盘 int[][] board, 你可以交换任何一个棋子和它的邻居（横向或者竖向相邻的棋子），如果交换后，在横向或者竖向产生了大于等于三个连续的一样的棋子 e.g. 4 4 4
5
5
5
那么就算交换有效。(就是一个比较常见的游戏，忘记叫啥名字了)
请你写一个函数返回所有可以有效交换的棋子的坐标对。 比如 （（0， 0）， （1， 0）） ， （（3,2），（3,3））.
2，看code，debug， 然后写出正确的code，这个没啥说的
3 Merge interval
Running Median : follow up: O(1) space
2,
write a fuction to titlecase a string
for example
input: the quick brown fox
output: The Quick Brown Fox
two pointers, remember to update flag
DFS,很像coursera普林算法课讲得CC， 看看所以0是不是在一个CC里面
从0，0开始做一次DFS，如果有0没被marked到那就是invalid的
分别是dict找word，anagram，edit distance 1, edit distance，然后到general。
先问了merge two sorted list， 又问了merge K sorted list，然后说让用MinHeap，也就是Java 里面的priorityQueue 来优化。
running median.
min stack
get top k numbers in max heap
follow up也都不难，做得很顺利，做完他们都说good, excellent, perfect之类的
在电脑上coding的问题，map相关，不是算法题，是多线程有关的，但个人感觉不用担心，按时写完即可
第二轮，简单来说就是求2个数组的交集，然后follow up，变形的奇奇怪怪，现在都不知道他要干什么，很麻烦，弄了半天没怎么弄懂，然后时间到了。
第三轮，求数组都最长等差数列（要求连续），follow up 可以不连续，这里答得不太好，直接暴力做了
第四轮，求一些区间的相交次数最多的任意一点。因为一开始是区间是int类型，我直接开了个数组，每读取一个区间就＋＋，然后求数组最大的点就行了。follow up区间是float类型，之前方法明显不行，后来先按区间的start排序，然后每次比较end，好麻烦感觉，弄了半天没符合他的要求。
第二轮白人，上来问我做过的那道一个乱序数组每个数的位置距离他应有的位置差不超过k，如何更快的排序数组。。直接给出了minheap的解法。。表示同意。。。然后问我乱序数组找排序好的median, kselection, 讲了原理以及时间复杂度的best和worst，写了kselection的code，一遍bug free
Read full article from Palantir面经 | shawnlincoding
1. 给你一个棋盘 int[][] board, 你可以交换任何一个棋子和它的邻居（横向或者竖向相邻的棋子），如果交换后，在横向或者竖向产生了大于等于三个连续的一样的棋子 e.g. 4 4 4
5
5
5
那么就算交换有效。(就是一个比较常见的游戏，忘记叫啥名字了)
请你写一个函数返回所有可以有效交换的棋子的坐标对。 比如 （（0， 0）， （1， 0）） ， （（3,2），（3,3））.
2，看code，debug， 然后写出正确的code，这个没啥说的
3 Merge interval
Running Median : follow up: O(1) space
2,
write a fuction to titlecase a string
for example
input: the quick brown fox
output: The Quick Brown Fox
two pointers, remember to update flag
DFS,很像coursera普林算法课讲得CC， 看看所以0是不是在一个CC里面
从0，0开始做一次DFS，如果有0没被marked到那就是invalid的
3,
Palantir:
电面
Given a vector, two items are considered duplicates if their indexes are within k. Find whether there are duplicates.
Given two nodes in a tree, find the least common ancestor
Palantir:
电面
Given a vector, two items are considered duplicates if their indexes are within k. Find whether there are duplicates.
Given two nodes in a tree, find the least common ancestor
onsite
Given an array, return the end index and difference of longest arithmetic sequence (no need to be consecutive).
Given a list of string, return the list of prefix that can uniquely define each string.
Given a string, return the number of characters you need to put at the end of the string in order for the string to be a palindrome.
Debug a program written in Java. The program is used to implement a smart way of lexicographical comparator. Problem: wrong output and slow run time.
Given a list of weights (each one associated with a label), generate a random label based on the weight. What if the label needs to be generated many times? How to speed up?
主要还是偏重coding，就是最后一轮讨论了下machine learning的相关问题
Given an array, return the end index and difference of longest arithmetic sequence (no need to be consecutive).
Given a list of string, return the list of prefix that can uniquely define each string.
Given a string, return the number of characters you need to put at the end of the string in order for the string to be a palindrome.
Debug a program written in Java. The program is used to implement a smart way of lexicographical comparator. Problem: wrong output and slow run time.
Given a list of weights (each one associated with a label), generate a random label based on the weight. What if the label needs to be generated many times? How to speed up?
主要还是偏重coding，就是最后一轮讨论了下machine learning的相关问题
4,
magic box
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=110120&extra=&highlight=palantir&page=1
magic box
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=110120&extra=&highlight=palantir&page=1
5,
1
1) Select Sort in place. Input: [2, 7, 1, 4, 5], 3 Output: [2, 1, 7, 4, 5]
2) Given a number n, count the sum of all a, which a<n and a%3 == 0 || a%7 == 0. For example, Input: 10 Output: 25 (3, 6, 7, 9) use constant time
1
1) Select Sort in place. Input: [2, 7, 1, 4, 5], 3 Output: [2, 1, 7, 4, 5]
2) Given a number n, count the sum of all a, which a<n and a%3 == 0 || a%7 == 0. For example, Input: 10 Output: 25 (3, 6, 7, 9) use constant time
2 Merge interval 的变形题.
Input: we have the time line of several jobs.
For example, Job A: [18, 25] Job B: [20 22] [24 27] Job C: [30 50]
Output: [18 20] A [20 22] AB [22 24] A [24 25] AB [25 27] B [30 50] C
Input: we have the time line of several jobs.
For example, Job A: [18, 25] Job B: [20 22] [24 27] Job C: [30 50]
Output: [18 20] A [20 22] AB [22 24] A [24 25] AB [25 27] B [30 50] C
3 Sort the nearly sorted array, in the array, every element is at most k distance with its final place.
一开始用常规的k size heap，但是被明确要求用multi-thread来提速，这个方法是不行了。应该用2K的方法来divide and conquer。用多线程最终可以提速到O(klogk)
first, mention insertion sort, O(nk) inner loop只需要比较k次
second, heap O(nlogk) 前面k个还可以有heapify做
third, divide into n/k份， 依次merge B_i B_(i+1)， 那么B_i sorted, B_i+1 ksorted，算法课作业
first, mention insertion sort, O(nk) inner loop只需要比较k次
second, heap O(nlogk) 前面k个还可以有heapify做
third, divide into n/k份， 依次merge B_i B_(i+1)， 那么B_i sorted, B_i+1 ksorted，算法课作业
6，
OA
first non-repeated character
Given an input string, update the string so that a letter t is never followed by h
OA
first non-repeated character
Given an input string, update the string so that a letter t is never followed by h
7，
1. LRU cache
2. given an array of integers, return an array whose ith value is the median of the first i integers in the input
follow up, if the input is too large, how can you solve it using only constant memory? You can have random access to the ith value in the input array. Expected runtime O(n^2) or faster
3. HR phone screen: why Palantir, what to expect, how do you think the interview, have you seen the interview questions before?. 1point3acres.com/bbs
2. given an array of integers, return an array whose ith value is the median of the first i integers in the input
follow up, if the input is too large, how can you solve it using only constant memory? You can have random access to the ith value in the input array. Expected runtime O(n^2) or faster
3. HR phone screen: why Palantir, what to expect, how do you think the interview, have you seen the interview questions before?. 1point3acres.com/bbs
8,
第一轮白人女面试官，Implement Rabin-Karp Algorithm. 对，就是pattern matching三算法之一的那个，要求在eclipse里面实现并且通过test cases.
做出来了但不是特别流畅，中间卡了壳。经验是如果想进顶级公司，不是说KMP, Boyes-Moore, Rabin-Karp 侃侃而谈就能打动面试官。任何成名算法都要做到一张白纸拍下去马上写出来bug free的代码。
第二轮白人男面试官，Code debugging. 给出一段代码，指出其中的问题并修改。这一轮做的还不错，面试官也比较满意。这一轮比较看平时项目经验和写代码的积累，考虑问题要全面。
第三轮白人男面试官，Online median. 双heap解决之。Follow up 是不可以使用heap, 不可以改变Input array. 这里的follow up 处理的不太好，没有给出最优解
第一轮白人女面试官，Implement Rabin-Karp Algorithm. 对，就是pattern matching三算法之一的那个，要求在eclipse里面实现并且通过test cases.
做出来了但不是特别流畅，中间卡了壳。经验是如果想进顶级公司，不是说KMP, Boyes-Moore, Rabin-Karp 侃侃而谈就能打动面试官。任何成名算法都要做到一张白纸拍下去马上写出来bug free的代码。
第二轮白人男面试官，Code debugging. 给出一段代码，指出其中的问题并修改。这一轮做的还不错，面试官也比较满意。这一轮比较看平时项目经验和写代码的积累，考虑问题要全面。
第三轮白人男面试官，Online median. 双heap解决之。Follow up 是不可以使用heap, 不可以改变Input array. 这里的follow up 处理的不太好，没有给出最优解
9,
店面：
第一轮问的是merge interval
第二轮问的是lru cache，还有一道题是说给定一个数组，这个数组有一个特性是，每一个元素距离其排序后的位置，最多差k个距离，然后叫我将这个数组排序，要求时间复杂度好于nlogn.
店面：
第一轮问的是merge interval
第二轮问的是lru cache，还有一道题是说给定一个数组，这个数组有一个特性是，每一个元素距离其排序后的位置，最多差k个距离，然后叫我将这个数组排序，要求时间复杂度好于nlogn.
第一题，主题是coding，check一系列byte是不是合法的utf8编码。utf8的定义大家可以去网上搜一下，具体我记不太清了。这轮主要是看代码是否简介清晰，无奈写出了一个bug。情况是这样，有一种byte组合是永远不会出现在utf8的编码里的，我忘记考虑了这种情况，结果就是跪在这个上面。
第二题，考algorithm，给一个数组，要求输出一个数组，第一个是原数组第一个的中位数（就是原数组的第一个），第二个是原数组第一个到第二个的中位数，第三个是原数组第一个到第三个的中位数，以此类推。我一开始说用一个最大堆和一个最小堆来做，然后又要求constant space来做。
第三题，考system design，题目是设计一个distributed 的key-value store.
10,
3. 第一道是reverse list。当时就傻眼了，我还问了一句，有没有环
4. 写一个可以运行的贪吃蛇backend。以前只听同学说过面google设计贪吃蛇，写还是第一次。士气大落，在动手前浪费了不少时间。虽然在提示下写出了大部分但是还是没有写完，如果一拿到就开始动手其实并不难。
3. 第一道是reverse list。当时就傻眼了，我还问了一句，有没有环
4. 写一个可以运行的贪吃蛇backend。以前只听同学说过面google设计贪吃蛇，写还是第一次。士气大落，在动手前浪费了不少时间。虽然在提示下写出了大部分但是还是没有写完，如果一拿到就开始动手其实并不难。
snake class
判断蛇的生死，存储蛇的位置，移动蛇的方法
判断蛇的生死，存储蛇的位置，移动蛇的方法
board class
food的生成
food的生成
11,
题目是给定一个矩阵，里面有0和非0值. 求最大的连通的非0元素的加和。用dfs做吧，要记得update访问过的元素为0follow up是如果有负数在里面怎么办。我的想法是跟maximum subarray的解法一样，running time估计在O(n2)。不知道对不对.
题目是给定一个矩阵，里面有0和非0值. 求最大的连通的非0元素的加和。用dfs做吧，要记得update访问过的元素为0follow up是如果有负数在里面怎么办。我的想法是跟maximum subarray的解法一样，running time估计在O(n2)。不知道对不对.
12,
第一题是Merge Interval， leetcode原题。
第二题和第三题都只要我说解题思路，用什么data structure以及runtime complexity，估计是因为他打电话迟了十分钟，怕时间不够。
/**
* Write a function that is given an array of integers. It should return true if
* any value appears at least twice in the array, and it should return false if every element is distinct..
boolean containsDuplicate(int[] arr) {}
–
/**
* Write a function that is given an array of integers and an integer k. It
* should return true if and only if there are two distinct indices i and j into.
* the array such that arr[i] = arr[j] and the difference between i and j is at most k.
*/
boolean containsNearbyDuplicate(int[] arr, int k) {}.
第一题是Merge Interval， leetcode原题。
第二题和第三题都只要我说解题思路，用什么data structure以及runtime complexity，估计是因为他打电话迟了十分钟，怕时间不够。
/**
* Write a function that is given an array of integers. It should return true if
* any value appears at least twice in the array, and it should return false if every element is distinct..
boolean containsDuplicate(int[] arr) {}
–
/**
* Write a function that is given an array of integers and an integer k. It
* should return true if and only if there are two distinct indices i and j into.
* the array such that arr[i] = arr[j] and the difference between i and j is at most k.
*/
boolean containsNearbyDuplicate(int[] arr, int k) {}.
设计分布式拍卖系统，楼主给了一个client-server的解和一个p2p的解，然后问了个简单的文本里找字典里的词的题(口答)，楼主给了个hashset，然后follow-up是anagram怎么解。
（面试官表示满意，move on）
（面试官表示满意，move on）
3. 第二次电面，面试官是一位phd，简单寒暄过后直入主题：第一道经典的无限输入流找中位数，第二道无限输入流找平均值，第三道无限输入流找mode。中间夹杂着问了溢出如何处理（转成字符串，或用链表，又问字符串和链表的优劣，存储位置不同）。前两道题楼主也是马上给出最优解就解了，最后一题卡了一下，面试官提示了一下也马上就搞定了，很快，总共35分钟。
设计题，mini-yelp。设计了存储的数据结构，然后问了2-D空间如何找最近的点，楼主给了个heap的解，面试官说可以用二分解。但这轮的主要还是面设计。最后问了如何测试mini-yelp，尤其是如何在分布式环境下测试min-yelp。（从测试case等）.分别是dict找word，anagram，edit distance 1, edit distance，然后到general。
先问了merge two sorted list， 又问了merge K sorted list，然后说让用MinHeap，也就是Java 里面的priorityQueue 来优化。
recruiter phone screen，会问你为什么选Palantir，我说完了以后他说注意他们有philanthropy engineering，帮助救灾等等，给我感觉如果提到这个会有帮助，提升“culture fit”
flip columns
find duplicates, find duplicates within distance k, find fuzzy duplicates within distance k… running median.
min stack
get top k numbers in max heap
follow up也都不难，做得很顺利，做完他们都说good, excellent, perfect之类的
在电脑上coding的问题，map相关，不是算法题，是多线程有关的，但个人感觉不用担心，按时写完即可
16，
Tower of Hanoi
Tower of Hanoi
17,
leetcode
rotate array
leetcode
rotate array
18,
clone graph DFS and BFS
第一轮，求一个string list的每个string对应的unique prefix，返回也是一个list。我用Trie解决，建Trie、查找写了半个大黑板。面试官觉得很好。clone graph DFS and BFS
第二轮，简单来说就是求2个数组的交集，然后follow up，变形的奇奇怪怪，现在都不知道他要干什么，很麻烦，弄了半天没怎么弄懂，然后时间到了。
第三轮，求数组都最长等差数列（要求连续），follow up 可以不连续，这里答得不太好，直接暴力做了
第四轮，求一些区间的相交次数最多的任意一点。因为一开始是区间是int类型，我直接开了个数组，每读取一个区间就＋＋，然后求数组最大的点就行了。follow up区间是float类型，之前方法明显不行，后来先按区间的start排序，然后每次比较end，好麻烦感觉，弄了半天没符合他的要求。
1，FizzBuzz，考基本功，感谢白人小帅哥。
2，Inorder Traversal, iterative和recursive。
3，Inorder successor, 元素可能不在tree内。
2，Inorder Traversal, iterative和recursive。
3，Inorder successor, 元素可能不在tree内。
二：
1，Valid BST, 要求至少两种办法。用inorder traversal和min-max法解决了。
2，MaxPath，找出一个树上最长的任意点到任意点的路径，GeekforGeek有原题。
1，Valid BST, 要求至少两种办法。用inorder traversal和min-max法解决了。
2，MaxPath，找出一个树上最长的任意点到任意点的路径，GeekforGeek有原题。
1，N个unsorted数，找出最长的连续等差序列。暴搜外加几个全局统计变量就可以。
2，升级版，不要求连续，可以有间隔的等差序列就可以，第一题配合DP解。有些难，最后没把DP的转换方程写好。
2，升级版，不要求连续，可以有间隔的等差序列就可以，第一题配合DP解。有些难，最后没把DP的转换方程写好。
二：
1，扯天聊项目，问了一些key value pair和relational的performance比较。
2，给N个string，找出他们各自的unique prefix，比如abc, bac, xyz, aac的unique prefix就是ab, b, x, aa，也就是最短的能idenfity原string的prefix。
2. 然后findPalindromeRemainder，找到最短的“拼在一个非palindrome字符串后面，使它变成palindrome的”额外字符串，比如baba就是拼个a在后面。做一个原字符串suffix树和倒转过来的字符串prefix树，然后两个树同时遍历，到第一个不同的元素，记下index，把原字符串从0到index的倒着append到原字符串后面就可以了。3. 机器人走格子，要求生成所有路线，而不只是单纯的总方法数。改下返回的结果和递归时的传参。1，扯天聊项目，问了一些key value pair和relational的performance比较。
2，给N个string，找出他们各自的unique prefix，比如abc, bac, xyz, aac的unique prefix就是ab, b, x, aa，也就是最短的能idenfity原string的prefix。
Design加算法混合，输入是N个日期和每个日期上发生的两种交易的交易量，交易量可以为0，然后要求存储交易量历史，同时输出所有两种交易量都不为0的日期的交易历史。难度不大，做好各种边界检查就好，要求不能存0交易量的相关数据。还要求最简化代码。
1. find missing number.
给一个sorted array, 这个array的size是N-K
原本这个array应该是有从1-N，N个数 但是miss了K个
请找出这miss的K个数
给一个sorted array, 这个array的size是N-K
原本这个array应该是有从1-N，N个数 但是miss了K个
请找出这miss的K个数
INPUT
N = 10
array = [3 4 6 7 9 10]
N = 10
array = [3 4 6 7 9 10]
OUTPUT
[1 2 8]
[1 2 8]
2. 2. 区间重叠总数
给一堆区间
给N个query，每个query是一个数k
返回包含k的区间的个数
[1, 3] [2, 5] [4, 8]
给一堆区间
给N个query，每个query是一个数k
返回包含k的区间的个数
[1, 3] [2, 5] [4, 8]
OUTPUT
1 -> 1
2 -> 2
9 -> 0
1 -> 1
2 -> 2
9 -> 0
第三轮白人， 设计一个monitor system，主要用来监控server群以及想前端的server传监控的更新数据。。上来给出了基本函数框架，然后开始各种发散。。我讲到了bottleneck是http request，解决办法是多线程，讲了线程数的tradeoff，还有如何实现函数的thread-safe，估算了大概的时间，还有一些关于communication的小问题。。问的问题基本都答出来了。。。最后看时间差不多就停了，走的时候还捋了一遍想聊的topic，说主要的已经聊到了
1 面试官一进来先问lz，认为写code最重要是什么，lz说是correctness，其次是space time 复杂度。他不满意，说假设你写的所有code写的都是正确的，你想写什么code，然后lz扯了扯自己的research里写的code，感觉他也没什么兴趣就开始出题。总之一上来就让lz感觉怪怪的，沟通的不好。
设计纸牌游戏，完整设计一个类，实现deck功能，还有几个其他功能。中间不停打断，问oo design的很多考虑。lz从来没准备过design的问题，所以第一面结束就知道已经gg了。
设计纸牌游戏，完整设计一个类，实现deck功能，还有几个其他功能。中间不停打断，问oo design的很多考虑。lz从来没准备过design的问题，所以第一面结束就知道已经gg了。
2 实现一个改进的double linkedlist数据结构，第i个node存2^i 个数据。要求实现添加元素和get第i个元素两个功能，其中add要求O(1), get(int index)要求worst(log n), average O(1)。面试官拿了一台笔记本，坐在我旁边看我敲。一开始写的复杂度不满足要求，给hint之后才写出来。
3 streaming setting下，要求uniform random 输出一个之前读入过的data point，要求constant space。然后follow up 输出k个uniform random数据。这一面答的比较快，也还算聊得来，然后还聊了下他们组做的项目，还蛮有意思。
24，
lintcode word_search 2 with trie
lintcode word_search 2 with trie
给你一个byte数组 判断是不是一串合理的utf-8编码
实现vlist的数据结构 这个结构内部实现是一系列数组 长度分别为1 2 4 8… 连续存储 前一个满了才能开辟下一个数组的空间
要求实现两个函数& T.
void append(T element) 复杂度O(1)
T getByIndex(int index) 复杂度O(logn)
要求实现两个函数& T.
void append(T element) 复杂度O(1)
T getByIndex(int index) 复杂度O(logn)
第三轮：
第一题 leetcode原题 set matrix zero
第二题 给你一个二位数组 每一行从左到右递增排列 每一列从上往下递增排列 要搜某个数存不存在
第一题 leetcode原题 set matrix zero
第二题 给你一个二位数组 每一行从左到右递增排列 每一列从上往下递增排列 要搜某个数存不存在
第四轮
给你一台机器作为administrator 查看一系列services是否工作正常 有没有down 怎么设计？
Follow up: 加了一些限制 administrator有100个线程 每个线程只能发一个阻塞的request给一个service 只能调用getstatus函数 每个request如果正常返回 需要100ms 如果超时就是3min 有5000个service 分布在一些主机上 不允许修改主机内容
继续follow up。如果要在1min内得到结果 并且已知有200个service挂了 怎么办
给你一台机器作为administrator 查看一系列services是否工作正常 有没有down 怎么设计？
Follow up: 加了一些限制 administrator有100个线程 每个线程只能发一个阻塞的request给一个service 只能调用getstatus函数 每个request如果正常返回 需要100ms 如果超时就是3min 有5000个service 分布在一些主机上 不允许修改主机内容
继续follow up。如果要在1min内得到结果 并且已知有200个service挂了 怎么办
Given a vector, two items are considered duplicates if their indexes are within k. Find whether there are duplicates..
Given two nodes in a tree, find the least common ancestor.
Given two nodes in a tree, find the least common ancestor.
onsite
Given an array, return the end index and difference of longest arithmetic sequence (no need to be consecutive).
Given a list of string, return the list of prefix that can uniquely define each string.
Given a string, return the number of characters you need to put at the end of the string in order for the string to be a palindrome.
Debug a program written in Java. The program is used to implement a smart way of lexicographical comparator. Problem: wrong output and slow run time.
Given a list of weights (each one associated with a label), generate a random label based on the weight. What if the label needs to be generated many times? How to speed up?
Given an array, return the end index and difference of longest arithmetic sequence (no need to be consecutive).
Given a list of string, return the list of prefix that can uniquely define each string.
Given a string, return the number of characters you need to put at the end of the string in order for the string to be a palindrome.
Debug a program written in Java. The program is used to implement a smart way of lexicographical comparator. Problem: wrong output and slow run time.
Given a list of weights (each one associated with a label), generate a random label based on the weight. What if the label needs to be generated many times? How to speed up?
27,
第一题是majority element,网上有个moore algorithm， 可以去搜一下看看
第二题是word search
第三题是股票问题。
http://shibaili.blogspot.com/2015/10/palantir-interview-question-1.html第一题是majority element,网上有个moore algorithm， 可以去搜一下看看
第二题是word search
第三题是股票问题。
Read full article from Palantir面经 | shawnlincoding
