Elements of Programming Interviews 白班编程记录，求挑刺求反馈

大木虫

445. Add Two Numbers II
这道题有多种解法：反转链表，stack，转成数字相加再转回，递归

我挑了我认为最麻烦的一种：递归，因为其它写法太直接，写起来达不到训练的效果。
本题递归的核心是tail recursion，代码如下（写了40分钟左右）

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
/* 0. MISC */
if(!l1 && !l2)return NULL;
if(!l1 || l1->val == 0)return Copy(l2);
if(!l2 || l2->val == 0)return Copy(l1);
/* 1. prep */
int l1Size = Size(l1), l2Size = Size(l2);
ListNode *shortList, *longList;
if(l2Size > l1Size){
longList = l2; shortList = l1;
}else{
shortList = l2; longList = l1;
}
int diff = abs(l1Size - l2Size);
/* 2. key algo */
ListNode *head = AddListRec(longList, shortList, diff);
if(head->val >= 10){
ListNode* tmp = new ListNode(head->val/10);
head->val %= 10;
tmp->next = head;
head = tmp;
}
/* 3. answer */
return head;
}
ListNode* AddListRec(ListNode *l1, ListNode *l2, int diff){
/* base case */
if(!l1 && !l2)return NULL;
ListNode * node = new ListNode(0), *child;
if(diff > 0){
child = AddListRec(l1->next, l2, diff-1);
node->val += l1->val;
}else{
child = AddListRec(l1->next, l2->next, diff);
node->val += l1->val + l2->val;
}
if(child){
node->val += child->val/10;
child->val %= 10;
}
node->next = child;
return node;
}
ListNode* Copy(ListNode* l){
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
while(l){
current->next = new ListNode(l->val);
l = l->next;
current = current->next;
}
ListNode * head = dummy->next;
delete dummy;
return head;
}
int Size(ListNode* l){
int ans = 0;
while(l){
l = l->next;
++ans;
}
return ans;
}
};

复制代码

大木虫 · 2018-11-25 00:22:25

结束了一些面试，开始准备下一波面试，18天的时间，争取把高难度高频旧题做30~40道，medium-hard高频新题做30~40道，实现最近两个月的onsite面经，以高频为主

大木虫 · 2018-11-25 00:26:50

主要的课题是graph, DFS, BFS, backtracking, tree, DP, array, string, stack.
follow up 的主要课题是scalability
会练一点OOD
不练design

补充内容 (2018-11-25 00:27):
对了还有linked list

大木虫 · 2018-11-25 01:53:49

今天做热身
LC 482 (easy)
LC 412 (easy)
LC 347 (medium)
都是一遍过，平均用时12分钟
下午有心情的话，再写几个偏简单的题目

大木虫 · 2018-11-26 06:03:26

今天做了一题LC 904，然后总结了最近两周面经15题左右，作为明天起的刷题指导

大木虫 · 2018-11-27 03:19:26

遇到了阻碍，我这样做下去效果堪忧。需要作出修改。

我面试的公司是Google，面试日期是12/14，不算今天的话还有16天的准备时间。我的模式是脱产准备，每天6小时。16天不多，但还是相对充足的。不过如果没有章法，那么就会出现问题。为此，我决定利用今天制定一套比较可行的计划，模仿之前准备Google phone screen的模式。

为了通过面试，我需要几个核心能力:
1. 把题听懂并想出来的能力
2. 让面试官听懂我想法的能力
3. 把不会的题说出个一二三的能力
4. 把答案迅速正确白板码出来的能力
5. 在陌生环境下稳定发挥的能力

我们从这几个点一个个分解，作出未来16天的确定的脚踏实地的计划。

1. 把题听懂并想出来的能力
对于google来讲，这个能力是相对单调的，就是对数据结构和算法的熟练运用。我在此更加依靠系统的对数据结构和算法的训练，而不是散乱的面经，因为这里训练的是得出答案思路，触类旁通，举一反三的能力，强调的是对主要知识点的熟练运用和融汇贯通。我的训练方法是集中训练高频知识点，不考虑公司tag。对于google，我认为的高频知识点有如下几个:
   array/string
   binary tree/BST/tree traversal
   graph/DFS/BFS
   backtracking
   hashmap/hashtable
   priority queue
   dynamic programming/memoization
   trie
   linked list
我会使用9天的时间进行知识点集中训练，训练目的是掌握知识点，梳理标准化解题步骤，以及提高对syntax的熟练度和码速，大致时间分配如下：
阶段一：树，图类，4天，总共写20题左右，每天做1~2道旧经典medium/hard，再做2~4道新medium/hard
阶段二：string/array/hashtable，3天，总共写15题左右，每天做1~2道旧经典medium/hard，再做2~4道新medium/hard
阶段三：dynamic programming，2天，总共写10题左右，每天做1~2道旧经典medium/hard，再做2~4道新medium/hard
这大概是之前的强度，再高的话难以坚持。9天45题，够多了。我估计这45题中AC之前看discussion的次数不会超过3次，这也是之前的表现。

2. 让面试官听懂我想法的能力 3. 把不会的题说出个一二三的能力 4. 把答案迅速正确白板码出来的能力 5. 在陌生环境下稳定发挥的能力
这些放一起来讨论，因为它们都是在真是面试情境中被考验的。
我的办法是用高频medium-hard和新题medium-hard来进行白板模拟，每天使用3小时来模拟2题，持续7天，题目从高频面经和LC里面出

3. 面经，押题
押题是非常有用的，所以单独拿出来讲。
对于我来讲就是看面经，总结面经，这是一个比较难的过程，因为总有一些面经题我写不出来。
计划是把近期的面经全写完，高频题要写出来，非高频得知道怎么想。从最近期一个月开始逐渐扩展。每天花3小时研究面经，持续7天，能做多少是多少。我会在面经贴下面直接贴我想的答案。不会的就展开讨论。

所以总结一下，计划如下：
第一阶段：高频知识点熟练掌握贯通，提高码力，练习标准化解题流程，9天
第二阶段：白板模拟练习训练心理素质和标准化执行，看面经押题，两者交替进行，7天

在以上过程的实践中，我格外注重几点：
思考一定要深，要自发，要有拉扯思维的感觉
要从解题中寻得乐趣
对于每一道题都要给出一两句的总结，并思考与其他题目联系，变型和转换
要把操作细节规程化习惯化
要每天8小时规律的睡眠

大概就是这样，希望这套计划能起到作用。

大木虫 · 2018-11-27 05:09:27

LC 016 three sum closest，得出了N^2 * logN的解法，N^2没有思路，看了topics和部分discuss title，说要用two pointers和sorting解，又想了60分钟，终于tm想出来了N^2解，是先用sort进行preprocess，然后用类似于trapping rain water的two pointers向中间合拢的方法来解。感觉想的好累好难。。。

补充内容 (2018-11-27 05:09):
topics是指LC的related topics

大木虫 · 2018-11-28 02:58:27

LC 489 robot cleaner 第三遍，AC in 28 min
idea: backtracking
tips: get your coder-friendly custom API defined before implementation

compile errors:
missing semicolon
swapped function signatures (decode/encode backwards)
missed i/j with loc.first/loc.second

no run time errors

C++ Code:

/**
* // This is the robot's control interface.
* // You should not implement it, or speculate about its implementation
* class Robot {
* public:
* // Returns true if the cell in front is open and robot moves into the cell.
* // Returns false if the cell in front is blocked and robot stays in the current cell.
* bool move();
*
* // Robot will stay in the same cell after calling turnLeft/turnRight.
* // Each turn will be 90 degrees.
* void turnLeft();
* void turnRight();
*
* // Clean the current cell.
* void clean();
* };
*/
/* backtracking problem, define custom APIs first */
class Solution {
private:
int state;
public:
Solution(): state(0){}
void cleanRoom(Robot& robot) {
/* 0. MISC */
/* 1. prep */
unordered_set<string> visited;
/* 2. key algo */
CleanRoomRec(&robot, &visited, {0, 0});
/* 3. answer */
/* void, no return */
}
void CleanRoomRec(Robot* robot, unordered_set<string>* visited, pair<int, int> loc){
/* before branching */
if(visited->find(Encode(loc)) != visited->end())return;
visited->emplace(Encode(loc));
robot->clean();
/* branching */
vector<string> directions = {"N", "E", "S", "W"};
vector<pair<int, int>> moves = {pair<int, int>(-1, 0), pair<int, int>(0, 1), pair<int, int>(1, 0), pair<int, int>(0, -1)};
for(int i = 0; i < directions.size(); ++i){
string dir = directions[i];
string revDir = directions[(i+2)%4];
if(CanEnter(dir, robot)){
TurnTo(dir, robot);
robot->move();
CleanRoomRec(robot, visited, {loc.first + moves[i].first, loc.second + moves[i].second});
TurnTo(revDir, robot);
robot->move();
}
}
/* done */
}
void TurnTo(string dir, Robot* robot){
int target = 0;
if(dir == "N")target = 0;
if(dir == "E")target = 1;
if(dir == "S")target = 2;
if(dir == "W")target = 3;
while(state != target){
robot->turnRight();
state += 1;
state %= 4;
}
}
void TurnAround(Robot* robot){
robot->turnRight();
robot->turnRight();
state += 2;
state %= 4;
}
bool CanEnter(string dir, Robot* robot){
TurnTo(dir, robot);
bool ans = robot->move();
if(ans){
TurnAround(robot);
robot->move();
}
return ans;
}
string Encode(const pair<int, int>& loc){
return to_string(loc.first) + " " + to_string(loc.second);
}
pair<int, int> Decode(const string& loc){
int div = loc.find(" ");
string strI = loc.substr(0, div);
string strJ = loc.substr(div + 1);
return {stoi(strI), stoi(strJ)};
}
};

复制代码

大木虫 · 2018-11-28 04:22:24

428. Serialize and Deserialize N-ary Tree (hard)

1. Understand Problem at 2 min
2. Get key concept at 8 min
3. Algorithm draft part 1 at 12 min
4. Detailed derivation part 1 at 16 min
5. Code draft part 1 at 19 min
6. Algorithm draft part 2 at 30 min
7. Detailed derivation at 35 min
8. Code draft at 49 min
9. solution AC at 59 min

compile error:
remember to pass pointer reference function(&param)

Runtime error:
incomplete answer (only root node)
had one boolean logic reversed
missed null case

主要思路是DFS，序列化和反序列化的思路都是DFS，反序列化要注意一些string parsing的细节，最好在序列化的时候就把string格式做的友善一些。
Ntree的序列化和binary tree的序列化想法类似，但是写法有一些差异，主要原因在于不知道每个node有几个children，与其说是tree序列化，这题更像是图学历恶化（graph serialization）。很好的题。

C++ code:

/*
// Definition for a Node.
class Node {
public:
int val = NULL;
vector<Node*> children;
Node() {}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(Node* root) {
string answer = " ";
SerializeRec(root, &answer);
cout << "ans: " << answer << endl;
return answer;
}
void SerializeRec(Node* node, string* answer){
if(!node)return;
(*answer) += to_string(node->val);
(*answer) += " ";
if(!node->children.empty()){
(*answer) += "[";
for(auto child: node->children){
SerializeRec(child, answer);
}
(*answer) += "] ";
}
}
char nextChar(string data, int index){
while(index < data.size() && data[index] == ' ')++index;
return data[index];
}
int nextNum(string answer, int* index){
string numStr;
while(*index < answer.size() && !isdigit(answer[*index]))++(*index);
while(*index < answer.size() && isdigit(answer[*index]))numStr += answer[(*index)++];
return stoi(numStr);
}
// Decodes your encoded data to tree.
Node* deserialize(const string& data) {
/* 0. MISC */
if(data == " ")return NULL;
/* 1. prep */
int index = 0;
/* 2. key algo, 3.answer*/
return DeserializeRec(data, &index);
}
Node* DeserializeRec(const string& data, int* index){
int val = nextNum(data, index);
Node* node = new Node(val, {});
if(nextChar(data, *index) == '['){
while(nextChar(data, *index) != ']')
node->children.emplace_back(DeserializeRec(data, index));
while(data[*index] != ']')++(*index);
++(*index);
}
return node;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

复制代码

补充内容 (2018-11-28 04:25):
follow up：用stack写一遍迭代版本

大木虫 · 2018-11-28 06:25:14

LC 99. Recover Binary Search Tree (hard)
没有仔细计时，但是临场应该可以35分钟AC，这是估算上限
我用的是in-order traversal解，space complexity O(h)，不是constant space。constant space据说要用Morris Traversal，这我还不会，要学一学。in-order解唯一有些复杂的地方就是一堆pointer的操作

C++ code:

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode* root) {
/* 1. prep */
TreeNode *prev = NULL, *first = NULL, *second = NULL;
/* 2. key algo */
FindSwappedNodesRec(root, &prev, &first, &second);
swap(first->val, second->val);
/* 3. answer */
/* no return */
}
void FindSwappedNodesRec(TreeNode* node, TreeNode** prev, TreeNode** first, TreeNode** second){
if(!node)return;
FindSwappedNodesRec(node->left, prev, first, second);
if(*prev != NULL){
if((*prev)->val > node->val){
if(*first == NULL)*first = *prev;
*second = node;
}
}
*prev = node;
FindSwappedNodesRec(node->right, prev, first, second);
}
};

复制代码

Elements of Programming Interviews 白班编程记录，求挑刺求反馈

浏览过的版块