店面是两个中国人,一开始知道是国人还比较欣喜. 结果证明完全不是这么回事,反而感
觉很严格,最终挂了. 请大家分析下为啥挂? 难道第二题没有按面试官心中理想的答案
在面试时给他写出来? 以后看来一定要注意时间.
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(lowif( (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; iif(!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; istrs[i] = words.get(i);
}
public int distance (String wordOne, String wordTwo) {
HashMap> map = new HashMapInteger>>();
if(strs==null || strs.length<2)
return 0;
for(int i=0; iif(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(index1if(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;
}
}
