Dropbox挂经换米

在浙里 · 2016-12-20 20:49:43

提示: 作者被禁止或删除内容自动屏蔽

zsll · 2016-12-23 06:38:03

274132666 发表于 2016-12-20 20:05
楼主之前电面面的什么题呀

电面我直接贴代码了，一共两轮，都是面经常见的：1是找重复文件，2是给电话号码找能由字典中的词组成的号码

Recruiter feedback：
Coding needs hints
Not enough attention to detail
Interviewers think it's flat, it will need more spikes
Interview Outline：
1 presentation
9:45 - 5:45
2 - 3 coding questions (data structure)
concurrency
coding about multi-threading, event driving program
1 cultrual interview (your recent project, how you tackle problem, how you work with your team, your personal passion, impact other people in the company
What if your team is not doing well. Do you tell your manager. Do you do nothing
How do you
)
project deep dive interview (15 - 25minutes, drive, how to refine)
1 hiring manager (professional development)
Phone interview 1：
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
//1 m, phone issue
//I am starting my phone
// 👍
//Something wrong, call failed
// Yeah, hm, let's see if my personal phone works...
// Can you join https://bluejeans.com/4273619641
class Solution {
public static void main(String[] args) {
print();
}
static List<List<String>> findDuplicates(String path);
List<List<String>> res = new ArrayList<List<String>>();
if(path != null && path.length() > 0) {
List<List<String>> files = findFileOfSameSize(path);
for(List<String> filegroup : files) {
HashMap<String, List<String>> h = new HashMap<String, List<String>>();
HashSet<String> s = new HashSet<String>();
for(String f : filegroup) {
String hash = checksum(f);
if(!h.containsKey(hash)) {
h.put(hash, new ArrayList<String>());
}
h.get(hash).add(f);
if(h.get(hash).size() > 1) {
s.add(hash);
}
}
for(String hash : s) {
res.add(h.get(hash);
}
}
}
return res;
}
static List<List<String>> findFileOfSameSize(String path) {
List<List<String>> res = new ArrayList<List<String>>();
if(path != null && path.length() > 0) {
Stack<String> s = new Stack<String>();
s.push(path);
HashMap<Integer, List<String>> h = new HashMap<Integer, List<String>>();
HashSet<Integer> set = new HashSet<Integer>();
while(!s.empty()) {
String cur = s.pop();
if(!isDir(cur)) {
int size = getFileSize(cur);
if(!h.containsKey(size)) {
h.put(size, new ArrayList<String>());
}
h.get(size).add(cur);
if(h.get(size).size() > 1) {
set.add(size);
}
} else {
List<String> children = listDir(cur);
for(String child : children) {
s.push(child);
}
}
}
for(Integer size : set) {
res.add(h.get(size));
}
}
return res;
}
}
// List<List<String>> findDuplicates(String path);
// /foo/bar.txt -> 'hello'
// /baz.txt -> 'bye'
// /bat.txt -> 'hello'
// /three.four -> 'hello'
// '/' -> [['/foo/bar.txt', '/baz.txt', '/three.four']]
//String checkSum(String path)
// bool isDir(String path)
// int getFileSize(String filePath)
// List<String> listDir(String path)
// String joinPath(directory, path)
//If there is a symlink 怎么办，防止loop
Phone Interview 2：
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
1 - nothing
2 - ABC
3 - DEF
4 - ...
...
7 - PQRS
...
9 - WXYZ
0 - nothing
1-800-FASTCAR
1-800-DROPBOX
1-800-376....
4667364 -> what word(s) can be made from this number (return as list)
dictionary is 50k
*/
class Solution {
public static void main(String[] args) {
HashSet<String> dict = new HashSet<String>();
dict.add("fast");
dict.add("car");
dict.add("drop");
dict.add("box");
dict.add("exactly"); //3922859
dict.add("ken");
dict.add("park");
dict.add("kenpark");
//HashSet<String> res = find("3922859", dict);
HashSet<String> res = find("5367275", dict);
//dfs(dict, res, new StringBuffer(), "222");
for(String s : res) {
System.out.println(s);
}
}
static void find2(String query, HashSet<String> dict, int start, List<HashSet<String>> pre, HashSet<String> res) {
if(start == query.length()) {
dfs2(res, pre, new StringBuffer(), 0);
} else {
for(int i = start + 3; i < query.length(); i++) {
String subQuery = query.substring(start, i);
HashSet<String> subRes = new HashSet<String>();
dfs(dic, subRes, new StringBuffer(), subQuery);
if(subRes.size() > 0) {
pre.add(subRes);
find2(query, dict, i, pre);
pre.remove(pre.size() - 1);
}
}
}
}
void dfs2(HashSet<String> res, List<HashSet<String>> pre, StringBuffer sb, int start) {
if(start == pre.size()) {
res.add(new String(sb));
} else {
for( String s : pre.get(start)) {
int oriLen = sb.length();
sb.append(s);
dfs2(res, pre, sb, start + 1);
sb.setLength(oriLen);
}
}
}
static HashSet<String> find(String query, HashSet<String> dict) {
HashSet<String> res = new HashSet<String>();
if(query != null && query.length() == 7 && dict != null) {
String a1 = query.substring(0, 4), b1 = query.substring(4, 7);
HashSet<String> firstRes = findHelper(a1, b1, dict);
res.addAll(firstRes);
a1 = query.substring(0, 3);
b1 = query.substring(3, 7);
HashSet<String> secRes = findHelper(a1, b1, dict);
res.addAll(secRes);
HashSet<String> thirdRes = new HashSet<String>();
dfs(dict, thirdRes, new StringBuffer(), query);
res.addAll(thirdRes);
}
return res;
}
static HashSet<String> findHelper(String a1, String b1, HashSet<String> dict) {
HashSet<String> a1Res = new HashSet<String>();
dfs(dict, a1Res, new StringBuffer(), a1);
HashSet<String> b1Res = new HashSet<String>();
dfs(dict, b1Res, new StringBuffer(), b1);
HashSet<String> res = new HashSet<String>();
for(String a : a1Res) {
for(String b : b1Res) {
res.add(a + b);
}
}
return res;
}
static void dfs(HashSet<String> dict, HashSet<String> res, StringBuffer sb, String query) {
if(sb.length() == query.length()) {
String word = new String(sb);
if(dict.contains(word)) {
res.add(word);
}
} else {
char [][] keys = {
{' '},
{' '},
{'a','b','c'},
{'d','e','f'},
{'g','h','i'},
{'j','k','l'},
{'m','n','o'},
{'p','q','r','s'},
{'t','u','v'},
{'w','x','y','z'}
};
int pos = sb.length();
char [] chars = keys[query.charAt(pos) - '0'];
for(char c : chars) {
sb.append(c);
dfs(dict, res, sb, query);
sb.deleteCharAt(sb.length() - 1);
}
}
}
}

复制代码

zsll · 2016-12-23 06:40:38

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限或查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

feyhi · 2016-12-23 15:22:49

想了一会，所以page table是存phone directory的page的table，不是内存的page table？不然就是黑科技了>.<
可是O(N/1000)还是O(N)呀，只是降了系数

shelly1996

zsll 发表于 2016-12-23 06:38
电面我直接贴代码了，一共两轮，都是面经常见的：1是找重复文件，2是给电话号码找能由字典中的词组成的号 ...

楼主好人，谢楼主！

tommyhahn

楼主请问电面1 中如果有symlink 是怎么解决的啊？

刘心惠

请问下楼主，他家new grad也会要求多线程之类的问题吗？一提多线程，怎么那么慌

shelly1996

刘心惠发表于 2017-2-8 16:19
请问下楼主，他家new grad也会要求多线程之类的问题吗？一提多线程，怎么那么慌

基本没准备去面的，不知道啊

补充内容 (2017-2-8 22:36):
无视我....

zsll

tommyhahn 发表于 2017-1-16 13:27
楼主请问电面1 中如果有symlink 是怎么解决的啊？

这属于写完以后瞎聊的问题我就说用hash

zsll

刘心惠发表于 2017-2-8 16:19
请问下楼主，他家new grad也会要求多线程之类的问题吗？一提多线程，怎么那么慌

我不是new grad 所以不敢保证

Dropbox挂经换米

评分

浏览过的版块