Leetcode: Google interview questions #4

Leetcode: Google interview questions #4
REF http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=136847&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
给我小哥没有废话直接上题
我coding速度太慢，只面了一道题目

给出一个迭代器，迭代器里存了很多个类R的实例, 类R里只有两个参数，都是String类型，分别代表Parent 和 Child，child只有一个Parent，Parent 可以有任意数量child
按所给示例输出所有的层级关系

eg：
A
  B1
  B2
C1
C2
  B3
D1
D2

就是建立一个compiler里面的inheritance graph，然后打印

struct TreeNode{

    string parent;

    string name;

    vector<TreeNode *> children;

    TreeNode(string p, string n) {

        parent = p;

        name = n;

    }

};

class A{

public:

    string parent;

    string child;

};

void printRecursively(TreeNode *root, string tab) {

    if (root == NULL) return;

    cout << tab << root->name << endl;

    for (int i = 0; i < root->children.size(); i++) {

        printRecursively(root->children[i],tab + "    ");

    }

}

void printGraph(vector<A> &source) {

    unordered_map<string,TreeNode*> dic;

    for (int i = 0; i < source.size(); i++) {

        TreeNode *p = NULL, *c = NULL;

        if (dic.find(source[i].parent) == dic.end()) {

            p = new TreeNode("",source[i].parent);  

            dic[source[i].parent] = p; 

        }

        if (dic.find(source[i].child) == dic.end()) {

            c = new TreeNode(source[i].parent,source[i].child); 

            dic[source[i].child] = c; 

        }

        p = dic[source[i].parent];

        c = dic[source[i].child];

        p->children.push_back(c);

    }

    for (auto t : dic) {

        if (dic[t.first]->parent.length() == 0) {

            printRecursively(dic[t.first],"");

        }

    }

}

int main()

{

    A a1;

    a1.parent = "A";

    a1.child = "B1";

    A a2;

    a2.parent = "A";

    a2.child = "B2";

    A a3;

    a3.parent = "A";

    a3.child = "B3";

    A b1;

    b1.parent = "B2";

    b1.child = "C1";

    A b2;

    b2.parent = "B2";

    b2.child = "C2";

    A c1;

    c1.parent = "B3";

    c1.child = "D1";

    A c2;

    c2.parent = "B3";

    c2.child = "D2";

    vector<A> v;

    v.push_back(a1);

    v.push_back(a2);

    v.push_back(a3);

    v.push_back(b1);

    v.push_back(b2);

    v.push_back(c1);

    v.push_back(c2);

    printGraph(v);

}

---------------------------------------------------------------------------
REF http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=134335&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
4月底MTV面的onsite, 很奇怪是5面，至今没消息，直接上面经

1.日本大叔
来晚了20分钟导致后面很紧。先写反转链表，然后第二题把链表变成a1->an->a2->an-1
LC reorder list
2.白人小哥+沉默的阿三
第一题是path sum难度一样的dp水果。第二题给画布上的几个线段，问怎么画最快（移动画笔会浪费时间)
待写
3.阿三
到这面的时候才20分钟后面找我吃饭的大叔就来了，草草写完，给一个字符串，问可否组成一个新串使得每两个相邻字符不重复
重复，见Google interview questions #2 onsite第1题

午饭是个黑叔叔，用手直接抓食物吃，震精

4.光头小白
先问简历，然后又是一个path sum难度一样的dp水果

5.白人小帅
q: 玩过扫雷吗？
a: yes
q: 实现它
a: wtf??

---------------------------------------------------------------------------------------
REF http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=137928&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
可能是因为我做得慢，总共就做了一道题，就是一个游戏。
input string：“+++--++-+”
游戏规则：每人每次可以 flip "++" to "--"（必须是相邻的）

第一问：generate all possible moves
第二问：determine if this player can will
Extra：这两个问题的implementation的Big-O

补充内容 (2015-7-12 13:13):
下个人没法flip了这个人就赢；all possible moves for next flip
permutation, O(n!)
T(n) = T(n - 1) + T(n - 1) + T(n - 1)...... + c = (n - 1) * T(n - 1) + c
T(n - 1) = (n - 2) * T(n - 2)
T(n - 2) = (n - 3) * T(n - 2)
.....
So T(n) = n!

bool canWin(string s) {

    int start = -1,end = -1;

    for (int i = 0; i < s.length(); i++) {

        if (s[i] == '+') {

            if (start != -1 && i - start > 0) {

                string t = s;

                t[start] = '-';

                t[i] = '-';

                if (!canWin(t)) return true;

                start++;

            }else {

                start = i;

            }

        }else {

            start = -1;

        }

    }

    return false;

}

另一方法：博弈论，可达到O(n^2), 关键词game theory, nimber, grundy number
http://www.1point3acres.com/bbs/thread-137953-1-1.html
----------------------------------------------------------------------------------------

Linked List e.g 1->5->2->3->7
Modify it so that it becomes: 1->7->5->3->2

一头一尾，第二头第二尾，O（1）空间复杂度，O（n）时间复杂度

-----------------------------------------------------------------------------------

Given a bunch of N random points in space, how would you

draw a line such that N/2 of them were to the left of the line and N/2 to the right of it. Complexity

按x坐标用quick select，找出median，只需要O(n)

-------------------------------------------------

Given an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).

reservoir sampling

void helper(TreeNode *root, int &count, int choice) {

 if (root == NULL) return NULL;

 count++;

 if (rand(1,count) == 1) {

  choice = root;

 }

 helper(root->left,count,choice);

 helper(root->right,count,choice);

}

TreeNode *findRandomNode(TreeNode *root) {

 TreeNode *choice = NULL;

 int count = 0;

 return helper(root,count,choice);

}

------------------------------

给一个array和target，找出在array里与target最接近的值的index

类似LC search insert position

----------------------------------------------------

REF http://www.mitbbs.com/article_t/JobHunting/33010083.html

onsite

1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡

片的下一个位置

e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的

话下个卡片位置是EDCBA。

问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，

能得话要多少次。

吐槽下，面试官是个三哥，全程非常严肃／黑脸，我说句话就用小本子记下搞得我很紧

张。我说用java写可以吗，曰可以，刚写了两行问我add是啥意思，不知道是想考我基

础知识还是不懂java。

O(n), 对shuffle里面的每一个点都走一遍，最后走回起始点，走过的路径全部mark起来，记录count。mark过的可以直接跳过
最后取所以count的最小公约数即可

int getSmallest(int i, int j) {

    for (int s = 1; s <= j; s++) {

        if (s * i % j == 0) return s * i;

    }

}

int jumpBack(vector<int> &shuffle) {

    vector<int> visit(shuffle.size(),-1);

    int count = 0, preCount = 1;

    for (int i = 0; i < shuffle.size(); i++) {

        count = 0;

        int index = i;

        while (visit[index] == -1) {

            count++;

            visit[index] = shuffle[i];

            index = shuffle[index];

            if (visit[index] != -1 && visit[index] != visit[i]) return -1;

        }

        if (count != 0) preCount = getSmallest(count,preCount);    

    }

    return preCount;

}

2. 给定一个binary search tree，返回range内所有key，key可以有重复。

略

版上出现了多次的把一个数拆成任意个平方和的最小拆法。

DP，重复

面试官是中年国人大叔，除了告诉我题目是啥就在电脑上自顾自工作，问话要问两遍才

有反应。写完说我程序有问题，查了半天查不出bug，然后指出我漏了个尖括号，跪了

。。

3. 版上出现多次的longest consecutive sequence in tree

follow up 如何加速，memory放不下怎么办。

国人小哥比较nice，但是只要我不和他主动说话绝不主动和我说话，因为前两场心情略

糟糕写完题目在白板前发呆，哥们就望着我啥也不说，尴尬。。当然也不怪他我自己比

较紧张，回家发现有很弱智的bug但小哥没提不知道怎么回事，可能放我水了

4. 设计个用bit形式表示时间（小时：分钟）的clock，

e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的

时间，

e.g. n＝0就只有0:0一种可能。

面试官是亚裔年轻mm，话不多人很cool，但是思路清晰会引导面试者，感觉碰到懂得引

导面试者或冷漠面试官对面试人表现会有很大影响，真的是看运气了。

5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选

两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写

isWin（String s）判断先行动的玩家能否赢。

followup 如何优化，时间上和空间上。

面试官是做android前端的白人mm，非常活泼健谈，一路聊天愉快，面完就感觉她会给

强推。

Read full article from Leetcode: Google interview questions #4

Leetcode: Google interview questions #4

Given a bunch of N random points in space, how would you

Labels

Popular Posts