G的几道面试题 | Hello World
1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡片的下一个位置
e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，能得话要多少次。
我能想到的做法是一个一个的字母找，看多少次能回到原来的位置（或者不能回到原来的位置），记录这个次数为t[i], 然后求所有t[i]的LCM最小公倍数,
求最小公倍数的方法是先求最大公约数（用辗转相除法），然后再用a*b/gcd(a,b) 求最小公倍数。
public int cardShuffler(int[] cards, int[] shuffle) {
int[] steps = new int [cards.length];
for(int i=0; i<cards.length; i++) {
steps[i] = stepsBack(i, shuffle);
if (steps[i] == -1)
return -1;
}
return LCM(steps);
}
private int stepsBack(int start, int[] shuffle) {
int i = start;
int res = 0;
Set visited = new HashSet();
do {
i = shuffle[i];
if (visited.contains(i)) // without this, it will cause infinite loop.
return -1;
visited.add(i);
res++;
} while(i != start);
return res;
}
private int LCM(int[] steps) {
int res = steps[0];
for(int i=1; i<steps.length; i++) {
res = res*steps[i]/GCD(res, steps[i]);
}
return res;
}
private int GCD(int a, int b) {
int n1 = Math.max(a,b);
int n2 = Math.min(a,b);
while(n1%n2 != 0) {
int tmp = n1%n2;
n1 = n2;
n2 = tmp;
}
return n2;
}
2.给定一个binary search tree，返回range内所有key，key可以有重复。
感觉这道题比较简单，就是二分法递归就可以。
3. 把一个数拆成任意个平方和的最小拆法。
f(0) = 0;
f(n) = for(i = 1 to sqrt(n))f(n-i*i) + 1;
应该可以用DP优化。
Read full article from G的几道面试题 | Hello World
1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡片的下一个位置
e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，能得话要多少次。
我能想到的做法是一个一个的字母找，看多少次能回到原来的位置（或者不能回到原来的位置），记录这个次数为t[i], 然后求所有t[i]的LCM最小公倍数,
求最小公倍数的方法是先求最大公约数（用辗转相除法），然后再用a*b/gcd(a,b) 求最小公倍数。
public int cardShuffler(int[] cards, int[] shuffle) {
int[] steps = new int [cards.length];
for(int i=0; i<cards.length; i++) {
steps[i] = stepsBack(i, shuffle);
if (steps[i] == -1)
return -1;
}
return LCM(steps);
}
private int stepsBack(int start, int[] shuffle) {
int i = start;
int res = 0;
Set visited = new HashSet();
do {
i = shuffle[i];
if (visited.contains(i)) // without this, it will cause infinite loop.
return -1;
visited.add(i);
res++;
} while(i != start);
return res;
}
private int LCM(int[] steps) {
int res = steps[0];
for(int i=1; i<steps.length; i++) {
res = res*steps[i]/GCD(res, steps[i]);
}
return res;
}
private int GCD(int a, int b) {
int n1 = Math.max(a,b);
int n2 = Math.min(a,b);
while(n1%n2 != 0) {
int tmp = n1%n2;
n1 = n2;
n2 = tmp;
}
return n2;
}
2.给定一个binary search tree，返回range内所有key，key可以有重复。
感觉这道题比较简单，就是二分法递归就可以。
3. 把一个数拆成任意个平方和的最小拆法。
f(0) = 0;
f(n) = for(i = 1 to sqrt(n))f(n-i*i) + 1;
应该可以用DP优化。
Read full article from G的几道面试题 | Hello World
