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......