The Hardest Coding Cook Book



In [1]:

    
%qtconsole



In [2]:

    
%pylab inline









    



Populating the interactive namespace from numpy and matplotlib

Chapter 5 Primitive Tyes

Problem 5.1 : Computing Parity: ------ How would you go about computing the parity of a very large number of 64-bit nonnegtive integers?



In [16]:

    
#What is Parity?
#Parity is defined as the even/odd number of bit 1 in the representation of binary.
#e.g. parity(10) is 0, since the number of 1 bits in 10 is 2(even)
def parity(num):
    result = 0
    while (num):
        result ^= 1        #Important: += is increment
        num &= (num -1)    #do not forget to renew
    return result



In [22]:

    
#test case:
test = 10
print bin(test), parity(test)



In [23]:

    
#Note:
#x & (x - 1): clear least significant bit
#x & ~(x - 1): keep the lowest set bit
#x ^ (x >> 1): What the hell is this? (Gray code)!!

Promblem 5.2 Swap Bits: ------ A 64-bit integer can be viewed as an array of 64 bits, with the bit at index 0 corresponding to the least significant bit, and the bit at index 63 corresponding to the most significant bit. Implement code that takes as input a 64-bit integer x and swaps the bits at indices $i$ and $j$.



In [18]:

    
#Python does not constrain the bits length of a object, but in C++ does.
#Check the data type to use before write the code.
def swap(num, i, j):
    if num & 1 << i != num & 1 << j :
        num ^= (1 << i | 1 << j)        #num^= 1<<i: flip the i bit value
    return num



In [20]:

    
#Test case:
test = 10
i = 4
j = 3
print bin(test), bin(swap(test, i, j))









    



0b1010 0b10010

Problem 5.3 Bit Reversal: ------ Write a function that takes a 64-bit integer x and returns a 64-bit interger consisting of the bits of x in reverse order.



In [10]:

    
#In python you can do what ever you want, but in cpp can not.
#Take care
def revers_bits(target):
    result = 0
    while(target):               #for 64 bits use i in range(64):
        result = result << 1
        result |= target & 1
        target = target >> 1
    return result



In [11]:

    
#test case
test = 10
print bin(test), bin(revers_bits(test))









    



0b1010 0b101

Problem 5.4 Closest Integers with the same weight: ----- Define the number of bits that are set to i in an unsigned 64-bit integer x to be the weight of x. Let $S_k$ donate the set of unsigned 64-bit integers whose weight is k. Suppose $x \in S_k$, and k is not 0 or 64. How would you compute $y \in S_k$ \ {x} such that $|y - x|$ is minimun?

暂时不会

Problem 5.5 The Power set: ----- Implement a method that takes as input a set S of distinct elements, and prints the power set of S. Print the subsets one per line, with elements separated by commas.



In [25]:

    
#use list data type as input
#return a list of list
from math import log
def power_set(target):
    result = []
    for i in range(2 ** len(target)):
        temp = []
        while(i):
            id = i & ~(i - 1)                   #get last sig bit
            s = target[int(log(id, 2))]         #get tie item correspond to id
            temp.append(s)
            i &= i - 1                          #clear last bit
        result.append(temp)
        print temp
    return result



In [26]:

    
#test case
test = [0,1,2,3,4]
result = power_set(test)
len(result)









    



[]
[0]
[1]
[0, 1]
[2]
[0, 2]
[1, 2]
[0, 1, 2]
[3]
[0, 3]
[1, 3]
[0, 1, 3]
[2, 3]
[0, 2, 3]
[1, 2, 3]
[0, 1, 2, 3]
[4]
[0, 4]
[1, 4]
[0, 1, 4]
[2, 4]
[0, 2, 4]
[1, 2, 4]
[0, 1, 2, 4]
[3, 4]
[0, 3, 4]
[1, 3, 4]
[0, 1, 3, 4]
[2, 3, 4]
[0, 2, 3, 4]
[1, 2, 3, 4]
[0, 1, 2, 3, 4]






    Out[26]:





32

Problem 5.6 String and integer conversions:------ "123" as 123. Your code should handle negative integers. It should throw an exception if the string does not encode an integer. e.g."123abc" is not a valid encoding. Implement string/integer inter-conversion functions. Use the following function signatures: String intToString(int x) and int stringToInt(String s)

暂时不会

Problem 5.7 Base Conversion:----- Write a function that performs base conversion. Specifically, the input is an integer base $b_1$, a string x, representing an integer x in base $b_1$, and another integer base $b_2$; the output is the string representing the integer x in base $b_2$. Assume $2 \le b_1, b_2 \le 16$. Use "A" to represent 10, "B" for 11,..., and "F" for 15



In [ ]:

!!!!Problem 5.10 Greatest common divisor:----- The greatest common divisor (GCD) of positive integers x and y is the largest integer d such that d | x and d | y, where a | b denotes a divides b, i.e., b mode a == 0. Design an algorithm for computing the GCD of two numbers without using multiplication, division or the modulus operators



In [26]:

!!!!Problem 5.14 Computing x/y:----- Given two positive integers x and y, how would you compute x/y if the only operators you can use are addition, sutraction, and multiplication?

Chapter 6: Arrays and Strings

Problem 6.1: Dutch National Flag:----- Quick sort Write a function that takes an array A and an index i into A, and rearranges the elements such that all elements less than A[i] appear first, followed by elements equal to A[i], followed by elements greater than A[i]. Space O(1), time O(|A|)



In [17]:

    
def swap(a, i, j):
    if i >= len(a) | j >= len(a) :
        print "wrong input!"
    temp = a[i] 
    a[i] = a[j]
    a[j] = temp

#input target vector(list) and i, modified list to < target[i], = target[i], > target[i]
def dutch_nation_flag(target, i):
    pivot = target[i]
    small = 0
    equal = 0
    large = len(target) - 1
    while (equal <= large):
        if(target[equal] == pivot):
            equal += 1
        elif (target[equal] < pivot):
            swap(target, equal, small)
            equal += 1
            small += 1
        else:
            swap(target, equal, large)
            large = large - 1



In [20]:

    
#test case:
a = [1,2,2,3,3,4,2,1,4,5,6,4,3,1,4,2,1]
i = 3
print a[3]
dutch_nation_flag(a, i)
a









    



3






    Out[20]:





[1, 2, 2, 1, 2, 1, 2, 1, 3, 3, 3, 4, 6, 4, 5, 4, 4]

The Hardest Coding Cook Book

Chapter 5 Primitive Tyes

Problem 5.1 : Computing Parity: ------ How would you go about computing the parity of a very large number of 64-bit nonnegtive integers?

Problem 5.3 Bit Reversal: ------ Write a function that takes a 64-bit integer x and returns a 64-bit interger consisting of the bits of x in reverse order.

Problem 5.5 The Power set: ----- Implement a method that takes as input a set S of **distinct** elements, and prints the power set of S. Print the subsets one per line, with elements separated by commas.

!!!!Problem 5.14 Computing x/y:----- Given two positive integers x and y, how would you compute x/y if the only operators you can use are addition, sutraction, and multiplication?

Chapter 6: Arrays and Strings

Problem 6.1: Dutch National Flag:----- Quick sort Write a function that takes an array A and an index i into A, and rearranges the elements such that all elements less than A[i] appear first, followed by elements equal to A[i], followed by elements greater than A[i]. Space O(1), time O(|A|)

Problem 6.2 Lazy Initialization:-----

Problem 5.5 The Power set: ----- Implement a method that takes as input a set S of distinct elements, and prints the power set of S. Print the subsets one per line, with elements separated by commas.