码农求职套路谈 第三讲 script

youtube课程讲义

面试官访谈

A君 ( 欧洲人，senior engineer，general）

• 5mins talk is just to make them comfortable (might be 5% bonus, but never negative)
• Communication: How he gets there, explain (almost equally important)
• After all you are looking for a teammate
• Not only solve the problem, but I can tell he enjoyed solving the problem
• Running through the test case and identify the problem is a bonus
• if candidate seems to see the problem before, then I would do some follow ups(time complexities, etc) to see if they truly understand (if they do then it's completely fine because we all prepare), if still not much signal then it's hire with low confidence

T君 （印度人， senior engineer， general)

• Ask about culture fit, and it would be a red flag if it's negative (like no idea why they want Facebook, or not knowing fb at all), could change from hire to no hire
• Coding is most important ofc
• if it's onsite interview, bad communication is a red flag
• Candidate needs to know what he's doing, the approach
• I normally prepare two questions, and completing one is the bottom line
• If the candidate has seen the problem before, they dont necessarily have to approach from the naive solution, but they need to understand the underline deatils (time complexity, how they came up with that)
• If no signal from them then it's no hire with low confidence, other interviewers can calibrate

T君 （华人，senior engineer, general）

• 给出hire或no hire意见的基准是什么？
  
  • “这个和电面还是onsite有关系，onsite是决定要不要hire，而电面是说要不要筛选掉。电面就是筛选掉明显不符合hiring bar的。”
  • “无论是电面还是onsite的feedback，都需要填confidence level，比如虽然是倾向于hire，但意见不强烈，那就要看其他面试官了。
• 一般面试官是如何准备面试问题的？
  
  • “很多面试官会有自己熟练的这么几道题，我反正一直就那么几道，懒得换了，主要自己熟悉，别的自己不一定会做。一般就是一道简单，一道难题。也有人喜欢一道题目，然后很多follow-up，比较开放。”
• 哪些情况意味着“直接死亡”？
  
  • “简单题需要提示才能做出来, 死”
  • “bug很多，死”（FB标准，code要bug少，clean）
• 多提几种解法，会不会加分呢？
  
  • “如果是简单题，不会怎么加分，这道题做到完美是应该的，主要看第二题。”
• 如果感觉到是背的解法，怎么评估呢？
  
  • “背不背题目挺难判断，我如果感觉是背题目，那么会给他/她做变种题”
  • “比如一个最长子序列类型的问题，可以说连续或者不连续，很多变种，如果变种也做出来，那说明是能力而不是背题”
• “Behavior”那一轮也可能是Engineer来面试，有design，behavior，算法三类，有不同的培训。
• Decision是怎么决定的？
  
  • “一般面试官的feedback一天左右就提交了，至于通知是另外一回事”
  • “如果interviewer之间有强烈的分歧，就会争论。有些aggressive的会根据自己的理由说服别人”
  • “面试官之间的feedback互相不分享，提交之前看不到别人的“
  • “感觉啊细节啊挺重要，可能你有些地方犹犹豫豫的或者思路不清楚，有的面试官就特别介意”

杂项

ADT与Data Structure的区别：
ADT代表的是有某种功能，就像是个interface；而Data Structure是一种它的具体implementation。
e.g. Hashtable也可以用BST，只要实现lookup这种功能。用程序语言表示是两个concrete的class都implement了 ICanLookup 这个interface

Linked List 是 ADT还是Data Structure?
ADT 与具体实现以至于performance是无关的
List是ADT，无论是ArrayList还是LinkedList，都可以插入删除查找。
LinkedList插入删除很高效，但是有额外的overhead，根据index随机访问很低效。

说这些，用意在于思考：我为什么要选择这个Data Structure? 实际上首先是根据问题的特征选择ADT (a sequence of numbers)，其次是根据performance的requirement来选择 (比如是一个数据流，并且需要插入删除）。
e.g. LRU - 需要插入删除的数据串，并且需要快速地检索

Stack/Queue - ADT 最简单的判定方法是他们有不同的implementation
Heap 堆栈 - Data Structure, Priority Queue 是 ADT
Queue 就是priority queue的一个特例

interface IQueue extends IPriorityQueue (where getPriority() returns getInsertedOrder());
class Heap implements IPriorityQueue;

JAVA的Stack是stack的一个实现，就像C++的PriorityQueue一样。用意在于你不需要去关心内在的实现。

第三讲 Linked List

//Definition for singly-linked list.
struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

2.linked list的基本操作
对节点操作，无非就是修改next指针，如果是双向链表，还有prev指针。也决定了节点之间的相对位置，基本就是决定了这个linked list。

所有操作务必注意边界条件( curr == head，curr == tail 或 curr == NULL)
凡是修改list的操作，只需考虑 1. 谁的next指针会受到影响，则需要修正 （毕竟绝大多数的问题，next指针就是node唯一重要的member variable) 2.删除trash指针

void delNode(ListNode *prev){
    ListNode *curr = prev->next;
    prev->next = prev->next->next;
    delete curr;
}

3.Dummy Node

对于涉及head节点的操作，不如ListNode *dummy = new ListNode(0); dummy->next = head;；使针对head节点的处理与其他节点一致。最后返回dummy->next作为头指针即可。(dummy作为绝对参照物)

e.g. Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

4.Runner technique
对于寻找list某个特定位置的问题，不妨：ListNode *chaser = head, *runner = head; chaser与runner以不同速率遍历，runner到达tail时，返回chaser。(这个办法实际上是解决单向链表无法随机访问，所以只能用walk through来确定相对位置， 毕竟绝对位置用计数就可以了)

e.g.1 Find the middle point of the linked list

ListNode *midpoint( ListNode *head){
    ListNode *chaser = head, *runner = head;
    while( runner->next && runner->next->next ){
        chaser = chaser->next;
        runner = runner->next->next;
    }
    return chaser;
}

e.g.2 Find the kth to last element of a singly linked list.
e.g.3 Given a circular linked list, return the node at the beginning of the loop.
e.g.4 Given a list, rotate the list to the right by k places, where k is non-negative. (Leetcode: Rotate List) (拆分成两个问题：找到拆分点，拆分)

模式识别

1.在遍历Linked list时，注意每次循环内只对一个或一对节点进行题意中的操作。

e.g.Reverse the linked list and return the new head.

ListNode *reverse( ListNode *head ){
    //Of course, it can also be done by recursion/stack
    ListNode *prev = NULL;
    ListNode *next = head->next;
    while(head){
        head->next = prev;
        prev = head;
        head = next;
        next = next->next;
    }
    return prev;
}   

2.Swap Node 问题
根据Rule No.2, 交换两个节点，不存在删除，两个节点的prev节点，以及两个节点的next指针，分别受到影响。
因此可以 a. 先交换两个prev节点的next指针的值 ; b. 再交换这两个节点的next指针。
e.g. 1->2->3->4 => 3->4->2->1
无论这两个节点的相对位置和绝对位置，以上处理总是成立。只是可能可以进一步缩写代码。

e.g. Given a linked list, swap every two adjacent nodes and return its head.( Leetcode: Swap Nodes in Pairs)
Given 1->2->3->4, you should return the list as 2->1->4->3.每个节点的next指针都会发生变化。

ListNode *swapPairs(ListNode *head) {
    if(!head)    return head; // 注意边界条件
    // swap之后head可能发生变化
    ListNode *dummy = new ListNode(0); 
    dummy->next = head;
    // 初始化    
    ListNode *prev1 = dummy;
    ListNode *node1 = head, *node2 = head->next;
    // 一次循环只处理这一个pair
    while(node1 && node1->next){
        node2 = node1->next;
        // 这时候只需要考虑 (prev1, node1) 和 (node1 , node2) 相互独立的两对
        // swap the "next" of prev nodes;
        ListNode *tmp = prev1->next; // =node1
        prev1->next = node1->next; // = node2
        node1->next = tmp; // = node1
        //swap the "next" of current nodes;
        tmp = node1->next; // = node1
        node1->next = node2->next;
        node2->next = tmp; // = node1
        // 也可以写 prev2, node2, 然后再node1 = prev2 代入解方程
        // 可以根据 comment来缩写
        prev1 = node1;
        node1 = prev1->next; // 这里不写node1->next, 因为不想纠缠这里面的关系，从新的prev1出发即可
    }
    return dummy->next;
}

3.处理两个长度未必相等的linked list的问题，循环的条件一般为 while( l1 && l2 ) ,再处理剩下非NULL 的list。 （而不是 while( l1 || l2 )）

e.g Merge two sorted linked lists and return it as a new list.(Leetcode: Merge Two Sorted Lists)

4.如果对靠前节点的处理必须在靠后节点之后，即倒序访问问题，则可视为recursion问题，或可以用stack等效解决。（前面节点的解依赖于后面节点的解）

e.g.1 Traverse the linked list reversely.

void traverse(ListNode *head){
    // 处理边界条件
    if( head == NULL ) 
        return;
    // Linked List 特别的地方
    traverse(head->next);
    visit(head);
}

e.g.2 Given input ( 7->1->6 ) + ( 5->9->2 ), output 2->1->9. // 无需递归，因为靠前节点不依赖于靠后节点
Follow up, Given input ( 6->1->7 ) + ( 2->9->5 ), output 9->1->2. // 用递归或stack处理，因为靠前节点的结果依赖靠后节点的处理, f(n) = Q( V(n), f(n-1) ), 这里的f(n)是进位 + linkedList的一个bundle (转换成string，先reverse再相加的空间复杂度是相同的）

e.g. A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.

Node {
 T value, 
 Node *next,
 Node *random,
}

Deep Copy: 建立一个hashtable来记录从oldNode到newNode的mapping: table[oldNode] = newNode, 然后去遍历老的数据结构（既然是copy，至少是O(n)），建立并且利用这个mapping;

 RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map< RandomListNode *, RandomListNode *> table;
        RandomListNode *old = head;
        RandomListNode *dummy = new RandomListNode(0);
        RandomListNode *new = dummy;
        while(old){
            new->next = new RandomListNode(old->label);
            table[old] = new->next; // old->next = new->next
            old = old->next;
            new = new->next;
        }
        new = dummy->next;
        old = head;
        while(old){
            if(old->random)
                new->random = table[old->random];
            old = old->next;
            new = new->next;
        }
        return dummy->next;
    }

这个问题一定要两次遍历，因为既可能依赖于前面的又可能依赖于后面的计算结果：反过来想，两次遍历是一个解决这类问题的一个思路

Shallow copy verus Deep copy (给所有的member variable也建立一份copy)
cloneGraph 也是类似的， 建立mapping的同时，利用这个mapping，类似于DP的思想

    GraphNode *cloneGraph(GraphNode *node, unordered_map<GraphNode *,GraphNode *>& table){
        if(!node)   return NULL;
        if(table.count(node)>0) return table[node];
        GraphNode *newNode = new GraphNode(node->label);
        table[node] = newNode;
        for(auto it = (node->neighbors).begin(); it != (node->neighbors).end(); ++it)
            (newNode->neighbors).push_back(cloneGraph(*it,table));
        return newNode;
    }

考虑时间复杂度的时候要有全局概念，比如建立cache的空间复杂度是O(n)，那么就不用去考虑递归的空间开销