自从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
unordered_map
// 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
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
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需要定义各种大小于号，不过感觉不需要那么麻烦，如果就三种颜色的话。。。。。
不太懂，不过还是上一些在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 main(int argc, char** argv) {
int input[5] = {1, 1, 1, 2, 3};
vector
cout << binarySearch(arr, 3) << endl;
return 0;
}
int binarySearch(vector
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