Tuesday, November 13, 2007

Using Cosmo (Chandlerserver) as a Git Server

I wanted my local Git to be updated to a server and came up across Git on Dreamhost. A nice link which talks on how Dreamhost with WebDAV can be used as a git remote repository. So any WebDAV server should work. I thought I will use Cosmo to host itself - A really cool idea! I have never used Cosmo for anything other than calendars or address book (which I worked on :) ) and had to dig the documentation to find the way to create a collection. I used Cadaver client to create the collection

# sudo port install cadaver

#cadaver http://osaf.us/cosmo/dav/vinu

dav:/cosmo/dav/vinu> ls
dav:/cosmo/dav/vinu> MKCOL git

In Mac OS X Tiger I used finder to connect to the server. I entered the URL as http://osaf.us/cosmo/dav/vinu/git - entered the username, password and it mounted :). But when I tried to put any file on this server it failed :(. After hanging out in IRC for some time I figured out Cosmo (Chandlerserver) does not implement locking yet and Mac OS X Finder expects the server to implement locking :(. I tried searching for a client like finder - but none of them had a way to put a complete folder into the collection.

I tried to copy the git repository using a Windows XP desktop I had - I created a web folder with the url http://osaf.us/cosmo/dav/vinu/git. I then copied my bare git repository from my Mac to Windows and from there to the webdav server (Cosmo). It partially failed with a message saying some files could not be copied :(


Links
  • http://wiki.dreamhost.com/Git
  • https://osaf.us

Sunday, November 11, 2007

Interview Questions

After attending a lot of interviews I found that most interviewers are obsessed with Hashmap and like to test your understanding on the algorithm complexity and how hashmap reduces the complexity to O(n). The list problem shown below is an interesting problem.

The List Problem


Its a search problem where you need to find if a small list is contained in a bigger list. The example below shows the goal of the problem.
Say you have two lists:

smallList = "red", "green";
largeList = "red", "green", "blue";

smallList is contained in largeList for the above data.

If you change the smallList like
smallList = "red", "green", "green";
smallList is not contained in largeList. The order of the strings does not matter. What is the best way to implement a function which will return a boolean value indicating if the smallList is contained in largeList.

Solution 1: worst case implementation
for (int i=0; i < smallList.size;i++) {
found = false;
for (int j=0;j < largeList.size;j++) {
if (smallList[i] == largeList[j]) {
largeList.remove(i);
found = true;
// slight improvement would be
// break; here
}
}
if (found == false) {
return false;
}
}
return true;

Complexity is O(n pow 2)
memory usage is good - since it just uses a boolean variable called found

Solution 2: Similar to solution 1 - if the method largeList.remove is not available
largeListMatches = new boolean[largeList.size]; //assume all the values are initialized to false

for (int i=0; i < smallList.size;i++) {
found = false;
for (int j=0;j < largeList.size;j++) {
if (smallList[i] == largeList[j]) {
if (largeListMatches[j] == true) {
continue;
}
largeListMatches[j] = true;
found = true;
}
}
if (found == false) {
return false;
}
}
return true;

Complexity will be the same - around O(n pow 2). Memory usage will be more since an array of boolean (of size largeArray) is used. So the memory required will be sizeof LargeArray + sizeof smallArray + 1byte * length of LargeArray + 1 byte for the boolean found variable

Solution 3: Use a hash map to hash the large list
for (int j=0;j < largeList.size;j++) {
if (value = largeHash.get(largeList[j])) {
largeHash.set(largeList[j], ++value);
} else {
largeHash.set(largeList[j], 1);
}
}
for (int i=0; i < smallList.size;i++) {
if (value = largeHash.get(smallList[i])) {
if (value == 0) {
return false;
} else {
largeHash.set(largeList[j], --value);
}
} else {
return false;
}

}
return false;

Complexity will be reduced to O(n) + O(n) which is O(n). Memory usage will be really high. For an array list of high value like 10000, etc this method will be infeasible. This is the most efficient algorithm - but assumes the system has a high amount of memory
Memory required is 2*(sizeof LargeList) + sizeof (smallList) + integer array of length largeList

Solution 4: Use binary search to find the elements. the largeList has to be sorted first. Any of the sorts like quick sort or merge sort can be used - complexity of O(nlogn). Binary search has a complexity of O(logn) - but it is for each element of small list. O(m*logn)
Overall complexity is O(nlogn) + O(m*logn) = O(nlogn)
Memory usage is equal to the size of largeList + smallList

quicksort(largeList); //or mergesort(largeList);
for (int i=0; i < smallList.size;i++) {
if (binarySearch(smallList[i], largeList) == true) {
largeList.remove(smallList[i]);
} else {
return false;
}
}
return true;

Tree problem

I don't remember the exact question - but here it is:
You have a class called Data Node.
class DataNode {
int id;
int parentId;

DataNode parentNode;
DataNode[] childNodes;
}

Define an efficient method called
public DataNode updateTree(DataNode[] dataNodes)
which will update all the parentNode and childNodes assuming that the id and parentId of all the nodes are already set. The parentId of the root node is set to zero.

Though the question is designed badly asking you to write a method inside a node - it was interesting otherwise. An example will things make more clear

Suppose you have a tree like

18
5 3

The DataNodes array will have
18, 0,NULL, NULL
5, 18, NULL, NULL
3,18, NULL, NULL


The goal of the question is to update the references parentNode and childNodes. So instead of NULL you will be able to navigate the tree structure.

Solution:
The O(n pow 2) solution is easy to design. The other solution is something to do with the thing I said in the top of the article :)

Saturday, November 3, 2007

Ubuntu on Macbook

Was thinking of installing Linux but seems that Bootcamp beta license is not valid after Oct - so i could not find a link to the beta and all the sites were updated to point to Leapord. The options I had was to either buy Bootcamp or rather upgrade to Leopord. I had no intension to do any of that. I just wanted a OSS operating system and charging to install an OSS is like loosing freedom! The other option was to use rEFit.
I had used reFIT before and I thought I will just use rEFit (refit.org) and parted to resize the partition. reFIT is a nice boot manager which shows the list of operating system during boot, includes booting from DVD/CD media. I installed rEFit and downloaded Ubuntu Gutsy Gibbon (the code name for the latest 7.10 version). I had purchased some Kodak CD -R media from Staples and thought I will use them to burn this image. To my surprise I tried it three times and could not verify the burnt image and so gave up for now. I think the CD -R has some issues or there is some compatibility issue between my Mac and CD -R. I suspect that the former one is true - probably some manufacturing defect or something.

Still waiting and hoping to find an option to install! Fedora 8 is scheduled to be released on 8th of November. I may rather install Fedora 8 if I don't get a resolution for the CD media issue.

Wednesday, October 31, 2007

Git/git-svn on Mac OS X Tiger (Macbook)

Though Git is complex to use I hope it will solve most of my version merge problems. I have used svk (a distributed version tool written in perl built on top of SVN and the SVN perl bindings) before and it is easy to use after creating a basic workflow (which may be slightly hard for a novice svn or CVS user). Unfortunately it dies with complex merge situations. It happens mainly if there is too much reorganization in the main trunk compared to your local branch. For example I worked/work (i try to work whenever I can but always get stupefied by the merge issues.) on an open source project called Cosmo - now renamed as Chandler server - it is actively developed and the trunk undergoes a huge change quite often. The merge interface of svk was really nice and I used it to keep merging changes from the trunk to my local branch. I also had my local branch merged to my own svn sandbox so that if my system crashes I can restore using my svn sandbox :). My entire workflow is documented at
http://chandlerproject.org/bin/view/Journal/SvkUsage

Now I got my almost new Macbook (repaired using Apple support) without any Linux (as of now) - I thought I will have most of the unix OSS goodies using Macports and Fink :). Git was one of my most wanted tool and I thought of installing it soon to get started with a few projects. As some of the websites pointed git install did not work using fink.
I did
# fink install git
and was greeted with some dependency error messages. I also tried
#fink selfupdate
asking me a lot of questions and taking a lot of time :(

#fink install git
again some dependency error message :(.

I always heard of Macports and wanted to give it a try. But installing Macports required installing XCode available through ADC, which requires a login. I first installed Macports without installing XCode hoping that it will work, but later realized that Macports needs a compiler as does any port based system. I have used Gentoo port based system and understood that everything is built using source and thus will require a compiler.

I downloaded the 3.0 version of XCode, but found that XCode 3.0 does not work with OS X 10.4 Tiger and is meant for leopard. I then downloaded the 2.5 version (around 1 GB download size) and installed it successfully. I could then issue port commands :)

# sudo port selfupdate

#sudo port install git-core

printed lot of stuff like downloading, building, etc taking a lot of time for the compilation
and Installation was a success :)

Happy with the success I typed
# git
it showed me the usage
I then typed
#git-svn
It said the command could not be found :(. A google search of git-svn on Mac showed me to use the command:
#sudo port install git +svn

That fetched a few more files, did some compilations, installations taking lots of time and I got an error that git-core is already installed. Obviously! But I wished the system was smarter and just installed git-svn.
I tried
#git-svn
and was greeted with the same command not found error.
I did see that the port system had two entries for git and I had to uninstall all git-core
# sudo port uninstall git-core @1.5.3.4_0+doc_svn
# sudo port uninstall git-core

Then I did a
#sudo port install git +svn

I tried
#git-svn
and yes I did see it was installed but the perl module had some missing dependencies. The module called Error.pm. I searched that package in port - but it was of no use and so I tried CPAN.
# sudo perl -MCPAN -e 'install Error'

It asked me a lot of questions - some missing programs which I installed either using fink or port. Both taking a lot of time and thus patience.
# sudo port install lynx
# sudo fink install wget
The path for port based installations was /opt/local - so I had to specify /opt/local/bin for the path of lynx binary.
For fink the path is /sw/ - so I had to specify /sw/bin for the path of wget binary.

You could use a single package management system to install the packages. I tried fink thinking that it was more like apt-get - but no it was getting all the deb's but I think they are source debs since I could see the output of configure, make.

The other package required by CPAN was ncftpget - both fink and ports did not have those packages :(. I just skipped that step.
Then I needed ncftp - ports had the package - So I did a
# sudo port install ncftp
and the next one
# sudo port install gpg-agent
But that did not give me the gpg binary and there was no gpg package in the default macports :(. I just skipped all the questions by pressing enter continuously. I got the Error.pm module installed :).
I then got an SVN/Core.pm not found error when I tried to run git-svn.

I first tried setting the PERL5LIB to my macports version of svn perl library and I got some weird error regarding some core bundler dependency. After struggling a bit I finally removed all git and svn from both Macports and fink. Downloaded git from kernel.org - compiled and installed it the unix way :)
# wget http://kernel.org/pub/software/scm/git/git-1.5.3.5.tar.bz2
# tar -jxvf git-1.5.3.5.tar.bz2
# cd git-1.5.3.5
# ./configure --prefix=/usr
# make && sudo make install


I followed http://speirs.org/2007/07/22/getting-git-svn-working-on-the-mac/ and downloaded the svn package precompiled with all the language binding. After installing the dmg file, I had to set PERL5LIB to /usr/local/lib/svn-perl.

I got git-svn working finally :).


I still miss the apt-get based installation in Debian systems which just installs the binary and is very fast. Ofcourse port based system has its own benefits like better optimized binary, etc - but it would be really frustrating to wait for 1-2 hours for a program to be installed :(.

Apple support

I recently had some issues with my Macbook and I am impressed with apple support - only disappointment was they had to ship my Macbook to Apple factory and get my Macbook repaired. I had to register for some Geniusbar appointment in Apple website and had to drive to the store. I went to Palo Alto apple store which is the nearest Apple store for me and I was greeted by a good support staff. I found the support guys to be really smart and very crisp compared to any other support I have dealt with. They immediately found out the issue is not resolvable by them and they have to send the Macbook to the factory for repair. I was told that it will take 10 days for the entire process and everything will be covered under waranty :). They replaced my hard drive, RAM and the case which was broken slightly. I handle my Macbook with great care and still the case developed a small hole by itself :(. Thanks to Apple support they replaced my case with a new one and I am happy about that :). They also replaced my Airport network card for some reasons - don't know why - it was working perfectly! Their online tracking system also updates me on the status of the repair and told me when it was shipped overnight.
Overall I am happy that my Macbook is working again now :).

Sunday, August 26, 2007

My Amazon interview experience

I was surprised to receive a mail from Amazon asking me for an interview. I had just applied to Amazon at the Dice career fair at Linux world and I did not expect a call from them after the initial talk I had with the software development manager at the fair. All excited with the email, I scheduled my interview for the nearest possible date. After some initial confusion I got a surprise call on my mobile - while I was in my friends car and in the middle of a traffic light! I had to reschedule my interview to some other day and again I made the mistake of scheduling it for the nearest possible date. I had no preparation and I was still doing my internship at Verisign. I scheduled my interview for the next day after my last day in Verisign and so I had only one evening to prepare for the interview :(. With so little time I managed to grab a book on Data structures to revise a few data structure fundamentals. After going through a few concepts I was bored and wished for more time! I then thought of revising a few of my Java concepts and grabbed a Java book which I had never touched before. The book was Practical Java and seemed to be really nice. I went through a few concepts like pass by value in Java and a detailed discussion about that including . After saturating myself with a few Java concepts I thought I will do a context switch and listen to some data structure lecture from Berkeley webcast. Unfortunately some of the streams lacked quality audio and I had to skip a few lectures. Then listening to some lecture and just slept off. I woke up at 11 am and was greeted by an engineer from Amazon. He started with some basic Java questions and I was happy that I could answer them...but then I had to deal with questions I did not know or did not remember :(. Here is the complete interview for everyone else searching for a job and preparing for an interview:

Question1: What is a final class in Java?
Answer: I was delighted to hear this question and gave this answer - A final class
cannot be inherited. The final keyword is overloaded in Java - a final class cannot be extended, a final method cannot be overridden and a final variable cannot be changed.

Question2: Difference between Abstract class and interface:
Answer: I said interface can have only method declaration whereas an abstract class can also have a method definition. The interviewer extended the question and asked me what is the difference between a pure abstract class which cannot have method definitions and an interface - I gave him the generic difference between an interface and class saying that multiple inheritance is possible with interface and not with a class. The interviewer again asked me if there is any other difference. Not able to think well at that time I said I don't know and said that I will prefer interface for my implementation.

Quesion 3: Difference between HashMap and Hashtable
Answer: I thought about it and said I know both are the same since I have used Properties which is a Hashtable and it is similar to HashMap.
After googling I saw that the difference is Hashtable is not synchronized and it supports null for key values.

Question 4: Difference between ArrayList and Vector
Answer: ArrayList is not thread safe and Vector is thread safe.

Question 5: What is the value of i in int i = 5/3
I said 1 since it takes the floor in Java and rounds off. He asked me the answer for float i=5/3 and I gave the answer(wrong) as 1.667. The correct answer is 1.0.

Question 6: How do you create a thread in Java.
Answer: Since I did not revise that section of Java, I could not answer this question well :(. I just said that there are two ways to create a thread. One is by extending the Thread class and the other is implementing the Runnable interface and overriding the run method. The interviewer asked me how do you start the thread? I answered that it can be started using the start method - but said I don't remember it that well since I did not use it recently.

Question 7: If you have a really big array - how do you find all the pairs whose sum is 50.
Answer: I gave a worst case complexity of adding all the elements in all possible ways to find the sum and see if it is 50. He tried going more in depth - but I declined to answer :(

Question 8: This was a tricky question and it took the interviewer some time to explain the question!. Given a number n, How do you find two numbers whose product is one of n+1 or n+2. In case both n+1 and n+2 have multiples - how do you find the multiples whose difference is really less. Eg: Take a number say 5. The two numbers n+1 and n+2 are 6 and 7. 6 has a multiple and 3,2 is the solution to the problem.
Take another number say 7. 8 and 9 are the two numbers. 4,2 and 3,3 are the two solutions to the problem. But since 3-3=0 is less - 3,3 is the correct answer to the problem....
My Answer:
Understanding the question was itself a big exercise for me and I think part of the question was an answer to the problem. But then he asked me how do you find a multiple of a number - I said we could divide it by 2, 4, etc. Then he asked me at what point you stop dividing and I said its n/2. So in case the number 8 - I will divide it by 4, etc. The second part of the question was how do you find the optimal pair (pair whose difference is less) - I had to take a wild guess and say that one way is to see if n has a root. So 9. 16, etc with pairs (3,3), (4, 4) will be the answer for n like 7,8 or 14,15.


Question 9: What happens when you type Amazon.com in your web browser?
I gave a really long answer on how DNS works. He also wanted the details about the hierarchical nature of DNS. So I explained about the root servers and the caching that happens in between. So the root server responds with the authoritative server for COM and then a DNS query is sent to COM server asking for the authoritative server for AMAZON.com. Finally the Amazon.com nameserver responds with the real ip of the machine hosting Amazon.com. There are some HTTP requests and response between the server and client. A successful response is usually a 200 OK status message followed by the complete HTML body.
The client renders the HTML and shows the page to the user. He asked me if there are multiple requests for getting the different images in a page and I said yes ofcourse.

Tuesday, April 24, 2007

Terracotta on FC6

Terracota makes clustering simpler by providing a shared VM concept, where the application programmer need not worry about any kind of clustering API's and assume that her code will be executed across multiple JVMs. Its a novel approach for clustering any application without the need of changing much code.

Its driven by a XML based configuration file called tc-config.xml file which can control the classes you want to share across multiple JVM. By sharing it is not the usual serialized way of sharing, instead Terracotta sends the difference between the objects and thus is more efficient.
The sample applications provided with Terracotta are very neat and show the power of Terracotta and it just works out of the box. While I was trying to download Terracotta on my Mac, I did not see any Mac binaries in the download page. I remember seeing the demos in different videos [1] used Mac. Ofcourse it is based on Java and it will work on Mac, but I was annoyed to see only three links when I clicked on the download link. Later I found out that it has been fixed with the new version 2.3-stable1 build which is a generic build and can be used in most unix like platform. Its available as a separate tab in the download page and was hard to notice. I did download the generic 2.3-stable version and got it working without any problems. I had to set my JAVA_HOME to /System/Library/Frameworks/JavaVM.framework/Home/


I dual boot Mac and Linux FC6 - unfortunately I have a few issues in Linux (battery, hibernate and sound related) and have to boot in Mac quite often. But being a Linux fan and with Terracotta giving me a reason to boot into my Linux again, I booted in FC6 got all the Linux binaries - the three binaries listed in the download site (DSO, Spring and Session). Untarred them to a terrocotta directory and ran the demos. For a start DSO is good and untarring that alone would be better.

#bash# cd terracotta/terracotta-2.2.1/dso/bin
#bash# ./tc-welcome.sh

FC6 has some issues with 3d Desktop effects and swing. The swing applications like JTable demo did not show up and it was not because of Terracotta - any swing application in FC6 did not work. I thought it was related to gcj java and I tried to remove all the gcj related packages. While removing gcj, I had to loose almost all the important packages like eclipse and open office which are dependent on libgcj. After loosing all my good applications, I tried running Terracotta again and still saw the same blank JTable frame. Then I had to google to find the solution to the problem and then I discovered that it was the 3d desktop effects (XGL) that was causing the problem. I was using Jdk 1.6 and it seems that the issue has been fixed in a newer jdk. For now I am happy running my swing applications without the 3d desktop! The JTable application and the Shared editor application worked just as shown in the video [1] and the introductory video at Terracotta.com.

Overall I was really impressed by the product. As with any rapidly developed open source (or commercial product) the documentation was really scattered around and there were lot of things to read.

[1] Google Video - Terracotta presentation


Monday, March 12, 2007

Macbook and Linux

I got the latest Macbook Core 2 duo (Mar 2007) and really liked the new OS with the speed of Intel Core 2 Duo processors. At first I found it hard to use OS X, mainly with the keyboard layout and new shortcuts, but I liked a few things about Mac. Few of the UI things were really mind blowing, but then I was lost trying to find a few things. I am more of a Linux fan, but Mac OS X seems to be a better alternative to the more dominant Windows. I found the Mac experience better compared to Linux, since most of the things work straight out of the box. I know Linux requires a bit more work in that area, but I am sure it will catch up soon.
Being a hard core Linux fan, I thought of installing Linux in my Macbook.
I had used bootcamp to partition the drive, but unfortunately I pressed OK somewhere and created only a 5GB Linux partition :(. I had also installed reFit for dual booting OS X and Linux.
I managed to install Fedora Core 6 64 bit version on this 5GB parition, but I was not able to boot because of some partition synchnozation issues. MacBook uses the new EFI partition. Many of the Linux tools like parted, etc is aware of this partitioning scheme, the Linux installers does not work straight out of the box :(. I had to do a few reboots and do synchronization using reFit.
I was impressed by the new effects in FC6. The cube effect and other desktop effects were really cool.
The new wireless card is not supported yet (Mar 2007) and I had to use the wired network to browse the internet. I saw Flash 9 was available, but could not have it working because of my 64 bit version. I could use ndiswrapper to make the wifi card work, but it required a 32 bit OS. I also had a 5GB linux partition, which was not enough by any means. I wanted to increase the partition and thought about installing different Linux versions in Macbook. Then I had some issues resizing and I had to completely remove the Linux partition and start from scratch. I did not want to install OS X again, so I had a 40GB OS X partition which I did not touch. I wanted to install various Linux versions and with the new EFI partitioning, there was a limitation of the number of partitions you can have. I wish there was something like extended partition to satisfy my ambitious goal of installing multiple Linux distribution. In my previous IBM thinkpad I had 3 Linux distributions and one other OS. (MS Windows which I rarely used). I found that one way I could achieve that in my Macbook is to use LVM and dynamically resize the partitions and create new partitions for new distributions that I want to install. Unfortunately Ubuntu at that time (or maybe even now) did not have support for LVM and Gentoo live CD did not work that well - X did not start and I tried running some install scripts from command line which failed.
I downloaded FC6 32bit version now and I burned a DVD. I booted using the FC6 DVD and created LVM partitions. So I had four partitions now - two of them were the EFI partition and the MAC hfs+ partition which I did not touch. I had to create a boot partition of 100+MB, since boot partition cannot reside on LVMs. I then created few partitions inside LVM - one of them was the / partition and others were partitions like /home and /opt. /home will be shared with all the distributions once I have more distributions installed.
After installing I got the basic rpm's like mplayer, flash which are not there by default. I was forced to use Yum, though I am not a big fan of Yum. I like apt-get and I am aware of the apt-get port for rpm, but recently I have been using the defaults provided by the distribution. With Ubuntu apt-get is the default since its debian based and I really like that command :). I have used Smart with OpenSuse - which was not bad.
I used ndiswrapper with a binary driver for some time and was irritated by the frequent kernel crash. I had no choice but to use this driver or stay near a wired network :(. I was constantly tracking ticket 1001 in madwifi and finally one fine day there was an announcement that support for the card with device id 024 is finally available. I checked out the madwifi branch and everything worked fine with an access point without encryption. But with WEP it did not work and I am now tracking ticket number 1243 and hoping to have WEP support soon! WEP support is finally available (Yay and thanks to all those developers who made this possible) for device id 024 ( the one that comes with Macbook). To compile the madwifi drivers, get the following branch of madwifi:

#bash#
svn co http://svn.madwifi.org/branches/madwifi-hal-0.9.30.13 madwifi-wep
#bash# cd madwifi-wep
#bash# make && make install
#bash# modprobe ath_pci
(also added the following entry in modprobe.conf
alias wifi0 ath_pci
)
NetworkManager in Fedora did not detect the card even after restarting it several times. May be it was some issue with uninstalling the previous version of madwifi driver that I had installed. I had to reboot (I have never done that in Linux, except for Kernel upgrades) to find that NetworkManager worked perfectly and I was just able to connect to a WEP based network using this new driver.

I do have issues with hibernation and suspend. It does suspend or hibernate properly, but after restoring, X behaves strangely. The mouse pointer sometime vanishes or the mouse pointer gets caught in a small area in the top left corner of the screen. I will have to kill X to get a usable desktop.
Microphone issues: The soundcard works fine, but the microphone does not work. I discovered that when I was trying to call someone in Skype and the other person was not able to hear anything. I am yet to apply the mactel patches to get the microphone working.
Battery Usage: I noticed my battery gets drained very fast in Fedora and so I usually have my power cord connected while using Linux. I tried stopping a few services but that did not help. I think I have to remove some modules and that may increase the battery life.