电面

Yelp new grad面经整理分享

之前面yelp的时候运气很不好，考了一道唯一没有做过的面经题（因为看了面经也不会，根本不知道要干嘛也就是第37题。。。），yelp题库明显，就那么几道题来回考，这里是我当时准备的时候在地里和mitbb上搜集的一些题目，希望能帮到以后面yelp的同学们（可能不全，但是应该会给你们省一点时间）

Coding questions part:

Generate 一個掃雷遊戲的 board.

用一個 2D array 來表示 board，給出 board 的長（L）寬(W) 和地雷數量（M），隨機地把 M 個地雷放在 L*W 個格子裏面，並在沒有地雷的格子中標記格子周圍地雷的數量。要求：絕對的 Random，並且避免發生 collision (generate 出同樣的 random number after processing)
def generateBoard(L, W, M):
""" return a 2D array representing the game board """

把数字与最后一位替换

#include <vector>
#include <iostream>
#include <cstdlib>
using namespace std;

vector<int> N_choose_K(vector<int>& indices, int n, int k) {
    vector<int> res;
    for (int i = 0; i < k; ++i) {
        int tmp = rand() % (n-i);
        res.push_back(indices[tmp]);
        indices[tmp] = indices[n-i-1];
    }
    return res;
}

vector<vector<char>> generateBoard(int l, int w, int m) {
    vector<vector<char>> board(l, vector<char>(w, '0'));
    if (l == 0 || w == 0 || m == 0) return board;

    int num_cells = l*w;
    vector<int> indices(num_cells);
    for (int i = 0; i < num_cells; ++i) indices[i] = i;
    vector<int> mine_indices = N_choose_K(indices, num_cells, m);
    for (int idx: mine_indices) {
        int row = idx/w, col = idx%w;
        board[row][col] = 'M';
        for (int i = -1; i <= 1; ++i) {
            for (int j = -1; j <= 1; ++j) {
                int x = row+i, y = col+j;
                if (x >= 0 && x < l && y >= 0 && y < w && board[x][y] != 'M') {
                    ++board[x][y];
                }
            }
        }
    }
}


int main() {
    int l = 7, w = 5, m = 8;
    vector<vector<char>> board = generateBoard(l, w, m);
    for (int i = 0; i < l; ++i) {
        for (int j = 0; j < w; ++j) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }

}

LC 53. Maximum subarray sum
LC 152. Maximum subarray product
LC 128. Longest Consecutive Sequence
LC 228. Summary Ranges
LC 56. Merge Intervals
LC 57. Insert Interval
LC 341. Flatten Nested List Iterator
LC 251. Flatten 2D Vector
LC 322. Coin Change

Cosine Similarity

算两个文本的cosine similarity
就是数一数每个词出现了多少次，比如一共有N个不同的词，可以把一个文档当成一个N给的向量。
然后求两个文档的相似就是求两个向量的余弦角。相同的文档其实余弦是1
比如文档1: dog cat dog. 文档二 cat dog dog . 这两个看词出现的频率是一样的。

余弦定理的应用：基于文字的文本相似度计算

Cosine Similarity

Address similarity

Compare the output of two textbox and reject if their content is too similar (reordering of paragraph should be rejected)
基本是dictionary, 加Edit distance

LC 72. Edit distance
LC 49. Group anagram
LC 139. Word break
LC 140. Word ladder II

Given 4 points, determine whether its a Square, Rectangle, Diamond or 平行四边形

Input 2D平面四个点第一问判断是不是一个square
不一定要跟x轴 y轴平行 (Square 可以旋转)
代码大致上像是:

struct Point {
    double x, y;
    Point(double x_, double y_) : x(x_), y(y_) {}
};

bool isSquare(const vector<Point>& points) {
    // ...
}

第二问是 return 四个点围成的形状:
"rectangle", "square", "diamond", “parallelogram",. ...
一开始閒聊花太长时间了最后没有写完

好像不用那么复杂，四个点我们可以得到C(4,2) = 6 条边。然后只要看看他们的长度关系就好，要是算角度就麻烦了。
先把6条边sort一下后面代码好写很多：
正方形：四个短边相等，两个长边彼此相等，并且长边刚好等于sqrt(2)*短边
菱形：同正方形，但是不用符合根号二那个要求
长方形：边的长度两两相等，最长边的平方等于最短边和次短边的平方和
平行四边形：同长方形，但不用符合平方和那个要求

几何忘的差不多了，大家看看有反例么？

Top K address - Top K frequent element

有一个网站会log 所有访问过该网站的ip address (streaming data）有什么方法是可以弹出top 10 ip address （real time)？

Top k address就是根据address出现次数排序吧，用PriorityQueue做

问一道经典系统设计题

LC 79/212. Word Search I / II
LC 241. Different ways to add parenthesis
LC 205. Isomorphic String
LC 3. Longest Substring Without Repeating Characters
LC 332. Reconstruct Itinerary
Reservoir Sampling with infinite stream

reservoir-sampling
LC 221. Maximum Square
LC 10. Regular Expression Matching
LC 210. Course Schedule II
LC 71. Simplify Path

Output all possible combination of a2c (变换大小写)

给一个String，全是小写或者数字，输出他的所有大小写组合。例如输入a2c，输出就是a2c, a2C, A2c, A2C.

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
    void dfs(string& word, int pos, vector<string>& res) {
        if (pos == word.size()) {res.push_back(word); return;}
        if (word[pos] >= '0' && word[pos] <= '9') dfs(word, pos+1, res);
        else {
            word[pos] = tolower(word[pos]);
            dfs(word, pos+1, res);
            word[pos] = toupper(word[pos]);
            dfs(word, pos+1, res);
        }
    }
public:
    vector<string> combination(string word) {
        vector<string> res;
        dfs(word, 0, res);
        return res;
    }
};

int main() {
    Solution s;
    for (auto& a: s.combination("a2bc")) cout << a << endl;
}

输入一个string，全部都是小写，然后把其中的某些变成大写，输出all combinations。follow up是问有多少种可能，我答的是n的阶乘，现在一想发现是2的n次方

version 1:

#include <vector>
#include <string>
#include <iostream>
using namespace std;

class Solution {
    void dfs(string& s, int pos, string out, vector<string>& res) {
        if (pos == (int)s.size()) {
            res.push_back(out);
            return;
        }
        dfs(s, pos+1, out+s[pos], res);
        char c = s[pos] - 32;
        dfs(s, pos+1, out+c, res);
    }
public:
    vector<string> allCombination(string s) {
        vector<string> res;
        dfs(s, 0, "", res);
        return res;
    }
};


int main() {
    Solution sol;
    for (auto s: sol.allCombination("abc")) cout << s << " ";
    cout << endl;

}

version 2:

#include <vector>
#include <string>
#include <iostream>
using namespace std;


class Solution {
    void dfs(string& s, int pos, vector<string>& res) {
        res.push_back(s);
        for (int i = pos; i <= s.size(); ++i) {
            if (s[i] >= 'a' && s[i] <= 'z') {
                s[i] -= 32;
                dfs(s, pos+1, res);
                s[i] += 32;
            }
        }
    }
public:
    vector<string> allCombination(string s) {
        vector<string> res;
        dfs(s, 0, res);
        return res;
    }
};

Min Stack/Queue
Implement BST (add find delete)

Select k smallest items in an array

k largest(or smallest) elements in an array | added Min Heap method

Preorder - Inorder reconstruct tree

Amicable pairs

An amicable pair (m,n) consists of two integers m,n for which the sum of proper divisors (the divisors excluding the number itself) of one number equals the other.
Given an integer k, find all amicable pairs between 1 and k.
Example:
Given 300, return [[220, 284]].
Note:
For each pair, the first number should be smaller than the second one.

Amicable Numbers

#include <iostream>
#include <vector>
using namespace std;

class Solution {

    //Exceed Time Limit
    /*
    int factorSum(int n) {
        int sum = 0;
        for (int i = 1; i < n; ++i) {
            if (n % i == 0) sum += i;
        }
        return sum;
    }
    */
    int factorSum(int n) {
        int sum = 1, i;
        for (i = 2; i * i < n; ++i) {
            if (n % i == 0) {
                sum += i + n / i;
            }
        }
        if (i * i == n) sum += i;
        return sum;
    }
public:
    vector<vector<int>> amicablePairs(int k) {
        vector<vector<int>> res;
        for (int i = 1; i <= k; ++i) {
            int amicable = factorSum(i);
            if (amicable <= i || amicable > k) continue;
            if (factorSum(amicable) == i) {
                res.push_back({i, amicable});
            }
        }
        return res;
    }
};

int main() {
    Solution s;
    vector<vector<int>> res = s.amicablePairs(300);
    for (auto& a: res) {
        cout << a[0] << " " << a[1] << endl;
    }
    return 0;
}

LC 253. Meeting Room II
LC 297. Serialize and Deserialize binary tree
LC 240. Search a 2D Matrix II
LC 287. Find the Duplicate number
LC 278. First Bad Version
LC 218. Skyline Problem
LC 380. Insert Remove Random(1) I
LC 381. Insert Remove Random(1) II
Basic SQLs

Sync Cursor row

The content updates and the word cat shifts down a line. However, Person B's cursor is left in it's original position instead of moving down a line as expected.

Implement the fixCursorRow method don't worry about updating the column.

public class Cursor {
    public int column;
    public int row;

    public Cursor(int row, int column);
    }
};
// diff comes from the other screen.
// content is content of the current screen before diff is applied.
// cursor is the cursor of the current screen.

// diff format:
// The diff contains all content from beginning to end of document.

{{"1", "\n"}, {"0", "cat"}}
// house -> horse = {{"0", "ho"}, {"-1", "u"}, {"1", "r"}, {"0", "se"}}
// "0" -> equality, "1" -> addition, "-1" -> removal
public Cursor fixCursorRow(String[][] diff, String content, Cursor cursor) {

}

So for this problem we get following diff array
{{"1", "\n"}, {"0", "cat"}}

So in the diff array you can see there is an addition of the new line {"1", "\n"} and also there is no change in the content {"0", "cat"}.This mean we have to move cursor to the next line.

This was kind of very open ended question and I got only 25 min to give the solution.Please let me know if you want more explanation.

General technical question part:

Difference between process and Thread (detail)
HashMap / HashSet / TreeSet / TreeMap / LinkedHashMap
Database Indexing / B+-Tree

快速理解数据库中的索引(Indexes in Database)

B+ Tree Basics 1

B+ Trees Basics 2 (insertion)

B+ Tree Basics 3
Java GC Collection
Basic multi-threading questions
Vector vs ArrayList vs LinkedList (java)
AVL / RB Tree

Yp 电面

电面

Yelp new grad面经整理分享

Generate 一個掃雷遊戲的 board.

Cosine Similarity

Address similarity

Given 4 points, determine whether its a Square, Rectangle, Diamond or 平行四边形

Top K address - Top K frequent element

Output all possible combination of a2c (变换大小写)

Select k smallest items in an array

Amicable pairs

Sync Cursor row

yelp phone 面经整合

yelp电话面试总结

yelp校招面经

results matching ""

No results matching ""