今天刚面的Linkedin第一轮电面, 发面经

原帖地址:一亩三分地

我的情况是已经工作了一年,h1b也到手了,于是准备跳槽, 题还没怎么刷突然Linkedin他们自己的Recruiter在Linkedin里面联系我和我们公司好几个engineer(我们都是好基友所以大家互相知道都无所谓), 我们就集体面试啰, 每天下班刷两小时题准备了三周, 今天的电面, 好久没面试了有点紧张.

面试官是一个Hawaiian, 十几年工作经验但是在Linkedin就一年多. 今天在Remote上班, 家里还有狗叫(我也是醉了).

一开始互相讲了下各自的role和working experience, 然后叫我讲了一个在公司最challenging的project, 就blabla…感觉工作一年多口语锻炼得还可以就没什么大碍.
然后剩45分钟开始做题.

第一题:
public interface TwoSum {
/**
* Stores @param input in an internal data structure.
*/
void store(int input);

/**
* Returns true if there is any pair of numbers in the internal data structure which
* have sum @param val, and false otherwise.
* For example, if the numbers 1, -2, 3, and 6 had been stored,
* the method should return true for 4, -1, and 9, but false for 10, 5, and 0
*/
boolean test(int val);
}

我的回答: (因为是interface, 所以要implements所有的virtual function).
public class TwoSumTest implements TwoSum{
private HashMap map;
private ArrayList list;

public TwoSumTest(){
map = new HashMap();
list = new ArrayList();
}

public void store(int input){
map.put(input,1);
list.add(input);
}

public boolean test(int val){
for (int i=0; i< list.size(); i++){ int key = list.get(i); if (map.containsKey(val-key)) return true; } return false; } } /////用了HashMap没用HashSet是怕要follow up说有duplicates, 结果没有, 也算了不影响逻辑. 第二题: follow up, 如果我要实现O(1)的test怎么办? 回答: 那store就不能保证O(1)了,每次存一个新数的时候,map要存前面所有数与这个数的和. 就是把可能的2 sum结果都枚举出来丢到map里 public class TwoSumTest2 implements TwoSum{ private HashMap map;
private ArrayList list;
int lastIndex;

public TwoSumTest2(){
map = new HashMap();
list = new ArrayList();
lastIndex = 0;
}

public void store(int input){
list.add(input);
for(int i =1; i<= lastIndex;i++){ map.put(list.get(i)+input,1); } lastIndex++; } public boolean test(int val){ if (map.containsKey(val)){ return true; } return false; } } //再次声明用的HashMap没用HashSet是因为怕follow up.不过也没问,面试官说也不用改了没关系. 第三题: 老生常谈WordDistance, 我问了, assume WordOne != WordTwo, 那就再简单不过了 /* This class will be given a list of words (such as might be tokenized * from a paragraph of text), and will provide a method that takes two * words and returns the shortest distance (in words) between those two * words in the provided text. * Example: * WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick")); * assert(finder.distance("fox","the") == 3); * assert(finder.distance("quick", "fox") == 1); * * "quick" appears twice in the input. There are two possible distance values for "quick" and "fox": * (3 - 1) = 2 and (4 - 3) = 1. * Since we have to return the shortest distance between the two words we return 1. */ public class WordDistanceFinder { public WordDistanceFinder (List words) {
// implementation here
}
public int distance (String wordOne, String wordTwo) {
// implementation here
}
}

我的回答:
public class WordDistanceFinder {
private String[] words2;

public WordDistanceFinder (List words) {
// implementation here
words2 = new String[words.size()];
for(int i = 0; i< words.size()-1; i++){ words2[i] = words.get(i); } } public int distance (String wordOne, String wordTwo) { // implementation here int p =-1, q =-1, min = Integer.MAX_VALUE; for (int i =0 ;i< words2.size()-1; i++){ if (words2[i].equals(wordOne)) p=i; if (words2[i].equals(wordsTwo)) q=i; if (p >0 q>0 ){
min = Math.min(Math.abs(p-q), min);
}
}
return min;
}
}

//感觉第一个constructor可以直接就private List然后把words pass 过去就行..当时就走直觉了..

之后时间差不多了就没继续出题了,问我有没有什么问题要问就blabla…

总体感觉和听几个同事说的, 感觉在职的题目简单一些似乎…完全没有超纲, 全在leetcode上和地里.

不过他们的题的特色就是总是会写一个完整的class, input总是一个个数而不是一整个数组给你, 所以用java的同学们就好好准备下面向对象啰.