j***m 发帖数: 6 | 1 1. 给两个类A和B
class A {
public void foo (A a) {
...
}
}
class B extends A {
public void foo (B b) {
...
}
}
问这么写会不会有问题
2. 关于Database的题,假如你执行
select * from employee
employee是一个table
但是返回错误说,这个table不存在什么的,但是现在已知存在这个table,问你可能是
什么原因。
完全没有思路,就说我也不知道。。。
3. 一种字母游戏这样的
给定四个位置 _,_,_,_
然后每个位置可以选5个candidates,然后问这些candidates最多可以组成多少个有效
的词,字典是给定的。
比如,
如果字典是 [cake, bike, fake]
我们可以这样选candidates
第一个位置可以选 b,c,f,e,d
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
那这些可以组成3个有效的词 cake, bike, fake.
但是如果,这样选每个位置的candidates
第一个位置可以选 z,c,v,b,y
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
只能组成一个有效的词就是bike.
这样就是第一种选candidates的方法比较好。
然后问你怎么选每个位置的candidates,最终可以让能组成的词最多。
没有什么特别好的思路,问是不是brutal search,还有更好的方法吗?答:你如果要
brutal search的话,你估算一下时间。
我就开始算时间,发现很长,然后面试官说,那你想办法优化。。。但是因为算brual
search的时间算了太长时间了,就没什么时间优化了。。。 |
z****0 发帖数: 4413 | 2 什么职位?
【在 j***m 的大作中提到】 : 1. 给两个类A和B : class A { : public void foo (A a) { : ... : } : } : class B extends A { : public void foo (B b) { : ... : }
|
z****0 发帖数: 4413 | 3 第二题是不是和死锁有关系? 大牛出来解答下
【在 j***m 的大作中提到】 : 1. 给两个类A和B : class A { : public void foo (A a) { : ... : } : } : class B extends A { : public void foo (B b) { : ... : }
|
j***m 发帖数: 6 | 4 entry level software engineer.因为之前有过一点Java 的经验和Database的经验,
所以被问到了这些,但是不懂啊。。。
【在 z****0 的大作中提到】 : 什么职位?
|
a**y 发帖数: 335 | 5 是权限问题吧。btw, 我是菜鸟。
【在 z****0 的大作中提到】 : 第二题是不是和死锁有关系? 大牛出来解答下
|
s***5 发帖数: 2136 | 6 第三题把那四组字母和在单词中的位置组合放进hashset。直接扫描字典,只考虑四个
字母的单词,应该比BF方法快。 |
s**********k 发帖数: 88 | 7 关于1,
应该是可以的,foo()是overload而不是override
【在 j***m 的大作中提到】 : 1. 给两个类A和B : class A { : public void foo (A a) { : ... : } : } : class B extends A { : public void foo (B b) { : ... : }
|
r*******k 发帖数: 1423 | 8 试了一下,确实可以
应该方法的signature是不同的
【在 s**********k 的大作中提到】 : 关于1, : 应该是可以的,foo()是overload而不是override
|
|
q****m 发帖数: 177 | 9 最后一道题感觉和max flow相关
【在 j***m 的大作中提到】 : 1. 给两个类A和B : class A { : public void foo (A a) { : ... : } : } : class B extends A { : public void foo (B b) { : ... : }
|
d*********t 发帖数: 4279 | 10 Nice to meet you here.
【在 r*******k 的大作中提到】 : 试了一下,确实可以 : 应该方法的signature是不同的
|
|
|
z**h 发帖数: 85 | 11 2. 关于Database的题
>wrong schema |
M********r 发帖数: 96 | 12 very likely. Need a synonym
【在 z**h 的大作中提到】 : 2. 关于Database的题 : >wrong schema
|
j***m 发帖数: 6 | 13 后来我想到是不是应该把所有4个字的词并且在字典里面的组成一个trie,
这样第一层对应第一个位置,第二层对应第二个位置,。。。
但是每层最多选5个字母,之后就不知道该怎么做了。。。
【在 j***m 的大作中提到】 : 1. 给两个类A和B : class A { : public void foo (A a) { : ... : } : } : class B extends A { : public void foo (B b) { : ... : }
|
s*l 发帖数: 9421 | 14 第二题table 的 owner was missing. like dbo.employee. |
X*4 发帖数: 101 | 15 字典里的所有单词都是一样的长度?
在你的例子里,都是4?
那么用trie挺好
【在 j***m 的大作中提到】 : 后来我想到是不是应该把所有4个字的词并且在字典里面的组成一个trie, : 这样第一层对应第一个位置,第二层对应第二个位置,。。。 : 但是每层最多选5个字母,之后就不知道该怎么做了。。。
|
b****y 发帖数: 35 | 16 第一题那么写虽然编译没问题,但设计上违反了多态原则,应该避免。
第二题可能是Schema/owner missing |
z****e 发帖数: 54598 | |
s*********e 发帖数: 40 | |
Z**********4 发帖数: 528 | |
Z**********4 发帖数: 528 | |
|
|
Z**********4 发帖数: 528 | 21 又想了一下 还是跟max flow更相关一点。
根据字典的单词可以画出一个图来。然后从中选择20个点,保证从第一个column到最后
一个column的paths最多。 |
n*****n 发帖数: 5277 | 22 第一题应该用dynamic dispatch, A和B的function argument 应该一致。 |
T*****u 发帖数: 7103 | 23 第三题第一感觉是dp。后来想也可以在四维空间,26*26*26*26个自由度(实际的有效
点比字典的容量要小,而字典是必须要历遍的),字典里就是你的sample,生成一个
heat map,从里面找5*5*5*5的一个最大的,可以是不连续的子空间。 |
j***m 发帖数: 6 | 24 对,在我的例子里就都是4.
【在 X*4 的大作中提到】 : 字典里的所有单词都是一样的长度? : 在你的例子里,都是4? : 那么用trie挺好
|
Z**********4 发帖数: 528 | 25 可以展开说说嘛?
听起来很高端~
【在 T*****u 的大作中提到】 : 第三题第一感觉是dp。后来想也可以在四维空间,26*26*26*26个自由度(实际的有效 : 点比字典的容量要小,而字典是必须要历遍的),字典里就是你的sample,生成一个 : heat map,从里面找5*5*5*5的一个最大的,可以是不连续的子空间。
|
T*****u 发帖数: 7103 | 26 我也不知道啊,我觉着是个野鸡方法。
【在 Z**********4 的大作中提到】 : 可以展开说说嘛? : 听起来很高端~
|
D*********G 发帖数: 193 | 27 不懂heat map
用什么data structure构建4维heat map呢?
对字典里的每一个词都要update 4维heat map,复杂度是多少?
我怎么感觉这样不可行阿,关键是无法确定5*5*5*5的最大的,除非开C(5,26)*C(5,26)
*C(5,26)*C(5,26)个buckets,那这个复杂度和Brute force没区别阿
【在 T*****u 的大作中提到】 : 第三题第一感觉是dp。后来想也可以在四维空间,26*26*26*26个自由度(实际的有效 : 点比字典的容量要小,而字典是必须要历遍的),字典里就是你的sample,生成一个 : heat map,从里面找5*5*5*5的一个最大的,可以是不连续的子空间。
|
f*********g 发帖数: 25 | 28 第三题不知道这样行不行?
第一个位置找出5个概率最大的argmax{P(X1)}
第二个位置找出5个条件概率和最大的,比如:argmax{P(x2|a) + P(x2|b) + P(x2|c)
+ P(x2|d) + P(x2|e)},a,b,c,d,e是之前找出的第一个位置的5个字母。
以此类推,只要遍历几遍字典就可以找出来了。 |
v***o 发帖数: 287 | 29 这5个位置有关联,概率不可性,max flow比较靠谱。
)
【在 f*********g 的大作中提到】 : 第三题不知道这样行不行? : 第一个位置找出5个概率最大的argmax{P(X1)} : 第二个位置找出5个条件概率和最大的,比如:argmax{P(x2|a) + P(x2|b) + P(x2|c) : + P(x2|d) + P(x2|e)},a,b,c,d,e是之前找出的第一个位置的5个字母。 : 以此类推,只要遍历几遍字典就可以找出来了。
|
h*******e 发帖数: 1377 | 30 字典给定了,是java c++ hash set 结构 ( script php python 语言: 字典结构)给
的,
还是 array vector 结构给定, 搜索的时候, 给定 key 访问其中元素 复杂度是O(n)
还是 O(1)啊?楼主问了面试官没有?
字典大小多少啊,是2个元素,还是 26 * 26 * 26 *26 * 26 个元素阿
,楼主问了没有?
【在 j***m 的大作中提到】 : 1. 给两个类A和B : class A { : public void foo (A a) { : ... : } : } : class B extends A { : public void foo (B b) { : ... : }
|
|
|
h*******e 发帖数: 1377 | 31 楼主的面试官要改变关于什么的复杂度啊,5 ^4 才625 不到0.01秒就算完
了如果字典是o(1) 查询的话 也不大阿,是要改善 关于 每个字符的可能字母数5 的
复杂度 还是要改善关于单词长度4的复杂度啊,楼主问了没有啊?
)
【在 h*******e 的大作中提到】 : 字典给定了,是java c++ hash set 结构 ( script php python 语言: 字典结构)给 : 的, : 还是 array vector 结构给定, 搜索的时候, 给定 key 访问其中元素 复杂度是O(n) : 还是 O(1)啊?楼主问了面试官没有? : 字典大小多少啊,是2个元素,还是 26 * 26 * 26 *26 * 26 个元素阿 : ,楼主问了没有?
|
m******e 发帖数: 82 | 32 第一题定义没错,编译可以通过,但是这样调用会出现不同结果
B* b = new B();
A* a = b;
B c;
a->foo(c); // 调用A的foo
b->foo(c); // 调用B的foo |
j***m 发帖数: 6 | 33 楼主我木有问啊,但是面试官的意思是,字典你可以随意存在你觉得合适的结构里面,
只要最后能保证求出正确的结果且尽量快就好了。
字典大小就是所有4个字母的英文单词,有多少就是多少。
这个面试官说这是他有天看他家孩子玩的玩具拍脑袋想出来的题,所以其实是一道非常
实际的题,只要够快,结果是对的,其他没有限制,想用什么结构都可以。
)
【在 h*******e 的大作中提到】 : 字典给定了,是java c++ hash set 结构 ( script php python 语言: 字典结构)给 : 的, : 还是 array vector 结构给定, 搜索的时候, 给定 key 访问其中元素 复杂度是O(n) : 还是 O(1)啊?楼主问了面试官没有? : 字典大小多少啊,是2个元素,还是 26 * 26 * 26 *26 * 26 个元素阿 : ,楼主问了没有?
|
l*********8 发帖数: 4642 | 34 最怕这种“拍脑袋想出来”的题目。
【在 j***m 的大作中提到】 : 楼主我木有问啊,但是面试官的意思是,字典你可以随意存在你觉得合适的结构里面, : 只要最后能保证求出正确的结果且尽量快就好了。 : 字典大小就是所有4个字母的英文单词,有多少就是多少。 : 这个面试官说这是他有天看他家孩子玩的玩具拍脑袋想出来的题,所以其实是一道非常 : 实际的题,只要够快,结果是对的,其他没有限制,想用什么结构都可以。 : : )
|
h*******e 发帖数: 1377 | 35 感觉 lz 爆搜可能单词方法说对了, 复杂度是不是算错了, 算成特别大了,600多怎
么算都够了阿, 即使所有四个字母26个字符的排序也就 45万 也很快的不到 0.1 秒,
字典
hash 存就好了。
如果要是字母特长比如10的话爆搜单词复杂度 26 ^10 约等于 10 ^14,那就爆搜字典
,
因为英语单词最多也就60多万个 我记得莎士比亚还是谁的来着词汇量最大 * 10
每次爆搜字典也不会超过一秒
【在 h*******e 的大作中提到】 : 楼主的面试官要改变关于什么的复杂度啊,5 ^4 才625 不到0.01秒就算完 : 了如果字典是o(1) 查询的话 也不大阿,是要改善 关于 每个字符的可能字母数5 的 : 复杂度 还是要改善关于单词长度4的复杂度啊,楼主问了没有啊? : : )
|
v***o 发帖数: 287 | 36 太brutal了。。。
,
【在 h*******e 的大作中提到】 : 感觉 lz 爆搜可能单词方法说对了, 复杂度是不是算错了, 算成特别大了,600多怎 : 么算都够了阿, 即使所有四个字母26个字符的排序也就 45万 也很快的不到 0.1 秒, : 字典 : hash 存就好了。 : 如果要是字母特长比如10的话爆搜单词复杂度 26 ^10 约等于 10 ^14,那就爆搜字典 : , : 因为英语单词最多也就60多万个 我记得莎士比亚还是谁的来着词汇量最大 * 10 : 每次爆搜字典也不会超过一秒
|
n*****n 发帖数: 5277 | 37 人家明明用的是java
【在 m******e 的大作中提到】 : 第一题定义没错,编译可以通过,但是这样调用会出现不同结果 : B* b = new B(); : A* a = b; : B c; : a->foo(c); // 调用A的foo : b->foo(c); // 调用B的foo
|
w*****z 发帖数: 1 | 38 我觉得复杂度还是挺高的。搜所有可能单词的话,所有方案数是C(26,5)^4,你说的5*5
*5*5只是一种方案中所有可能的单词个数。这里需要遍历所有方案找出最好的。
如果按词典搜的话,每个词取或不取,最坏情况时间复杂度是O(2^n),n是词典的单词
个数。当然其中可以减掉很多枝。
所以我觉得时间复杂度还是挺高的。不知道我是不是有什么地方没想到,不吝赐教。谢
谢。
,
【在 h*******e 的大作中提到】 : 感觉 lz 爆搜可能单词方法说对了, 复杂度是不是算错了, 算成特别大了,600多怎 : 么算都够了阿, 即使所有四个字母26个字符的排序也就 45万 也很快的不到 0.1 秒, : 字典 : hash 存就好了。 : 如果要是字母特长比如10的话爆搜单词复杂度 26 ^10 约等于 10 ^14,那就爆搜字典 : , : 因为英语单词最多也就60多万个 我记得莎士比亚还是谁的来着词汇量最大 * 10 : 每次爆搜字典也不会超过一秒
|
h*******e 发帖数: 1377 | 39 恩,你说得有理, 是我想差了。
又想了一下,我能想出的 大概是 搜前三个字母, C(26, 5)^ 3 , 第四
个字母 26个各搜一遍 ..取前5
*5
【在 w*****z 的大作中提到】 : 我觉得复杂度还是挺高的。搜所有可能单词的话,所有方案数是C(26,5)^4,你说的5*5 : *5*5只是一种方案中所有可能的单词个数。这里需要遍历所有方案找出最好的。 : 如果按词典搜的话,每个词取或不取,最坏情况时间复杂度是O(2^n),n是词典的单词 : 个数。当然其中可以减掉很多枝。 : 所以我觉得时间复杂度还是挺高的。不知道我是不是有什么地方没想到,不吝赐教。谢 : 谢。 : : ,
|
c********r 发帖数: 107 | |
|
|
M*******a 发帖数: 1633 | 41 第三题怎么做啊,我考,我看了都没思路阿,很罕见阿 |
s******n 发帖数: 226 | 42 把所有4 letter长的单词建立trie 每个node加上wordCount 和 prefixCount, 每一层
选的时候以 wordCount+prefixCount为标准,选五个最大的 |
J*******o 发帖数: 741 | 43 第一题是可以的,
第二题也有可能没在正确的database下啊(或者应该说schema?)
第三题还没思路 |
Q****a 发帖数: 296 | |