A Microsoft Interview Question

interview_q1.py

# Q: Given an array of numbers, shift 0 and 1 numbers to the end of the array without changing the orders.
# Example:
# input = [912, 92, 0, 1, 1, 3, 0, 7]
# output = [912, 92, 3, 7, 0, 1, 1, 0]

# This, BTW, is a tough problem. All the inplace(0(1) space) solutions have O(n^2) time complexity below. But have a 
# hard logarithmic solution. You can see this Quora thread for details on this: 
# http://www.quora.com/What-algorithms-move-all-negative-numbers-before-positive-numbers-and-preserve-their-original-orders-at-the-same-time-O-n-time-and-O-1-space-are-required

def d(a):    
    for i in range(len(a)):
        if a[i] == 0 or a[i] == 1:
            for j in range(i+1, len(a)):
                if not (a[j] == 0 or a[j] == 1):
                    for w in reversed(range(i+1, j+1)):
                        a[w], a[w-1] = a[w-1], a[w]
                    break
    return a

# optimized version of above as we only use iterators.
def d_optimize(a):
    setb = (0, 1)
    for i, x in enumerate(a):
        if x in setb:
            for j, y in enumerate(a[i:]):
                if y not in setb:
                    be = i + j
                    for k, _ in enumerate(reversed(a[i:be])):
                        k = be - k 
                        a[k], a[k-1] = a[k-1], a[k]
                    break
    return a

# a more simpler version: use list remove/insert to eliminate continuous swapping.
# sometimes it seems to run faster than above. I think it has better average time 
# complexity.
def d_optimize2(a):
    setb = (0, 1)
    for i, x in enumerate(a):
        if x in setb:
            for j, y in enumerate(a[i:]):
                if y not in setb:
                    a.pop(i+j)
                    a.insert(i, y)
                    break
    return a

# simplest but correct one (used for testing)
def correct_a(a):
    post = []
    pre = []
    for x in a:
        if x == 0 or x == 1:
            post.append(x)
        else:
            pre.append(x)
    return  pre + post


import random 
p = [int(random.randint(1,1000)) for i in range(10000)]
p += [int(random.randint(0,1)) for i in range(10000)]

p2 = p[:]
b = d(p2)
c = d_optimize(p) # %5 performance gain
for i in range(len(b)):
    assert b[i] == c[i]