Saturday, March 19, 2016

[LeetCode] Counting Bits

This problem is from  leetcode 

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].

Let's list the some examples, left column are the numbers, the right column are the number of bits for each number.

0 0
1 1 <-- go back to 1
2 1 <-- go back to 1
3 2
4 1 <-- go back to 1
5 2
6 2
7 3
8 1 <-- go back to 1
.
.
.
16 1 <-- go back to 1

First of all, we observe for every 2^n number, the number of bits will be 1. Now we need to figure out the number of bits for each number between the 2^(n-1) and 2^n. Using function bits(int num) as example, we can see
bits(2)=1
bits(3) = bits(2) + bits(3-2)
bits(4) = 1
bits(5) = bits(4) + bits(5-4)
bits(6) = bits(4) + bits(6-4)
bits(7) = bits(4) + bits(7-4)
bits(8) = 1

Got it?

 

Learning python: the case of logger

Recently I came across a python codebase like below: 

Main.py
import A as a
import B as b

logger = logging.getLogger(__name__)
a.logger = logger
b.logger = logger

A.py

 logger = None # set from main

B.py

 logger = None # set from main

What is the problem with that? What is good practice to use logger? To answer these questions, let's look at how python logger works. Python logging module is influenced by log4j java logging framework. So we will see many things can be applied to java logging as well.

Logging module class diagram

Each logger instance can have multiple handlers, each handler can have one formatter which contains the log message format. Each logger has a parent pointer to its parent. Below is the python logger module's internal class diagram.



- The loggers are arranged as hierarchy tree based on the name's dotty namespace hierarchies. The top is root logger. For example, logger named 'a.b.c''s parent is a logger named 'a.b' whose parent is logger named 'a' whose parent is the root logger.

Logging configuration

The root logger can be configured by basicConfig() method and can only be configured once. It does basic configuration for the logging system. The function does nothing if the root logger already has handler configured. It is a convenience method intended for use by simple script to do one-shot configuration of the logging package.

FORMAT = "[%(filename)s:%(lineno)s - %(funcName)10s() ] %(message)s"
logging.basicConfig(format=FORMAT)

ANOTHER_FORMAT = "[%(filename)s:%(lineno)s] %(message)s"
logging.basicConfig(format=ANOTHER_FORMAT)

The above second call won't have any effect.

Logger creation

Logger is obtained by a factory method. 

logger = logging.getLogger(__name__)

The above method will register logger in an internal logger instance cache keyed by the module name. It returns a logger with the specified name, creating it if necessary. If no name is specified, return the root logger.

Thread safety

Both method getLogger and basicConfig are thread safe by acquiring a lock. Below is the source code from python 2.7

#_lock is used to serialize access to shared data structures in this module.
#This needs to be an RLock because fileConfig() creates and configures
#Handlers, and so might arbitrary user threads. Since Handler code updates the
#shared dictionary _handlers, it needs to acquire the lock. But if configuring,
#the lock would already have been acquired - so we need an RLock.
#The same argument applies to Loggers and Manager.loggerDict.
#
if thread:
    _lock = threading.RLock()
else:
    _lock = None

def _acquireLock():
    """
    Acquire the module-level lock for serializing access to shared data.

    This should be released with _releaseLock().
    """
    if _lock:
        _lock.acquire()

def _releaseLock():
    """
    Release the module-level lock acquired by calling _acquireLock().
    """
    if _lock:
        _lock.release()


Log message propagation

The most important, log messages are bubbled up, just like event bubbling in browser, from children all the way to root.

Asynchronized logging

One of most import aspects of logging inside web application is the logging should be asynchronized, since I/O operation is blocking. The standard python logging module doesn't have async handler.

Initialize logger

We can initialize logger at the module level like the above example or at the class instance level.

A.py
import logging
logger = None
class A(object):
    def __init__(self, params):
    logger = logging.getLogger(__name__)


The benefit of setting logger at the class level is that the logger is lazy initialized only when the class A is created and used.     

So the problem with the approach mentioned at the beginning is that all python modules use the same logger, there is no hierarchy. We lose the benefit of attaching different log handler to the loggers and message propagation.

Conclusion

As conclusion let's look at the following example,

Main.py 
import logging
import A

rootLogger = logging.getLogger()
rootLogger.setLevel(logging.DEBUG)
rootLogger.addHandler(logging.FileHandler("main.log"))


A.py 
logger = logging.getLogger(__name__)
logger.setLevellogging.DEBUG)
logger.addHandlerlogging.FileHandler("app.log"))

logger.info('logging message at A')

What will be the end result? The message will appear in both logs! 

Monday, March 14, 2016

Pascal's Triangle - LeetCode

I have not done any coding problem recently. Here is simple problem with a simple solution. https://leetcode.com/problems/pascals-triangle/

Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return

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


The idea here is every row in the triangle is generated based on the row above it. For example, the 3rd row [1, 2, 1] can be generated by going through each item in the row [1, 1], add pre number or 0 for the first item and itself, so it will be 0+1 = 1, 1+1=2, then append 1 in the list.

The code is pretty straightforward.

Saturday, February 20, 2016

[LeetCode] ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R


Result: PQHNAPLSIIGYIR

If we think of the above as 2D matrix of letters, the key here is to figure out for each character of the string, what will be its row index and column index in the matrix? Once we have the 2D matrix, we can just go through it row by row to construct the output string.

In the above example, the number of row is 3. Then there will be 3-2=1 element between each multiple-element column. So if the string length is 4, 4/(3+(3-2))=1, there will be 1*(3-2+1) = 2 columns. If the string length is 5, 6, 7, there will be 1*(3-2+1) + 1 = 3 columns, if string length is 8, there will be 2*(3-2+1) = 4 columns.

Got the math?

And here is the code:


Friday, February 12, 2016

Three ice water buckets challenge

This problem is found here: http://learningandtheadolescentmind.org/resources_02_bucket.html

I called it three "Ice Bucket Challenge" for fun. ;) Here is the problem description.

There are an 8-liter bucket filled with ice water and empty 3-liter and 5-liter buckets. You solve the puzzle by using the three buckets to divide the 8 liters of water into two equal parts of 4 liters. Try to solve the puzzle in the fewest number of moves.

Although to find a fewest number of moves is not easy, but I can design depth first search to find the necessary moves to distribute the waters.
Here is the code
The idea here is to for each possible case, we find the all possible cases which can be derived from it. For example, from 8, 0, 0, it could be 5, 0, 3 or 3, 5, 0. And we use a list keep track of the cases we already visited. Think of all possible cases as a graph, we essentially do a depth first search until we find the case contains 4. A potential solution to find the fewest moves is to use the breath first search. We can use a Queue to contain the list of cases we already visited, then generate the queue of next level based on that, also keep track of the parent case for each case in the queue until we find the case.

Saturday, January 16, 2016

Messages delivery pipeline usign Apache Kafka, Solr and Velocity

Messaging delivery is one of the core functionality in an enterprise IT infrastructure. The message can be any format either in json or xml format or binary data. Its content can be email, file and any network request and etc.

There are many messaging frameworks like Websphere MQ, RabbitMQ and Kafka. One of the benefits of Kafka is the messaging persistence for configurable period due to its disk-based message storage. See Kafka website for nice introduction about Kafka.

Recently I work on a high-throughput message delivery pipeline which allows multiple consumers listen to various Kafka topic streams, and filters message based on configurable rules and delivers the messages to various endpoints such as file system, email, web services and etc.

The following diagram illustrates the high-level components in the pipeline. Its core job consists of MessageLisenter: a Kafka consumer listen to a topic, RuleEvaluator: process the polled data stream against velocity template based rules and MessageDeliver: deliver the message to one endpoint. If we define subscription as a kafka topic, rules and an endpoint. Then pipeline is a thread pool which contains many subscription-based process jobs or threads.

A Spring task scheduler is used to pull all of subscriptions from an object store and create thread if necessary. 





The pipeline is a state machine goes through various states such as message_acquired, message_rule_matched, message_delivered and etc. We also use Apache Solr to index the job related data and its status. This allows us to build a job monitoring UI to query Solr and display job status to users.

Another two important features are the message delivery retry and replay capability. Basically when message goes through the steps in the pipeline, it can fail at any points such as failing to deliver or rule engine system failure. In failing to deliver case we will retry in an exponentially increased interval interval until giving up at some point. Then once developer fixes any issue associated with the failure, he/she can send relay message and pipeline can replay it.

Circuit breakers are also implemented to allow us throttle the various network-intensive requests if there are any system failure.  See Martin Fowler's blog for introduction to circuit breaker.

Sunday, January 10, 2016

Largest Number - Java8 Stream - LeetCode

This problem is from LeetCode:

Given a list of non negative integers, arrange them such that they form the largest number. For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330. Note: The result may be very large, so you need to return a string instead of an integer.

The first simple solution is to treat each integer as string, sort the strings, then going through the strings in reversed lexicographical order and concatenate them all.

This approach works for some cases like: 99, 87, 34. Result is 998734.
However it doesn't work for [3, 30, 34, 5, 9], since it will generate 9534303 in stead of 9534330. So we need to make sure when we sort the array in a special way that  "3" is larger than numbers like "30", "31", "32". Why? Because 330 > 303, 331>313...

How can we archive that? Actually the above comparison results already give us the hint! We can build a comparator, and concatenate the string in different ways and compared them.
Here is the code:


If we use Java8 stream API, without worrying about the all 0s case, this solution becomes a one-liner!!!