d*****0
发帖数: 72 | 1 May 23面的
一共三轮
就第一轮简单问了一下resume的intern
其他的每轮就只有一个算法题
1. 给定rand1()：能够产生random数字0,1
用rand1()实现:
rand3()--> 0, 1, 2, 3
rand4()--> 0, 1, 2, 3, 4
randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
，注意edge case
2. given 一个字符串，这个字符串是一个算式，包含加减乘除，没有括号，符号和数
字之间以一个空格格开，比如：“1 + 2 * 4 / 5”，return算式的结果
3. given两个字符串，分别表示两个元素等和不等，比如：
arr1 = {“A=B”, "B=C", ...}
arr2 = {"A!=C", "F!=R", ...}
判断是否有矛盾，这个例子就有矛盾：A!=C
given提取元素的method: getID(..)，这个不用自己写：String[] sarr = getID(arr1
[0]) --> sarr {A, B}
今天问道口头offer, 正在executive committee review中，求bless！！！ |
c*******r
发帖数: 610 | 2 多谢分享。
第三题没看明白，是什么意思呢？
String[] sarr = getID(arr1[0]) --> sarr {A, B}， 这个方法的意思是给定数组元
素，提取该元素里面涉及到的element吗？那么两个元素是否相等需要自己提取吗？ |
y***n
发帖数: 1594 | |
d*****0
发帖数: 72 | 4
本来最先题目是一个数组，也有提取符号的方法。不不过面试官简化了，弄成了两个数
组，第一个数组都是等的，第二个都是不等的
【在 c*******r 的大作中提到】
: 多谢分享。
: 第三题没看明白，是什么意思呢？
: String[] sarr = getID(arr1[0]) --> sarr {A, B}， 这个方法的意思是给定数组元
: 素，提取该元素里面涉及到的element吗？那么两个元素是否相等需要自己提取吗？
|
d*****0
发帖数: 72 | 5
2^k*rand1() + 2^k-1*rand1() + ... + 2^2*rand1() + 2*rand1() + rand1()
while 循环，如果上面式子得到的值少于等于n就return
【在 y***n 的大作中提到】
: 第一个有什么好的解法。
|
y***n
发帖数: 1594 | |
m******s
发帖数: 1469 | 7 Bless
【在 d*****0 的大作中提到】
: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case
|
j******4
发帖数: 66 | |
|
j******4
发帖数: 66 | 9 第三题的 思路 是不是 先的建无向图，然后，根据第二个集合，traverse验证? |
d**e
发帖数: 6098 | 10 请问这个是根据什么而得出来的式子？
谢谢！
【在 d*****0 的大作中提到】
:
: 2^k*rand1() + 2^k-1*rand1() + ... + 2^2*rand1() + 2*rand1() + rand1()
: while 循环，如果上面式子得到的值少于等于n就return
|
|
|
j**********3
发帖数: 3211 | |
S******1
发帖数: 216 | 12 //11:55 第3题不是图，是disjoint set
boolean isRight(String[] ss1, String[] ss2) {
if (ss1 == null || ss2 == null)
return false;
Map indexMap = new HashMap();
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
if (!indexMap.containsKey(c1))
indexMap.put(c1, indexMap.size());
if (!indexMap.containsKey(c2))
indexMap.put(c2, indexMap.size());
}
int[] set = new int[indexMap.size()];
for (int i = 0; i < set.length; i++)
set[i] = -1;
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
union(set, indexMap.get(c1), indexMap.get(c2));
}
for (String s : ss2) {
char c1 = s.charAt(0);
char c2 = s.charAt(3);
if (indexMap.containsKey(c1) && indexMap.containsKey(c2)) {
int p1 = findParent(set, indexMap.get(c1));
int p2 = findParent(set, indexMap.get(c2));
if (p1 == p2)
return false;
}
}
return true;
}
void union(int[] set, int i, int j) {
int p1 = findParent(set, i);
int p2 = findParent(set, j);
if (set[p1] < set[p2])
set[p2] = p1;
else
set[p1] = p2;
}
int findParent(int[] set, int i) {
if (set[i] < 0)
return i;
int p = findParent(set[i]);
set[i] = p;
return p;
} |
S******1
发帖数: 216 | 13 第一题reject sampling,
binary search
suppose sample space is power of 2, if more, reject and select again
If negative, set offset and restore |
l*****a
发帖数: 14598 | 14 不根据什么呀
简单是就是生成如下序列(这个例子是rand5())
0000
0001
0010
0011
0100
0101
.....
每个digit调用一次rand1()
如果生成的序列超过n，就排除
剩下的这些按照概率来说出现的频率一样
【在 d**e 的大作中提到】
: 请问这个是根据什么而得出来的式子？
: 谢谢！
|
d*****0
发帖数: 72 | 15
是的 new grad
【在 j**********3 的大作中提到】
: is LZ new grad?
|
d*****0
发帖数: 72 | 16
谢谢！就你bless我，大家都看题去了。。嘿嘿
【在 m******s 的大作中提到】
: Bless
|
y***n
发帖数: 1594 | |
d*****0
发帖数: 72 | 18
哈哈，谢谢~
【在 y***n 的大作中提到】
: 不好意思，一看题就忽略主题了，bless。
|
j******4
发帖数: 66 | 19
-------------------------
第一次见这种类型题，学习了，非常感谢。
【在 S******1 的大作中提到】
: //11:55 第3题不是图，是disjoint set
: boolean isRight(String[] ss1, String[] ss2) {
: if (ss1 == null || ss2 == null)
: return false;
:
: Map indexMap = new HashMap();
: for (String s : ss1) {
: char c1 = s.charAt(0);
: char c2 = s.charAt(2);
: if (!indexMap.containsKey(c1))
|
d**e
发帖数: 6098 | 20 难道你说的序列不算根据啊？这个理解比较简单。
不过话说回来，我到现在还是不明白那题，就是跟这题类似的，好像是rand3生成rand5
还是7的，说如果大过某数就去除，然后再继续得到某个范围为止。
打个比方，可以得到1~25，但expect得到1～21，所以如果产生的数是22～25，就去掉
，再继续找到1～21为止。这时问题我的问题就来了。
如果说一个随机函数是均匀分布的可以得到1~25,那是说不管我运行多少次，得到的数
都是1～25.那希望以此函数产生均匀分布的函数得到1~21，也就是说原随机函数不管运
行多少次，那根据某个公式得到的数也都是1～21，但如果去除某些结果，这还是算随
机分布吗？
我不是学数学的，高数概率也学得不好，所以没好好去证明，但就是想不明白。
【在 l*****a 的大作中提到】
: 不根据什么呀
: 简单是就是生成如下序列(这个例子是rand5())
: 0000
: 0001
: 0010
: 0011
: 0100
: 0101
: .....
: 每个digit调用一次rand1()
|
|
|
R*******d
发帖数: 13640 | 21 祝福
【在 d*****0 的大作中提到】
: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case
|
c********s
发帖数: 817 | 22 Bless!
May 23面的一共三轮就第一轮简单问了一下resume的intern其他的每轮就只有一个算法
题1. 给定rand1()：能够产生random数字0,1
【在 d*****0 的大作中提到】
:
: 哈哈，谢谢~
|
w*****c
发帖数: 7276 | |
D*******7
发帖数: 61 | 24 bless，问题不大，yahoo最近招不到人
【在 d*****0 的大作中提到】
: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case
|
d*****0
发帖数: 72 | 25 May 23面的
一共三轮
就第一轮简单问了一下resume的intern
其他的每轮就只有一个算法题
1. 给定rand1()：能够产生random数字0,1
用rand1()实现:
rand3()--> 0, 1, 2, 3
rand4()--> 0, 1, 2, 3, 4
randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
，注意edge case
2. given 一个字符串，这个字符串是一个算式，包含加减乘除，没有括号，符号和数
字之间以一个空格格开，比如：“1 + 2 * 4 / 5”，return算式的结果
3. given两个字符串，分别表示两个元素等和不等，比如：
arr1 = {“A=B”, "B=C", ...}
arr2 = {"A!=C", "F!=R", ...}
判断是否有矛盾，这个例子就有矛盾：A!=C
given提取元素的method: getID(..)，这个不用自己写：String[] sarr = getID(arr1
[0]) --> sarr {A, B}
今天问道口头offer, 正在executive committee review中，求bless！！！
-----------
收到正式offer！谢谢大家的祝福！ |
c*******r
发帖数: 610 | 26 多谢分享。
第三题没看明白，是什么意思呢？
String[] sarr = getID(arr1[0]) --> sarr {A, B}， 这个方法的意思是给定数组元
素，提取该元素里面涉及到的element吗？那么两个元素是否相等需要自己提取吗？ |
y***n
发帖数: 1594 | |
d*****0
发帖数: 72 | 28
本来最先题目是一个数组，也有提取符号的方法。不不过面试官简化了，弄成了两个数
组，第一个数组都是等的，第二个都是不等的
【在 c*******r 的大作中提到】
: 多谢分享。
: 第三题没看明白，是什么意思呢？
: String[] sarr = getID(arr1[0]) --> sarr {A, B}， 这个方法的意思是给定数组元
: 素，提取该元素里面涉及到的element吗？那么两个元素是否相等需要自己提取吗？
|
d*****0
发帖数: 72 | 29
2^k*rand1() + 2^k-1*rand1() + ... + 2^2*rand1() + 2*rand1() + rand1()
while 循环，如果上面式子得到的值少于等于n就return
【在 y***n 的大作中提到】
: 第一个有什么好的解法。
|
y***n
发帖数: 1594 | |
|
|
m******s
发帖数: 1469 | 31 Bless
【在 d*****0 的大作中提到】
: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case
|
j******4
发帖数: 66 | |
j******4
发帖数: 66 | 33 第三题的 思路 是不是 先的建无向图，然后，根据第二个集合，traverse验证? |
d**e
发帖数: 6098 | 34 请问这个是根据什么而得出来的式子？
谢谢！
【在 d*****0 的大作中提到】
:
: 2^k*rand1() + 2^k-1*rand1() + ... + 2^2*rand1() + 2*rand1() + rand1()
: while 循环，如果上面式子得到的值少于等于n就return
|
j**********3
发帖数: 3211 | |
S******1
发帖数: 216 | 36 //11:55 第3题不是图，是disjoint set
boolean isRight(String[] ss1, String[] ss2) {
if (ss1 == null || ss2 == null)
return false;
Map indexMap = new HashMap();
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
if (!indexMap.containsKey(c1))
indexMap.put(c1, indexMap.size());
if (!indexMap.containsKey(c2))
indexMap.put(c2, indexMap.size());
}
int[] set = new int[indexMap.size()];
for (int i = 0; i < set.length; i++)
set[i] = -1;
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
union(set, indexMap.get(c1), indexMap.get(c2));
}
for (String s : ss2) {
char c1 = s.charAt(0);
char c2 = s.charAt(3);
if (indexMap.containsKey(c1) && indexMap.containsKey(c2)) {
int p1 = findParent(set, indexMap.get(c1));
int p2 = findParent(set, indexMap.get(c2));
if (p1 == p2)
return false;
}
}
return true;
}
void union(int[] set, int i, int j) {
int p1 = findParent(set, i);
int p2 = findParent(set, j);
if (set[p1] < set[p2])
set[p2] = p1;
else
set[p1] = p2;
}
int findParent(int[] set, int i) {
if (set[i] < 0)
return i;
int p = findParent(set[i]);
set[i] = p;
return p;
} |
S******1
发帖数: 216 | 37 第一题reject sampling,
binary search
suppose sample space is power of 2, if more, reject and select again
If negative, set offset and restore |
l*****a
发帖数: 14598 | 38 不根据什么呀
简单是就是生成如下序列(这个例子是rand5())
0000
0001
0010
0011
0100
0101
.....
每个digit调用一次rand1()
如果生成的序列超过n，就排除
剩下的这些按照概率来说出现的频率一样
【在 d**e 的大作中提到】
: 请问这个是根据什么而得出来的式子？
: 谢谢！
|
d*****0
发帖数: 72 | 39
是的 new grad
【在 j**********3 的大作中提到】
: is LZ new grad?
|
d*****0
发帖数: 72 | 40
谢谢！就你bless我，大家都看题去了。。嘿嘿
【在 m******s 的大作中提到】
: Bless
|
|
|
y***n
发帖数: 1594 | |
d*****0
发帖数: 72 | 42
哈哈，谢谢~
【在 y***n 的大作中提到】
: 不好意思，一看题就忽略主题了，bless。
|
j******4
发帖数: 66 | 43
-------------------------
第一次见这种类型题，学习了，非常感谢。
【在 S******1 的大作中提到】
: //11:55 第3题不是图，是disjoint set
: boolean isRight(String[] ss1, String[] ss2) {
: if (ss1 == null || ss2 == null)
: return false;
:
: Map indexMap = new HashMap();
: for (String s : ss1) {
: char c1 = s.charAt(0);
: char c2 = s.charAt(2);
: if (!indexMap.containsKey(c1))
|
d**e
发帖数: 6098 | 44 难道你说的序列不算根据啊？这个理解比较简单。
不过话说回来，我到现在还是不明白那题，就是跟这题类似的，好像是rand3生成rand5
还是7的，说如果大过某数就去除，然后再继续得到某个范围为止。
打个比方，可以得到1~25，但expect得到1～21，所以如果产生的数是22～25，就去掉
，再继续找到1～21为止。这时问题我的问题就来了。
如果说一个随机函数是均匀分布的可以得到1~25,那是说不管我运行多少次，得到的数
都是1～25.那希望以此函数产生均匀分布的函数得到1~21，也就是说原随机函数不管运
行多少次，那根据某个公式得到的数也都是1～21，但如果去除某些结果，这还是算随
机分布吗？
我不是学数学的，高数概率也学得不好，所以没好好去证明，但就是想不明白。
【在 l*****a 的大作中提到】
: 不根据什么呀
: 简单是就是生成如下序列(这个例子是rand5())
: 0000
: 0001
: 0010
: 0011
: 0100
: 0101
: .....
: 每个digit调用一次rand1()
|
R*******d
发帖数: 13640 | 45 祝福
【在 d*****0 的大作中提到】
: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case
|
c********s
发帖数: 817 | 46 Bless!
May 23面的一共三轮就第一轮简单问了一下resume的intern其他的每轮就只有一个算法
题1. 给定rand1()：能够产生random数字0,1
【在 d*****0 的大作中提到】
:
: 哈哈，谢谢~
|
w*****c
发帖数: 7276 | |
D*******7
发帖数: 61 | 48 bless，问题不大，yahoo最近招不到人
【在 d*****0 的大作中提到】
: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case
|
c******1
发帖数: 37 | 49 我面试的时候面了这个我用union find做的那人说有o（n)的解法，面试官没跟我说正
确解法。但是一起面的人用了你这个解法面试官表示满意，我之前没看懂你这个解法，
现在觉得你这个做法也是O(n^2)把？
【在 S******1 的大作中提到】
: //11:55 第3题不是图，是disjoint set
: boolean isRight(String[] ss1, String[] ss2) {
: if (ss1 == null || ss2 == null)
: return false;
:
: Map indexMap = new HashMap();
: for (String s : ss1) {
: char c1 = s.charAt(0);
: char c2 = s.charAt(2);
: if (!indexMap.containsKey(c1))
|
I**********s
发帖数: 441 | 50 第一题应该也可以这样吧: n == 0 ? 0 : ((rand1() * INT_MAX) % n).
第三题可以用union find.
【在 d*****0 的大作中提到】
: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case
|
|
|
z***y
发帖数: 73 | 51 祝福lz！
1.相当于每次产生一个bit，运行k次，保证2^k >= n，如果超过n就重新运算，否则就
返回；
2.可以用一个stack吧，碰到*/操作立马计算，完了以后再处理一下剩下的+ -；
3.用hash table吧。如果对象都只是一个字符，那么char table[256]即可。遍历相等
的串，把相等的元素设置成同样的值。然后遍历不等的串，取值出来比较即可。 |
f********c
发帖数: 147 | 52 能具体说说第三个怎么做吗如果用hashmap?
【在 z***y 的大作中提到】
: 祝福lz！
: 1.相当于每次产生一个bit，运行k次，保证2^k >= n，如果超过n就重新运算，否则就
: 返回；
: 2.可以用一个stack吧，碰到*/操作立马计算，完了以后再处理一下剩下的+ -；
: 3.用hash table吧。如果对象都只是一个字符，那么char table[256]即可。遍历相等
: 的串，把相等的元素设置成同样的值。然后遍历不等的串，取值出来比较即可。
|
f********c
发帖数: 147 | 53 感觉这个算法有bug,加入输入：
A=B,C=D,B=D
A!=C
按这个算法返回true啊
【在 c******1 的大作中提到】
: 我面试的时候面了这个我用union find做的那人说有o（n)的解法，面试官没跟我说正
: 确解法。但是一起面的人用了你这个解法面试官表示满意，我之前没看懂你这个解法，
: 现在觉得你这个做法也是O(n^2)把？
|
d********m
发帖数: 101 | |
c******1
发帖数: 37 | 55
我也觉得，这个问题感觉是个标准的union find 怎么会有O（n）的解法（我面试的时
候说只有26个字母所以是26n 也可以是 lg26 n）那人马上说如果有很多别的item ，不
知道是不是面试官想错了
【在 f********c 的大作中提到】
: 感觉这个算法有bug,加入输入：
: A=B,C=D,B=D
: A!=C
: 按这个算法返回true啊
|
t******d
发帖数: 1383 | |
f********c
发帖数: 147 | 57 不知你面的时候怎么做的？有没有和别人讨论得到O(n)的解啊？
【在 c******1 的大作中提到】
:
: 我也觉得，这个问题感觉是个标准的union find 怎么会有O（n）的解法（我面试的时
: 候说只有26个字母所以是26n 也可以是 lg26 n）那人马上说如果有很多别的item ，不
: 知道是不是面试官想错了
|
u*****l
发帖数: 444 | |
