1，
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
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的相关问题
4,
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
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
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，算法课作业
6，
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
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 处理的不太好，没有给出最优解
9,
店面：
第一轮问的是merge interval
第二轮问的是lru cache，还有一道题是说给定一个数组，这个数组有一个特性是，每一个元素距离其排序后的位置，最多差k个距离，然后叫我将这个数组排序，要求时间复杂度好于nlogn.
第一题，主题是coding，check一系列byte是不是合法的utf8编码。utf8的定义大家可以去网上搜一下，具体我记不太清了。这轮主要是看代码是否简介清晰，无奈写出了一个bug。情况是这样，有一种byte组合是永远不会出现在utf8的编码里的，我忘记考虑了这种情况，结果就是跪在这个上面。
第二题，考algorithm，给一个数组，要求输出一个数组，第一个是原数组第一个的中位数（就是原数组的第一个），第二个是原数组第一个到第二个的中位数，第三个是原数组第一个到第三个的中位数，以此类推。我一开始说用一个最大堆和一个最小堆来做，然后又要求constant space来做。
第三题，考system design，题目是设计一个distributed 的key-value store.
10,
1. 上来自我介绍
2. 挑简历里一个项目聊.
3. 第一道是reverse list。当时就傻眼了，我还问了一句，有没有环
4. 写一个可以运行的贪吃蛇backend。以前只听同学说过面google设计贪吃蛇，写还是第一次。士气大落，在动手前浪费了不少时间。虽然在提示下写出了大部分但是还是没有写完，如果一拿到就开始动手其实并不难。
snake class
判断蛇的生死，存储蛇的位置，移动蛇的方法
board class
food的生成
11,
题目是给定一个矩阵，里面有0和非0值. 求最大的连通的非0元素的加和。用dfs做吧，要记得update访问过的元素为0
follow 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) {}.
13,
1. HR的电话，问问毕业时间，简述职位内容等例行公事。最后问了个single number的简单题，口答就行了
2. 第一次电面， 面试官是个年级比楼主小的本科生，简单问问简历，介绍实习经历。然后问了个设计题，设计分布式拍卖系统，楼主给了一个client-server的解和一个p2p的解，然后问了个简单的文本里找字典里的词的题(口答)，楼主给了个hashset，然后follow-up是anagram怎么解。
（面试官表示满意，move on）
3. 第二次电面，面试官是一位phd，简单寒暄过后直入主题：第一道经典的无限输入流找中位数，第二道无限输入流找平均值，第三道无限输入流找mode。中间夹杂着问了溢出如何处理（转成字符串，或用链表，又问字符串和链表的优劣，存储位置不同）。前两道题楼主也是马上给出最优解就解了，最后一题卡了一下，面试官提示了一下也马上就搞定了，很快，总共35分钟。
（面试官表示满意，move on）
Onsite:
于是一个星期后就飞到了palo alto，酒店的环境很不错，接机司机是一位百人金发MM。第二天早上，楼主到了office，check in，然后上到三楼。当天总共大约有16位候选人左右（包括所有职位），大部分是面实习职位（Palantir把实习生也onsite了）。公司目测三哥极少，大部分是白人和亚裔(目测不少abc)。
一. 10点开始第一面。是位白人女面试官，寒暄过后是道设计题，mini-yelp。设计了存储的数据结构，然后问了2-D空间如何找最近的点，楼主给了个heap的解，面试官说可以用二分解。但这轮的主要还是面设计。最后问了如何测试mini-yelp，尤其是如何在分布式环境下测试min-yelp。（从测试case等）.
二. 第二位面试官，这就是此次onsite之行的缺憾了。在Palantir遇到的所有的面试官都很nice很有耐心，除了这位。典型的技术宅，穿着人字拖进来了坐下后很显然没睡醒，一遍哈欠一遍说：我想..想啊，给你出个什么..么题..（无语）。然后楼主等了一会，这位大爷终于想出了个DAG的题，然后楼主clarify了一下约束条件（面试官显然没睡醒，模模糊糊地答了一下），原来就是detect cycle。楼主马上用DFS写好了，可是这时问题来了，面试官看着白板上的DFS说：你的DFS会返回”false true”。楼主以为写出了bug，于是盯着这短短几行DFS看了又看，实在是找不出bug了，说：hmm..let me see… hmm … this looks good. 面试官欲言又止憋着什么似的，说：这..这个DFS是没问题的，但..但..在一些情况下会”false true”，你能不能给出那些情况？（我勒个去，这false true是面试官您说的喂，你应该给出case才对，我实在想不出DFS为啥不能detect cycle）然后面试官从坐着的抠脚丫子（他是真的在抠脚丫子）的状态站起来，在白板上画了个图，说：这..这种情况。哦好吧，原来是一次DFS不能cover所有点，然后面试官又说：你能不能..hmm..这个是O(n)的啊，能不能小于O(n)？于是楼主开始思考如何小于O(n)的情况下detect cycle（没想出来，楼主以为是拓扑排序，或者其他算法）…无奈时间最后只剩下五分钟时候楼主似乎明白了面试官的意图。但时间已不够，问了两个问题草草结束了。
三. 第三位面试官貌似是位ABC，非常有礼貌而且干净整洁，和之前那位“技术宅”形成强烈反差。寒暄过后先是讲了一个project，楼主在白板上画出来后面试官表示很满意，中间没有涂改，面试官表示很满意，交流也很顺畅。然后开始做题，也都是给出题，楼主马上给了最优解然后写出来，面试官表示满意。做了好几题，面试官表示很不错直到时间快不够了。分别是dict找word，anagram，edit distance 1, edit distance，然后到general。面试官表示很有兴趣继续讨论下去，但可惜时间到了，楼主问了个问题就结束了。
. visit 1point3acres.com for more.
然后午饭后看了个demo，等了一会楼主被hr叫走，给了个T恤说面试结束了。楼主知道，他家一般面不到4-5轮就挂了。
整体的感觉是：题目并不难，跟面试官的交流很重要，要注意code的细节，领会面试官的意图。尤其是当思维发散太多的时候要及时止住。但是如果面试官“没睡醒”或者一开始就不耐烦的话就很麻烦了，所以运气在面试中也是很重要的。
总之这是一次意外的onsite：楼主没想到能onsite。Onsite中又出了意外，最后还是不幸挂了。把这次经历写一写，希望对其他人有帮助吧。
14,
Palantir：
第一轮OA是Magic Box的题，地里曾经有过。第二轮电面是个很nice的白人小哥，先问了merge two sorted list， 又问了merge K sorted list，然后说让用MinHeap，也就是Java 里面的priorityQueue 来优化。由于对heap不熟，卡住了一小会儿，在小哥不断的提示下才想出来。然后又问了改进前后的时间和空间复杂度。不知道能不能过，不过听说他家bar很高。
15,
recruiter phone screen，会问你为什么选Palantir，我说完了以后他说注意他们有philanthropy engineering，帮助救灾等等，给我感觉如果提到这个会有帮助，提升“culture fit”
coding challenge，跟网上说的一样，flip columns那个题，搜一下就知道啦
phone interview，跟网上说的一样，find duplicates, find duplicates within distance k, find fuzzy duplicates within distance k… 顺利做完后onsite
onsite，我不知道是full stack简单还是怎么，题都比较简单
running median.
min stack
get top k numbers in max heap
follow up也都不难，做得很顺利，做完他们都说good, excellent, perfect之类的
在电脑上coding的问题，map相关，不是算法题，是多线程有关的，但个人感觉不用担心，按时写完即可
UI设计题，设计一个网页上的file explorer，这个很难自我评估做得好不好，反正他都是说上面那三个词-google
泛泛地讨论如何设计一个twitter api，怎么考虑性能之类的，没有特别具体深入的系统设计的题
最后跟一个manager泛泛地聊天，还问了我小时候是怎么开始对计算机感兴趣的。。。
.
面完感觉没什么问题，尤其是technical部分，我本来准备好了手写strstr三大算法，结果没出现-google 1point3acres
两天后打电话说不给offer，我说有什么feedback，他说algorithm部分还可以做得更好。。。表示不是很理解
所以，我个人的感觉是传说中的bar高，并不是technical方面的，更多的是culture，聊天时他们说他们工作时间比一般公司长，工资并不成比例增长，因为员工都爱这个工作，有使命感等等，一个组一般有人崩溃到quit才会招新人进来补充人手，而且没有分级title，大家都是software engineer，极端flat。可能有同学会喜欢吧，但我并没有发现他们的产品有什么特别神奇/有趣的地方，而且说员工有使命感什么的，只能说我culture上确实不太fit可能被发现了
16，
Tower of Hanoi
17,
leetcode
rotate array
18,
clone graph DFS and BFS
19,
第一轮，求一个string list的每个string对应的unique prefix，返回也是一个list。我用Trie解决，建Trie、查找写了半个大黑板。面试官觉得很好。
第二轮，简单来说就是求2个数组的交集，然后follow up，变形的奇奇怪怪，现在都不知道他要干什么，很麻烦，弄了半天没怎么弄懂，然后时间到了。
第三轮，求数组都最长等差数列（要求连续），follow up 可以不连续，这里答得不太好，直接暴力做了
第四轮，求一些区间的相交次数最多的任意一点。因为一开始是区间是int类型，我直接开了个数组，每读取一个区间就＋＋，然后求数组最大的点就行了。follow up区间是float类型，之前方法明显不行，后来先按区间的start排序，然后每次比较end，好麻烦感觉，弄了半天没符合他的要求。
电面（45分钟一轮，第二次是加面，一般是一面）
一：
1，FizzBuzz，考基本功，感谢白人小帅哥。
2，Inorder Traversal, iterative和recursive。
3，Inorder successor, 元素可能不在tree内。
二：
1，Valid BST, 要求至少两种办法。用inorder traversal和min-max法解决了。
2，MaxPath，找出一个树上最长的任意点到任意点的路径，GeekforGeek有原题。
Onsite：（1小时一轮，第一轮因为我接着BlackRock面试晚了半小时，所以缩短了）
一：
1，N个unsorted数，找出最长的连续等差序列。暴搜外加几个全局统计变量就可以。
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。一个办法是一个字母一个字母扫所有string，然后建立hashmap，扫完一次，map里为1的写进结果里，然后用递归去一路扫后面。另外一个办法是用trie，把字符串转90度，然后每个重复字母下面都会延伸出下一层的child，一层层延伸tree，不能延伸的时候就把这条path写到结果里去。
三：:
1. 先是isPalindrome，轻松撸掉。
2. 然后findPalindromeRemainder，找到最短的“拼在一个非palindrome字符串后面，使它变成palindrome的”额外字符串，比如baba就是拼个a在后面。做一个原字符串suffix树和倒转过来的字符串prefix树，然后两个树同时遍历，到第一个不同的元素，记下index，把原字符串从0到index的倒着append到原字符串后面就可以了。
3. 机器人走格子，要求生成所有路线，而不只是单纯的总方法数。改下返回的结果和递归时的传参。
四：
Design加算法混合，输入是N个日期和每个日期上发生的两种交易的交易量，交易量可以为0，然后要求存储交易量历史，同时输出所有两种交易量都不为0的日期的交易历史。难度不大，做好各种边界检查就好，要求不能存0交易量的相关数据。还要求最简化代码。
20,
1. find missing number.
给一个sorted array, 这个array的size是N-K
原本这个array应该是有从1-N，N个数 但是miss了K个
请找出这miss的K个数
INPUT
N = 10
array = [3 4 6 7 9 10]
OUTPUT
[1 2 8]
followup
如果只miss了两个数呢？
http://www.geeksforgeeks.org/find-the-missing-number/
2. 2. 区间重叠总数
给一堆区间
给N个query，每个query是一个数k
返回包含k的区间的个数
[1, 3] [2, 5] [4, 8]
OUTPUT
1 -> 1
2 -> 2
9 -> 0
3.还有一道题跟trie有关，但是不记得了。大家自行熟悉一下trie的insert和find的实现吧
21,
第一轮abc，主要是让我设计一个拱猪纸牌游戏。。。想了一下就一口气写到了这轮结束，主要就是把card，suit，deck，player，game全部都抽象出了应有的类。。然后实现了关键函数，面试官应该是很满意的。。。这轮应该是做的最好的一轮了
第二轮白人，上来问我做过的那道一个乱序数组每个数的位置距离他应有的位置差不超过k，如何更快的排序数组。。直接给出了minheap的解法。。表示同意。。。然后问我乱序数组找排序好的median, kselection, 讲了原理以及时间复杂度的best和worst，写了kselection的code，一遍bug free。。他表示还算满意。。。这轮一开始他带着电脑进来的，不知道是不是一开始打算让我在ide上面写，后面看我太菜了就改成直接在白板上面写了
第三轮白人， 设计一个monitor system，主要用来监控server群以及想前端的server传监控的更新数据。。上来给出了基本函数框架，然后开始各种发散。。我讲到了bottleneck是http request，解决办法是多线程，讲了线程数的tradeoff，还有如何实现函数的thread-safe，估算了大概的时间，还有一些关于communication的小问题。。问的问题基本都答出来了。。。最后看时间差不多就停了，走的时候还捋了一遍想聊的topic，说主要的已经聊到了
22，
running median
min stack
get top k numbers in max heap
follow up也都不难，做得很顺利，做完他们都说good, excellent, perfect之类的
在电脑上coding的问题，map相关，不是算法题，是多线程有关的，但个人感觉不用担心，按时写完即可
UI设计题，设计一个网页上的file explorer，这个很难自我评估做得好不好，反正他都是说上面那三个词
泛泛地讨论如何设计一个twitter api，怎么考虑性能之类的，没有特别具体深入的系统设计的题
23，
1 面试官一进来先问lz，认为写code最重要是什么，lz说是correctness，其次是space time 复杂度。他不满意，说假设你写的所有code写的都是正确的，你想写什么code，然后lz扯了扯自己的research里写的code，感觉他也没什么兴趣就开始出题。总之一上来就让lz感觉怪怪的，沟通的不好。
设计纸牌游戏，完整设计一个类，实现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
25,
第一轮：
给你一个byte数组 判断是不是一串合理的utf-8编码
第二轮：
实现vlist的数据结构 这个结构内部实现是一系列数组 长度分别为1 2 4 8… 连续存储 前一个满了才能开辟下一个数组的空间
要求实现两个函数& T.
void append(T element) 复杂度O(1)
T getByIndex(int index) 复杂度O(logn)
第三轮：
第一题 leetcode原题 set matrix zero
第二题 给你一个二位数组 每一行从左到右递增排列 每一列从上往下递增排列 要搜某个数存不存在
第四轮
给你一台机器作为administrator 查看一系列services是否工作正常 有没有down 怎么设计？
Follow up: 加了一些限制 administrator有100个线程 每个线程只能发一个阻塞的request给一个service 只能调用getstatus函数 每个request如果正常返回 需要100ms 如果超时就是3min 有5000个service 分布在一些主机上 不允许修改主机内容
继续follow up。如果要在1min内得到结果 并且已知有200个service挂了 怎么办
26
电面.
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?
27,
第一题是majority element,网上有个moore algorithm， 可以去搜一下看看
第二题是word search
第三题是股票问题。
shawnlincoding 