kenics.net

Technical notes on perl, python, php, sql, cgi, c/c++, q/kdb+, unix/shell, revision control tools, data structures & algorithms, and their applications into web services and other various forms of software engineering.

python exercise

 
################################## 
#####    random exercises    ##### 
################################## 
 
 
### 
###  subsequence check 
### 
 
 
--------------------------------- 
def subseqCheck(a,b):  # is b a seubsequence of a? 
   j = 0 
   for i in a: 
      if i == b[j]: 
         j += 1 
         if j == len(b): 
            return True 
   return False 
--------------------------------- 
 
### 
###  fibonacci 
### 
 
------------------------------------ 
 

#  fibonacci with recursion 

def fiboRec(n): 
    if n == 1 or n == 2: 
        return 1 
    else: 
        return fiboRec(n-1) + fiboRec(n-2) 
 

#  fibonacci with iteration 

def fiboIte(n): 
    fib = [1,1] 
    if n == 1 or n == 2: 
        return 1 
    for i in range(2,n): 
        fib.append(fib[i-1] + fib[i-2]) 
    return fib.pop() 
 
print fiboRec(5) 
print fiboIte(6) 
 
----------------------------------- 
 
 
### 
###  singly linked list; loop detection demo 
### 
 
----------------------------------- 
#!/usr/bin/python 
 
class node: 
    def __init__(self,data): 
        self.next = None 
        self.data = data 
 
class LL: 
    def __init__(self): 
        self.head = None 
        self.tail = None 
    def addNode(self,data): 
        if self.head == None: 
            self.head = node(data) 
            self.tail = self.head 
        else: 
            self.tail.next = node(data) 
            self.tail = self.tail.next 
    def printLL(self): 
        tmp = self.head 
        while tmp != None: 
            print tmp.data 
            tmp = tmp.next 
 
def detectLoop1(ll):  # keep track of visited nodes, so when any reappears, it is a loop 
    visited = []      # time O(n) is ok, but auxiliary space O(n) can be a problem 
    tmp = ll.head 
 
    while tmp != None: 
        if visited.count(tmp): 
            return True 
        visited.append(tmp) 
        tmp = tmp.next 
 
    return False 
 
def detectLoop2(ll):  # slow iterater iterates one by one, fast iterator iterates every second node 
                      # in theory, fastItr will catch up with slowItr if any loop 
                      # time O(n), and auxiliary space(1) in that regard this is a better version. 
    slowItr = ll.head 
    fastItr = ll.head 
 
    while(slowItr != None and fastItr != None): 
        if fastItr.next == None: 
            break 
        fastItr = fastItr.next.next 
        slowItr = slowItr.next 
        if slowItr == fastItr: 
            return True 
 
    return False 
 
if __name__ == "__main__": 
 
    ll = LL() 
    ll.addNode("foo") 
    ll.addNode("bar") 
    ll.addNode("yen") 
    ll.addNode("pen") 
    ll.printLL()             #  foo-bar-yen-pen 
 
    # lets test two functions 
 
    print detectLoop1(ll)    # False 
    print detectLoop2(ll)    # False 
 
    ll.tail.next = ll.head.next   #  lets connect "pen"->"bar" thus causing an infinite loop 
 
#    ll.printLL()    # inifite loop 
 
    print detectLoop1(ll)    # True 
    print detectLoop2(ll)    # True 
 
------------------------------------------------------------ 
 
 
### 
###  rotate the elements of an array by k pos 
### 
 
##  (a typical interview question)  #(ref)  http://leetcode.com/2010/04/rotating-array-in-place.html 
 
-----------------------------------------------------// rotateArr.py 
def reverseElem(array,begin,end): 
    if begin == end: # one elem array, nothing to do 
        return array 
    size = end - begin + 1 
    for i in range(size/2): 
        array[begin+i] = array[begin+i] + array[end-i] 
        array[end-i] = array[begin+i] - array[end-i] 
        array[begin+i] = array[begin+i] - array[end-i] 
    return array 
 
 
array = [1,2,3,4,5] 
k = 3 
 
array = reverseElem(array,0,len(array)-1) 
array = reverseElem(array,k,len(array)-1) 
array = reverseElem(array,0,k-1) 
 
print array 
 
------------------------------------------------------// 
 
 
## 
## There is a sorted array of integers. rotate it by N index positions. write a function to determine N. 
## 
 
# e.g. 
rotatedList = [3,4,5,1,2]    # n = 3 
 
# O(n) ver. 
def findRotationCount(rotatedList): 
    min = rotatedList[0] 
    idx = -1 
    prev = -1 
    for i in range(len(rotatedList)): 
        if prev > rotatedList[i]: 
            idx = i 
            break 
        if min > rotatedList[i]: 
            min = rotatedList[i] 
            idx = i 
        prev = rotatedList[i] 
    return idx 
 
# O(log n) ver. 
def findRotationCount2(rotatedList,begin,end): 
    if end == -1: 
        print "empty list" 
        return -1 
    if begin == end:  # single elem array 
        return 0 
    # if only two elem, the latter's idx is n (assuming the ascending order in the original array) 
    if begin == (end-1): 
        if(rotatedList[begin] == rotatedList[end]): # just a special case where every elem in the array is the same val 
            return 0 
        return end 
    mid = (end+begin)/2 
    if rotatedList[begin] <= rotatedList[mid]: 
        return findRotationCount2(rotatedList,mid,end) 
    elif rotatedList[begin] > rotatedList[mid]: 
        return findRotationCount2(rotatedList,begin,mid) 
 
print findRotationCount(rotatedList)                        # 3 
print findRotationCount2(rotatedList,0,len(rotatedList)-1)  # 3 
 
 
## 
##  given a sorted array of integers. rotate it by N index positions. 
##  Now write a function to sort it in O(n) in-place. 
## 
 
# just combines solutions from the prev two questions. 
 
-------------------------------------------------- 
 
def rotateBackToSorted(rotatedList): 
    size = len(rotatedList) 
    idx = findRotationCount2(rotatedList,0,size-1) 
    rotatedList = reverseElem(rotatedList,0,idx-1) 
    rotatedList = reverseElem(rotatedList,idx,size-1) 
    rotatedList = reverseElem(rotatedList,0,size-1) 
    return rotatedList 
 
print rotateBackToSorted(rotatedList) 
 
-------------------------------------------------- 
 
### 
###  self-printing code 
### 
 
demonstrates "recursion theorem" from computation theory. 
 
Th: Let T be a Turing machine that computes a function t: Z*,Z* -> Z* 
    There is a Turing machine R that computes a function r: Z* -> Z*, where for every w, 
          r(w) = t(<R>,w) 
 
 
many examples on the web. here is a python example. 
 
-----------quine.py-------------- 
s = "print \"s = \\\"\"+s.replace(\"\\\\\",\"\\\\\\\\\").replace(\"\\\"\",\"\\\\\\\"\")+\"\\\"\"+\"\\n\"+s" 
print "s = \""+s.replace("\\","\\\\").replace("\"","\\\"")+"\""+"\n"+s 
--------------------------------- 
 
Essentially the string defines the program core while the program core prints the string and the rest of the code (which may include header, footer, variable declaration, etc). Notice we print the string twice, first time for the string definition itself, and the second time for printing the program core itself which is defined in the string. The only tricky part is taking care of escape characters, which is the source of the headache as shown above. There are many more elegant examples on the web that makes use of each language's builtin functions, etc. 
 
 
 
### 
###  vwap calc 
### 
 
def calc_vwap(filename):   # suppose an input csv file with ticker,px,qty,ts   # ts = timestamp 
   ticker2data = {}        # that contains a whole day tick history 
   with open(infile, 'r') as infile: 
      while(True): 
         line = infile.readline() 
         if line == "\n": 
            continue 
         elif line == '':  # EOF 
            break 
         [ticker,px,qty,ts] = line.strip(',') 
         if ticker not in ticker2data.keys(): 
            ticker2data[ticker] = {} 
            ticker2data[ticker][vwap] = 0 
            ticker2data[ticker][mktcap] = 0 
            ticker2data[ticker][cumqty] = 0 
         ticker2data[ticker][mktcap] += px * qty 
         ticker2data[ticker][cumqty] += qty 
         ticker2data[ticker][vwap] = ticker2data[ticker][mktcap] / ticker2data[ticker][cumqty] 
         print(ticker,',',ts,',',round(ticker2data[ticker][vwap],4))  # intraday vwap 
   for t in ticker2data.keys(): 
      print(t,':'ticker2data[t][vwap])   # EOD vwap 
 
 
### 
###  twap 
### 
 
def calc_twap(filename):   # suppose an input csv file with ticker,px,qty,ts   # ts = timestamp 
   ticker2data = {}        # that contains a whole day tick history 
   with open(infile, 'r') as infile: 
      while(True): 
         line = infile.readline() 
         if line == "\n": 
            continue 
         elif line == '':  # EOF 
            break 
         [ticker,px,qty,ts] = line.strip(',') 
         if ticker not in ticker2data.keys(): 
            ticker2data[ticker] = {} 
            ticker2data[ticker][twap] = 0 
            ticker2data[ticker][sumup] = 0 
            ticker2data[ticker][sumts] = 0 
            ticker2data[ticker][prevpx] = 0 
            ticker2data[ticker][prevts] = 0 
         ticker2data[ticker][sumup] = ticker2data[ticker][prevpx] * (ts - ticker2data[ticker][prevts]) 
         ticker2data[ticker][sumts] += (ts - ticker2data[ticker][prevts]) 
         ticker2data[ticker][prevpx] = px 
         ticker2data[ticker][prevts] = ts 
         ticker2data[ticker][twap] = ticker2data[ticker][sumup] / ticker2data[ticker][sumts] 
         print(ticker,',',ts,',',round(ticker2data[ticker][twap],4))  # intraday twap 
   for t in ticker2data.keys(): 
      print(t,':'ticker2data[t][twap])   # EOD twap 
 

  1. 2015-02-05 23:55:54 |
  2. Category : python
  3. Page View:

Google Ads