y*****e
发帖数: 712 | 1 大神们看在我夜里1点还在做题的份上，给点思路吧，都是以前mark的帖子的上的题 >_<
1. Convert map > to map > >
这题要干嘛？ 毫无思路啊
2. Write a function to get a positive integer n as input and return 0 or 1.
The probability of returning 1 should be 1/(2^n)
这题有点思路，先generate一个fair coin的function, 然后call N次。附上我的丑小
鸭解法，希望抛砖引玉啊
public class probability_N_true{
public static boolean fair(){
Random rand = new Random();
return rand.nextInt(2) == 0;
}
public static boolean probNth(int N){
if(N == 1){
return fair();
}
if(fair() == true){
return probNth(N - 1);
}
return false;
}
}
3. Sort strings like "TADTTTTBDB", fixed length of 10, made up by only four
characters: T A D B，要求linear time, 来自帖子
http://www.mitbbs.com/article_t/JobHunting/32752575.html
想问一下这个是sort color的变种吗？ fixed length这个条件怎么用呢？
今天是14年的最后一天，希望小伙伴们2015年都有大offer！ |
k******e
发帖数: 145 | 2 Can counter be used for the 3rd problem?
Since many factors are fixed... |
v****a
发帖数: 236 | |
w****a
发帖数: 710 | 4 第三题可以直接数数吧。
走一个pass然后记录下四个字母依次多少个，然后直接输出 |
i********r
发帖数: 110 | 5 这是正解。
[在 wangya (fgdsb) 的大作中提到：]
：第三题可以直接数数吧。
：走一个pass然后记录下四个字母依次多少个，然后直接输出
：........... |
s*w
发帖数: 729 | 6 你说的是 sort 一个字符串本身； 他问的是 sort 很多个。
不过解法还是类似，4^10 = 2^20 才 1MB 直接转字符串为数字， linear scan 数每
个数的频率；输出的时候再转数字为字符串
【在 w****a 的大作中提到】
: 第三题可以直接数数吧。
: 走一个pass然后记录下四个字母依次多少个，然后直接输出
|
s*w
发帖数: 729 | 7 2. 直接用 for loop 比 recursion 好点
>_<
.
【在 y*****e 的大作中提到】
: 大神们看在我夜里1点还在做题的份上，给点思路吧，都是以前mark的帖子的上的题 >_<
: 1. Convert map > to map > >
: 这题要干嘛？ 毫无思路啊
: 2. Write a function to get a positive integer n as input and return 0 or 1.
: The probability of returning 1 should be 1/(2^n)
: 这题有点思路，先generate一个fair coin的function, 然后call N次。附上我的丑小
: 鸭解法，希望抛砖引玉啊
: public class probability_N_true{
: public static boolean fair(){
: Random rand = new Random();
|
S********s
发帖数: 29 | 8 第一题，看个例子就好明白了：
a1->{b1->c1, b2->c2}, a2->{b1->c1, b3->c2}
所有有如下：
a1,b1,c1; a1,b2,c2; a2,b1,c1; a2,b3,c2
把上面的反过来放倒map里面就好了
第三题，是不是看成bucket sort，直接放入每个字符的index就好了（这就用上了长度
10）
T: 0,3，4，5，6
A:1
D:2，8
B:7，9 |
y*****e
发帖数: 712 | 9 谢谢ls各位，果真思路宽阔多了，我来总结一下大家的想法
第一题就是 flatten and reverse
第二题用iteration比recursion更有效
第三题用count sort应该可以，我还看到一个叫LSD的算法，专门排序等长的strings，
http://algs4.cs.princeton.edu/51radix/LSD.java.html, 其实就是count sort, 不过用上了fixed length这个条件。 |
