Monday, June 25, 2012

django+postgres setup

For my own reference.  django 1.4 + python 2.7

Apparently if you want to connect to postgres in your django application, it doesn't work right out of the box. You need to install the connection driver layer psycopg2 yourself.

sudo apt-get install python-dev postgresql-server-dev-all
sudo pip install psycopg2

then in your settings file, change your ENGINE to:

'django.db.backends.postgres_psycopg2'

Thursday, March 24, 2011

masterpiece of bitwise operation...



What does this piece of code do?

It finds one single unique number in an array where all other numbers appear three times. This is essentially mod3.

Explanation (Thanks to Rama B@careercup)

"The code works in similar line with the question of "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer.

Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element.
Since XOR operation is associative, commutative.. it does not matter in what fashion elements appear in array, we still get the answer.

Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want.

To rectify this mistake, the code makes use of 2 variables.
ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.

So if at any point time,
1. A new number appears - It gets XOR'd to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twice".
3. A number appears for the third time - It gets removed from both "ones" and "twice".

The final answer we want is the value present in "ones" - coz, it holds the unique element.

So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,

not_threes = ~(ones & twos)
ones & = not_threes
twos & = not_threes

All it does is, common 1's between "ones" and "twos" are converted to zero.

For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).

Explanation for step 1
------------------------
Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".

The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.

Explanation for step 2.
------------------------
Lets say an element(x) appears twice.
CURRENT SITUATION - "ones" has recorded "x" but not "twos".

Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.

Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".

Explanation for step 3.
-------------------------
Lets say an element(x) appears for the third time.
CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.

Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".

Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".

1st example
------------
2, 2, 2, 4

After first iteration,
ones = 2, twos = 0
After second iteration,
ones = 0, twos = 2
After third iteration,
ones = 0, twos = 0
After fourth iteration,
ones = 4, twos = 0

2nd example
------------
4, 2, 2, 2

After first iteration,
ones = 4, twos = 0
After second iteration,
ones = 6, twos = 0
After third iteration,
ones = 4, twos = 2
After fourth iteration,
ones = 4, twos = 0

Explanation becomes much more complicated when there are more elements in the array in mixed up fashion. But again due to associativity of XOR operation - We actually end up getting answer."


Wednesday, March 23, 2011

Selecting the largest/smallest N numbers out of M numbers

Given sufficient amount of memory to hold all M.

  1. Your gut feeling that this can be a heap sort. O(n*log(n)).
    Don't be shy, say it out load, it is indeed correct and efficient. But also, do not settle.

  2. Your can also do this by using quick sort, by adjusting the next pivot accordingly after partition. Still O(n*log(n)), but in real world the gain here is actually quite significant as you can ignore at least one of the two partitions each time.

  3. In #2, you may have noticed the fact that you are not required to sort the N number. But taking that one step further. You can apply Selection Sort, which is O(n), to find the Nth number during one iteration, and you should have guessed what steps to follow when you have the Nth number at hand.
Even if you want to have the N number sorted, #3 is still the optimal solution as you can take the N number and sort them in O(Nlog(N)) time, which is smaller than O(Mlog(M)) as N.

Update: It seems that I was wrong about #2. #2 is actually linear. See here. Randomized-Select is the name, and it is introduced in Chapter 9 of "Introduction of Algorithms" 2nd Edition.

Read the book, as always...

Monday, March 14, 2011

recursively removing files with wildcard in linux

If you are a Linux rookie as me, you might expect this to work, as well as I did:
rm -r *.class

Bozinga! this only deletes the *.class under wherever you are, because wildcards are expanded before executing the commands.

here is a non-trivial command that does the seemingly trivial magic you wish:
find /path_to_search -type f -name "*the_patern*" -exec rm {} \


Thursday, March 10, 2011

Installing Ubuntu 10.10 on my Thinkpad T60

Just for future reference. Should write a bash script to automate this.
  • Ubuntu Screen flickering/flashing problem with ATI x1300/x1400
    cat /etc/modprobe.d/radeon-kms.conf 
    options radeon modeset=1
    reboot
  • Install Java
    Turn on "Partner" in repo list
    sudo apt-get update  
    sudo apt-get install sun-java6-jdk
  • Install Aptitude
  • Install chrome, dropbox, eclipse
  • Sync VI configuration, Sync Terminal configuration, Sync .bash_aliases
  • Layout Dev, Workspaces, git clone, etc

Thursday, January 27, 2011

Windows Command Line args to get file paths

%~0 - expands %I removing any surrounding quotes (")
%~f0 - expands %I to a fully qualified path name
%~d0 - expands %I to a drive letter only
%~p0 - expands %I to a path only
%~n0 - expands %I to a file name only
%~x0 - expands %I to a file extension only
%~s0 - expanded path contains short names only
%~a0 - expands %I to file attributes of file
%~t0 - expands %I to date/time of file
%~z0 - expands %I to size of file

The flags can be combined.

Friday, January 21, 2011

Accessing 32bit Registry under 64bit machine (non-wow location)

Starting from .Net 4.0, there is actually RegistryView used for this purpose. For any .Net version earlier than that, here is the rule:

"The rules are pretty straightforward:

  • .NET app compiled for "x86":
    • Always 32-bit
    • On 32-bit platforms, accesses 32-bit registry
    • On 64-bit platforms, accesses 32-bit registry (inside Wow6432Node)
      • 64-bit registry inaccessible (without doing something weird)
  • .NET app compiled for "x64":
    • Always 64 bit
    • On 32-bit platforms, won't run
    • On 64-bit platforms, accesses 64-bit registry (not inside Wow6432Node)
      • If you want to get to the 32-bit registry, you need to do something weird
  • .NET app compiled for "AnyCpu"
    • Either 32 or 64 bit depending on platform
    • On 32-bit platforms, accesses 32-bit registry
    • On 64-bit platforms, accesses 64-bit registry (not inside Wow6432Node)
      • If you want to get to the 32-bit registry, you need to do something weird

"Something weird" technically requires passing a special flag to RegOpenKeyEx to obtain the alternate registry view. .NET doesn't expose any function that will do this nicely, so you'd have to drop to p/invoke to get there."

Reference: http://social.msdn.microsoft.com/forums/en-US/netfx64bit/thread/92f962d6-7f5e-4e62-ac0a-b8b0c9f552a3

Saturday, December 4, 2010

Git Gotta

>> mkdir foo
>> git init
Initialized empty Git repository in /home/jianlu/repos/web/foo/.git
>> git branch master
fatal: Not a valid object name: 'master'.

// How to fix this?
// make an arbitrary checkin by git submit. You are done.

Update:
git commit --allow-empty -m "initial commit"

Source of this update: (thanks to Mohamed Meligy's tip)

>> git branch
master.

Git claims this to be by design because before the user makes the first initial commit, there is nothing to be branched.

This kinda makes sense but not always a valid restriction. It is not a rare case that you want to lay out your repository structure because you know the repro structure should be like that even before you write the first line of your project code.

and btw, this is a terrible error message. It barely says anything about the real cause of this failure, or any suggestion on possible fixes.

Sunday, November 28, 2010

Some random mysql pitfalls.

Constraints
Only PK, FK, Nullability, Unique are enforced in InnoDB. Check (expression) is not. So don't expect the following check constraint to help you catch any insertion/update with foo.value <= 20.



FK
both sides of your FK should have exactly the same signature. Otherwise you get errno 150, which indicates a syntax error in FK definition.

Monday, September 27, 2010

Uninstalling MySQL on Mac OS X

Source: http://steveno.wordpress.com/2009/03/26/uninstall-mysql-on-mac-os-x/

  • sudo rm /usr/local/mysql
  • sudo rm -rf /usr/local/mysql*
  • sudo rm -rf /Library/StartupItems/MySQLCOM
  • sudo rm -rf /Library/PreferencePanes/My*
  • edit /etc/hostconfig and remove the line MYSQLCOM=-YES-
  • sudo rm -rf /Library/Receipts/mysql*
  • sudo rm -rf /Library/Receipts/MySQL*

Tuesday, August 31, 2010

Arrange number 1..n so that each pair of consecutive numbers sum up to a square number

Problem Statement
Write a program to arrange numbers from 1 to n such that the sum of two consecutive numbers is a perfect square.

An interesting way of looking at this problem
Make a graph so that each node is one of the numbers and there is an edge between two nodes if these two numbers can add up to a square number. Find a path starting from one node and end up in another so that each node is visited once and all nodes are visited. Such path may not exist.

There should be an easier way to do this by seeking for nodes with only one edge in/out...

Wednesday, August 25, 2010

Given a dictionary of words and a string with all spaces removed, determine whether the string is composed of valid words

Problem Statement

Given a dictionary of words and a string with all spaces removed, determine whether the string is composed of valid words

Examples
helloworld-> hello world (valid)
isitniceinhere-> is it nice in here (valid)
zxyy-> invalid

Time Complexity Requirement
O(n^2)

Algorithm
True/False array T of size equal to the input. T[i] = true => the substring starting from i is composed of valid words.

Assume API method IsValidWord() is O(1) since we are given a dictionary.

for each element in the array:

T[i] = (IsValidWord(s.substring(i, 1)) && T[i+1])
|| (IsValidWord(s.substring(i, 2)) && T[i+2])
...
|| (IsValidWord(s.substring(i, n-i-1)) && T[n-1])

The result is T[0].

Complexity analysis
for each i, it takes O(n) to compute. and we start the computation from i = s.length - 1 and decrease i, and there are n element in the array to compute. So we get O(n^2) as the total time complexity.

Tuesday, August 24, 2010

Given two strings of a and b. Find the max window in a and b where the substrings in the window are anagrams.

Problem description:

1. Given two strings a and b, find the max value of "length" where for some i and j, a.substring(i, i+length) and b.substring(j, j+length) are anagrams.

2. Given two strings a and b, find the max window of matching patterns between a and b where the pattern matching doesn't have to be an exact match but also can be a permutation of each other. (which is essentially anagrams...)

Algorithm:

let m = a.length;
let n = b.length;
let matrix = int[m][n]

if a[i] == b[j] then matrix[i][j] = 1
else matrix[i][j] = 0

With the matrix populated by the routines above, find the largest square that meets the following two conditions:
  • no column contains all 0s. For each column, at least one cell is 1
  • no rows contains all 0s
The time complexity is O(n^2). I don't believe it can be done in O(nlogn). But I could be wrong.

Someone was asked the following question during interview: if m = n, would that help speeding up the complexity?

Well, I have no idea...

Thursday, July 8, 2010

Checking whether a binary tree is balanced or not using recursion

Balanced: no path from root to leaf node is longer than another such path by 1.

The code is just so elegant...



this can be extended to general trees with more than two children by examining all children's maxDepth or minDepth.

ArrayList vs. LinkedList

There has been quite a bit discussion already. So just sum up by a few words:

ArrayList
  • Lookup by index is O(1). (in Java, it implements RandomAccess) Suitable for dataset with random access pattern.
  • Insertion can be expensive. Worst case O(n).
    1. Insertion to the middle can cause shifting.
    2. Insertion to the end can cause changing in the size of the internal storage, usually doubling.
  • Deletion Depending on the implementation, it may vary a bit. Generally not bad.
LinkedList
  • Lookup by index is O(n) in worst case. (in Java, it implements Queue). Suitable for data set that most of operations against it is iteration, or access mostly happens at the beginning or the end, such as FIFO queues, FILO stacks.
  • Insertion is O(1)
  • Deletion
    1. Deletion by reference is O(1)
    2. Deletion by value is as bad as lookup.
General thoughts:

Comparing two data structures, always at least think from two perspectives:
  1. operations: lookup, insertion, deletion, manipulation.
  2. input data characteristics: matching the characteristics with the cost of each operation to find the better data structure to solve your problem.

Hashtable

Disadvantage: generally, it wastes spaces.
Advantage: generally, it does fast lookup.

Three normal types: Chained, Chained Scattered, Open Scatter



Tuesday, July 6, 2010

Finding all numbers which are smaller than K and only divisible by 2, 3, and 5

This may not be the most optimal solution...

Essentially we are looking for all possible {(x, y, z) | (2^x * 3^y * 5^z) <= K}
  1. When x+y+z = 1, we get {2, 3, 5},

  2. Let:

    S(i) = { (2^x * 3^y * 5^z) | (2^x * 3^y * 5^z) < K and (x + y + z = i)}

    S(i, j) = Union of all s in S(i-1, t) * j that:
    a. t and j belong to {2, 3, 5}
    b. t >= j
    c. s <= K

    for example:
    S(2,2) = {2, 3, 5} * 2 = {4, 6, 10}
    S(2,3) = {3, 5} * 3 = {9, 15}
    S(2,5) = {5} * 5 = {15}

  3. S(i) = S(i-1, 2) + S(i -1, 3) + S(i-1, 5).

    for example:
    S(2) = S(2,2) + S(2,3) + S(2, 5)

  4. Stops when S(i) is empty.

Saturday, March 8, 2008

Install mysql++ for C++ connection to mysql database

1. Install mysql

2. Install mysqlpp-3.0 from source
http://tangentsoft.net/mysql++/releases/mysql++-3.0.0.tar.gz.
Don't use apt-get to install libmysqlpp-dev if you are using old version of ubuntu. It would give you outdated version of mysql++.
Generally it would be install in /usr/local/include and the libs would appear in /usr/lib/ or /usr/local/lib.

3. include mysql++.h in your program.

4. in your make file, put the following flags when you compile and build:
//include the header files
-I/usr/local/include/mysql++ -I/usr/include/mysql
//load the libraries. otherwise you are gonna get undefined reference error during linking stage.
-L/usr/local/lib -lmysqlpp (-lmysqlclient)
The path might differ from different linux distributions. Look for the lib named libmysqlpp.so* and libmysqlclient.so*.

5. remember to put the library path in /etc/ld.so.conf, and sudo ldconfig

Sunday, January 13, 2008

Integer Division by 7 Trick

Q:How to make an integer division by 7 faster?

No closed discussion found so far.
As I was wondering: the following pieces of pseudo codes might perform well

x = x>>3 + x>> 6 + x>> 9 + x>>12 + x >> 15 .....+ (increase i by 3 until x >> i becomes zero)

since it is an integer operation, we are not really looking at the exact value. The logic behind this is approximation.
To notice: x/7 = x/8 + x /7*8 = x/8 + x/8*8 + x/7*8*8 = x /8 + x/8*8 + x/8*8*8 + x/7*8*8*8......