Z**********4
发帖数: 528 | 1 一面：
给一个电话号码盘，就是跟手机上一样。
然后有一个国际象棋的马在1的位置，问有多少中路径可以刚好十步跳到9. 注意*跟#不
用考虑，但是得考虑0.
跳法就是1可以跳到6， 6可以跳到0， 0也可以跳到4， 4跳到9。
递归解决。
onsite
1. boggle的游戏。类似于leetcode的wordsearch。唯一的区别是，最好把dictionary
里面的单词放入trie里面，这样
匹配的时候会快点。
2. 聊工作经验。面试官是个老美，声音小，语速快。
感觉对我的经验不是很感兴趣。
并且也没有问code问题。
问了一些宽泛的问题，比如如果要load 1million records到内存，用什么数据结构。
我答看需要执行什么query。如果类似于找到exact matched record就用hash。如果
是找类似于满足一定大小关系的records，应该用ordered map。他很不满意，也不知道
该怎么回答了。但是很确定会挂了。
果然他问了30分钟以后说，你还有什么问题，问吧。
随便问了几个问题，被告知等待。他去叫下一个面试官。
正打算换换脑子，hr过来说，不好意思，下面的人有会议，you are free to go。
于是大家都不想搞得太尴尬，我就说听起来不错。这就结束啦。 | n****e
发帖数: 2401 | 2 哈哈，秒据了
dictionary
【在 Z**********4 的大作中提到】
: 一面：
: 给一个电话号码盘，就是跟手机上一样。
: 然后有一个国际象棋的马在1的位置，问有多少中路径可以刚好十步跳到9. 注意*跟#不
: 用考虑，但是得考虑0.
: 跳法就是1可以跳到6， 6可以跳到0， 0也可以跳到4， 4跳到9。
: 递归解决。
: onsite
: 1. boggle的游戏。类似于leetcode的wordsearch。唯一的区别是，最好把dictionary
: 里面的单词放入trie里面，这样
: 匹配的时候会快点。
| d******8
发帖数: 2191 | 3 good lesson, good luck!
dictionary
【在 Z**********4 的大作中提到】
: 一面：
: 给一个电话号码盘，就是跟手机上一样。
: 然后有一个国际象棋的马在1的位置，问有多少中路径可以刚好十步跳到9. 注意*跟#不
: 用考虑，但是得考虑0.
: 跳法就是1可以跳到6， 6可以跳到0， 0也可以跳到4， 4跳到9。
: 递归解决。
: onsite
: 1. boggle的游戏。类似于leetcode的wordsearch。唯一的区别是，最好把dictionary
: 里面的单词放入trie里面，这样
: 匹配的时候会快点。
| G******n
发帖数: 572 | | G******n
发帖数: 572 | 5 还有lz是在哪申请的？
dictionary
【在 Z**********4 的大作中提到】
: 一面：
: 给一个电话号码盘，就是跟手机上一样。
: 然后有一个国际象棋的马在1的位置，问有多少中路径可以刚好十步跳到9. 注意*跟#不
: 用考虑，但是得考虑0.
: 跳法就是1可以跳到6， 6可以跳到0， 0也可以跳到4， 4跳到9。
: 递归解决。
: onsite
: 1. boggle的游戏。类似于leetcode的wordsearch。唯一的区别是，最好把dictionary
: 里面的单词放入trie里面，这样
: 匹配的时候会快点。
| h**********w
发帖数: 39 | | v***0
发帖数: 5096 | 7 这个公司我当年拒过两次，一次intern一次full time
一直有说法公司文化有问题，看来当年选择没错。
dictionary
【在 Z**********4 的大作中提到】
: 一面：
: 给一个电话号码盘，就是跟手机上一样。
: 然后有一个国际象棋的马在1的位置，问有多少中路径可以刚好十步跳到9. 注意*跟#不
: 用考虑，但是得考虑0.
: 跳法就是1可以跳到6， 6可以跳到0， 0也可以跳到4， 4跳到9。
: 递归解决。
: onsite
: 1. boggle的游戏。类似于leetcode的wordsearch。唯一的区别是，最好把dictionary
: 里面的单词放入trie里面，这样
: 匹配的时候会快点。
| Z**********4
发帖数: 528 | 8 谢谢：）
【在 d******8 的大作中提到】
: good lesson, good luck!
:
: dictionary
| Z**********4
发帖数: 528 | 9 对啊 人生完整啦！
【在 n****e 的大作中提到】
: 哈哈，秒据了
:
: dictionary
| v***0
发帖数: 5096 | 10 另外这个公司的package也一般。
【在 v***0 的大作中提到】
: 这个公司我当年拒过两次，一次intern一次full time
: 一直有说法公司文化有问题，看来当年选择没错。
:
: dictionary
| | | Z**********4
发帖数: 528 | 11 递归。暴力就可以。
但是如果它要问第100步刚好走到9估计就不行了。
感觉可以dp
【在 G******n 的大作中提到】
: 第一题怎么做？
| Z**********4
发帖数: 528 | 12 哈哈。谢谢。
就是想赞人品~~
【在 h**********w 的大作中提到】
: lz最近发面经好多，赞一个，rp+1
| Z**********4
发帖数: 528 | 13 给力啊~
佩服。
【在 v***0 的大作中提到】
: 这个公司我当年拒过两次，一次intern一次full time
: 一直有说法公司文化有问题，看来当年选择没错。
:
: dictionary
| v***0
发帖数: 5096 | 14 这种雇写手写review的公司想来也不是什么好地方
“Very interesting hedge fund”
Software Developer (Former Employee) New York, NY
Pros – Salary, benefits are exceptional; work with the latest technologies;
flexible work arrangements; growing company;
Cons – None really -- be prepared to work hard, but have fun because the wo
rk is so amazing;
Advice to Senior Management – Don't change anything -- it's a good work env
ironment -- rewarding personally and economically
Yes, I would recommend this company to a friend – I'm optimistic about the
outlook for this company
【在 Z**********4 的大作中提到】
: 给力啊~
: 佩服。
| v***0
发帖数: 5096 | 15 连老婆都不让怀孕。
Cons – See the title. A new hire passed all the exams and get an official o
ffer from Hong Kong office. The new hire then let them know his wife is preg
nant since he needs to ask some information. After knowing that, Citadel too
k the offer back with the reason that they lost the confidence of the new hi
re.
technologies;
wo
env
the
【在 v***0 的大作中提到】
: 这种雇写手写review的公司想来也不是什么好地方
: “Very interesting hedge fund”
: Software Developer (Former Employee) New York, NY
: Pros – Salary, benefits are exceptional; work with the latest technologies;
: flexible work arrangements; growing company;
: Cons – None really -- be prepared to work hard, but have fun because the wo
: rk is so amazing;
: Advice to Senior Management – Don't change anything -- it's a good work env
: ironment -- rewarding personally and economically
: Yes, I would recommend this company to a friend – I'm optimistic about the
| h*******e
发帖数: 1377 | 16 店面是dp阿，rebecca9的微软面经里面有的 算法复杂度
O(stepNum * 10)
【在 Z**********4 的大作中提到】
: 递归。暴力就可以。
: 但是如果它要问第100步刚好走到9估计就不行了。
: 感觉可以dp
| m*****k
发帖数: 731 | 17 why?
递归都写出来了， 多少步不就是个输入参数么？
我跑了跑，
reach('1', '9', 10);
返回
1-->8-->3-->4-->0-->6-->7-->#-->5-->*-->9
reach('1', '9', 100);
无解。
【在 Z**********4 的大作中提到】
: 递归。暴力就可以。
: 但是如果它要问第100步刚好走到9估计就不行了。
: 感觉可以dp
| G******n
发帖数: 572 | 18 #不考虑。
无解是说超过time limit了？
【在 m*****k 的大作中提到】
: why?
: 递归都写出来了， 多少步不就是个输入参数么？
: 我跑了跑，
: reach('1', '9', 10);
: 返回
: 1-->8-->3-->4-->0-->6-->7-->#-->5-->*-->9
: reach('1', '9', 100);
: 无解。
| G******n
发帖数: 572 | 19 哦我还以为是数学题。。我来跑一跑，你的答案是多少
【在 Z**********4 的大作中提到】
: 递归。暴力就可以。
: 但是如果它要问第100步刚好走到9估计就不行了。
: 感觉可以dp
| Z**********4
发帖数: 528 | 20 GodofPen说的对，
我说不行了就是说递归太慢 100 肯定run 死了。
# *的确不能算。
【在 m*****k 的大作中提到】
: why?
: 递归都写出来了， 多少步不就是个输入参数么？
: 我跑了跑，
: reach('1', '9', 10);
: 返回
: 1-->8-->3-->4-->0-->6-->7-->#-->5-->*-->9
: reach('1', '9', 100);
: 无解。
| | | Z**********4
发帖数: 528 | 21 我忘了。。六百多好像。。
【在 G******n 的大作中提到】
: 哦我还以为是数学题。。我来跑一跑，你的答案是多少
| t**********h
发帖数: 2273 | 22 尼玛，这不算秒据吧，最多算面到一半被赶出去了。这个很正常，很多很吊的公司都这样
【在 n****e 的大作中提到】
: 哈哈，秒据了
:
: dictionary
| y***n
发帖数: 1594 | 23 其实我觉得这样好，大家都不要浪费时间，像相亲一样，不行就走。 | m*****k
发帖数: 731 | 24 public static int reach(char start, char end , int steps){
HashMap keyboard = new HashMap<>();
keyboard.put('1', new int[]{0,0});
keyboard.put('2', new int[]{0,1});
keyboard.put('3', new int[]{0,2});
keyboard.put('4', new int[]{1,0});
keyboard.put('5', new int[]{1,1});
keyboard.put('6', new int[]{1,2});
keyboard.put('7', new int[]{2,0});
keyboard.put('8', new int[]{2,1});
keyboard.put('9', new int[]{2,2});
keyboard.put('*', new int[]{3,0});
keyboard.put('0', new int[]{3,1});
keyboard.put('#', new int[]{3,2});
return reach( start, end , steps, keyboard, "");
}
private static int reach(char start, char end, int steps,
HashMap keyboard, String path) {
if(steps == 0){
if(start==end){
System.out.println(path);
System.out.println();
return 1;
}
else{
return 0;
}
}
else{
int[] startPosition = keyboard.get(start);
int startX = startPosition[0];
int startY = startPosition[1];
int routes = 0;
for(char charX: keyboard.keySet()){
if(path.contains(charX+"")){
continue;
}
int[] position = keyboard.get(charX);
int x = position[0];
int y = position[1];
if(Math.abs(startX - x)==2 && Math.abs(startY - y)==1 || Math.abs
(startX - x)==1 && Math.abs(startY - y)==2 ){
int temp = reach( charX, end, steps - 1, keyboard, path.
equals("")? start + "-->" + charX : path + "-->" + charX);
routes+=temp;
}
}
return routes;
}
}
public void testReach(){
int routes = InterviewQs.reach('1', '9', 6);
System.out.println(routes);
routes = InterviewQs.reach('1', '9', 100);
System.out.println(routes);
}
一秒都不到。
# * does not matter at all, 不需要注释掉就行了。
看结果吧：
1-->6-->7-->#-->5-->*-->9
1
0
无解表示不可能100步从1到9
# * 注释掉后10步从1到9也无解，
你们有解的话贴个路径出来看看吧，我看看我哪儿错了。
【在 Z**********4 的大作中提到】
: GodofPen说的对，
: 我说不行了就是说递归太慢 100 肯定run 死了。
: # *的确不能算。
| m*****n
发帖数: 2152 | 25 显然用dp最快(2*N^2)，递归的话是O(2^N);
int main()
{
vector > table{
{4,6},{6,8},{7,9},{4,8},{0,3,9},
{},{0,1,7},{2,6},{1,3},{2,4}
};
vector count(10, 0);
count[1] = 1;
for(int ipos=1; ipos<11; ipos++)
{
vector temp(10, 0);
for(int idigit=0; idigit<10; idigit++)
{
for_each(table[idigit].begin(), table[idigit].end(),
[&](int elem){temp[idigit]+=count[elem];});
}
count = temp;
}
cout << "total count = " << count[9] << endl;
}
答案是 696次。 | Z**********4
发帖数: 528 | 26 我看了下，的确没啥问题。
我当时没有run 100了。。他要求9我就不想自找麻烦看看100可不可以搞定。。
不过也很惊奇，你这个竟然没有超时。你要不要试试看1000会不会超时？
【在 m*****k 的大作中提到】
: public static int reach(char start, char end , int steps){
: HashMap keyboard = new HashMap<>();
: keyboard.put('1', new int[]{0,0});
: keyboard.put('2', new int[]{0,1});
: keyboard.put('3', new int[]{0,2});
: keyboard.put('4', new int[]{1,0});
: keyboard.put('5', new int[]{1,1});
: keyboard.put('6', new int[]{1,2});
: keyboard.put('7', new int[]{2,0});
: keyboard.put('8', new int[]{2,1});
| Z**********4
发帖数: 528 | 27 这个办法果然代码简洁很多。
有个问题
那个foreach的后面的[&]是什么意思？意思是函数地址？
【在 m*****n 的大作中提到】
: 显然用dp最快(2*N^2)，递归的话是O(2^N);
: int main()
: {
: vector > table{
: {4,6},{6,8},{7,9},{4,8},{0,3,9},
: {},{0,1,7},{2,6},{1,3},{2,4}
: };
: vector count(10, 0);
: count[1] = 1;
: for(int ipos=1; ipos<11; ipos++)
| m*****n
发帖数: 2152 | 28 跳100次的是 4090112886582542336 次，跳1000次溢出了。
【在 Z**********4 的大作中提到】
: 我看了下，的确没啥问题。
: 我当时没有run 100了。。他要求9我就不想自找麻烦看看100可不可以搞定。。
: 不过也很惊奇，你这个竟然没有超时。你要不要试试看1000会不会超时？
| m*****n
发帖数: 2152 | 29 lambda 函数，取引用，C++11的新功能。
【在 Z**********4 的大作中提到】
: 这个办法果然代码简洁很多。
: 有个问题
: 那个foreach的后面的[&]是什么意思？意思是函数地址？
| Z**********4
发帖数: 528 | 30 哈哈，这样这个foreach就跟
underscore.js里面的_.each一样差不多啦！
有意思。
【在 m*****n 的大作中提到】
: lambda 函数，取引用，C++11的新功能。
| | | Z**********4
发帖数: 528 | 31 那我觉得这一题用递归解也是完全可以达。
【在 m*****n 的大作中提到】
: 跳100次的是 4090112886582542336 次，跳1000次溢出了。
| h*******e
发帖数: 1377 | 32 mark
【在 m*****n 的大作中提到】
: 显然用dp最快(2*N^2)，递归的话是O(2^N);
: int main()
: {
: vector > table{
: {4,6},{6,8},{7,9},{4,8},{0,3,9},
: {},{0,1,7},{2,6},{1,3},{2,4}
: };
: vector count(10, 0);
: count[1] = 1;
: for(int ipos=1; ipos<11; ipos++)
| m*****n
发帖数: 2152 | 33 是啊，现在C++,java,python是越来越像了。
【在 Z**********4 的大作中提到】
: 哈哈，这样这个foreach就跟
: underscore.js里面的_.each一样差不多啦！
: 有意思。
| m*****k
发帖数: 731 | 34 请教一下，跳100次的是 4090112886582542336 次 是啥意思啊？
696又是咋回事？
【在 m*****n 的大作中提到】
: 跳100次的是 4090112886582542336 次，跳1000次溢出了。
| m*****k
发帖数: 731 | 35 啥六百多啊？
跳10步从1到9有六百多不同跳法？
贴个路径出来看看好不？
【在 Z**********4 的大作中提到】
: 我忘了。。六百多好像。。
| m*****k
发帖数: 731 | 36 long s = System.currentTimeMillis();
int routes = reach('1', '9', 1000);
System.out.println(routes);
long e = System.currentTimeMillis();
System.out.println(e - s);
返回
0
8
8毫秒
【在 Z**********4 的大作中提到】
: 我看了下，的确没啥问题。
: 我当时没有run 100了。。他要求9我就不想自找麻烦看看100可不可以搞定。。
: 不过也很惊奇，你这个竟然没有超时。你要不要试试看1000会不会超时？
| t*******e
发帖数: 274 | 37 没看懂这个table是什么意思？ 这种解法有java version的么？c++实在苦手
【在 m*****n 的大作中提到】
: 显然用dp最快(2*N^2)，递归的话是O(2^N);
: int main()
: {
: vector > table{
: {4,6},{6,8},{7,9},{4,8},{0,3,9},
: {},{0,1,7},{2,6},{1,3},{2,4}
: };
: vector count(10, 0);
: count[1] = 1;
: for(int ipos=1; ipos<11; ipos++)
| t*******e
发帖数: 274 | 38 终于知道dp那个解法怎么得出696种路径了，它允许一个数字键被多次访问。
部分解如下：
1-->8-->1-->8-->1-->8-->3-->8-->3-->4-->9
1-->8-->1-->8-->1-->8-->1-->6-->0-->4-->9
1-->8-->1-->8-->1-->8-->1-->6-->7-->2-->9
1-->8-->1-->8-->1-->8-->1-->8-->3-->4-->9
【在 m*****k 的大作中提到】
: 啥六百多啊？
: 跳10步从1到9有六百多不同跳法？
: 贴个路径出来看看好不？
| m*****k
发帖数: 731 | 39 OMG!
谢谢你！
那就把continue注释掉，
的确得出696了。
now run 100 does take too long.
【在 m*****k 的大作中提到】
: long s = System.currentTimeMillis();
: int routes = reach('1', '9', 1000);
: System.out.println(routes);
: long e = System.currentTimeMillis();
: System.out.println(e - s);
: 返回
: 0
: 8
: 8毫秒
| Z**********4
发帖数: 528 | 40 兄弟 难为你了
我忘了提醒同一个数字键可以被多次访问。。
【在 m*****k 的大作中提到】
: OMG!
: 谢谢你！
: 那就把continue注释掉，
: 的确得出696了。
: now run 100 does take too long.
| | | Z**********4
发帖数: 528 | 41 最后还是得上dp。
【在 m*****k 的大作中提到】
: OMG!
: 谢谢你！
: 那就把continue注释掉，
: 的确得出696了。
: now run 100 does take too long.
| m*****k
发帖数: 731 | 42 那就再加个map存中间结果不就dp了么。
public static BigInteger reach(char start, char end, int steps) {
Map keyboard = new TreeMap<>();
Map pathsMap = new HashMap<>();
keyboard.put('1', new int[] { 0, 0 });
keyboard.put('2', new int[] { 0, 1 });
keyboard.put('3', new int[] { 0, 2 });
keyboard.put('4', new int[] { 1, 0 });
keyboard.put('5', new int[] { 1, 1 });
keyboard.put('6', new int[] { 1, 2 });
keyboard.put('7', new int[] { 2, 0 });
keyboard.put('8', new int[] { 2, 1 });
keyboard.put('9', new int[] { 2, 2 });
//keyboard.put('*', new int[]{3,0});
keyboard.put('0', new int[] { 3, 1 });
//keyboard.put('#', new int[]{3,2});
return reach(start, end, steps, keyboard, "", pathsMap);
}
private static BigInteger reach(char start, char end, int steps, Map<
Character, int[]> keyboard, String path,
Map pathsMap) {
if (steps == 0) {
if (start == end) {
System.out.println(path);
System.out.println();
return BigInteger.ONE;
} else {
return BigInteger.ZERO;
}
} else {
String key = start + "-" + end + "-" + steps;
BigInteger paths = pathsMap.get(key);
if (paths != null) {
return paths;
}
int[] startPosition = keyboard.get(start);
int startX = startPosition[0];
int startY = startPosition[1];
BigInteger routes = BigInteger.ZERO;
for (char charX : keyboard.keySet()) {
if (path.contains(charX + "")) {
//continue;
}
int[] position = keyboard.get(charX);
int x = position[0];
int y = position[1];
if (Math.abs(startX - x) == 2 && Math.abs(startY - y) == 1 |
| Math.abs(startX - x) == 1
&& Math.abs(startY - y) == 2) {
BigInteger temp = reach(charX, end, steps - 1, keyboard,
path.equals("") ? start + "-->" + charX
: path
+ "-->" + charX, pathsMap);
routes = routes.add(temp);
}
}
pathsMap.put(key, routes);
return routes;
}
}
public void testReach() {
BigInteger routes =reach('1', '9', 10);
System.out.println(routes);
routes = InterviewQs.reach('1', '9', 100);
System.out.println(routes);
routes = InterviewQs.reach('1', '9', 1000);
System.out.println(routes);
}
得到
696
161326776045551861650639200341458944
5755469127911337978907905189388895948285161975385919087010608542550728215754
3098806982869783933438688666317090663581570571220159209666265828797940405008
0195814408998009258564884590288989879453462828464073845025495674738321705016
1407076971753536452865941814100676939481337447683253416477183189051839890694
6545293067858343682376465068439420004636984010558406656
速度还ok啦 | m*****k
发帖数: 731 | 43 请教一下
>>dp(2*N^2)，why？
为何不是 N*N*steps， where N ＝ number of digits, here N = 10
2 哪儿来的？
>>递归的话是O(2^N);
为何不是N^steps ， where N ＝ number of digits
2 哪儿来的？
【在 t*******e 的大作中提到】
: 没看懂这个table是什么意思？ 这种解法有java version的么？c++实在苦手
| m*****k
发帖数: 731 | 44 int 算100时不够用吧
【在 m*****n 的大作中提到】
: 显然用dp最快(2*N^2)，递归的话是O(2^N);
: int main()
: {
: vector > table{
: {4,6},{6,8},{7,9},{4,8},{0,3,9},
: {},{0,1,7},{2,6},{1,3},{2,4}
: };
: vector count(10, 0);
: count[1] = 1;
: for(int ipos=1; ipos<11; ipos++)
| m*****k
发帖数: 731 | 45 {4,6},{6,8},{7,9},{4,8},{0,3,9},
{},{0,1,7},{2,6},{1,3},{2,4}
啥意思啊？肯定是从马的跳步出来的但就是看不懂，大神点拨一二？
【在 Z**********4 的大作中提到】
: 这个办法果然代码简洁很多。
: 有个问题
: 那个foreach的后面的[&]是什么意思？意思是函数地址？
|
|
