Interview Questions

1. Simulate a seven-sided die using only five-sided

2. Giving Two Strings, Find out whether they are Anagrams or not?

3. find the longest palindrome in a string?

4. find longest common substring in 2 strings using suffix tree

Some terms:

• suffix tree of a string S: a tree whose edges are labeled with strings, such that each suffix of S corresponds to exactly one path from the tree's root to a leaf.
• trie: each edge is labelled with a single character
• radix tree, Patricia tree/trie: edges are labelled with a string instead of single character
  

suffix tree: a special type of radix tree

• How to construct suffix tree?
• How to find longest common substring using suffix tree?

DP algorithm runs in O(mn).

Reference:
Fast String Searching With Suffix Trees

Algorithm Reviews

Foundation of Algorithms Using C++ Pseudocode, 3rd Edition.
By Richard Neapolitan and Kumarss Naimipour

Chapter 5 Backtracking
Backtracking is the technique to prune non-promising nodes in the state space tree.

CLRS
Ch 11 Hash Tables

11.3 Hash Functions

11.4 Open Addressing
Uniform hashing: idealized hashing function selects a permutation with equal prob.
Linear Probing: h(k,i) = ( h'(k) + i ) mod m
Quadratic Probing:
Double Hashing

Wireless Crackers

I came across this website today:
http://forums.remote-exploit.org/

Indeed many people are constantly trying to crack other's wireless password. How scary is that?

Interview Questions

From careercup.com:

• Given a document and a query of K words, how do u find the smallest window that covers all the words at least once in that document? (given you know the inverted lists of all K words, that is, for each word, you have a list of all its occurrrences). This one is really hard. Could someone propose an algorithm in O(n)?

Answer: Use two pointers, one is the left of the range, one is the right of the range. For each word w_i we also keep a left and right pointer. Both initialize to the head of occurrence list (0).
Initially left is at the leftest word occurrence.
(Loop)
(AdvanceRight) Advance right by advancing the leftest of the right pointers in the occurrence list.
if reached the right end, break the main loop

Keep an array of counters for each word to count how many times w_i occurs in the range.
Advance right until all words are included.
Record range(left,right)
(AdvanceLeft)
Advance the left pointer and decrement the corresponding counter whenever left pointer moves pass word w_i
Repeat until at least one word doesn't occur in the range

Record range( left-1, right) if it's the current optimal

Go back to Loop

• Find the median of 2 sorted arrays

Which phone to buy

My contract with AT&T was over like 2.5 years ago but I haven't renew the contract. It's about time to get a new phone. Here are some choices I found on Amazon:

• Sony W760a
• Nokia 6650
• Samsung A867 ($50)
  

W760a looks good but I already have a Sony Ericsson. Nokia a little boxy but seems like a good phone and the battery is good. A867 seems like a good i-phone alternative, but I don't really need all the smartphone features. So which one to buy? still deciding...

mac ports rsync error

Macports failed to install git-core because it failed to fetch rsync.

---> Fetching rsync
---> Attempting to fetch rsync-3.0.0.tar.gz from http://rsync.samba.org/ftp/rsync/
---> Attempting to fetch rsync-3.0.0.tar.gz from http://svn.macports.org/repository/macports/distfiles/rsync---> Attempting to fetch rsync-3.0.0.tar.gz from http://svn.macports.org/repository/macports/distfiles/general/
---> Attempting to fetch rsync-3.0.0.tar.gz from http://svn.macports.org/repository/macports/downloads/rsyncError: Target org.macports.fetch returned: fetch failed
Error: Status 1 encountered during processing.

Can I manually download rsync-3.0.0.tar.gz and continue building?

I actually found there's no rsync-3.0.0.tar.gz on the above url of samba.org. Instead I downloaded rsync-3.0.2.tar.gz.

It also fails to to self update. I suspect it's because it's using the wrong version of rsync to sync with the rsync server of macports.org.

$ sudo port -d selfupdate

rsync: read error: Operation timed out (60)
rsync error: error in rsync protocol data stream (code 12) at /SourceCache/rsync/rsync-24.1/rsync/io.c(515)
rsync: connection unexpectedly closed (303841 bytes received so far) [generator]
rsync error: error in rsync protocol data stream (code 12) at /SourceCache/rsync/rsync-24.1/rsync/io.c(359)
DEBUG: Couldn't sync the ports tree: Synchronization the local ports tree failed doing rsync
while executing
"macports::selfupdate [array get global_options]"
Error: /opt/local/bin/port: port selfupdate failed: Couldn't sync the ports tree: Synchronization the local ports tree failed doing rsync

I think it's all due to my macports database is too old and thus the port file uses obsolete url to download and build rsync. But rsync is also used to update the mac ports database. Therefore I have to either manually update mac ports so that it can build the newer rsync or manually download and compile rsync to update the mac ports database.

mountd problem: "Can't change attributes"

A very weird problem on a NetBSD 2.0.2 (I know. It's really old, but I don't have time to upgrade it yet). It seems only the first directory in /etc/exports can be successfully exported. Other lines cause this error:

[kung@lion2 wireless_drivers]$ cat /etc/exports
/mnt/extra/exports/mesh-allrw -maproot=32767:39 mesh-c mesh-d mesh-e mesh-f mesh-g mesh-i mesh-j mesh-l
/mnt/extra/exports/mesh-allro -maproot=32767:39 -ro mesh-c mesh-d mesh-e mesh-f mesh-g mesh-i mesh-j mesh-l

Error messages:
Feb 24 19:20:15 lion2 mountd[6982]: "/mnt/extra/exports/mesh-allro -maproot", line 2: Can't change attributes for /mnt/extra/exports/mesh-allro to mesh-c: Operation not permitted


I have no idea why it would happen. But it seems only the first line of /etc/exports will work. It maybe a bug of this very old version of NetBSD. I will upgrade the machine to a more recent version of NetBSD soon.

Wi-spy

http://www.metageek.net/products/wi-spy_24x

This small spectrum analyzer looks very interesting. Maybe I should persuade Nitin to buy one to analyze how busy the spectrum is.

virus kavo

I am trying to help a junior student remove rootkit virus kavo.exe and ubs.exe from her computer. But it always comes back after I thought it's cleaned. So far I've tried:

1. del_kavo.exe

2. del_kavo from trend micro

It seems some copy of the executable was hidden and executed every time I thought the virus is removed. I'll try the following:

• Disable "system restore" function of windows XP.
• Delete autorun.inf on disks and removable media.
  

Link of Virus Kavo at Trend Micro

Follow up: (3/04)
A post of detailed steps to clean kavo:
http://forums.spywareinfo.com/index.php?showtopic=108252&hl=kavo

Random Thoughts About Patents

Just randomly browsed the US patent office website and found that Microsoft has filed 1965 patents in just 7 months of 2007, that's an average of 9.35 patents/day. Some of the patents are kinda absurd, for example "Optical Mouse". Hmm, when did Microsoft invent optical mouse, that's interesting. And many other titles look funny too. After learning the story of the patent war between broadcom and qualcomm, it reconfirms my belief that there's something wrong with the patent legal system. With some many patents being filed everyday and the ridiculous broad range of their claims, the small companies will certainly violates some patents even if they can deliver a new product to the market. For the big companies, they can benefit from unreasonable royalties and create an unfair entry barrier. To conclude, I agree that innovations are valuable and the inventor should be awarded. However the current mechanism of awarding inventors through patents are not efficient and fair. The legislators and legal experts should work on creating a better system.

Web conference tools

http://www.kolabora.com/news/2007/06/22/web_conferencing_tools_and_technology.htm

Vim + Cscope in Windows

1. Download vim from vim.org
2. Download cscope binary for win32 native here: http://blog.csdn.net/mslk/archive/2007/05/06/1598513.aspx
3. Set TMPDIR to something like "c:/WINDOWS/TEMP"
4. Put cscope.exe somewhere in the %PATH.
5. It should work now.

PS. I couldn't get vim to use the cygwin version of cscope.

Vim: Better Colors for Syntax Highlighting

:set background=dark

gosh, i should've learned this 100 years ago!

UNIX Hints & Hacks

UNIX Hints & Hacks
http://www.umiacs.umd.edu/~jusub/unix-hints-and-hacks/index.htm

Tools for drawing math figures

http://www.maa.org/editorial/mathgames/mathgames_08_01_05.html

I would like to try at least one or two programs in the category of "geometry exploration programs."

Office for Mac

http://www.ciac.org/ciac/techbull/CIACTech02-003.shtml
It's funny that MS uses this stupid scheme to detect pirate software.

Atheros HAL

I came acroos to read this paper:
http://www.cse.iitk.ac.in/users/braman/students/2006/narasima.html

In this paper, the author implemented a 802.16-like MAC protocol on top of Atheros Madwifi driver. They were able to:

o Disable the backoff mechanism on Atheros card
o Partly disable virtual sense by increasing the CCA theshold
o Nullify DIFS, SIFS

These functions are not available in HAL. Thus we must set the hardware registers bypassing HAL. I also found the OpenHAL is actually inside the source of OpenBSD. I will look at the Open HAL code and continue to investigate how to achieve these goals.

FreeBSD architecture handbook

Useful for understanding the kernel internels of BSD.
http://www.freebsd.org/doc/en_US.ISO8859-1/books/arch-handbook/index.html

NetBSD on a USB Key

This is probably going to be useful for our mesh project.

http://imil.net/nlk/#downloads

GPL issue of Linux kernel modules

Linux: The GPL And Binary Modules
http://kerneltrap.org/node/1735

A discussion about the legal issues of Linux binary modules.