【跟着pongba思考】也是一道面试题
51 views
Skip to first unread message
Yong Yuan
May 19, 2008, 10:35:02 AM5/19/08
to pon...@googlegroups.com
凑个热闹。:-) 觉得这道题有趣之处在于找出一项可行的解不难，但找出最优解，却需要细致的观察和思维的跳跃。也许这道题没有那么难，只不过我没有点石成金的洞察力，导致解法冗长。这道题断断续续花了很久才做出来。要在面试的短短10来分钟里写出最优解的代码，肯定是不行了。//惭愧ing。下面是题目：
给出一长度为2n的数组：A1A2A3...AnB1B2B3...Bn，要求把该数组重组为A1B1A2B2A3B3...AnBn。该算法只能使用O(1)的额外空间。例子：27543hiwca重组后变为2h7i5w4c3a。
现在想来，如果事先知道几项数学知识，也许求最优解就方便多了。How to Solve It: Modern Heuristics里说如果知道用哪些知识解题，题目也就容易了。搜索空间小了嘛。所以这里就不说是哪几坨知识了。:-)
pongba
May 19, 2008, 10:37:55 AM5/19/08
to pon...@googlegroups.com
2008/5/19 Yong Yuan <yyc...@gmail.com>:
凑个热闹。:-) 觉得这道题有趣之处在于找出一项可行的解不难，但找出最优解，却需要细致的观察和思维的跳跃。也许这道题没有那么难，只不过我没有点石成金的洞察力，导致解法冗长。这道题断断续续花了很久才做出来。要在面试的短短10来分钟里写出最优解的代码，肯定是不行了。//惭愧ing。下面是题目：给出一长度为2n的数组：A1A2A3...AnB1B2B3...Bn，要求把该数组重组为A1B1A2B2A3B3...AnBn。该算法只能使用O(1)的额外空间。例子：27543hiwca重组后变为2h7i5w4c3a。现在想来，如果事先知道几项数学知识，也许求最优解就方便多了。How to Solve It: Modern Heuristics里说如果知道用哪些知识解题，题目也就容易了。搜索空间小了嘛。所以这里就不说是哪几坨知识了。:-)
嗯嗯， 这道题目好像silwile不久前跟我说过。programming pearl上一道题目与此类似。
--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba
Yong Yuan
May 19, 2008, 10:40:49 AM5/19/08
to pon...@googlegroups.com
red...@gmail.com
May 19, 2008, 10:52:40 AM5/19/08
to pon...@googlegroups.com
大家都很喜欢思考, 似乎我中学的时候才喜欢思考数学题, 大学和毕业之后一段时
间喜欢思考怎么写好软件, 现在什么都不想思考, 只想吃饱睡好, 向猪学习了 :(
间喜欢思考怎么写好软件, 现在什么都不想思考, 只想吃饱睡好, 向猪学习了 :(
Yong Yuan wrote:
> 凑个热闹。:-) 觉得这道题有趣之处在于找出一项可行的解不难，但找出最优
> 解，却需要细致的观察和思维的跳跃。也许这道题没有那么难，只不过我没有点
> 石成金的洞察力，导致解法冗长。这道题断断续续花了很久才做出来。要在面试
pongba
May 19, 2008, 10:54:25 AM5/19/08
to pon...@googlegroups.com
2008/5/19 <red...@gmail.com>:
大家都很喜欢思考, 似乎我中学的时候才喜欢思考数学题, 大学和毕业之后一段时
间喜欢思考怎么写好软件, 现在什么都不想思考, 只想吃饱睡好, 向猪学习了 :(
哈哈，肖兄说出了大家的心声:-)
lbaby
May 19, 2008, 8:43:04 PM5/19/08
to TopLanguage
Googol Lee
May 19, 2008, 9:45:42 PM5/19/08
to pon...@googlegroups.com
心声阿～～～～～
2008/5/20 lbaby <lba...@yahoo.com.cn>:
--
新的理论从少数人的主张到一统天下，并不是因为这个理论说服了别人抛弃旧观点，而是因为一代人的逝去。
My blog: http://googollee.blog.163.com
sanachilleus
May 19, 2008, 11:55:44 PM5/19/08
to TopLanguage
Yong Yuan
May 20, 2008, 12:20:25 AM5/20/08
to pon...@googlegroups.com
liuxinyu
May 20, 2008, 12:48:07 AM5/20/08
to TopLanguage
正好前阵在cpper上大家讨论过此题，感兴趣者不妨看看，可以节省一些duplicate的思考
http://www.cpper.com/c/t4838.html
> 觉得这道题有趣之处在于找出一项可行的解不难，但找出最优解，却需要细致的观察和思维的跳跃。也许这道题没有那么难，只不过我没有点石成金的洞察力，导致解法冗 长。这道题断断续续花了很久才做出来。要在面试的短短10来分钟里写出最优解的代码，肯定是不行了。//惭愧ing。下面是题目：
>
> 给出一长度为2n的数组：A1A2A3...AnB1B2B3...Bn，要求把该数组重组为A1B1A2B2A3B3...AnBn。该算法只能使用O(1) 的额外空间。例子：27543hiwca重组后变为2h7i5w4c3a。
http://www.cpper.com/c/t4838.html
> 觉得这道题有趣之处在于找出一项可行的解不难，但找出最优解，却需要细致的观察和思维的跳跃。也许这道题没有那么难，只不过我没有点石成金的洞察力，导致解法冗 长。这道题断断续续花了很久才做出来。要在面试的短短10来分钟里写出最优解的代码，肯定是不行了。//惭愧ing。下面是题目：
>
> 给出一长度为2n的数组：A1A2A3...AnB1B2B3...Bn，要求把该数组重组为A1B1A2B2A3B3...AnBn。该算法只能使用O(1) 的额外空间。例子：27543hiwca重组后变为2h7i5w4c3a。
Concrete Vitamin
May 20, 2008, 1:03:55 AM5/20/08
to pon...@googlegroups.com
obtuseSword
May 21, 2008, 7:10:40 AM5/21/08
to TopLanguage
// Algorithm: 逐个变换
// ----- 比如原本第二个位置的元素，被放置到第三个位置
// ----- 原本第三个位置的元素，被放置到第五个位置……
// ----- 当所有元素都放置到正确的位置上，算法结束
// ----- 思考具体实现，如果元素的位置编号从 0 开始
// ----- 容易得到： 原本处于位置 i 的元素将被放置到位置 2i%(2n-1)
// ----- 因此变换的过程就是，先将原本处于位置 1 的元素放置到位置 2
// ----- 再将原本处于位置 2 的元素放置到位置 4 ……
// ----- 这样编号为 X1 = { 2^k mod (2n-1) | k=1,2,...} 的元素都放置到正确的位置上
// ----- 在剩下的元素 { 1,2,...,2n-1 } - X1 中取最小元，执行同样的过程，又有一部分
// ----- 元素被放置到正确的位置上。反复执行这个过程，直至所有元素都被放置到正确位置
// Author: obtuseSword
// Date: 2008-05-21
// Compiler: Visual Studio 2005
// Note: 程序中有个值得改进的地方，就是如何快速判断某一位置是否已经在先前处理过
// ----- 这就需要求助于数论的知识了
#include <iostream>
#include <string>
using namespace std;
int n;
string str;
inline int NEXT(int index){
return 2*index % ( 2*n-1 );
}
int main()
{
while( cin>> n, n ){
// 输入原始字符串
cin>> str;
// 变换到目标字符串
for(int start = 1; start <= 2*n-2; start++){
// 测试 start 是否已经访问过了
// 根据我们的变换规则，容易证明：
// start 未被访问，当且仅当
// 含 start 的变换循环中不含小于 start 的数
int index = NEXT( start );
while( index > start )
index = NEXT( index );
if( index < start )
continue;
// 从 start 开始对字符串进行变换
char preChar = str[ start ];
for(index = NEXT( start ); index != start;
index = NEXT( index ) ){
char tmp = str[ index ];
str[ index ] = preChar;
preChar = tmp;
}
str[ start ] = preChar;
}
// 输出变换后的字符串
cout<< str <<endl;
}
}
// ----- 比如原本第二个位置的元素，被放置到第三个位置
// ----- 原本第三个位置的元素，被放置到第五个位置……
// ----- 当所有元素都放置到正确的位置上，算法结束
// ----- 思考具体实现，如果元素的位置编号从 0 开始
// ----- 容易得到： 原本处于位置 i 的元素将被放置到位置 2i%(2n-1)
// ----- 因此变换的过程就是，先将原本处于位置 1 的元素放置到位置 2
// ----- 再将原本处于位置 2 的元素放置到位置 4 ……
// ----- 这样编号为 X1 = { 2^k mod (2n-1) | k=1,2,...} 的元素都放置到正确的位置上
// ----- 在剩下的元素 { 1,2,...,2n-1 } - X1 中取最小元，执行同样的过程，又有一部分
// ----- 元素被放置到正确的位置上。反复执行这个过程，直至所有元素都被放置到正确位置
// Author: obtuseSword
// Date: 2008-05-21
// Compiler: Visual Studio 2005
// Note: 程序中有个值得改进的地方，就是如何快速判断某一位置是否已经在先前处理过
// ----- 这就需要求助于数论的知识了
#include <iostream>
#include <string>
using namespace std;
int n;
string str;
inline int NEXT(int index){
return 2*index % ( 2*n-1 );
}
int main()
{
while( cin>> n, n ){
// 输入原始字符串
cin>> str;
// 变换到目标字符串
for(int start = 1; start <= 2*n-2; start++){
// 测试 start 是否已经访问过了
// 根据我们的变换规则，容易证明：
// start 未被访问，当且仅当
// 含 start 的变换循环中不含小于 start 的数
int index = NEXT( start );
while( index > start )
index = NEXT( index );
if( index < start )
continue;
// 从 start 开始对字符串进行变换
char preChar = str[ start ];
for(index = NEXT( start ); index != start;
index = NEXT( index ) ){
char tmp = str[ index ];
str[ index ] = preChar;
preChar = tmp;
}
str[ start ] = preChar;
}
// 输出变换后的字符串
cout<< str <<endl;
}
}
dailiangren
May 21, 2008, 9:53:26 PM5/21/08
to pon...@googlegroups.com
哎，这个问题的最终解答是什么啊，我都想好久
dailiangren
2008-05-22
发件人：
obtuseSword
发送时间：
2008-05-21 19:10:55
收件人：
TopLanguage
抄送：
主题： [TopLanguage] Re:
【跟着pongba思考】也是一道面试题
hong
May 22, 2008, 12:44:46 AM5/22/08
to TopLanguage
/****
@author shxiao
首先最中间的两个数调换，分别把这两个数移到第2和2n-1的位置，
把移数时所经过的位置都向中间靠拢一个位移，此时问题就转化
成了数组[1..2n-1]的同样的问题了。
下面是通过循环实现的
**/
function test(data) {
if (data.length%2){
alert("偶数长度");
return ;
}
var swap = function(i, j){
var t = data[i];
data[i] = data[j];
data[j] = t;
}
var len = data.length/2 - 1; //数组下标从0开始，所以减一
for (var i = len; i > 0; i--, i--) { //迭代的实现互换数据
swap(len, len+1);
for( var j = 0; j < ( i-1); j++) {
swap(len-j, len-j-1);
swap(len+j+1, len+j+2);
}
}
return data;
}
@author shxiao
首先最中间的两个数调换，分别把这两个数移到第2和2n-1的位置，
把移数时所经过的位置都向中间靠拢一个位移，此时问题就转化
成了数组[1..2n-1]的同样的问题了。
下面是通过循环实现的
**/
function test(data) {
if (data.length%2){
alert("偶数长度");
return ;
}
var swap = function(i, j){
var t = data[i];
data[i] = data[j];
data[j] = t;
}
var len = data.length/2 - 1; //数组下标从0开始，所以减一
for (var i = len; i > 0; i--, i--) { //迭代的实现互换数据
swap(len, len+1);
for( var j = 0; j < ( i-1); j++) {
swap(len-j, len-j-1);
swap(len+j+1, len+j+2);
}
}
return data;
}
lbaby
May 22, 2008, 4:14:45 AM5/22/08
to TopLanguage
liuxinyu
May 22, 2008, 6:46:15 AM5/22/08
to TopLanguage
缺点是这一方法的时间复杂度是O(n^2)，而cpper上提出要挑战O(n)
Eric
May 22, 2008, 6:30:46 PM5/22/08
to TopLanguage
O(n) 's algorithm is quite complicated. The challange here is to find
the representative element of each cyclic group which in total are a
permutation.
Here are two papers, one is based on number theory, the other is based
on recursive algorithm (and some number theory).
http://www.cs.uvic.ca/%7Ejellis/Publications/shuffle.ps [Source:
http://zhiqiang.org/blog/posts/an-algorithm-face-interviews-question-test.html]
or:
http://arxiv.org/pdf/0805.1598
Method 2 is easier and interesting. [The idea in this paper is quite
interesting]
As far as I know, there is no trivial solution (w/o number theory) in
O(n). Don't touth this problem w/o basic Number Theory background. ;)
the representative element of each cyclic group which in total are a
permutation.
Here are two papers, one is based on number theory, the other is based
on recursive algorithm (and some number theory).
http://www.cs.uvic.ca/%7Ejellis/Publications/shuffle.ps [Source:
http://zhiqiang.org/blog/posts/an-algorithm-face-interviews-question-test.html]
or:
http://arxiv.org/pdf/0805.1598
Method 2 is easier and interesting. [The idea in this paper is quite
interesting]
As far as I know, there is no trivial solution (w/o number theory) in
O(n). Don't touth this problem w/o basic Number Theory background. ;)
可口可乐
May 22, 2008, 8:51:20 PM5/22/08
to TopLanguage
Cool!
Thanks for these two papers you provided
On May 23, 7:30 am, Eric <xu.math...@gmail.com> wrote:
> O(n) 's algorithm is quite complicated. The challange here is to find
> the representative element of each cyclic group which in total are a
> permutation.
>
> Here are two papers, one is based on number theory, the other is based
> on recursive algorithm (and some number theory).
>
> http://www.cs.uvic.ca/%7Ejellis/Publications/shuffle.ps[Source:http://zhiqiang.org/blog/posts/an-algorithm-face-interviews-question-...]
Thanks for these two papers you provided
On May 23, 7:30 am, Eric <xu.math...@gmail.com> wrote:
> O(n) 's algorithm is quite complicated. The challange here is to find
> the representative element of each cyclic group which in total are a
> permutation.
>
> Here are two papers, one is based on number theory, the other is based
> on recursive algorithm (and some number theory).
>
dailiangren
May 22, 2008, 10:10:56 PM5/22/08
to pon...@googlegroups.com
果然挺复杂的
dailiangren
2008-05-23
发件人：
Eric
发送时间：
2008-05-23 06:31:06
收件人：
TopLanguage
抄送：
主题： [TopLanguage] Re:
【跟着pongba思考】也是一道面试题
Reply all
Reply to author
Forward
0 new messages