@smilence 2016-04-10T01:57:02.000000Z 字数 6851 阅读 2101

码农求职套路谈第二讲 script

标题

youtube课程讲义

Homework:

Cracking the Coding Interview 这本书的文字内容 (p60-p81,知识讲解，hints，advanced topics)

N nodes, each node consists of a couple fields and methods. These are:

int id; //every node has an ID. All of these IDs are sequential, and begin with 0. 
int val; //every node has a value  
int max; //max = N. Every node knows how many nodes are in the system.  
void send(int idTo, int payload);  
int recv(int idFrom);

Write a single piece of code which runs on every node simultaneously, such that when it is finished running every node in the system knows the sum of the values of all the nodes in the system.( Ebay interview ) https://www.careercup.com/question?id=19695693

首先应该从问题的特征出发去分析：
每台机器上运行的代码都完全一致，但每台机器并不一定是对等的；
机器之间有互相连接的关系；
每台机器都同时发送和接收

1.机器之间是怎么样的连接关系，也就是怎么样的数据结构？
2.连接关系之间的方向性，也就是发送给谁，向谁接收？

解法：
a. 两两互相传递
b. 假定一台为SERVER 时间复杂度是否可能比O(n)更好呢？能否从机器之间并行计算的角度出发，避免不平衡的计算 (load balance), 抽象到数据结构就是用具备D&C特性的tree，通过并行计算subproblem来更快的解决problem

Binary Tree 天生具有D&C的特性，能够很方便地掌握子树的情况，并在整个数据结构中传递全局信息。

int getSum() {    //as member function of the node
    int parent = ( id - 1)/2;
    int left = 2*id + 1;
    int right = 2*id + 2;
    // DFS
    int subsum = val;
    if( right < max ) subsum += recv(right);
    if( left < max ) subsum += recv(left);
    if(parent >= 0 ) send( parent, subsum);
    int sum = 0;
    if(parent >= 0) sum = recv( parent);
    else sum = subsum;
    send( left, sum);
    send(right, sum );
    return sum;
}

如何计算Backtracking的时间复杂度？

Backtracking就是
典型的例子是phone number -> alphabet combinations
假定每次有 $x$ 种选择，有 $y$ 个step，那么就是 $x^y$ ( $x$ to $y_{th}$ power)

减枝后的backtracking问题：八皇后

$TimeComplexity = \quad\prod_{i=1}^n f(i) \quad$

如何拿到面试机会？

简历

--简历的作用
--只需要考虑自己能改变的东西

简历写什么？

找一个好看的模板

应届生优先
在工业界有经验优先，最好是有声望的公司或者热门startup
有趣的side project，而不是class projects
参加过hackathon或者竞赛，显示对coding的热情
名校，高GPA加分
CS相关社团加分
CS课程TA加分
有Github
Diversity 的考量

对于优势，尽可能地cover：

以上提及的这些
英文女名
本地地址
绿卡/公民

对于劣势，尽可能地模糊：

低GPA
时间上的gap
需要Visa Sponsorship

什么不要写？自己也觉得水的东西，不要写；不相关的经历，通通不要写（滥竽充数 or 背景不相干的印象）

简历的内容描述原则

核心之核心是体现解决问题的能力
过去时动词开头，具体讲做了什么事情，但做成什么并不重要，重要在于为什么这件事你做到什么别人做不到的，或者比别人基础改进的，或者比传统办法改进的，哪怕只是。
"完成了哪些component，有什么改进，使用了什么技能，（做成了件什么事情）”
少用形容词（没有人会说自己不好），多用事实： worked across all the stacks, from UI development with javascript to php server deployment and mySQL database
没实现的想法也可以写上去，趁这个机会把以前的project拿出来看一下，看看现在有什么想法，还是体现能力（e.g. 化妆品网站）

如何拿到面试机会

不管 job description，可以利用linkedin投一些local小公司
能内推的就内推
内推的人可以帮你做的事情很大程度上取决于你
- 没有消息的时候，多push一下
- 内推人可以帮你push hr
- 内推词要主动提供，马上你就跟别人区别开了
- 内推词，和简历完全不同，要很强的形容词
  - "our recruiting system is broken if we dont hire him"
  - "I would be very surprised if we don't give him an interview"

第二讲 Array, String 与 Hashtable

从结构形式来说，这三个是一种东西。array是特殊的hashtable，key是连续的index，例如当key是char的时候就可以一一对应。比如有一些字符，我们需要做一些预处理来检索一些信息（每个字符出现的数量）。我们应该用hashtable还是array呢？（分布是密集还是稀疏）

Open hashing & Closed hashing (略）
特别地，Hash table还可以用Balanced BST来实现，如std::map, lookup的时间由 $O(1)$ 增长为 $O(log(n))$ ，但可能节省space cost ,且可以按照key的值有序输出pairs。(CtCI p89)
使用hashtable时，key没有预设hash function情况下的语言细节：

对于C++，
map<Key,Val,key_comp> table ，对于严格弱序判断的不同定义，可以通过重载<操作符或者定义functor class实现。
注意对于map无需重载==运算符，因为 A==B 等效于 !(A<B)&&!(B<A)。

对于unordered_map<Key,Val>则更加复杂，需要定义：
(1) A hash function, 用于确定Index即hash值；(2) 重载==操作符，用于区分hash值相同的不同key。
详见：http://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key

对于JAVA，需要对HashMap重定义equals()与hashCode()。

e.g 1.4 Find a line which passes the most number of points. ( CtCI 7.6 )
string的语言细节 ( Java: stringbuilder与String )
reverse string or array （经常用到的piece of code）
(1) 用头尾两个指针，相向遍历，swap元素（不适用于数据流）
(2) 顺序遍历元素，push入stack，再依次pop。(或者递归)
String matching (CtCI page 636)
将每一个匹配子串映射为一个hash值。例如，将子串看做一个多进制数，计算它的值与目标字符串的hash值比较，如果相同，再比较两个字符串是否相同。顺序shift过程中，可以增量计算hash值（扣除最高位，增加最低位）。因此能在average case下做到O(m+n)。
2-D array, 总是推荐用collection而不是C-style

模式识别

1.统计一个元素集中元素出现的次数，用Hash Table，即std::unordered_map或std::map。只统计元素出现与否的问题，可以用bitvector即bitset，二进制数来记录。

e.g. 1 Implement an algorithm to determine if a string has all unique characters. (也可以用排序)
e.g. 2 Write a method to decide if one string is a permutation of the other. (也可以用sorting，不仅把相等的放在一起，更会有序地把相近地放到一起）
e.g. 3 Given a newspaper and message as two strings, check if the message can be composed using letters in the newspaper.(Google interview)
（只需要找到match_cnt == count(message)就可以了）

2. 处理vector，array或string问题的几点细节：

a.数组或string内前驱subproblem推出problem的问题，总是以 $[0,i]$ 为范围，检索前驱节点 $j$ 求解当前节点。如果只是检索特定的value，则可以用将当前value作为key建立hash table（value取决于你需要什么前驱子问题的信息），使得后驱节点每次检索的复杂度降低到 $O(1)$ 。实际上类似于dynamic programming的思维方式，记录前驱节点的信息，用空间换取重新扫描需要的时间。

e.g.1 Given an array of integers, find two numbers such that they add up to a specific number.(Leetcode: 2Sum) （也可以用排序）

sum = 6
[1, 3, 5, 7, 6]

e.g.2 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. (Leetcode: Longest Consecutive Sequence)

Given [6, 4, 8, 1, 3, 2，7],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

一个好的习惯是walkthrough这个test case观察自己的思维过程。
1. 前驱子问题的解 + 当前节点这个增量 => 新的子问题的解
2. 需要什么前驱子问题的信息？上界和下界

struct Bound{
    int high;
    int low;
    Bound(int h = 0 , int l = 0){
        high = h;
        low = l;
    }
};
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        unordered_map<int,Bound> table;
        int local;
        int max_len = 0;
        for(int i = 0; i < num.size(); i++){
            if(table.count(num[i])) continue;
            local = num[i];
            int low = local, high = local;
            if(table.count(local-1))
                low = table[local-1].low;
            if(table.count(local+1))
                high = table[local+1].high;
            table[low].high = table[local].high = high; // 试一下如果第一条不赋值会怎么样 [1,2,0,1]
            table[high].low = table[local].low = low; // 再想一想，为什么我们只需要维护low和high这两条，而不用考虑这个范围内的value [1,2,3,4，,3]
            if(high - low + 1 > max_len)
                max_len = high - low + 1;
        }
        return max_len;
    }
};

b.求最值或总和的问题，总是可以在update的过程中不断记录更新，而不用再次遍历。
也是一种从subproblem -> problem, 通过记录前驱子问题的解，而不需要再次遍历（只不过它只需要记录一个前驱子问题就可以了），就像上一个问题我们不需要再把这些bound重新遍历一遍

c.处理两个不等长的数组或string，总是可以以while( aIndex < aSize && bIndex < bSize )作为结束条件，再处理可能剩下的元素。

e.g. 1 Merge two sorted arrays into a new array

d.对于要求in-place的删除或修改，可以用两个int变量分别记录新index与原index，观察：如果改动后size增大，则先resize(int)，再倒序赋值；反之，则先顺序赋值，再resize.

e.g. 1 Given input "Mr John Smith", output "Mr%20John%20Smith" (CtCI 1.4)
e.g. 2 Given input "Mr%20John%20Smith" , output "Mr John Smith" (Facebook interview)
e.g. 3 Given two sorted arrays, merge B into A in sorted order. (CtCI 11.1, Leetcode: Merge Sorted Array)

3.对于简单修改长字符串的问题，通常可以顺序或倒序一次遍历，在O(n)内解决。对于分段处理的情况，则使用两个int变量记录段首、段尾Index来处理（slicing window）。可以利用C++ string类的 += 操作符来增量输出结果。

e.g.1 Given input -> "I have 36 books, 40 pens2."; output -> "I evah 36 skoob, 40 2snep."(Ebay interview)

用begin和end去标记window的初始和终止点，这两个总是核心变量；建议用 while(end < str.size()) 作为循环形式而不是 for loop 因为begin和end每次的增量未必是1.

e.g.4 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). (Leetcode: Minimum Window Substring)
*典型的将复杂问题划归为简单问题的思维过程：newspaper -> message 问题
Solution: http://paste.ofcode.org/auYff2uez54SBCzYetA6ik

4.对于处理array或string的问题，如果要求 constant space 且允许修改输入，则总是可以尝试排序后再操作（Sorting 或建立hash table，本质上都是一种分类的过程，将同类元素归并到一起）。

e.g.1 Given an array of integers, find two numbers such that they add up to a specific number.(Leetcode: 2Sum)
e.g.2 Find all unique triplets in the array which gives the sum of zero.(Leetcode: 3Sum)
e.g.3 Remove duplicates from a vector of int.

6.需要用数字或者bitset来映射/hash的情境， 可以利用进制数的正交性，即：数字的高位和低位是互相正交、独立的。或者反过来说，一个数用m进制来表示，只有唯一一种可能。

e.g. 1 Design a hash function that is suitable for words in a dictionary.(EPI: 12.1)

hash对象的特征是什么? 1. word不会很长 2.每一位的可能性非常有限且离散

e.g. 2 A hash function for the state of a chess game.(EPI: 12.2)

常识：对于一次transition，能够简单地转换hash ( $1+2*6 = 13$ ， $13^{64}$ )

e.g. 3 Implement a method rand7() given rand5().(CtCI:17.11) (课后思考)

码农求职套路谈 第二讲 script

标题

如何拿到面试机会？

简历

第二讲 Array, String 与 Hashtable

模式识别

内容目录

码农求职套路谈第二讲 script