[原创]一道面试题

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

要求：时空复杂度尽量低

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

?
001
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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等群友的提醒，优化一下，第二版：

?
002
1
2
3
4
5
6
7
8
9
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发了一个点积的优化

?
optimization of inner produc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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;  
}  

 

Scrawl 面试题 Comments(2) 2011年8月21日 22:52

[原创]生成自描述的序列

给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数  
要求下排每个数都是先前上排那十个数在下排出现的次数。  
上排的十个数如下：  
【0，1，2，3，4，5，6，7，8，9】

最省脑细胞的做法自然是盲搜：

?
selfDescribableSeqence
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def selfDescribableSeqence(arr):
    for guess in range(9*10**len(arr)):
        guess_list = (['0']*(10-len(str(guess))))
        guess_list.extend(list(str(guess)))
        if isOK(arr, guess_list):
            return guess_list  
     
def isOK(top, bottom):
    def freq(val):
        return len(list(filter(lambda x: x == val, bottom)))
    return len(list(filter(lambda x: str(freq(x)) == bottom[int(x)], top))) == len(top)
  
 
if __name__ == '__main__':
    print(selfDescribableSeqence(list(map(str, list(range(0,10))))))

显然，脑细胞是省下了，CPU就太浪费了，要判断解空间之外的很多分支。改成宽度优先：

?
selfDescribableSeqence2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def selfDescribableSeqence():
    res = list(range(10))
    while True:
        for pos in range(10):
            adjust(res, pos)
            if isOK(res):
                return res
 
def freq(arr,val):
    return len(list(filter(lambda x: x == val, arr)))
     
def adjust(arr, pos):
    the_freq = freq(arr, pos)
    if arr[pos] != the_freq:
        arr[pos] = the_freq
        pos = the_freq
 
def isOK(arr):
    id_and_value = [(id, val) for (id,val) in enumerate(arr)]
    return len(list(filter(lambda x : freq(arr, x[0])==x[1], id_and_value))) == len(id_and_value)
 
if __name__ == '__main__':
    print(selfDescribableSeqence())

 

Scrawl 面试题 Comments(0) 2011年3月23日 16:08