Friday, November 18, 2011

Find all possible ways of representing a number n

During one of my recent interview with a giant software company, I was asked this question:

Given an array of numbers, find all possible ways of representing a number n. For example, let's assume we have [2, 3, 5] in an array, and the target number is 10.
Well... I fail this interview in that I'm trying to work out a iterative solution given the stressful condition. I went home and I suddenly realize this is a manageable problem as long as I'm not greedy.



  • Tip 1: for all "combination" / "subset" questions, you should always start with hacking a recursive solution, because it's the most intuitive one. 
  • Tip 2: never try to provide the "best" answer to your interviewer. Don't worry, they will challenge you and ask you to propose a better answer later. 
Some people might argue that tip 2 looks stupid, especially if you know that recursive is usually awful in terms of space complexity. Don't get me wrong here, the time complexity for a permutation style question is O(N!), factorial, and for a subset style question is O(2^N), exponential. But hey...this is not the side effect of recursive, but it is the nature that the space you have to search !! Yes, the space complexity is awful, and you may fix by Dynamic Programming or Iterative solution. However, what you need in the interview is not a perfect answer, but is to show you ability of coding, and analyzing complexity. And don't worry, if you get this simple answer quickly, they will ask you to improve it. That's the time for "iterative" solution.



Here is the simple way of doing it:
import java.util.ArrayList;
import java.util.Arrays;

public class FindAllComb {
    public static void main(String[] args) {
        int[] ar = {3,5, 2};
        printCombForN(ar,10,0, new ArrayList());
    }


    //try = 0, meaning we start from the first element in the array
    public static boolean printCombForN(int[] ar, int target, int idx, ArrayList buffer){
        //base case: if no more choice
        if(target == 0) {
            return true;
        }
        else if (target < 0) {
            return false;
        }

        // for all possible choice
        for(int i=idx; i < ar.length; i++){
            //make a choice
            buffer.add(ar[i]);
            target-=ar[i];
            if (printCombForN(ar, target, i, buffer)){
                //print buffer
                System.out.println(Arrays.toString(buffer.toArray()));
            }
            //unmake the choice
            buffer.remove(buffer.size() -1);
            target += ar[i];
        }
        return false;
    }
}
It may looks hard at its first glance but essentially this is a simple back-tracking problem. For back-tracking problem, here is the template I follow:
bool Solve(configuration conf) //Credit: Zelenski, Julie
{
    if (no more choices) // BASE CASE
        return (conf is goal state);

    for (all available choices) {
        try one choice c;
        // solve from here, if works out, you're done
        if (Solve(conf with choice c made)) return true;
        unmake choice c;
    }
    return false; //tried all choices, no soln found
}

Can we do better?

Yes, with the help of DP.
The idea is that we can "memorize" things we did before.


For example, if we know th only possible choice of making 5 are (2,3) or (5), we can simple save it in a HashMap so that we don't have to go over same path again.

So let's slightly change the problem, what if we don't need you to print all possible combination, but we just want you to return number of possible combinations?

The idea here is Num(array, 10) = the sum of the following
  1. Num(array, 8)  + 1 (we deal with 2)
  2. Num(array, 7)  + 1 (we deal with 3)
  3. Num(array, 5)  + 1 (we deal with 5)
So you get the big picture now, if we have an array that index is the "target", which is the remainder after we recursively call the function , and the value is the "# of possible combinations" we already know. We can simple sum them up.

I will add answer later, but one thing you should keep in mind is that to make things faster, often times the price is space. In this example, we need extra space for tracking counts. Though, here (the revised question) the cost is acceptable.


Note that all back-tracking problem can be accelerated by some heuristic pruning. That is, you may "return false" earlier if you know there's no way you can get a goal state along the path.

Wednesday, August 17, 2011

Log (logging) in Python

Logging is always an important topic when you try to develop a "real-world" app. I once wrote my own logging system, but apparently the best practice is to use something provided by Python Standard Library, not to reinvent the wheel.

Here, I have no intent to write a complete tutorial of teaching the python's logging framework. I extract the most useful/simple part(s) of logging from my viewpoints, which I believe it solves 90% cases I(you) need.


Firstly, you should try to build a customized logger. It is impractical to use the logging module directly via changing basicConfig() because you cannot tell where the log comes from if you have multiple modules in your app. This is one of the reason why I write this article.

To get a "customized" logger, firstly you should assign a name to it.
mlogging = logging.getLogger("test_log") #Get a logging for this module

If you would like to have some beautiful format on logging records, logging.Formatter is something you need to set it up. Sure you should do it because the default one seems to be a little clumsy. To change the date format (that is, %(asctime)s), please refer to things used in time.strftime(). And to create a format for a record, the related variables can be found in attributes of LogRecord.

# -- Set up Formatter --
log_format = '%(asctime)s(%(name)s--%(levelname)s):%(message)s'
log_date_format = '[%m/%d/%y %H:%M:%S]'
uniform_fmt = logging.Formatter(fmt=log_format, datefmt=log_date_format)

Mostly, we store logs in a file, so you need a file handler.
# -- Log to File --
hdlr = logging.FileHandler('OnlyOneFile.log')   # or "mlogger.name + 'log' if you would like to separate logs
hdlr.setFormatter(uniform_fmt)

If you would like to see log in your screen, say, for debugging, you have to link it to STDOUT.
# -- Log to Console --
hdlrConsole = logging.StreamHandler(sys.__stdout__)
hdlrConsole.setFormatter(uniform_fmt)

Do not forget to link your handler with your logger.
mlogging.addHandler(hdlr)
mlogging.addHandler(hdlrConsole)

Finally, you have to assign a log level so that you can get all the details. Otherwise, The default level is WARNING. (All default levels)
mlogging.setLevel(logging.DEBUG) #this is the most detailed level

Putting all together, here is an example:
import sys
import logging

mlogging = logging.getLogger("test_log") #Get a logging for this module
"""
logging.basicConfig(
    #filename=mlogging.name + '.log', #Use the name of logger as log file name
    filename='onefile.log', #Use the name of logger as log file name
    level=logging.DEBUG,
    format='%(asctime)s(%(name)s--%(levelname)s):%(message)s',
    datefmt='[%m/%d/%y %H:%M:%S]'
"""

# -- Set up Formatter --
log_format = '%(asctime)s(%(name)s--%(levelname)s):%(message)s'
log_date_format = '[%m/%d/%y %H:%M:%S]'
uniform_fmt = logging.Formatter(fmt=log_format, datefmt=log_date_format)

# -- Log to File --
hdlr = logging.FileHandler('OnlyOneFile.log')
hdlr.setFormatter(uniform_fmt)

# -- Log to Console --
hdlrConsole = logging.StreamHandler(sys.__stdout__)
hdlrConsole.setFormatter(uniform_fmt)

mlogging.addHandler(hdlr)
mlogging.addHandler(hdlrConsole)
mlogging.setLevel(logging.DEBUG)

mlogging.debug('This is debug msg')
mlogging.info('Ok~ info now')
mlogging.warning('Warning here')

try:
    x = 4/0
except Exception as e:
    mlogging.exception(e)

Before we leave the discussion, you should pay attention to mlogging.exception(e). This is the way we log an exception, including its trace-back information.

Tuesday, July 12, 2011

Git Version Control Resource

I'm a heavily Subversion (SVN) developer. Recently, I join several projects that use git as their version control frameworks. Thus, I document some useful resource as follows:


To learn more about git:

Firefox 5 on ubuntu 10.04 LTS

For people who are using ubuntu 10.04, the default version of Firefox is 3.6. (Seriously?) It's suggested that you update to the latest stable version of ubuntu.

To install the latest "stable" version of ubuntu, add the following ppa repository:

sudo add-apt-repository ppa:mozillateam/firefox-stable


This is nothing more than add a mozillateam-firefox-stable-lucid.list to "/etc/apt/sources.list.d".

Than, do "sudo apt-get update && sudo apt-get upgrade" and you are done.

Tuesday, March 8, 2011

MySQL Remote Access

By default, the mysql (5.x) allows login within localhost. What if you need to access a MySQL database from another computer?

I found this tutorial is quite helpful:
how-do-i-enable-remote-access-to-mysql-database-server

Unfortunately, I still get the following errors
chucheng@laptop:~$ mysql -ufoo -pcrap mysql.ucla.edu
ERROR 1044 (42000): Access denied for user 'foo'@'laptop' to...

After trying several solution, I finally realized that in the statement GRANT ALL ON db_name.* TO foo@'%' IDENTIFIED BY 'PASSWORD'; you cannot skip "IDENTIFIED BY password".

It turns out that you will "override" existing passwords with an empty password if you did not provide corresponding inputs.

Just in case that you still have problems:
Please make sure that
(1) Your bind-address in /etc/mysql/my.cnf has been changed to "real" IP.
(2) your port is listening
netstat -an | grep 3306
(3) You grant remote access permission to the user accounts.
p.s if you encounter any problems when login from localhost, instead of granting foo@'%', please grant foo@'localhost' as well.

Friday, February 4, 2011

Ubuntu Application

I would like to document several apps that, I believe, are very useful as follows. Though there are many choices in WWW. The followings are really handy ones.

Programming Tools:
  • WingIDE (Python)
  • IntelliJ IDEA (Java)
  • Eclipse (C++/Java)
  • Rabbit VCS (Version Control)

MISC:
  • Mendeley
  • Stardict (Dictionary)

Tuesday, February 1, 2011

Brightness Control on T410 (T410s)

I find the brightness control seems to be not working after installing ubuntu 10.04 on my Thinkpad T410s.

Here are two solutions:

(1) Switch to console (CTRL+ALT+F2) and adjust the brightness. Then switch back to GNOME (CTRL+ALT+F7)

(2) Edit /etc/X11/xorg.conf
Under the "DEVICE" section, add the following OPTION
Option "RegistryDwords" "EnableBrightnessControl=1"


Done! Enjoy it!