Dropbox挂经换米

zsll

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

1. LC379. Design Phone Directory
这题是主要的挂因，10分钟之内顺利写了常见的两种写法

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

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

er见面具体描述职位细节，我假装很有兴趣。

对方最后的评价是总体很好，但1. 代码需要hint 2. 代码有detail的问题 3. 没有什么交流火花（这也算）。据了。
Dropbox的面经题不多，这回碰到的我都看过并且写过，但写的不深入，或者没用这么多方法写。希望以后发面经的同学能发些细节，帮助准备的同学好多加注意。

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-12 07:47:08

milolyfcmu 发表于 2016-12-11 01:12
楼主可否详细描述下爬虫这题？没懂是问什么要做什么？

爬虫就是提供一个List<String> parse(String url) function还有一个初始url，要求遍历所有的子url。

zsll

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

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

Didi313

请问楼主Onsite之后多久收到的消息？

zsll

横跨感恩节，三个工作日有的消息，她本来答应一天就行。没问冷冻期的事。

小逻辑

问下楼主，Design Phone Directory这个怎么用page table来做？？page table??

JunoJ

word 天，这也太难了，下个月电面，心慌慌

小逻辑

哦哦，我明白了，LZ人真nice！因为我对page table的概念不是很熟，所以开始一头雾水怎么做，现在感觉道理上跟用TREE差不多哈~

补充内容 (2016-12-8 12:21):
哦对了，你说注意使用内存的意思是面试官会问的很具体存储大小什么的嘛？

小逻辑

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

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

zsll

小逻辑发表于 2016-12-8 12:19
哦哦，我明白了，LZ人真nice！因为我对page table的概念不是很熟，所以开始一头雾水怎么做，现在感觉道理上 ...

要具体到给1m id 需要多少MB内存

Dropbox挂经换米

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

评分

浏览过的版块

	2垅无效楼层，该帖已经被删除