j**7
发帖数: 143 | 1 面的组是Amazon Fulfillment in Seattle. 两轮电话面试，四轮on-site，每轮45分钟
。我是new grad.
1. Implement Huffman code. 面试官首先给了算法，然后叫我去implement.我用的是
min-heap 还有HashMap. 面试官看起来比较满意。
2. 老中bar raiser. 介绍project，然后做一道题。Given a list of integers of
length n, find the duplicate element. The integers are all in the range of 1
to n-1. There is only one duplicate element.
my answer: use a for loop to compute the sum of the list. Then returns sum-
(n-1)*n/2.
follow-up: Give another algorithm for this problem. Find as many algorithms
as you can.
3. Find all permutations of a string (我写的是CC150原题的答案）.
4. 老印manager. 介绍project，然后做一道题。
Given a phone number as input, print all combinations of words that can be
produced from this phone number.
Ex. 2:ABC 3:DEF 4:GHI 5:JKL 6:MNO ....
Ex. input="234" ->{ADG,ADH,ADI, AEG,AEH,AEI, AFG,AFH,AFI,BDG,BDH,BDI...}
You can use a function to help you that returns a char given a digit and a
position. int function(int digit, int pos)
Ex. function(2,0)->'A' function(2,1)->'B' function(4,2)->'I'
我用了 depth first search.
最后问了几道有关OOP and Java 的问题。
1. What is your favorite language?
my answer: Java
2. What is encapsulation?
my answer: hide variables and methods, public, private, etc...
3. What is the difference between HashMap and HashTable?
my answer: HashMap is not thread-safe. HashTable is synchronized.
杯具了。不知道哪儿做的不对。 |
w****x
发帖数: 2483 | 2
1
-
algorithms
太慢了？
【在 j**7 的大作中提到】
: 面的组是Amazon Fulfillment in Seattle. 两轮电话面试，四轮on-site，每轮45分钟
: 。我是new grad.
: 1. Implement Huffman code. 面试官首先给了算法，然后叫我去implement.我用的是
: min-heap 还有HashMap. 面试官看起来比较满意。
: 2. 老中bar raiser. 介绍project，然后做一道题。Given a list of integers of
: length n, find the duplicate element. The integers are all in the range of 1
: to n-1. There is only one duplicate element.
: my answer: use a for loop to compute the sum of the list. Then returns sum-
: (n-1)*n/2.
: follow-up: Give another algorithm for this problem. Find as many algorithms
|
j**7
发帖数: 143 | 3 是不是算法的time complexity太慢了。 |
h***i
发帖数: 1970 | 4 慢倒是不慢，就是容易溢出，他显然不是expect这个答案，他等的是换位。
【在 w****x 的大作中提到】
:
: 1
: -
: algorithms
: 太慢了？
|
w****x
发帖数: 2483 | 5
我的意思是，是不是每个人才做了一道题感觉有点慢
【在 h***i 的大作中提到】
: 慢倒是不慢，就是容易溢出，他显然不是expect这个答案，他等的是换位。
|
j**7
发帖数: 143 | 6
你是指第四题吗？应该怎么做？
【在 h***i 的大作中提到】
: 慢倒是不慢，就是容易溢出，他显然不是expect这个答案，他等的是换位。
|
s*********s
发帖数: 140 | 7 感觉被bar raiser挂了吧。bar raiser有一票否决权吧
1
★ 发自iPhone App: ChineseWeb 7.8
【在 j**7 的大作中提到】
: 面的组是Amazon Fulfillment in Seattle. 两轮电话面试，四轮on-site，每轮45分钟
: 。我是new grad.
: 1. Implement Huffman code. 面试官首先给了算法，然后叫我去implement.我用的是
: min-heap 还有HashMap. 面试官看起来比较满意。
: 2. 老中bar raiser. 介绍project，然后做一道题。Given a list of integers of
: length n, find the duplicate element. The integers are all in the range of 1
: to n-1. There is only one duplicate element.
: my answer: use a for loop to compute the sum of the list. Then returns sum-
: (n-1)*n/2.
: follow-up: Give another algorithm for this problem. Find as many algorithms
|
j**7
发帖数: 143 | 8
第一个面试官说很少人能在45分钟之内做完那道题，但我做完了。第二轮bar raiser也
很快就结束了。老中说我的算法是对的。可能问题出在第四轮。老印说我的算法是对的
，但让我检查code有没有bug. 然后我说没bug.
【在 w****x 的大作中提到】
:
: 我的意思是，是不是每个人才做了一道题感觉有点慢
|
f*******7
发帖数: 943 | 9 跟我上个月面亚麻bar raiser是一道题。。。估计答出的解决办法太少了
同样悲剧 |
l*********8
发帖数: 4642 | 10 int findDuplication(int * A, int n)
{
for (int i=0; i
while (A[i] != i+1) {
if ( A[ A[i]-1 ] == A[i])
return A[i];
swap(A[i], A[ A[i]-1 ]);
}
}
}
【在 j**7 的大作中提到】
:
: 第一个面试官说很少人能在45分钟之内做完那道题，但我做完了。第二轮bar raiser也
: 很快就结束了。老中说我的算法是对的。可能问题出在第四轮。老印说我的算法是对的
: ，但让我检查code有没有bug. 然后我说没bug.
|
|
|
j**7
发帖数: 143 | 11
一共有多少个解决方法？我面试时只想出了四个。我以为四个足够了，就没再多答出几
个。
【在 f*******7 的大作中提到】
: 跟我上个月面亚麻bar raiser是一道题。。。估计答出的解决办法太少了
: 同样悲剧
|
l**b
发帖数: 457 | 12 我觉得bar raiser那道题目是不是做错了？
没说只有那个dup只有一次啊。所以如果是[1, 1, 1]的话，你那个方法不成立吧？ |
j**7
发帖数: 143 | 13
只有一个duplicate element.
【在 l**b 的大作中提到】
: 我觉得bar raiser那道题目是不是做错了？
: 没说只有那个dup只有一次啊。所以如果是[1, 1, 1]的话，你那个方法不成立吧？
|
l**b
发帖数: 457 | 14 There is only one duplicate element，可以理解为只有一个数字有dup，但是并没有
说只duplicate了一次吧？当然，如果我老年痴呆理解错题意，那你的做法肯定是对的。
【在 j**7 的大作中提到】
:
: 只有一个duplicate element.
|
l****i
发帖数: 2772 | 15 Find all permutations of a string的CC150的答案，没有考虑重复的char吧？ |
j**7
发帖数: 143 | 16
follow-up要求考虑重复的permutation.
【在 l****i 的大作中提到】
: Find all permutations of a string的CC150的答案，没有考虑重复的char吧？
|
c***w
发帖数: 134 | 17 我觉得你面的已经很好了，居然还是被fail，估计运气不好。 |
j**7
发帖数: 143 | 18
郁闷死了！一个星期被两家公司拒掉（M和A)。
【在 c***w 的大作中提到】
: 我觉得你面的已经很好了，居然还是被fail，估计运气不好。
|
d**********x
发帖数: 4083 | 19 关键问题是他那个玩意溢出了
【在 l**b 的大作中提到】
: 我觉得bar raiser那道题目是不是做错了？
: 没说只有那个dup只有一次啊。所以如果是[1, 1, 1]的话，你那个方法不成立吧？
|
s*********s
发帖数: 140 | 20 感觉lz真的已经答的很好了。面试确实也要看运气的。加油
【在 j**7 的大作中提到】
:
: 郁闷死了！一个星期被两家公司拒掉（M和A)。
|
|
|
M********5
发帖数: 715 | 21 我真是看不出来你哪里面的不行了。。。答得好像还挺好的嘛，我答不出这个水平出来
。。。 |
j**7
发帖数: 143 | 22
我明白了。谢谢。如果n是非常大的integer,sum就会出现integer overflow,对吗？当
时我只考虑了time和space complexity.
int duplicate(int [] list)
{
//n=list.length
int sum=0;
for(int i=0;i
{
sum+=list[i];//这里会出现integer overflow.
}
return sum- (list.length-1)*(list.length)/2;
}
【在 d**********x 的大作中提到】
: 关键问题是他那个玩意溢出了
|
d**********x
发帖数: 4083 | 23 恩，后面的 (n-1)*n 也会溢出
大小不用太大，超过 1 << 16 就不行了
如果你两个数都是加出来的说不定真的可以抵消溢出，但是乘法截断是另一套规律。。
【在 j**7 的大作中提到】
:
: 我明白了。谢谢。如果n是非常大的integer,sum就会出现integer overflow,对吗？当
: 时我只考虑了time和space complexity.
: int duplicate(int [] list)
: {
: //n=list.length
: int sum=0;
: for(int i=0;i: {
: sum+=list[i];//这里会出现integer overflow.
|
j**7
发帖数: 143 | 24 另外一个方法是用sort,然后再找重复的element.这样就不会有integer overflow,但是
time complexity 是 nlog(n).
Arrays.sort(list);
for(int i=0;i
{
if(list[i]==list[i+1])
return list[i];
} |
M******7
发帖数: 30 | |
c******5
发帖数: 84 | 26 你这几轮有几个印度面试官啊？是不是被阿三给黑了？ |
p*****2
发帖数: 21240 | 27
可以用long吧？
【在 d**********x 的大作中提到】
: 恩，后面的 (n-1)*n 也会溢出
: 大小不用太大，超过 1 << 16 就不行了
: 如果你两个数都是加出来的说不定真的可以抵消溢出，但是乘法截断是另一套规律。。
|
f*******3
发帖数: 206 | 28 仔细读题的话能发现重复只可能有一次我觉得不管写几个算法xor是他想看到的
【在 p*****2 的大作中提到】
:
: 可以用long吧？
|
p*****2
发帖数: 21240 | 29
不是有followup吗？我觉得LZ那个sum作为第一个解答还可以吧？后面的followup可以
说xor呀。
follow-up: Give another algorithm for this problem. Find as many algorithms
as you can.
【在 f*******3 的大作中提到】
: 仔细读题的话能发现重复只可能有一次我觉得不管写几个算法xor是他想看到的
|
f*******3
发帖数: 206 | 30 对啊我觉得是不是中午吃饭跟hr在behavior上出差错了?感觉运气差点，继续加油吧。
祝lz好运
algorithms
【在 p*****2 的大作中提到】
:
: 不是有followup吗？我觉得LZ那个sum作为第一个解答还可以吧？后面的followup可以
: 说xor呀。
: follow-up: Give another algorithm for this problem. Find as many algorithms
: as you can.
|
|
|
j**7
发帖数: 143 | 31 第二题bar raiser,用Exclusive OR 不会有Integer overflow.
时间复杂度：O(n)
空间复杂度：O(1)
int [] list={2,3,1,5,4,6,3};
System.out.println(duplicate(list));
static int duplicate(int []input)
{
int n=input.length;
int XOR1=1;
for(int i=2;i<=n-1;i++)
{
XOR1=XOR1^i;
}
int XOR2=input[0];
for(int i=1;i
{
XOR2=XOR2^input[i];
}
return XOR1^XOR2;
} |
s***y
发帖数: 203 | |
j**7
发帖数: 143 | 33
他说了。我问过他是否是这个组的。
【在 s***y 的大作中提到】
: 第2个人说他是bar raiser了么？
|
s*****a
发帖数: 72 | 34 bar-raiser 那道题可以用hashmap解啊，难道不是更简单直接么？
我两周前onsite的时候也遇到这个题了，当时是45分钟里的第二道题（第一道是OOD）
，面试官没说要写多种解法，所以我就直接上了。
follow-up questions是如何设计一个好的 hash function。
面试官好像满意我的答复。
1
-
【在 j**7 的大作中提到】
: 面的组是Amazon Fulfillment in Seattle. 两轮电话面试，四轮on-site，每轮45分钟
: 。我是new grad.
: 1. Implement Huffman code. 面试官首先给了算法，然后叫我去implement.我用的是
: min-heap 还有HashMap. 面试官看起来比较满意。
: 2. 老中bar raiser. 介绍project，然后做一道题。Given a list of integers of
: length n, find the duplicate element. The integers are all in the range of 1
: to n-1. There is only one duplicate element.
: my answer: use a for loop to compute the sum of the list. Then returns sum-
: (n-1)*n/2.
: follow-up: Give another algorithm for this problem. Find as many algorithms
|
e***s
发帖数: 799 | 35 请问您的“如何设计一个好的 hash function”如何回答?
【在 s*****a 的大作中提到】
: bar-raiser 那道题可以用hashmap解啊，难道不是更简单直接么？
: 我两周前onsite的时候也遇到这个题了，当时是45分钟里的第二道题（第一道是OOD）
: ，面试官没说要写多种解法，所以我就直接上了。
: follow-up questions是如何设计一个好的 hash function。
: 面试官好像满意我的答复。
:
: 1
: -
|
j**7
发帖数: 143 | 36
用HashMap或者BitSet要使用更多的内存。空间复杂度是O(n).
【在 s*****a 的大作中提到】
: bar-raiser 那道题可以用hashmap解啊，难道不是更简单直接么？
: 我两周前onsite的时候也遇到这个题了，当时是45分钟里的第二道题（第一道是OOD）
: ，面试官没说要写多种解法，所以我就直接上了。
: follow-up questions是如何设计一个好的 hash function。
: 面试官好像满意我的答复。
:
: 1
: -
|
B********t
发帖数: 147 | 37 bar raiser那个，能想到的所有的
1. 求sum
2. hash map
3. 类似 first missing positive, 不停的swap
4, xor
5, sort
还有别的么 |
j**7
发帖数: 143 | 38
还可以用一个double for loop, O(n^2)
【在 B********t 的大作中提到】
: bar raiser那个，能想到的所有的
: 1. 求sum
: 2. hash map
: 3. 类似 first missing positive, 不停的swap
: 4, xor
: 5, sort
: 还有别的么
|
j**7
发帖数: 143 | 39 Amazon的第四道面试题跟CodeEval上面的一道题几乎一样。可惜面试的时候没有检查到
bug.
https://www.codeeval.com/open_challenges/59/
public class Main {
/**
* @param args
*/
static StringBuilder build=new StringBuilder();
public static void main(String[] args) {
// TODO Auto-generated method stub
telephone("4155230");
}
static void telephone(String input)
{
telephone(input,0,"");
build.deleteCharAt(build.length()-1);
System.out.println(build.toString());
}
static void telephone(String input, int index,String path)
{
if(index==input.length())
{
build.append(path);
build.append(",");
}
else
{
int length=wordLength(input.charAt(index)-'0');
for(int i=0;i
{
telephone(input,index+1,path+word(input.charAt(index)-'0',i
));
}
}
}
static int wordLength(int digit)
{
if(digit==0 || digit==1)
return 1;
if(digit==7 || digit==9)
return 4;
return 3;
}
static char word(int digit, int pos)
{
if(digit==0)
return '0';
if(digit==1)
return '1';
String result;
switch(digit)
{
case 2:
result="abc";
break;
case 3:
result="def";
break;
case 4:
result="ghi";
break;
case 5 :
result="jkl";
break;
case 6 :
result="mno";
break;
case 7 :
result="pqrs";
break;
case 8 :
result="tuv";
break;
case 9:
result="wxyz";
break;
default:
result="-1";
}
return result.charAt(pos);
}
} |
B********t
发帖数: 147 | 40 这题还是用iteration吧。。leetcode上的原题吧。
class Solution {
public:
vector letterCombinations(string digits) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector ret;
if(!digits.size())
ret.push_back("");
if(digits.size())
{
string one;
map hm;
hm['2'] = "abc";
hm['3'] = "def";
hm['4'] = "ghi";
hm['5'] = "jkl";
hm['6'] = "mno";
hm['7'] = "pqrs";
hm['8'] = "tuv";
hm['9'] = "wxyz";
int count[digits.size()];
for(int i = 0; i < digits.size(); i++)
count[i] = 0;
while(count[0] <= hm[digits[0]].size() - 1)
{
for(int i = 0; i < digits.size(); i++)
one.push_back(hm[digits[i]][count[i]]);
ret.push_back(one);
one = "";
count[digits.size()-1]++;
for(int i = digits.size() - 1; i > 0; i--)
{
if(count[i] == hm[digits[i]].size())
{
count[i-1]++;
count[i] = 0;
}
}
}
}
return ret;
}
};
【在 j**7 的大作中提到】
: Amazon的第四道面试题跟CodeEval上面的一道题几乎一样。可惜面试的时候没有检查到
: bug.
: https://www.codeeval.com/open_challenges/59/
: public class Main {
: /**
: * @param args
: */
: static StringBuilder build=new StringBuilder();
: public static void main(String[] args) {
: // TODO Auto-generated method stub
|
