6 digits palindrome number

设计百货大楼

有不同顾客，不同department有不同employee 有商品

硬币问题

给几个面值的硬币 给几个target找最小组合

用最小硬币 dp CC150 后两张内容

在美国改善办公室人际的小招

FROM MITBBS

最近好像种族歧视贴很多啊。我自己的经历，觉得多数情况下华人感到的种族歧视其实
是不能与同事顺畅交流造成的，归根结底是人际问题。在美国抱怨种族歧视的回国多数
会抱怨社会黑暗，在哪也处不好。
好了，废话少说，总结一下办公室人际小招:

1， 干好本职工作。办公室最讨厌的人就是不出力搞破坏让人擦屁股的人了。自己份内
的事做好，信息透明，做什么进程如何让大家看清楚。对上级要想到做到上级想到的，
也要想到做到上级想不到但是喜闻乐见的。做个报告弄个总结条理清楚简洁明了1234，
长email先上summary后上细节。

2， 对下级己所不欲勿施于人，不到不得已别老下午4、5点甩工作给人。对同级特别是
竞争关系同级主动合作，而且公开在会议和email里帮助其邀功，比如“要不是John昨
天熬夜写这个brief，我们不可能赢得今天客户的认可。”多数人都是投桃报李的。而
且在一个地方久了，你当年的同级可能变成你的下属，也可能变成你的小头头。不要以
为夸了同事领导就会把功劳归给别人，每个人的作品都有自己的特色，老板一眼就能看
出来谁干了什么，发现同事的贡献并认同是最廉价而有效的改善人际方式。

2， 争取和谁都面熟。我在国内工作的时候有个刚毕业的小姑娘敢在电梯里直接和大老
板拉家常，很快就升上去了（该姑娘相貌平平，身材矮胖，但是工作认真，爱表现，人
缘好，所以不是潜规则，而是会做事升上去的）。我在美国的以前的一个单位有个清洁
工见到所有new hire都会问对方姓名，而且一次记住，以后永远见面直呼你姓名。见过
他和大PA互相问候对方家人，而且都是知道对方妻子子女名字的。这个清洁工可能不会
变成白领，但是永远不会被解雇。在电梯里见到本单位其他部门的随便说几句天气球赛
，看见别人桌上有孩子照片的恭维一下别人孩子，聊聊自己孩子，很快就成了见面打招
呼的熟人了。

3，大家一起去喝咖啡看球赛喝小酒happy hour的不要不去。球赛，孩子，旅游啥的聊
一聊，别当壁花。

4，要好的同事过生日结婚生孩子的时候送点小礼物，或者出面组织其他同事写个贺卡
，凑钱买个蛋糕，办个shower，别老不参加，也别老被动参加。最不好相处的是中年女
同事，最好改善关系的也是中年女同事。小恩小惠最能收买中年女性的心。一张小卡片
一个小礼物一个大拥抱那效果是杠杠的。不管是对青年还是中年女同事，夸赞衣服鞋新
发型都不招人恨。没事聊几句最近的deal，关系马上就不一般了。如果你是男的，这些
不必做，做不好有骚扰嫌疑。凑份子的时候出钱即可。

5，和男同事那就是聊旅游，天气，新近电影和新闻也是好话题。中年男同事可以聊娃
，青年男同事最好相处，没有共同话题他也不会不友好。

6，如果同事刻意不友好，争取发现解决问题。有一次我发现小秘不开心，后来知道是
因为小秘加班回家出了车祸，加班是我间接造成的，我赶快送花送卡摆了她一桌子，并
且各种道歉，直到她给我一个拥抱。。也有过同事刻意下绊，后来发现是我曾无意在领
导面前让她过不去，所以以后多当领导和她的面说她的好话。

7， 如果有人恶意对待你而且不能感化，不要恶语反驳，但是绝不背黑锅。收集证据，
联系证人，告到HR，让他／她吃一壶。

8， 荣誉可以分享，坏了事责任必须分清楚。当然是自己的责任也别说谎，尽最大可能
改进并获得原谅。

9,   有不同意见对事不对人，理由要客观，语言要礼貌。一旦针对个人了你就会树敌，
然后花精力去斗争。实在是得不偿失的事情。永远不要提及对方种族宗教国籍性别年龄，
哪怕是夸奖对方也不能涉及这些方面。如果对方是不可化解的敌人，抓住对方提及你宗
族宗教年龄性别并且将其与你的工作表现联系起来的的证据（比如email里说“XX年纪大
了就是爱忘事”），一举告倒他。

10,  虚心接受批评。多数批评都是针对工作方式的。你的领导或者同事知道这样不成,
告诉你一个可行方式。如果你马上反驳找理由试图证明你是对的，人家以后不帮你了。
特别是新人，别把批评当坏事。举个例子，比如你刚入职, steve是你前辈，你提出A方
案，他要你做b方案。你如果坚持认为你的方案好,可以两个都做出来，最后让Steve选
一个。如果Steve选b，以后有你显示的时候，别对着干。如果选a，提交的时候不要弄
得我比你厉害那样子，而是当着领导和Steve，口头或email声明Steve给了你莫大帮助。
这样以后人家接着帮你。

11,主动寻求帮助，感激帮助者。新人入职几个月内要自己找几个导师，包括下属
，比如资深小秘。然后要资料要信息要模板求指点，态度诚恳，感恩戴德。有些对你
很有帮助的信息，可给可不给的，有时候你不要就不给了，有时候你不感激就不给
了，有时候怕你超过他就不给了。用了人家东西受了人家指点要在领导面前指出成果
有某人某人贡献和支持，要让人看到帮助你成功的好处。入职一年要形成自己的关系网。
开始给你的信息以后会一直给, 开始不给你的以后一直不给你。好开头很重要。

12,什么时候做什么事。新人多学习请教接受批评, 得到信任以后放手创新。当了管理层
学会立威。别一入职就大爷似的世界围你转，说你一下就种族歧视了。中年还在混
基层和领导对着干是很尴尬的。不肯当小媳妇怎么能熬成婆婆。

13, 不要人一走茶就凉。要好同事，当年直接领导，给你写reference的人逢年过节寄个
卡，写个email。举手之劳。现在background check追祖宗18代，你工作过的所有地方
基本都问到。一个差评永远找不到好工作。我对离职造成不高兴的老板一直过节快递水
果，先在妥妥的。

其他小tip:

1,  注意个人卫生。鞋和裤子可以连续穿，上衣必须天天换。

2，注意衣着。就是再casual的地方，男士别拖鞋运动裤的，女士别露背装海滩裙的。
还有啊，小姑娘和大妈们，别穿得太性感了！领口太低裙子太短的HR不会真来说的，但
是有人会觉得不舒服，直接关系到你和别人合作机会，内部调转机会和提升机会。

3， 别怕开口，到了一个地方以最快速度和所有你能见到的人说上话。开口越晚越尴尬。

4，看点新闻看点球赛啥的，没有时间看就看个网站标题，一天大事也知道个差不多了。

5，别老什么都联想到种族歧视。人一旦有了敌意别人都会感觉的而远离，于是你越发
觉得别人有敌意。

6, 一切努力要微小而持续。不然有怕马屁或者骚扰的嫌疑。礼物除非是凑份子买的，
不要超过$20。贺卡可以买很多，各种时机以自己的名义写几句暖心的话。其实人都寻找认同
感，你认同他，他就感激你。没有那么复杂的。

7, 差点忘了，可以带点心去办公室。我老公喜欢做饭，有时候做一锅西餐汤，或者烤
点点心我带去单位，很受欢迎的。吃了你的东西，总得和你说话把。另外自己采摘的水果也特
别受欢迎。

8, 有人说很难做到。其实和游泳开车一样，不会的如临大敌，会的如鱼得水。见面说
几句，开会夸几句，过节发个信能难到哪呢。其实大敌不是别人，是自己心里对与外族人交流的
恐惧和障碍。过了自己的关，很容易的。你以为别人费了多少心，其实对常年照顾别人
情绪的人，都是下意识的举动。别觉得在美国维护人际多费事，要是美国混不好，回国死
得更惨。你同学里混得一官半职有自己公司生意甚至高级打工的都比你会做人多了。这些
是从小需要学的技能，现在学也不晚。

先说到这里。以后想到什么再补充吧。

median-of-5-sorted-arrays

两个数相乘，不能用乘号，怎么做？

问个题，两个数相乘，不能用乘号，怎么做？ 把小的那个数转换成二进制，然后就可以多次自加翻倍 比如 a * 11, 11二进制是1011，则等于 a*8 + a*2 + a，每一项都是2的power 具体实现方式： 除了最高位的1以外，从次高位往低位，遇到1就翻倍后加自己，遇到0就只是翻倍 10: a * 2 101: (a * 2) * 2 + a 1011: ((a * 2) * 2 + a) * 2 + a 至于其中秘密，自己画画二进制和十进制的转换，大概就明白了，需要一点数学细胞

Book

1. Refactoring: Improving the Design of Existing Code

2. Design Patterns: Elements of Reusable Object-Oriented Software

3. Mary Shaw's Publication about: Software Architecture.

LINUX & UNIX

AWK CUT SED
IMSG

Design Facebook news feed API

http://www.buzzfeed.com/mattlynley/this-is-how-an-ad-gets-placed-in-your-facebook-news-feed#3ay4r5p

面经

1.

1. behavior + sort color
2-1. Binary number add
2-2. Matrix中有G,X,O三种字符，按照与G的距离改变O为最小距离的char（eg。‘1’，‘2’）
3. 设计news feed API
4. 根据dict设计数据结构，判断一个含有*的单词是否合法（*可以取代任意一个字符） trie树实现（常见题）

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Insert into a Cyclic Sorted List

RT

Saving a Binary Search Tree to a File

RT

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

思路：

1.

2.

3.

Serialization/Deserialization of a Binary Tree

RT

Convert Binary Search Tree (BST) to Sorted Doubly-Linked List

RT

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

代码如下：

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

思路：

树的遍历首先想到的一定是递归。

迭代版本的程序，需要引入prev指针和cur指针，cur指针指向栈顶节点。根据左右子节点入堆栈的不同方式有两种做法。

解法一是无论任何情况，总是先入右子节点后入左子节点。这样的话prev和cur的关系就分为：

1. prev->left == cur || prev->right == cur（从上往下，还未到达树的底部）
2. cur->left == prev（因为堆栈先入右子节点后入左子节点，这种情况意味着完成左子树，没有右子树）
3. cur->right == prev （完成右子树遍历）
4. any other （完成左子树，下一步遍历右子树）

解法二是有左子节点的时候只入左子节点，完成左子节点才入右子节点。这也是Leetcode官网上的答案（链接点这里）。这种方法的好处就是prev和cur的关系比较清晰：

1. 从上往下未达到树底部
2. 完成左子树
3. 完成右子树

解法三。根据解法一，优化之后，发现问题可以简化为考虑节点何时出栈何时入栈。于是我们有了解法三：

• 何时出栈？

1. 当前节点为叶子节点
2. 完成左子树遍历，没有右子树，隐含条件prev不为空。
3. 完成右子树遍历，隐含条件prev不为空。

• 何时入栈? 不出栈时，先入右子节点后入左子节点。

代码如下：

100 most frequently used string in 24 hours

Design a queue using array

多生产者多消费者设计

语录

这面试啊，有点像考厨师炒菜，这一道算法题，就像考得是一盘菜。先回答考官用啥数据结构，应该怎么做，写个代码我看看。就像问你用啥食材，怎么做，做好了端上来我尝尝。

这面试啊，特别是设计题，说白了就是BJ，让面试官爽了就成。

能读博客，写博客。就已经一只脚踏进湾区IT公司的大门了。

我常感叹到，学计算机的人是幸福的，因为在这个领域中有如此多的通俗易懂的经典好书，你需要做的只是坚持把它们一本一本读下去而已。学力学就没有这样的好事了，除了论文就是论文，满篇公式，晦涩坚深，真不是给人看的。

远离那些经常把你当垃圾桶给你负能量的人。记住，所谓朋友，交心不交心不是必要条件，能不能持续的鼓励，给你积极的影响，并且为你的进步感到由衷的开心才是朋友的必要条件。

变卖资产，最好还是能有所回收，否则太亏。实在没办法时必须速战速决0元抛售。

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?

Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

基础概念题

1. what is a hash table?
answer: Hash table is a data structure to implemented associated array, a structure that can map keys to values. A hash table uses a hash function to compute a index into an array of buckets or slots, from which the correct value could be found.

hashtable一般会问open addressing的实现
 注意一下rehash就好了
链表hash不是纯没技术含量么。。。
而且一般正经的库里也不用链表的实现

2. what is the difference between a pointer and a reference in c++?

answer: They are completely different type of concepts. A reference is an alias of a object. A pointer is an object contains address pointed to another object.

3. explain the various uses of keyword "static" in c++?

answer: In C++, there are 3 different use of keyword static: local static objects, static class data members and static class member functions.

A local static objects is a local objects whose value persist across calls to the function. It is initialized before the first time execution pass through the object's definition. The local static objects are not destroyed when function call ends. They are destroyed when program ends.

Static data members of a class exist outside any objects of its class type. They are not initialized by class' constructors. More over, we must initialize each static data member outside the class body(except const static data member). Once they are defined, they exist until program ends.

Static member functions are also not bound to any objects. They cannot access non-static data members of the class. They do not have "this" pointer, as a result, may not be declared as const. Both static data members and static member function can be accessed by a scope operator "::".

4. 一个空的class 的大小？
answer: 1 byte.

5. 有没有virtual constructor？
answer: no.

6. heap sort

heapsort两个部分 一个是由下而上的heapify，用来从数组生成heap

另一个是从heap顶端弄出来一个元素和结尾的元素交换，然后重新heapify

哦，后面这个操作较heapify

前面那个一般叫make heap

Example