[原创]一道面试题

duweifu posted @ 2011年8月21日 22:52 in Scrawl with tags 面试题 , 1148 阅读

题目: 2n个数,一半奇数,一半偶数,设计一个程序让奇数位上的数是奇数,偶数位上的是偶数

要求:时空复杂度尽量低

看到群里发的这个题目,随手写了个一个答案:

def swap(a, i, j): 
    a[i] = a[i] + a[j]
    a[j] = a[i] - a[j]
    a[i] = a[i] - a[j]
        
def Fun():
    the_list = [x for x in range(100)]
    print "orginal:", the_list
    random.shuffle(the_list)
    print "shuffled:", the_list
    i,j = 0,1
    nSwap = 0
    while nSwap < 50 and max(i,j) < 100:
        if the_list[i] % 2 != 0 and the_list[j] % 2 == 0 :
            swap(the_list,i,j)
            i += 2
            j += 2
            nSwap += 1
        elif the_list[i] % 2 == 0 :
            i += 2
        elif the_list[j] % 2 != 0 :
            j += 2
    print "sorted:", the_list

经penny等群友的提醒,优化一下,第二版:

def Fun2():
    the_list = [x for x in range(100)]
    print "orginal:", the_list
    random.shuffle(the_list)
    print "shuffled:", the_list 
    for i,j in zip([pos for pos in range(0,100,2) if (the_list[pos] + pos) % 2 != 0],
                              [pos for pos in range(1,100,2) if (the_list[pos] + pos) % 2 != 0]):
        the_list[i], the_list[j] = the_list[j], the_list[i]
    print "sorted:", the_list

附:penny发了一个点积的优化

A[]={<0,4>,<3,5>,<8,3>}
B[]={<3,5>,<9,3>}

C=A*B = {<3,25>}

for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;	
	if(A[i].index == B[j].index)
	{
		C[k].index = A[i].index;
		C[k].value = A[i].value * B[j].value
		k++
	}
	else if(A[i].index < B[j].index)
	{
		i++;
	}
	else if(A[i].index > B[j].index )
	{
		j++;
	}
}

A_I[]={0,3,8}
B_I[]={3,9}
A_V[]={4,5,9}
B_V[]={5,3}
for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;
	if(A_I[i] == B_I[j])
	{
		C[k].index = A_I[i];
		C[k].value = A_V[i]*B_V[j];
	}
	else if(A_I[i] < B_I[j])
	{
		i++;
	}
	else
	{
		j++;
	}
}

for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;
	i=0;
	j=0;
	bool equal  =  A_I[i] == B_I[j];
	bool smaller=  A_I[i] < B_I[j]; 
	bool bigger =  A_I[i] > B_I[j];
	C[k].index  =  equal*A_I[i];
	C[k].value  =  equal*A_V[i]*B_V[j];
	k+=equal;
	i+=equal;
	j+=equal;
        i+=smaller;
	j+=biger;	
}	

 

Avatar_small
scturtle 说:
2011年8月22日 14:39

个人觉得虽然复杂度高点儿但pythonic的写法:
from itertools import ifilter,ifilterfalse
a=[1,2,3,4]
odd=list(ifilter(lambda x: x%2, a))
even=list(ifilterfalse(lambda x: x%2, a))
a[::2]=even
a[1::2]=odd
print a

Avatar_small
duweifu 说:
2011年8月22日 14:47

@scturtle: 嗯,不错。而且之前不知道可以ifilterfalse,多谢! 一直纠结于降低空间复杂度,代码写得很别扭。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter