自从3月被Epic据了之后，在1个月前才开始正式投简历，开始正式找工作，这次是第一个技术电面，虽然Pocket Gems在面试中风评不好，但还是希望能够把握住机会，争取最少过一轮电面！ /***********************************************************************************************我是分割线*****************************************************************************************/ 2015/7/20过了第一轮的电面，考的是Ternary Expression to Binary Tree，现在开始准备第二轮电面了，感觉Pocket Gems的电面题目相对固定，我现在是想大概把电面约到7/28，之前估计需要准备一天到两天，大概做十五道题吧。。。希望能拿到第三轮电面，或者最好是Onsite吧，如果毕业找工作季一开始就是一个Onsite，应该会对士气有很大的提升。。 /****************************************************************************************************************************************************************************************************/ 更新一下，第二轮电面被据了，考的题就是sort color和Inorder Successor in BST。。。可能我面试中表达能力不太行吧。。。。move on。。。。其实pocket gems这种公司我是没有抱太大希望的，毕竟题目近似于公开，就没啥太大意思了，录用标准反倒捉摸不透。。Move on!!下个面试继续努力。。
Pocket Gems NO.1 Strstr() 这题在Leetcode上有原题，用brute force解出，虽然也可以用KMP解，但感觉作为电面第一轮，KMP有点太过于难。 代码如下：NO.28
Pocket Gems NO.2 K Most Frequently Occurring Numbers 本题就是先用hashmap存储，再sort即可，代码如下： struct pair_struct { int key; int val; }; bool Comp(const pair_struct& p1, const pair_struct& p2) { return p1.val > p2.val; }int kfrequent1(vector nums, int k) { unordered_map hashmap; // store element to hashmap for (int i = 0; i < nums.size(); ++i) { auto got = hashmap.find(nums[i]); if (got != hashmap.end()) { hashmap[nums[i]] += 1; } else { hashmap[nums[i]] = 1; } } // sort the hashmap by value vector newArr(hashmap.size(), pair_struct()); auto iter = hashmap.begin(); for (int i = 0; i < newArr.size(); ++i) { newArr[i].key = iter->first; newArr[i].val = iter->second; ++iter; } sort(newArr.begin(), newArr.end(), Comp); return newArr[k-1].key; } Pocket Gems NO.3 Ternary Expression to Binary Tree 举个例子，就是 a?b?c:d:e转化成         a       /         b      e   /   c     d 这题的基本思路就是用stack，遇到"?"，入栈，遇到":"，出栈。 我自己写的代码跟网上的不太一样，不太理解网上的解法，虽然估计是我错了，但是确实30分钟内没有发现错在哪里，面试知道题已经占便宜了，所以不准备再把题搞得那么透彻了，大概理解了即可。。。。欢迎大家指正我的错误。 struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(char x): val(x), left(nullptr), right(nullptr){} // constructor }; TreeNode* ternaryToBT(string input) { TreeNode* root = new TreeNode(input[0]); tmp = root; stack mystack; for (int i = 1; i < input.length(); i += 2) { if (input[i] == '?') { tmp->left = new TreeNode(input[i+1]); mystack.push(tmp); tmp = tmp->left; } else if (input[i] == ':') { tmp = mystack.top(); mystack.pop(); tmp->right = new TreeNode(input[i+1]); tmp = tmp->right; } } return root; }
Pocket Gems NO.4 Lowest Common Ancestor of Binary Tree 如果是Binary Search Tree的话本题很简单，请参考Leetcode原题：NO.235 如果是Binary Tree的话，其实也不算复杂，但是要考一点思维了。。Leetcode原题，我的blog里面也有答案：NO.236 Pocket Gems NO.5 Sort Color 本题应该是以Leetcode那道题为原型。。。就是用3-way quicksort。。。可以看一下：NO.75 据说，本题的color是struct，看面经也看不太明白，但是估计就是比较struct需要定义各种大小于号，不过感觉不需要那么麻烦，如果就三种颜 {MOD}的话。。。。。 不太懂，不过还是上一些在struct里面写comparator的代码吧： #include using namespace std; struct Color { int color; int other; friend bool operator<(const Color& a, const Color& b) { return a.color < b.color; } friend bool operator>(const Color& a, const Color& b) { return a.color == b.color; } Color(int c, int o): color(c), other(o) {} }; int main(int argc, char** argv) { Color* a = new Color(1, 2); Color* b = new Color(2, 3); cout << (a < b) << endl; cout << (a > b) << endl; return 0; }
Pocket Gems NO.6 Inorder Successor in BST 第一个要求提供parent node， 结构体如下： struct Node { int val; Node* left; Node* right; Node* parent; Node(int x): val(x), left(nullptr), right(nullptr), parent(nullptr) {} // constructor };

• 如果给定节点的right node不空，则找以right node为subtree的第一个点。
• 如果给定节点的right node为空，则找以该节点为最后一点的最大subtree的root，这个root必将是其parent的左节点，或者是给定node的next node是nullptr

讲的不是很清楚，直接上代码吧： // with parent node Node* inorderSuccessor(Node* n) { // step 1 of the algorithm if (n->right != nullptr) { return minVal(n->right); } // step 2 of the algorithm Node* p = n->parent; while (p != nullptr and n != p->left) { n = p; p = p->parent; } return p; }; Node* minVal(Node* n) { Node* cur = n; while (cur->left != nullptr) { cur = cur->left; } return cur; }
然后再讨论不提供parent node的，其实思路差不多，找最大的以给定node为最后一个点的subtree的root,然后返回这个root的parent 代码如下： Node* inorderSuccessor2(Node* root, Node* n) { // step 1 of the algorithm if (n->right != nullptr) { return minVal(n->right); } // step 2 of the algorithm Node* succ = nullptr; while (root != nullptr) { if (n->val < root->val) { succ = root; root = left; } else if (n->val > root->val) { root = root->right; } else { break; } } return succ; }
Pocket Gems NO.7 First Occurrence of Binary Search 这题没有太多好说的，就是binary search做一点改动就行了，直接上代码: #include #include using namespace std; int binarySearch(vector, int); int main(int argc, char** argv) { int input[5] = {1, 1, 1, 2, 3}; vector arr(input, input + sizeof(input) / sizeof(input[0])); cout << binarySearch(arr, 3) << endl; return 0; } int binarySearch(vector arr, int val) { int low = 0; int high = arr.size(); int first = -1; while (low <= high) { int mid = low + ((high - low) >> 1); if (val > arr[mid]) { low = mid + 1; } else if (val < arr[mid]) { high = mid - 1; } else { first = mid; high = mid - 1; } } return first; }
Pocket Gems NO.8 Word Break 这是一道Leetcode上面的题目，直接参考我的Leetcode 题解：NO.139