Amex SPG卡送25K points 白送500刀现金 最佳酒店卡# Living
c*p
1 楼
1. design and implement LRUCache
要求给出完整的实现代码，包括类的声明，变量的声明，初始化等的。几乎就是那种可以直接编
译运行的。
我在白板上写代码的时候，面试官（似乎是manager）在电脑上记录。由于我在写代码
的时候，位置安排的不好，写到后来没有地方了，我就把一部分写好的擦掉了。他似乎
很不高兴。所以，今后面试的XDJM要注意避免犯这样的错误。
2. The problem description is as follows:
You are given a deck containing 313 cards. While holding the deck:
1. Take the top card off the deck and set it on the table
2. Take the next card off the top and put it on the bottom of the deck
in your hand.
3. Continue steps 1 and 2 until all cards are on the table. This is a
round.
4. Pick up the deck from the table and repeat steps 1-3 until the deck
is in the original order.
Write a program to determine how many rounds it will take to put the
deck back into the original order."
他们希望你尽量用stl， boost来写。
这个题目看起来简单，直接queue， stack 模拟就行了。但是对于有些数字，比如题目
中的313， 运行时间就会很长。
比较好的解法是计算法：
一个是用最大公约数 lcm(),这个是最快的。
另外一个是求解n, 使得permutation matrix p的n次方是单位矩阵。
参见
http://www.gamedev.net/topic/589859-card-shuffle-problem/
和： http://www.careercup.com/question?id=7780673 （注意Eric Xu的解法）
注：这个组叫G e o T e am. 面的人有做data analysis的，有data mining的，也有编
程的。 不知道这个组究竟要找什么样的人。有个面试官希望你有object-oriented
design能力和线性代数的知识（比如，Eigenvalues）。如果要面这个组，最好提前复
习点这方面的知识。 这个组好像是新成立的，挺需要人的。
反馈比较快，三天就给结果了。。。 据了。
要求给出完整的实现代码，包括类的声明，变量的声明，初始化等的。几乎就是那种可以直接编
译运行的。
我在白板上写代码的时候，面试官（似乎是manager）在电脑上记录。由于我在写代码
的时候，位置安排的不好，写到后来没有地方了，我就把一部分写好的擦掉了。他似乎
很不高兴。所以，今后面试的XDJM要注意避免犯这样的错误。
2. The problem description is as follows:
You are given a deck containing 313 cards. While holding the deck:
1. Take the top card off the deck and set it on the table
2. Take the next card off the top and put it on the bottom of the deck
in your hand.
3. Continue steps 1 and 2 until all cards are on the table. This is a
round.
4. Pick up the deck from the table and repeat steps 1-3 until the deck
is in the original order.
Write a program to determine how many rounds it will take to put the
deck back into the original order."
他们希望你尽量用stl， boost来写。
这个题目看起来简单，直接queue， stack 模拟就行了。但是对于有些数字，比如题目
中的313， 运行时间就会很长。
比较好的解法是计算法：
一个是用最大公约数 lcm(),这个是最快的。
另外一个是求解n, 使得permutation matrix p的n次方是单位矩阵。
参见
http://www.gamedev.net/topic/589859-card-shuffle-problem/
和： http://www.careercup.com/question?id=7780673 （注意Eric Xu的解法）
注：这个组叫G e o T e am. 面的人有做data analysis的，有data mining的，也有编
程的。 不知道这个组究竟要找什么样的人。有个面试官希望你有object-oriented
design能力和线性代数的知识（比如，Eigenvalues）。如果要面这个组，最好提前复
习点这方面的知识。 这个组好像是新成立的，挺需要人的。
反馈比较快，三天就给结果了。。。 据了。
