上周一个老客户高高兴兴的拿到了paypal的面试，虽然临近新年老师团队的日程也非常紧张，但是石老师必须要让同学过一个好新年，全力出击！
paypal总共有三场面试，同学分2天完成，csoahelp团队全程陪跑关注，全力备战。
很快第一场面试就开始了，和石老师一起看看面试题先
第一题
Given an arbitrary string, give me a mapping between each unique character in that string and the number of times that character occurs.
Example
Given the string:
"aabbbbbcDDD"
This is the expected mapping:
a => 2
b => 5
c => 1
D => 3给一个任意字符串，统计每个字符出现的次数，返回一个 mapping。
送分题感觉只要学过技术数据结构和算法的同学不可能在这题翻车，大家就当热身吧。这题同学甚至没有抄我们的解答，非常自信的自己完成了。很多同学也会有这样的问题：假如题目我自己也会找你们帮忙不是亏了？其实我们大部分情况是作为兜底保底的，有我们在背后陪伴会无形增加你的自信心，很多自己能答90分的也会选择找我们上个保险保证拿到100分，就是因为现在就业市场竞争过于激烈了。大家认为这样伤保险划算吗？
第二题开始初见端倪，开始了长篇大论
第二题
Now that we have an understanding of the relative frequency of each character, we’re going to build a data structure that will help us give us that shorter encoding we talked about.
As part of this step, we’re going to convert the map in the first step into a binary tree.
We’re going to think about every character and count in the map from step 1 as a node in the tree.
For example, the letter "c" with a count of 1 will be represented by a node with a character of "c" and a count of 1.
The way we build the tree is we take the node with the lowest count as the starting point of our tree.
(c, 1)
We then take the node with the next lowest count and add it as a sibling to this node.
The way we make it a sibling is by creating a parent node for both of these children.
The count of the parent node should be the sum of its children’s counts.
The character of the parent node doesn’t matter. It can be null or an arbitrary value.
Our tree now looks like this:
(#, 3)
/ \
(a, 2) (c, 1)
We take the next node with the lowest count and add it as a sibling of this tree.
As with the previous step, make it a sibling by creating a parent whose count is the sum of its children’s.
(#, 6)
/ \
(D, 3) (#, 3)
/ \
(a, 2) (c, 1)
Continue in this way until you’ve handled all the entries in your map.
At the end of the process, give me a pointer to the root of that tree.
The final tree should look like this:
(#, 11)
/ \
(b, 5) (#, 6)
/ \
(D, 3) (#, 3)
/ \
(a, 2) (c, 1)数据结构题。太长懒得翻译了，原文一字不改大家自己看，原来题目一的频率表只是一个入参。构建规则很像 Huffman Tree，也许是为了防止有候选人不知道，paypal的面试官这里把构建细节写的非常详细
这部分的核心就是用 min-heap 反复合并频率最小的两个节点，构建一棵“频率越高离根越近”的二叉树，最后返回 root。我们写了大量注释和代码让候选人同学完整复述，复述的过程中明显同学有些紧张，辅助老师很温柔的让他不要紧张，念和抄的时候一定要自信，这样才能走到最后。
第二题答完，发现paypal的面试题真的套娃，一层接一层，第三题又和第二题的树有关。
第三题
The tree we just constructed is going to help us determine a new encoding for each character.
The encoding for each character is given by the path to the node that holds that character.
We’re going to describe the path as follows:
- Start at the root and keep track of a path
- When you go left, add a
0to your path - When you go right, add a
1to your path - If you hit a leaf node, the path you’ve kept track of becomes the encoding for that character
Given the tree we just built:
(#, 11)
/ \
(b, 5) (#, 6)
/ \
(D, 3) (#, 3)
/ \
(a, 2) (c, 1)
To reach the character b from the root, you go left (0) once.
The encoding for b is:
0
To reach the character a from the root, you go right (1), right (1), and left (0).
The encoding for a is:
110
Traverse the tree and build a map between each character and its new encoding.
For now, don’t worry about making your encoding binary.
A simple string representation will suffice.
We should expect this encoding for the characters in our example string:
b => 0
D => 10
a => 110
c => 111候选人同学先假装阅读题目，超长的文本给了我们拼命告诉写提示的时间段。我们特意提醒候选人同学不要紧跟着我们的提示来念，等我们写了3-4行之后再念。如果紧追着我们的注释念可能会导致语速停顿的比较奇怪。
候选人同学非常给力的等到了我们写了大片注释后才开始与面试官沟通，等待的过程中假装思考默默的年了一下题目给我们辅助老师争取了宝贵的时间。
然后他开始答“这一步其实就是一次树的遍历，我需要在遍历过程中记录从 root 到当前节点的路径.....”
“当我走到叶子节点时，把当前路径存到 map 里....”
当复述完我们写的思路之后，面试官又突击追问了一个follow up "如果树只有一个节点怎么办？“，候选人这个时候没有慌，先假装思考等待我们输出，看到新增的注释提示后他念了出来
“如果只有一个字符，我会特殊处理，给它一个固定编码，比如
0。”
面试官整体非常满意。
paypal的这套面试题从part1开始非常简单，到后面不停套娃，part1的结果是part2的入参，part2的结果是part3的入参。层层相扣非常精妙，这种原创题建议准备paypal面试的同学收藏备用，相信是个非常高频的题。
加石老师微信，还有更多未公开题库可以免费分享哦。如果你也需要付费服务比如面试辅助，代面试，模拟面试，简历修改，代投简历等等服务均可以加我微信联系我。
