Tagged: Python Toggle Comment Threads | Keyboard Shortcuts

  • loctv 1:53 pm on July 13, 2017 Permalink | Reply
    Tags: , Python   

    Segment Tree: min/max range queries problem. 

    Given an array arr[0…n-1] and multiple queries. With each query, we need to find the minimum (or maximum) value from index qs (query start) to qe (query end) where 0 <= qs <= qe < n.


    Input : arr[] = {1, 8, 5, 9, 6, 14, 2, 4, 3, 7}
    queries = 5
        qs = 0 qe = 4
        qs = 3 qe = 7
        qs = 1 qe = 6
        qs = 2 qe = 5
        qs = 0 qe = 8
    Output: Minimum = 1 and Maximum = 9
        Minimum = 2 and Maximum = 14
        Minimum = 2 and Maximum = 14
        Minimum = 5 and Maximum = 14
        Minimum = 1 and Maximum = 14

    There are multiple ways for solving this problem.

    1. Simple solution:
    Each query, we run through arr[qs…qe], find and print out the min/maximum value. This approach is useful on a small scale problem, but when array involves thousands of elements and we have thousands of queries, it is impractical, since its time complexity is O(q * n), with q is number of queries and n is number of elements in array.

    2. Segment Tree
    Utilize the properties of segment tree can help us solve this problem efficiently.
    A segment tree is a binary tree, the way it is built can be compared to merge sort algorithm. The root node contains the min value in range [0…n-1], left and right child of root node contains range of half left and half right: [0…mid] and [mid+1…0], respectively. This can be applied on left and right child of any node.
    Except leaf nodes, leaf nodes contain elements in the original array.


    Segment tree of array: [2, 5, 1, 4, 9, 3]

    Number of elements in segment tree is 2*n – 1, with n is the number of elements in the array. But since we gonna use array for the implementation, we need 2*next_power_of_two(n) – 1, next_power_of_two is a function return the smallest possible power of two that is bigger than n. Example next_power_of_two(5) will yield 8.

    Time complexity will be O(q * logn) with q is the number of queries and n is number of elements in array, which is significantly faster than the simple approach.

    class SegmentTree:
        ########################### Private Interface ############################
        def __init__(self, arr):
            self._seg_tree = [float('Inf')]*(2*self._next_power_of_two(len(arr))-1)
            # input array
            self._arr = arr
            self._construct_tree(self._arr, self._seg_tree, 0, len(self._arr)-1, 0)
        def _construct_tree(self, arr, seg_tree, low, high, pos):
            if low >= high:
                # build two child first
                # (value, (range)) -> help query easier
                seg_tree[pos] = (arr[low], (low, low))
            mid = (low+high) // 2
            # build left subtree
            self._construct_tree(arr, seg_tree, low, mid, 2*pos+1)
            # build right subtree
            self._construct_tree(arr, seg_tree, mid+1, high, 2*pos+2)
            # build the parent of two children above
            # get min of two children, and range is [low, high]
            seg_tree[pos] = (min(seg_tree[self._left(pos)][0], seg_tree[self._right(pos)][0]), (low, high))
        def _is_power_of_two(self, n):
            return n > 0 and (n & (n-1)) == 0
        def _next_power_of_two(self, n):
            # if n is already a power of two, return it
            if self._is_power_of_two(n):
                return n
            count = 0
            while n > 0:
                count += 1
                # right shift bit = divide by 2
                n = n >> 1
            # 1 << count = 2**count
            return 1 << count
        def _left(self, p):
            # return left child of p
            return p*2 + 1
        def _right(self, p):
            # return right child of p
            return p*2 + 2
        def _has_child(self, p):
            # check if p has children
            return self._left(p) < len(self._seg_tree) and self._right(p) < len(self._seg_tree)               ########################### Public Interface ############################          def query_min(self, qs, qe, pos):         # since there are some INF element         # we need to check instance type         if isinstance(self._seg_tree[pos], float):             return float('Inf')         # get range of the current 'pos'         # and min of current range         start, end = self._seg_tree[pos][1]         min_val = self._seg_tree[pos][0]                  # case 1: range of node is within qs and qe          #       => return min of range
            if qs <= start and qe >= end:
                return min_val
            # case 2: range of node is outside qs and qe
            #       => return INF (indicate redundant value)
            if end < qs or start > qe:
                return float('Inf')
            # case 3: range of node is partition overlapped with qs and qe
            #       return min([left_child, qs, qe], [right_child, qs, qe])
            # first we need to check if it has child
            # if no, return its value, otherwise call query_min for left and right child
            if self._has_child(pos):
                return min(self.query_min(qs, qe, self._left(pos)), self.query_min(qs, qe, self._right(pos)))
                return self._seg_tree[pos][0]

    As you can see in the query_min() method, there are three cases can happen.
    1. The range of current node is completely inside the range of query.
    2. The range of current node is completely outside the range of query.
    3. The range of current node is partition overlapped with the range of query.

    More understanding can be gained after watching this video. In my opinion, it is by far the most understandable video describing how a min/max query works on segment tree.
    Segment Tree Query Demo

    Some problem for practising:

  • loctv 1:20 pm on July 2, 2017 Permalink | Reply
    Tags: Python   

    Advanced Python: Pickle, Shelve. Pickling 'unpickable' objects 

    + A module supports writing objects to file, more about pickle can be found at Python docs.
    + Simple example: dump a dictionary into file

    d = {'a':1, 'b':2}
    # open file with write - binary mod 
    f = open('data.pkl', 'wb')
    import pickle
    # dump d into file f
    pickle.dump(d, f)
    # read back d from f
    f = open('data.pkl', 'rb')
    e = pickle.load(f)
    # print out: {'a':1, 'b':2}

    + Another example: dump a list into file

    import pickle
    # list contain a list, string and a number
    some_data = [['a', 'list'], 'a string', 5]
    with open('pickle_list','wb') as f:
        pickle.dump(some_data, f)
    # reload dumped list 
    with open('pickle_list', 'rb') as f:
        loaded_data = pickle.load(f)
    # no error popup
    assert some_data == loaded_data

    How it works:
    + When pickle tries to dump (serialize) object, it simply tries to store object’s __dict__ attribute. __dict__ is a dictionary mapping all the attribute names on the object to their values. Before checking __dict__, pickle checks to see whether a __getstate__ method exists. If it does, it will store the returned value of that method instead of __dict__.
    + But some objects that are ‘unpickable’, example: open network socket, open file, running thread, database connection stored as an attribute of an object.

    Example: Supposed you have an URL that automatically update after every one hour. You implement it with a class call UpdatedURL, this class has 4 attribute:
    + url: the url
    + content: content when you open it in browser
    + last_updated: the last time the url was updated
    + timer: Timer object, start the schedule
    The objects of class UpdatedURL are unpickable because of the timer attribute (running thread). So the solution here is to remove it before pickling and re-initialize it (get back the timer) after unpickling it from file.

    from threading import Timer
    import datetime
    from urllib.request import urlopen
    class UpdatedURL:
        def __init__(self, url):
            self.url = url
            self.contents = ''
            self.last_updated = None
        def update(self):
            self.contents = urlopen(self.url).read()
            self.last_updated = datetime.datetime.now()
        def schedule(self):
            self.timer = Timer(3600, self.update)
        # pickle use this for pickling
        def __getstate__(self):
            new_state = self.__dict__.copy()
            if 'timer' in new_state:
                del new_state['timer']
            return new_state
        # and while unpickling, we get back the timer (call schedule())
        def __setstate___(self, data):
            self.__ditct__ = data

    + __setstate__ method can be implemented to customize unpickling. This method accepts value returned by __getstate__, which is a dictionary.

    + shelve uses pickle to convert object into byte string, an associate that object with a key.
    + Example: Suppose we have a class Person, with three attributes: name, job, payment. We create three Person objects, bob, sue, tom and we want to write it in a way that we can get them back by key. Shelve works as a small database (dictionary) with key corresponding to each object that we dump into file.

    import shelve
    # write
    db = shelve.open('persondb') # create a file name persondb.db
    for obj in (bob, sue, tom):
        db[obj.name] = obj # associate key - obj
    db.close() # force pushing all data (flush) into file
    # read
    db = shelve.open('persondb')
    for key in shelve.keys(): # dictionary's interface

    + Under the hood, when instances are shelved or pickled, the underlying pickling system records both instance attributes and enough information to locate their class automatically when they are fetched.

  • loctv 9:36 pm on June 19, 2017 Permalink | Reply
    Tags: Python   

    Advanced Python: Coroutines 

    Coroutines are extremely powerful constructs that are often confused with generators. The difference between generator and coroutines: a generator only produces values, while a coroutine can also consume them.
    How coroutines works?

    • yield occurs and the generator pauses.
    • send() occurs from outside the function and the generator wakes up.
    • the value sent in assigned to the left side of the yield statement.
    • the generator continues processing until it encounters another yield statement.

    Let’s take two examples.

    1. Score board in 1-1 match.

    Suppose we want to make a score board for a basketball match between Houston and Golden State. There are multiple ways to do this, but let’s use coroutines.

    First we need to create a coroutine object.

    def tally():
        score = 0
        while True:
            increment = yield score
            score += increment

    Then we use it to update score of Houston and GoldenState

    houston = tally()
    next(houston) # return 0
    golden_state = tally()
    next(golden_state) # return 0

    Why call next? Whenever a ‘next’ call called on a coroutine object, the code inside is run until it meet the first yield statement, return the value on the right side of yield (which is score), pause and wait for the next call called.
    So the first two values to be printed out are two zeros.

    Then Houston just got 2 scores, right after that Golden State pay back with 3 scores

    houston.send(2) # return 2
    golden_state.send(3) # return 3

    Next, Houston continue with 2 scores and Golden State reply them with 2 scores

    houston.send(2) # return 4
    golden_state.send(2) # return 5

    The way that corountines work is: Whenever you call send method, it get the value that you send in, run the code until it meets the next yield statement, yield that value out and wait until the next send method is sent.
    So first houston’s score is 0, we call next, it returns 0. Then we send 2, it assigns 2 for increment, score increase 2, meet yield statement, and yield out score (2), pause there. Finally, we send 2, it assigns 2 for increment, score increase 2, meet yield statement, and yield out score again (now 4). Since yield is inside an infinite loop, it will run forever.

    2. Log file parser.
    Let’s say we have a log file with the content below.

    unrelated log messages
    sd 0:0:0:0 Attached Disk Drive
    unrelated log messages
    sd 0:0:0:0 (SERIAL=ZZ12345)
    unrelated log messages
    sd 0:0:0:0 [sda] Options
    unrelated log messages
    XFS ERROR [sda]
    unrelated log messages
    sd 2:0:0:1 Attached Disk Drive
    unrelated log messages
    sd 2:0:0:1 (SERIAL=ZZ67890)
    unrelated log messages
    sd 2:0:0:1 [sdb] Options
    unrelated log messages
    sd 3:0:1:8 (SERIAL=WW11111)
    unrelated log messages
    sd 3:0:1:8 [sdc] Options
    unrelated log messages
    XFS ERROR [sdc]
    unrelated log messages

    The task is: obtain the serial number of any drives that have XFS ERROR.

    We use regular expression for this task, so what we send to the coroutine is the pattern that the re module use to find matching values.

    Let’s define a function called get_serials, this function takes a file_name as an input, and it will return all the serial numbers of devices (or drives) that have XFS ERROR.

    import re
    def get_serials(file_name):
        ERROR_PAT = 'XFS ERROR ('\[sd[a-z]\])'
        matcher = match_regex(file_name, ERROR_PAT)
        device = next(matcher)
        while True:
            bus = matcher.send('(sd \S+) {}'.format(re.escape(device)))
            serial = matcher.send('{} \(SERIAL=([^)]*)\)'.format(bus))
            yield serial 
            device = matcher.send(ERROR_PAT)

    What is missing from the code above is match_regex function, we haven’t define it yet. It will be our coroutine object, we send it the pattern, it will return the string match the pattern.

    def match_regex(file_name, regex):
        with open(file_name) as f:
            lines = f.readlines()
        for line in reversed(lines):
            match = re.match(regex, line)
            if match:
                t = match.group()[0]
                regex = yield t 

    Here we read the log file in reversed order.
    Note it regex = yield t. First next call on match_regex inside get_serial will run the code inside match_regex, with the initialized pattern. It yields the result of the first matching line, which is XFS ERROR [sdc].
    Each iteration inside while of get_serials will get the serial number of the drive that has XFS Error. The first send call will send the pattern to get the drive’s bus, which is something like sd 2:0:0:1, then the serial will be found based on that bus value. It keeps repeating the process until nothing to be parsed.
    The returned values (serial numbers) are: WW11111, ZZ12345

    Those are two example that demo the usage of coroutines. In real life software development, we rarely see coroutines in action, but it still worth knowing.

  • loctv 6:41 pm on March 19, 2017 Permalink | Reply
    Tags: , Python   

    Problem: Manasa and Stones 

    Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either a or b. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 0, find all the possible values for the number on the last stone.

    Note: The numbers on the stones are in increasing order.

    Input Format

    The first line contains an integer T, i.e. the number of test cases. T test cases follow; each has 3 lines. The first line contains n (the number of stones). The second line contains a, and the third line contains b.


    1 <= T <= 10
    1 <= n, a, b <= 10^3

    Output Format

    Space-separated list of numbers which are the possible values of the last stone in increasing order.

    Sample Input


    Sample Output

    2 3 4 
    30 120 210 300 


    All possible series for the first test case are given below:

    1. 0,1,2
    2. 0,1,3
    3. 0,2,3
    4. 0,2,4

    Hence the answer 2 3 4.

    Series with different number of final steps for second test case are the following:

    1. 0, 10, 20, 30
    2. 0, 10, 20, 120
    3. 0, 10, 110, 120
    4. 0, 10, 110, 210
    5. 0, 100, 110, 120
    6. 0, 100, 110, 210
    7. 0, 100, 200, 210
    8. 0, 100, 200, 300

    Hence the answer 30 120 210 300.


    1. Using backtracking. Generate all possible sequences, get all last values, and put them into a set. This is acceptable with n small (less than 15), since the complexity is O(2^n). Here is the code for backtracking
    2. Analyze. Let’s take 2 examples above and find out the pattern. In the first example, n = 3 and there are 3 different ending values, max value is 4 and the difference from the largest to the smallest is 1 (4 -> 3 -> 2) . In the second example, n = 4 and there are 4 different ending values, max value is 300 and difference between pairs is 90. Have you seen the pattern yet? With n, there are n different values, the largest value is max(a,b)*(n-1), the difference is max(a,b) – min(a,b), or a – b, if a is bigger, otherwise b-a. How can we know that this pattern is the one that we’re looking for. First, since there are only two values a,b, assume a is bigger than b (it works the same way if b is bigger than a). Then the biggest possible value you can get is b*(n-1). since the first one is 0. The second biggest is b*(n-1) – (a-b), since this is the second biggest, the last value is b, instead of a. We c0ntinue this as long as the value return after calculate the difference is positive. And this is actually n-1 times, since we already manually calculate the largest.

    Source code. The chain function is how you print out all possible stones chain, with complexity O(2^n). Inside main is the code to solve this problem.

    def chain(n, arr, options):
        for i in options:
            arr[n] = arr[n-1] + i
            if n == len(arr) - 1:
                chain(n+1, arr, options)
    def test():
        chain(1, [0]*4, (10, 100))
    if __name__ == '__main__':
        t = int(input().strip())
        for _ in range(t):
            n = int(input().strip())
            a = int(input().strip())
            b = int(input().strip())
            if b > a:
                a, b = b, a
            pos_values = [0]*n
            pos_values[0] = a*(n-1)
            for i in range(1, len(pos_values)):
                pos_values[i] = pos_values[i-1] - (a-b)
            pos_values = list(set(pos_values))
  • loctv 10:50 pm on March 7, 2017 Permalink | Reply
    Tags: , Python   

    Problem: Check Mirror in N-ary tree 

    *Difficulty: Medium

    Given two n-ary tree’s the task is to check if they are mirror of each other or not.


    1                      1
    /    \                 /   \
    2      3             3     2

    Output: 1

    1                        1
    /  \                    /  \
    2    3                2     3

    Output: 0

    Note: you may assume that root of both the given tree as 1.

    The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two space separated values n and e denoting the no of nodes and edges respectively. Then in the next line two lines are 2*e space separated values u,v denoting an edge from u to v for the both trees .

    For each test case in a new line print 1 if both the trees are mirrors of each other else print 0.



    3 2
    1 2 1 3
    1 3 1 2
    3 2
    1 2 1 3
    1 2 1 3

    Approach: Since this is a N-arr tree, that means one node can have multiple child. So the easiest way is to consider it as a graph. Each graph has a list of adjacent nodes. The way to to check  if two threes (or graphs if you will) are mirror of each other or not is:

    1. They have the same number of nodes
    2. All node have the same number of adjacent nodes
    3. The child list of each node in the first tree when reversed will be exactly like the one in the node of second tree and vice versa.

    Implementation: Python 3

    def is_mirror(tree_1, tree_2):
        if len(tree_1) != len(tree_2):
            return False
        for node in tree_1:
            if len(tree_1[node]) != len(tree_2[node]):
                return False 
            if tree_1[node] != list(reversed(tree_2[node])):
                return False 
        return True 
    def create_tree():
        tree = {}
        arr = list(map(int, input().strip().split()))
        for i in range(0,len(arr),2):
            if arr[i] in tree:
                tree[arr[i]] = [arr[i+1]]
        return tree
    if __name__ == '__main__':
        t = int(input().strip())
        for _ in range(t):
            n, e = list(map(int, input().strip().split()))
            tree_1 = create_tree()
            tree_2 = create_tree()
            # print(tree_1)
            # print(tree_2)
            print(1 if is_mirror(tree_1, tree_2) else 0)
  • loctv 7:44 pm on February 27, 2017 Permalink | Reply
    Tags: Python   

    Thug life creator 


    Source code:



  • loctv 12:49 pm on February 22, 2017 Permalink | Reply
    Tags: , Python   


    *Difficulty: Easy



    Since the constraints is so high, we need a way to insert and sort the array (or list) that has the complexity equal or lower than O(logn). With n loop and each loop costs O(logn) we have the complexity O(nlogn), which is acceptable. Using linked list and binary search is one of the possible ways. But If you know Python, this problem can be solved in 10 lines of code, using insort method from bisect module.

    Implementation: Python 3

    import bisect
    n = int(input())
    l = []
    for _ in range(n):
        ai = int(input())
        bisect.insort(l, ai)
        if len(l) % 2 == 0:
            print('%.1f' % ((l[len(l)//2-1]+l[len(l)//2])/2))
            print('%.1f' % (l[len(l)//2]))
  • loctv 11:46 pm on February 21, 2017 Permalink | Reply
    Tags: , Python   

    Problem: Separate the Numbers 

    *Difficulty: Easy


    Here’s how I did it, and I think example is the best way to explain it:
    s = 1011121314
    Start with first number = 1, next is 0, False
    Start with first number = 10, next is 11, next is 12, …..
    Eventually, return True
    The maximum length of first number will be equal len(s) // 2 (if length s is even), or len(s) // 2 + 1 (length s is odd)
    Let’s take another example:
    First number: 1, next 0 => False
    First number: 10, next 00=> False
    First number: 100, next 000=>False
    First number: 1000. next 000=>False
    First number:1000000 next 1000001 => True
    Hope you get the idea :>

    Implementation: Python 3

    def is_beautiful(number):
        if number == '' or number[0] == '0' or len(number) <= 2:
            return [False] 
        bound = len(number) // 2
        start_length = 1
        while start_length <= bound:
            first_str = number[:start_length]
            first_int = int(first_str)
            i = start_length
                while i < len(number):
                    next = next_str(i, first_str, first_int, number)
                    if next is None:
                        changed = False
                        next_1, next_2 = next
                        if int(next_1) == first_int+1:
                            first_str = next_1
                            first_int = int(next_1)
                            i += len(next_1)
                            changed = True 
                            if next_2:
                                if int(next_2) == first_int+1:
                                    first_str = next_2
                                    first_int = int(next_2)
                                    i += len(next_2)
                                    changed = True 
                        # cant found next number 
                        if not changed:
                        # check out of bound 
                        if i > len(number):
                        # all numbers statisfy the condition
                        if i == len(number):
                            return True, number[:start_length]
            except Exception:
            start_length += 1
        return [False]
    def next_str(i, first_str, first_int , number):
        # get the next number 
        # check if it has equal or longer length 
        # return two next, but only one of them is usable 
        next_1 = ""
        next_2 = ""
        if i < len(number):
            if number[i] == '0':
                return None 
                if i + len(first_str) <= len(number):
                    next_1 = number[i:i+len(first_str)]
                if i + len(first_str) + 1 <= len(number):
                    next_2 = number[i:i+len(first_str)+1]
                return next_1, next_2
        return None
    def main():
        t = int(input())
        for _ in range(t):
            number = str(input().strip())
            result = is_beautiful(number)
            if result[0]:
                print('YES', result[1])
    if __name__ == '__main__':
  • loctv 3:28 pm on February 20, 2017 Permalink | Reply
    Tags: , Python   

    Problem: Making Anagrams 

    *Difficulty: Easy



    Approach: To be able to make anagrams from two string, we have to find their common characters first. For example, if we have abccd and cdcc, then their common characters is c and d. Then we build two string contains only character that is in both string a and string b. In the previous example, string a = ccd and string b = cdcc. The last thing we need to do is make them anagrams. We do that by iterating through either string a or string b, with each character d, if there are more d in string a than string b, we remove d from a to make the number of d equal in both a and b. In our example, string b will remove 1 ‘c’, then a = ccd and b = dcc. Notice that we don’t have to do this on string, we rather do this on dictionary of string. Since the input only contains lower English alphabet, the maximum size of the dictionary will contain only 26 keys and 26 corresponding values. If key ‘c’ in a has higher value than key ‘c’ in b, then set its value to ‘c’ in b.

    Implementation: Python 2.7

    from collections import Counter
    def make_anagrams(a, b):
        a_set = set(list(a))
        b_set = set(list(b))
        a_counter = Counter()
        b_counter = Counter()
        # get char in common 
        for c in a:
            if c in b_set:
                a_counter[c] += 1
        for c in b:
            if c in a_set:
                b_counter[c] += 1
        # make anagrams 
        for key in a_counter.keys():
            a_val = a_counter.get(key)
            b_val = b_counter.get(key)
            if a_val > b_val:
                a_counter[key] = b_val
                b_counter[key] = a_val
        # calculate removed char
        a_lost = len(a) - sum([a_counter.get(x) for x in a_counter.keys()])
        b_lost = len(b) - sum([b_counter.get(x) for x in b_counter.keys()])
        return a_lost + b_lost
    if __name__ == '__main__':
        a = input().strip()
        b = input().strip()
        print(make_anagrams(a, b))
  • loctv 10:25 pm on February 19, 2017 Permalink | Reply
    Tags: , Python   

    Problem: Arrays Left Rotation 

    • Difficulty: Easy

    Problem description:
    Array Left Rotation pdf

    All approaching ideas is inspired by Python.
    Approach: The first thing come in my mind is using a for loop, using Python list slice notation. But it’s too expensive both in computing muscle and memory usage. With the constraints, it will get TLE. Another approach is using modular arithmetic. Basically, rotate array d times means that we start iterating at index d. We have to use modular arithmetic to wrap around the array in case of reaching the end of array but still haven’t iterated through all elements yet.

    Implementation: Python 3

    def rotate(arr, d):
        count = 0
        start = d % len(arr)
        while count < len(arr):
            print(arr[start], end=' ')
            count += 1
            start = (start + 1) % len(arr)
    if __name__ == '__main__':
        n, d = list(map(int, input().strip().split()))
        arr = list(map(int, input().strip().split()))
        rotate(arr, d)
Compose new post
Next post/Next comment
Previous post/Previous comment
Show/Hide comments
Go to top
Go to login
Show/Hide help
shift + esc