p*y
发帖数: 108 | 1 店面是两个中国人,一开始知道是国人还比较欣喜. 结果证明完全不是这么回事,反而感
觉很严格,最终挂了. 请大家分析下为啥挂? 难道第二题没有按面试官心中理想的答案
在面试时给他写出来? 以后看来一定要注意时间.
1. two sum
一开始根据题目理解以为是排好序的数组, 于是从两头开始找:
boolean twoSum(int[] nums, int sum){
if(nums==null || nums.length<2)
return false;
int low = 0, high = nums.length-1;
while(low
if( (nums[low]+nums[high]) == sum ){
return true;
}else if((nums[low]+nums[high]) < sum){
low++;
}else{
high--;
}
}
return false;
}
等我写好告之数组非排好序, 于是马上用hashmap方法写出:
boolean twoSum2(int[] nums, int sum){
if(nums==null || nums.length<2)
return false;
HashMap map = new HashMap();
for(int i=0; i
if(!map.containsKey(nums[i])){
map.put(sum-nums[i], i);
}else{
return true;
}
}
return false;
}
第二题也比较常见,CC150原题, 找俩字符串在一段文字中最近的距离:
直接用CC150解法, 用两个index比较得出Math.abs(index1-index2), update最小距离.
写好后提示要是 cat dog cloud dog dog dog......,即后面有million个dog, 是否不
用比较整个文章.
回答说用map提早存储每个单词的index, 然后在map中找到单词比较, 在讨论后最坏情
况下复杂度也是O(n).
由于没有时间写代码了所以这样结速了.
结果几个小时后recruitor打电话要求把hashmap的解法补上发给他, 自个马上在IDE上
写了一个并调试后发给他:
public class WordDistanceFinder {
String[] strs;
public WordDistanceFinder (List words) {
strs = new String[words.size()];
for(int i=0; i
strs[i] = words.get(i);
}
public int distance (String wordOne, String wordTwo) {
HashMap> map = new HashMap
Integer>>();
if(strs==null || strs.length<2)
return 0;
for(int i=0; i
if(strs[i].equals(wordOne) || strs[i].equals(wordTwo)){
ArrayList list;
if(map.containsKey(strs[i])){
list = map.get(strs[i]);
}else{
list = new ArrayList();
}
list.add(i);
map.put(strs[i], list);
}
}
ArrayList list1 = map.get(wordOne);
ArrayList list2 = map.get(wordTwo);
// if(list1.size()==0 || list2.size()==0) //check the null
if (list1==null || list2==null || list1.size() == 0 || list2.size()
== 0)
return 0;
int index1=0, index2=0;
int minDis = Integer.MAX_VALUE;
while(index1
if(Math.abs(list1.get(index1)-list2.get(index2))
minDis = Math.abs(list1.get(index1)-list2.get(index2));
if(list1.get(index1)
index1++;
else
index2++;
}
return minDis;
}
} |
S******2
发帖数: 248 | |
g********t
发帖数: 53 | 3 Two Sum
LC原题就不是排好序的，楼主想当然了。不过还好，code都挺好的
第二题求问原题是什么样子的？ 感觉楼主都答出来了，不至于挂啊 |
p*y
发帖数: 108 | 4 他有一个奇怪的初始化函数, 什么
fun(1) 1
fun(2) 1, 2
fun(3) 1, 2, 3
以至我以为比如fun(n)是 1, 2, 3, 4,...,n.
是啊 我也感觉没问题 至少给二面.
【在 g********t 的大作中提到】
: Two Sum
: LC原题就不是排好序的，楼主想当然了。不过还好，code都挺好的
: 第二题求问原题是什么样子的？ 感觉楼主都答出来了，不至于挂啊
|
p*y
发帖数: 108 | 5 原题就是给一些单词, 求两个单词的最近距离.
【在 g********t 的大作中提到】
: Two Sum
: LC原题就不是排好序的，楼主想当然了。不过还好，code都挺好的
: 第二题求问原题是什么样子的？ 感觉楼主都答出来了，不至于挂啊
|
g********r
发帖数: 89 | 6 请问第二题，用hashmap的话，不是要事先建立好hashmap么？也就是说在constructor
里面建立好，然后每次调用计算diat的函数的时候，直接lookup hashmap，然后用
index table算。LZ为什么要把建立hashmap的code放到计算dist的函数里呢？
【在 p*y 的大作中提到】
: 店面是两个中国人,一开始知道是国人还比较欣喜. 结果证明完全不是这么回事,反而感
: 觉很严格,最终挂了. 请大家分析下为啥挂? 难道第二题没有按面试官心中理想的答案
: 在面试时给他写出来? 以后看来一定要注意时间.
: 1. two sum
: 一开始根据题目理解以为是排好序的数组, 于是从两头开始找:
: boolean twoSum(int[] nums, int sum){
: if(nums==null || nums.length<2)
: return false;
: int low = 0, high = nums.length-1;
: while(low
|
w******n
发帖数: 61 | 7 第二题是不是可以直接两个pointer扫过去o1的空间复杂度
[在 ppy (ppy) 的大作中提到：]
：店面是两个中国人,一开始知道是国人还比较欣喜. 结果证明完全不是这么回事,反而
感觉很严格,最终挂了. 请大家分析下为啥挂? 难道第二题没有按面试官心中理想的答案
：在面试时给他写出来? 以后看来一定要注意时间.
：........... |
r*****3
发帖数: 27 | 8 第二题面试官意思是不是希望你加个判断 比如如果当前最小距离是1的话 那么我后面
都不用搜了 |
p*y
发帖数: 108 | 9 距离不一定1啊 多少都可能
【在 r*****3 的大作中提到】
: 第二题面试官意思是不是希望你加个判断 比如如果当前最小距离是1的话 那么我后面
: 都不用搜了
|
r*******e
发帖数: 971 | 10 楼主你挂得不冤。我是面试官也会挂掉你的。
1）数组是否排序要提前问面试官，自己想当然属于lacking communication
然后面试官在你声明low 与high 两个变量时候没有提醒你么？还是说你没有提前跟面
试官说你的方法？？
2）速度不够快。否则第二题即使只有15分钟也能写个大概的。
3）如果楼主不服，我们现在来说代码
1：if(nums==null || nums.length<2) return false;
这里可能是需要抛出异常的 throw new NullPointerException（）；
2：if( (nums[low]+nums[high]) == sum ){ return true;｝。。。
更好点的办法是在循环外面声明一个变量temp，temp ＝ nums［low］＋nums［high］
否则每次循环都得多算一次。
3.HashMap map = new HashMap();
应该写成Map map = new HashMap<>();这样可以显示你理解java
中的多态
4.第二道题根本不需要Map来储存位置的。你只需要对每个关键词各保留一个位置即可
。从list的末尾往前遍历，若发现关键词，更新位置，计算距离。若距离为最小，则保
留。
改一下：还是需要的，不过可以在Constructor实现。
5. strs = new String[words.size()];
for(int i=0; i
strs[i] = words.get(i);
为啥要再建立一个数组？？这个数组跟已有的List没有区别啊？然后一定要建立一个新
数组的话，为何要遍历一遍么？List有toArray这个方法啊？然后一定要遍历的话，为
何要用get（）呢？如果原有List是LinkedList呢？
6. if(map.containsKey(strs[i])){
list = map.get(strs[i]);
}else{
list = new ArrayList();
}
list.add(i);
map.put(strs[i], list);
最后一句会造成重复操作。
也就这些了。希望楼主在不爽之后能多多练习，早拿offer
|
|
|
p*y
发帖数: 108 | 11 应该就是这个原因 要不constructor函数实在没用. 看来真是做到标准答案才行
constructor
【在 g********r 的大作中提到】
: 请问第二题，用hashmap的话，不是要事先建立好hashmap么？也就是说在constructor
: 里面建立好，然后每次调用计算diat的函数的时候，直接lookup hashmap，然后用
: index table算。LZ为什么要把建立hashmap的code放到计算dist的函数里呢？
|
g********r
发帖数: 89 | 12 我觉得这些细节面试官不会在意的。LZ的问题是没有理解第二题面试官的题意：为了避
免每一次计算dist go through entire list，把O（n）复杂度转移到构造函数里面。
这样的话，就解决了heavy request on computing dist.
包括twosum那题啊，两个函数：store(), twosum(), 取决于哪个调用更频繁，
algorithm也不一样。比如bool twosum()调用频繁，那么就应该存key为sum的map。这
时，store的复杂度就升为O（n）。
【在 r*******e 的大作中提到】
: 楼主你挂得不冤。我是面试官也会挂掉你的。
: 1）数组是否排序要提前问面试官，自己想当然属于lacking communication
: 然后面试官在你声明low 与high 两个变量时候没有提醒你么？还是说你没有提前跟面
: 试官说你的方法？？
: 2）速度不够快。否则第二题即使只有15分钟也能写个大概的。
: 3）如果楼主不服，我们现在来说代码
: 1：if(nums==null || nums.length<2) return false;
: 这里可能是需要抛出异常的 throw new NullPointerException（）；
: 2：if( (nums[low]+nums[high]) == sum ){ return true;｝。。。
: 更好点的办法是在循环外面声明一个变量temp，temp ＝ nums［low］＋nums［high］
|
r*******e
发帖数: 971 | 13 你说得在理，确实应该在constructor 实现。
【在 g********r 的大作中提到】
: 我觉得这些细节面试官不会在意的。LZ的问题是没有理解第二题面试官的题意：为了避
: 免每一次计算dist go through entire list，把O（n）复杂度转移到构造函数里面。
: 这样的话，就解决了heavy request on computing dist.
: 包括twosum那题啊，两个函数：store(), twosum(), 取决于哪个调用更频繁，
: algorithm也不一样。比如bool twosum()调用频繁，那么就应该存key为sum的map。这
: 时，store的复杂度就升为O（n）。
|
g********r
发帖数: 89 | 14 LZ你two sum那题双指针O(nlogn)的code，面试官就让你写到底了啊？能描述一下当时
的情形吗？因为这题完全不是考two pointer的，很好奇面试官为什么没有拦住你，你
写code之前跟他交流了你的双指针的想法了没有？
【在 p*y 的大作中提到】
: 应该就是这个原因 要不constructor函数实在没用. 看来真是做到标准答案才行
:
: constructor
|
L*****1
发帖数: 34 | 15 请问LZ，说的是CC150具体哪个题啊？怎么感觉像LC的word ladder？谢谢！ |
l*****a
发帖数: 14598 | 16
发信人: reclapple (加菲鲸), 信区: JobHunting
标 题: Re: 最新L家面经
发信站: BBS 未名空间站 (Mon Nov 10 19:41:25 2014, 美东)
楼主你挂得不冤。我是面试官也会挂掉你的。
1）数组是否排序要提前问面试官，自己想当然属于lacking communication
然后面试官在你声明low 与high 两个变量时候没有提醒你么？还是说你没有提前跟面
试官说你的方法？？
2）速度不够快。否则第二题即使只有15分钟也能写个大概的。
3）如果楼主不服，我们现在来说代码
1：if(nums==null || nums.length<2) return false;
这里可能是需要抛出异常的 throw new NullPointerException（）；
==> 这个真的需要吗？我认为不需要吧。
3.HashMap map = new HashMap();
应该写成Map map = new HashMap<>();这样可以显示你理解java
中的多态
==> 这个题真的需要Map吗？HashSet足够了吧？没看见存那个index有什么意义
4.第二道题根本不需要Map来储存位置的。你只需要对每个关键词各保留一个位置即可
。从list的末尾往前遍历，若发现关键词，更新位置，计算距离。若距离为最小，则保
留。
改一下：还是需要的，不过可以在Constructor实现。
==> 如果只调用一次，map的意义不大
如果函数调用无数次，还是用Map>记下每个string的
index
然后取出两个list做compare好一些
【在 r*******e 的大作中提到】
: 楼主你挂得不冤。我是面试官也会挂掉你的。
: 1）数组是否排序要提前问面试官，自己想当然属于lacking communication
: 然后面试官在你声明low 与high 两个变量时候没有提醒你么？还是说你没有提前跟面
: 试官说你的方法？？
: 2）速度不够快。否则第二题即使只有15分钟也能写个大概的。
: 3）如果楼主不服，我们现在来说代码
: 1：if(nums==null || nums.length<2) return false;
: 这里可能是需要抛出异常的 throw new NullPointerException（）；
: 2：if( (nums[low]+nums[high]) == sum ){ return true;｝。。。
: 更好点的办法是在循环外面声明一个变量temp，temp ＝ nums［low］＋nums［high］
|
l*****a
发帖数: 14598 | 17
你这两个函数说得是别的需求把
LZ这题目不是就要求写一个
【在 g********r 的大作中提到】
: 我觉得这些细节面试官不会在意的。LZ的问题是没有理解第二题面试官的题意：为了避
: 免每一次计算dist go through entire list，把O（n）复杂度转移到构造函数里面。
: 这样的话，就解决了heavy request on computing dist.
: 包括twosum那题啊，两个函数：store(), twosum(), 取决于哪个调用更频繁，
: algorithm也不一样。比如bool twosum()调用频繁，那么就应该存key为sum的map。这
: 时，store的复杂度就升为O（n）。
|
l********g
发帖数: 372 | 18 第一题应该是leetcode上头因为输出是要index所以才用了Map来做
lz这道只判断是否exist的，确实只要Set就够了 |
y*********i
发帖数: 244 | 19 2 sum这种题目是不是一定要写的bug free一次成型
【在 p*y 的大作中提到】
: 店面是两个中国人,一开始知道是国人还比较欣喜. 结果证明完全不是这么回事,反而感
: 觉很严格,最终挂了. 请大家分析下为啥挂? 难道第二题没有按面试官心中理想的答案
: 在面试时给他写出来? 以后看来一定要注意时间.
: 1. two sum
: 一开始根据题目理解以为是排好序的数组, 于是从两头开始找:
: boolean twoSum(int[] nums, int sum){
: if(nums==null || nums.length<2)
: return false;
: int low = 0, high = nums.length-1;
: while(low
|
p*y
发帖数: 108 | 20 这次遇到到得面试官很少说话 所以很多时候我代码写好之后再提出问题 包括第二个题
我也是用两个index解法写完之后才提示我 导致时间不够. 看来以后一定得注意面试官
的意图和题目的细节
【在 g********r 的大作中提到】
: 我觉得这些细节面试官不会在意的。LZ的问题是没有理解第二题面试官的题意：为了避
: 免每一次计算dist go through entire list，把O（n）复杂度转移到构造函数里面。
: 这样的话，就解决了heavy request on computing dist.
: 包括twosum那题啊，两个函数：store(), twosum(), 取决于哪个调用更频繁，
: algorithm也不一样。比如bool twosum()调用频繁，那么就应该存key为sum的map。这
: 时，store的复杂度就升为O（n）。
|
|
|
l*****a
发帖数: 14598 | 21 这个题目如果还写出很多问题的话人家真的没法给你过
【在 y*********i 的大作中提到】
: 2 sum这种题目是不是一定要写的bug free一次成型
|
r******j
发帖数: 92 | 22 这样是不是可以？
public int distance (String[] words, String wordOne, String wordTwo) {
if (wordOne.equals(wordTwo)) {
return 0;
}
int minDistance = Integer.MAX_VALUE;
int lastOne = -1;
int lastTwo = -1;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(wordOne)) {
if (lastTwo != -1) {
int curMin = i - lastTwo;
minDistance = Math.min(minDistance, curMin);
}
lastOne = i;
} else if (words[i].equals(wordTwo)) {
if (lastOne != -1) {
int curMin = i - lastOne;
minDistance = Math.min(minDistance, curMin);
}
lastTwo = i;
}
}
return minDistance;
} |
r*******e
发帖数: 971 | 23 有bug
//Need to check if words contains wordOne
【在 r******j 的大作中提到】
: 这样是不是可以？
: public int distance (String[] words, String wordOne, String wordTwo) {
: if (wordOne.equals(wordTwo)) {
: return 0;
: }
: int minDistance = Integer.MAX_VALUE;
: int lastOne = -1;
: int lastTwo = -1;
:
: for (int i = 0; i < words.length; i++) {
|
r******j
发帖数: 92 | 24 刚才发的时候还想at一下你，让你给点意见，你给楼主提的建议都非常好，忠言逆耳。
。。
有bug啊。。。丢人了。。。我查查！！
【在 r*******e 的大作中提到】
: 有bug
:
: //Need to check if words contains wordOne
|
r******j
发帖数: 92 | 25 哦！其实刚才我想这个问题了，没想出太好看的解决方案，似乎还是给扫一遍，就没写
。。。就当面试官告诉我都直接返回0就好了。。。哈哈
【在 r*******e 的大作中提到】
: 有bug
:
: //Need to check if words contains wordOne
|
p***y
发帖数: 637 | 26 1。没理清要求匆忙写代码
2。发现问题后又匆忙再写个代码
不好帮啊，on site给了也很难过。不过如果我是面试官，会给点feedback.
"" low="0," high="nums.length-1;" :="">
="">
【在 p*y 的大作中提到】
: 店面是两个中国人,一开始知道是国人还比较欣喜. 结果证明完全不是这么回事,反而感
: 觉很严格,最终挂了. 请大家分析下为啥挂? 难道第二题没有按面试官心中理想的答案
: 在面试时给他写出来? 以后看来一定要注意时间.
: 1. two sum
: 一开始根据题目理解以为是排好序的数组, 于是从两头开始找:
: boolean twoSum(int[] nums, int sum){
: if(nums==null || nums.length<2)
: return false;
: int low = 0, high = nums.length-1;
: while(low
|
c**********8
发帖数: 1052 | 27
可能bar就这样
我以前面L的时候，两个店面都是45分钟3题最优解+coding出来无bug的节奏
因为都是原题，没有特殊题，想的快写的快，都是第二天通知下一步
结果onsite挂了，感觉onsite重心在扯皮（经验）不是coding
【在 p*y 的大作中提到】
: 店面是两个中国人,一开始知道是国人还比较欣喜. 结果证明完全不是这么回事,反而感
: 觉很严格,最终挂了. 请大家分析下为啥挂? 难道第二题没有按面试官心中理想的答案
: 在面试时给他写出来? 以后看来一定要注意时间.
: 1. two sum
: 一开始根据题目理解以为是排好序的数组, 于是从两头开始找:
: boolean twoSum(int[] nums, int sum){
: if(nums==null || nums.length<2)
: return false;
: int low = 0, high = nums.length-1;
: while(low
|
y**********a
发帖数: 824 | 28
这个算法，如果 document 大一点不是很慢么？真要快的话，就把所有的处理都放在
constructor 里面。用 map 存两个词的index 差最小值。
【在 r******j 的大作中提到】
: 这样是不是可以？
: public int distance (String[] words, String wordOne, String wordTwo) {
: if (wordOne.equals(wordTwo)) {
: return 0;
: }
: int minDistance = Integer.MAX_VALUE;
: int lastOne = -1;
: int lastTwo = -1;
:
: for (int i = 0; i < words.length; i++) {
|
g*****e
发帖数: 3417 | 29 没有abs()
【在 r******j 的大作中提到】
: 这样是不是可以？
: public int distance (String[] words, String wordOne, String wordTwo) {
: if (wordOne.equals(wordTwo)) {
: return 0;
: }
: int minDistance = Integer.MAX_VALUE;
: int lastOne = -1;
: int lastTwo = -1;
:
: for (int i = 0; i < words.length; i++) {
|
g*****e
发帖数: 3417 | 30 已经找到当前str1,str2的最小距离了，就不用继续找了
【在 p*y 的大作中提到】
: 距离不一定1啊 多少都可能
|
|
|
y**********a
发帖数: 824 | 31 class MinDist{
Map dist;
String separator;
int minDist(String s1, String s2, Map>map) {
dist=new HashMap<>();
Listl1,l2;
if ((l1=map.get(s1))==null||(l2=map.get(s2))==null) return -1;
int rel=Integer.MAX_VALUE;
for(int i1=0,i2=0;i1
int v1=l1.get(i1),v2=l2.get(i2),dif=v1-v2;
rel=Math.min(rel,Math.abs(dif));
if (rel==1) return 0;
else if (dif<0) ++i1;
else ++i2;
}
return rel;
}
public MinDist(List doc, String separator) {
Map> map=new HashMap<>();
int k=0;
for (String s:doc) {
Listlist=map.get(s);
if (list==null) map.put(s,list=new ArrayList<>());
list.add(k++);
}
String[]keys=map.keySet().toArray(new String[0]);
for (int i=0,n=keys.length;i
for (int j=i+1;j
String s1=keys[i],s2=keys[j],key;
if (s1.compareTo(s2)<=0) key=s1+s2;
else key=s2+s1;
dist.put(key,minDist(keys[i],keys[j],map));
}
this.separator=separator;
}
public MinDist(Listdoc) {this(doc," ");}
public int getDist(String word1, String word2) {
Integer val;
if (word1.compareTo(word2)<=0) val=dist.get(word1+separator+word2);
else val=dist.get(word2+separator+word1);
return val==null?-1:val;
}
} |
m*******1
发帖数: 168 | |
s*******m
发帖数: 228 | 33 第二题用hashmap就可以避免面试官的疑问吗？
---------------------
写好后提示要是 cat dog cloud dog dog dog......,即后面有million个dog, 是否不
用比较整个文章.
constructor
【在 g********r 的大作中提到】
: 请问第二题，用hashmap的话，不是要事先建立好hashmap么？也就是说在constructor
: 里面建立好，然后每次调用计算diat的函数的时候，直接lookup hashmap，然后用
: index table算。LZ为什么要把建立hashmap的code放到计算dist的函数里呢？
|
e********c
发帖数: 66 | 34 没有code是完美的，精益求精是好事。 可能运气不好，碰到的人太挑剔，相互看不对
眼。 |
x*******6
发帖数: 262 | 35 第二题是l家电面常考题啊， 我记得当时是要求把存储word位置信息（map）和找出两
个words最小距离分开写出来。找出两个words最小距离是可以o（n）实现的。 |
s*****r
发帖数: 43070 | 36 对，code不够efficient，有些没必要的步骤和变量
constructor
【在 g********r 的大作中提到】
: 请问第二题，用hashmap的话，不是要事先建立好hashmap么？也就是说在constructor
: 里面建立好，然后每次调用计算diat的函数的时候，直接lookup hashmap，然后用
: index table算。LZ为什么要把建立hashmap的code放到计算dist的函数里呢？
|
s****a
发帖数: 794 | 37 按说C++如果nums--null 判断为真的话后面的||就不会再看了吧。
【在 r*******e 的大作中提到】
: 楼主你挂得不冤。我是面试官也会挂掉你的。
: 1）数组是否排序要提前问面试官，自己想当然属于lacking communication
: 然后面试官在你声明low 与high 两个变量时候没有提醒你么？还是说你没有提前跟面
: 试官说你的方法？？
: 2）速度不够快。否则第二题即使只有15分钟也能写个大概的。
: 3）如果楼主不服，我们现在来说代码
: 1：if(nums==null || nums.length<2) return false;
: 这里可能是需要抛出异常的 throw new NullPointerException（）；
: 2：if( (nums[low]+nums[high]) == sum ){ return true;｝。。。
: 更好点的办法是在循环外面声明一个变量temp，temp ＝ nums［low］＋nums［high］
|
