一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 518|回复: 2
收起左侧

dropbox电面合集

[复制链接] |试试Instant~ |关注本帖
shiloh00 发表于 2016-11-7 03:20:37 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Dropbox - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
已经挂了 被面试官怀疑见过原题 发上来我准备的面经合集 为后面的onsite攒攒人品

  • 1. Hit counter. 鍥磋鎴戜滑@1point 3 acres
.鐣欏璁哄潧-涓浜-涓夊垎鍦
. from: 1point3acres.com/bbs

#include<queue>
#include<iostream>
#include<mutex>
using namespace std;

class HitCounter{
private:
        mutex l;
        queue<int> q;
public:
        HitCounter(){}
        void hit(int t) {
                l.lock();
                q.push(t);
                l.unlock();
        }
        int getHit(int timestamp) {
                l.lock();       
                while(!q.empty() && timestamp - q.front() >= 300) {
                        q.pop();
                }
                l.unlock();
                return q.size();
        }
};
. visit 1point3acres.com for more.
int main() {
        HitCounter h1;
        h1.hit(1);
        h1.hit(2);
        h1.hit(3);
        h1.hit(300);
        cout << h1.getHit(300) << endl;
//        h1.hit(301);
        cout << h1.getHit(301) << endl;
}
..








2. word pattern

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        stringstream ss(str);
        string s;
        int count = 0;
        unordered_map<string, char> map1;
        unordered_map<char, string> map2;
        while(ss >> s) {
            if(count >= pattern.size())
                return false;
            if(map1.find(s) == map1.end()) {
                map1 = pattern[count];
            }
            else {
                if(map1 != pattern[count])
                    return false;
            }
            if(map2.find(pattern[count]) == map2.end()) {
                map2[pattern[count]] = s;
            }
            else{
                if(map2[pattern[count]] != s)
                    return false;
            }
            count++;
        }
        if(count < pattern.size())
            return false;
        else
            return true;
    }
};
. 1point 3acres 璁哄潧

3.  Game of Line

// state 0: 0->0
//state 1: 1->1
//state 2: 1->0
//state 3: 0->1
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        vector<int> d1 = {-1, -1, -1, 0, 0, 1, 1, 1};
        vector<int> d2 = {1, 0, -1, 1, -1, 1, 0, -1};
        int row = board.size();
        int col = row ? board[0].size() : 0;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                int  count = 0;
                for(int k = 0; k < 8; k++) {
                    int new_row = i + d1[k];
                    int new_col = j + d2[k];
                    if(new_row >= 0 && new_row < row && new_col >= 0 && new_col < col && (board[new_row][new_col] == 1 || board[new_row][new_col] == 2)) {
                        count++;                        
                    }
                }   
                if(board[j] && (count < 2 || count > 3)) {
                    board[j] = 2;
                }
                else if(!board[j] && count == 3) {
                    board[j] = 3;
                }
                        
            }
        }
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                board[j] = board[j] % 2;
            }
        }
    }
};

4. Letter of phone number

class Solution {
public:



const vector<string> keyboard { " ", "", "abc", "def",
            "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
void dfs(string& digits, int cur, string path, vector<string>& res) {
    if(cur == digits.size()) {
        res.push_back(path);
        return;
    }
    for(char c: keyboard[digits[cur] -  '0'])
        dfs(digits, cur + 1, path + c, res);
   
}
    vector<string> letterCombinations(string digits) {
        if(digits == "")
            return {};
        vector<string> res;
        dfs(digits, 0, "", res);
        return res;
    }
};


6. word break II
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
class Solution {
public:
    unordered_map<string, vector<string>> map;
    vector<string> combine(string s, vector<string>& vec) {
        for(int i = 0; i < vec.size(); i++) {
            vec += " ";
            vec += s;
        }
        return vec;
    }
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        if(map.find(s) != map.end())
            return map;
        vector<string> res;
        if(wordDict.find(s) != wordDict.end())
            res.push_back(s);
        for(int i = 1; i < s.size(); i++) {
            string word = s.substr(i);
            if(wordDict.find(word) != wordDict.end()) {
                string front = s.substr(0, i);
                vector<string> tmp_res = wordBreak(front, wordDict);
                vector<string> new_res = combine(word, tmp_res);
                res.insert(res.end(), new_res.begin(), new_res.end());
            }
        }
        map = res;
        return res;
    }
};

7.  find duplicate files
. from: 1point3acres.com/bbs
BFS


有些file 没
有 permission 去访问, 会有 exception (isreadable)

DFS 会stackoverflow

"这题关键不是考你的BFS,虽然你需要用BFS或者DFS先把所有文件先找出来。找出来之后怎么除重才是真正他们想考你的地方。
. 1point3acres.com/bbs
最简单的方法:
用MD5 hash值做hashmap的key,然后对key相同的文件两两比较(所以MD5有可能会碰撞,所以需要double check)
这样做的坏处:就算目录里只有少量的duplicated的文件,每个文件都还是需要从头到尾扫描一遍(计算MD5)。"

改进的办法:
可以先按照size分组,再按照前1K个bytes作为hashmap的key将文件分组,然后每个文件数不少于2的组按照[1K+1, 2K]这接下来的1K个bytes分组……然后按照这个思路一直分下去。
这样做的好处:在现实中,一般目录里面大部分的文件都是unique的,只有少量duplicate,在这个逐层分组的过程中,大量的文件都会在前几步的分组里面被分到一个只有它自己的组里,对于这些文件,我们就已经不再需要扫描它后面的部分





input: string

vector<string> find_all_file(string input) {
        queue<string> q;
        q.insert(input);
        vector<string> res;
        while(!q.empty()) {
                string tmp = q.top();
                q.pop();
                if(is_readable(tmp)) {
                        if(is_directory(tmp)) {
                                vector<string> list_of_files = get_files(tmp);
                                for(string s : list_of_files) {
                                        q.push(s);
                                }
                        }
                        else
                                res.push_back(tmp);
                }
        }
        return res;
}

vector<vector<string>> find_same_file(vector<string>& value, int start, int size) {
        vector<vector<string>> res;
        int interval = min(1000, size - start);
        unordered_map<int, vector<string>> m;
        if(start >= size)
                return {value};
        for(int i = 0; i < value.size(); i++) {
                int hash_key = get_hash(value, start, interval);
                m[hash_key].push_back(value);
        }
        if(m.size() == value.size())
                return res;
        for(auto t = m.begin(); t != m.end(); t++) {
                if(t->second.size() > 1) {
                        vector<vector<string>> vec = find_same_file(it->second, start + interval, size);
                        res.insert(res.end(), vec.begin(), vec.end());
                }
        }
        return res;
}
vector<vector<string>> find_dul_files(string input) {
        vector<string> files = find_all_files(input);
        vector<vector<string>> res;
        unordered_map<int, vector<string>> map;
        for(int i = 0; i < files.size(); i++) {
                map[get_size(files)].push_back(files)
        }
        for(auto it = map.begin(); it != map.end(); it++) {
                if((it->second).size() > 1) {
                        vector<vector<string>> tmp_res = find_same_file(it->second, 0, it->first);
                        res.insert(res.end(), tmp_res.begin(), tmp_res.end());
                }
        }
        return res;
       
}

. 鍥磋鎴戜滑@1point 3 acres



评分

4

查看全部评分

jigsaw_Becky 发表于 2016-11-7 03:50:06 | 显示全部楼层
面试官是觉得你答的太好了么?
回复 支持 反对

使用道具 举报

Crazy_fight 发表于 2016-11-13 15:18:58 | 显示全部楼层
楼主一轮答了这么多?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 23:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表