Nov
23

# Merge sort of linked list

Last time I started with the simplest question of reversing a linked list this time let me go a bit further – sorting a linked list.

Just for a minute consider sorting a linked list , some of the standard sorting mechanism assumes random access of data (like quick sort, heapsort ) so linked list becomes a special case. But then we have one more wonderful sort left to consider , which is merge sort. Merge sort is very special (in fact many standard sort libraries like in java internally uses a combination of merge sort and insertion sort) because it has the wonderful property of being a stable sort. In fact it is the only stable sort with asymptotic complexity of O(nlogn) but its draw back typically is the use of O(n) extra space. There are wonderful inline merge sort algorithms which I would cover in a different post altogether. Now what is more wonderful is that for sorting linked list, we can use merge sort’s O(nlogn) without the drawback of O(n) space. Again a quick search in net seem to suggest it is a very complicated algorithm to implement , again I am not sure why , this is my version of it (in Java).

The basic idea of merge sort is this basic recursive idea , how most of us learned recursion to start with –

```
merge_sort(list) {
split list into two halfs, say first and second ;
merge_sort(firstHalf);
merge_sort(secondHalf);
merge(firstHalf,secondHalf);
}
```

A working implementation in Java :

``````
Node middle = getMiddle(head);      //get the middle of the list
Node sHalf = middle.next; middle.next = null;   //split the list into two halfs

}

public Node merge(Node a, Node b) {
while(a !=null && b!= null) {
if(a.info <= b.info) { curr.next = a; a = a.next; }
else { curr.next = b; b = b.next; }
curr = curr.next;
}
curr.next = (a == null) ? b : a;
}

Node slow, fast; slow = fast = head;
while(fast.next != null && fast.next.next != null) {
slow = slow.next; fast = fast.next.next;
}
return slow;
}
``````
``` ```

Nov
20

# Wonder what that flight in the sky is ?

Interesting ..now you don’t have to wonder what is the plane you are seeing like a dot in the sky [ at least I used to as a child]

Update: I got some comments in my fb and g+ pages claiming this to be a useless feature. This is my reply “I think this is just tip of the iceberg, once you have this granular information of flights and tracking them, you can have interesting applications around it like
– ex. if you are in a flight and take a photo and later given the time and flight number it can tell you exactly where you were while taking the photo.
– all the flights from point A to B and average delays and better airlines in a particular route .

Overall it is taking airline search to another level , though I am not sure whether we have time to do all that analysis in our daily lives :)”

Nov
19

# Reverse a linked list in java

If you search for it you will get millions of solutions but sadly (like many things in internet) the first few solutions seem unintuitive and unnecessarily complex for such a simple problem, not sure why, anyway putting mine out there for somebody to point out why I should go for a more complex solution. [in java for a change]

Idea : Use two references and reverse their links and proceed till we reach the end

``````
public void reverse_iterative {
if(isEmpty()) { return;}    //curr == null
Node currNode,nextNode , loopNode;

while(nextNode != null) {
loopNode = nextNode.next;
nextNode.next = currNode;
currNode = nextNode;
nextNode = loopNode;
}
}
```
```

Recursive Idea : Reverse the sublist starting from second node and point the second node to first, apply this recursively.

``````
private void reverse(Node curr) {
if(isEmpty()) { return;}     //curr == null
if(curr.next == null) {
return;
}
reverse(curr.next);
curr.next.next = curr;
curr.next = null;
}
```
```
Oct
27

# Apple tablet vs Amazon tablet headed in different directions ?

Contrast of Apple and Amazon tablets : Apple sells media so that they can sell more tablets , Amazon sells tablets so that they can sell media later on it. So Apple will give you (now and in future) lot of cool cloud based services and apps (like Siri) in exchange to an expensive tablet while Amazon will continuously reduce the price of the tablet to sell their services.

Will you put your money in any of these ?

Oct
25

# Netflix – Is the honeymoon over ?

Had I posted this blog few weeks or months back I would have sounded more like a visionary, I had the same thoughts then too, anyway better now than never.

Today’s third quarter results of Netflix and the nose-diving of their stocks was splashed across tech sites, but it was not a surprise to me, I was always surprised how they were so hugely successful till now. It is a tricky business they are in, always a tricky business to be the middleman , let me try to explain my rationale.

Netflix was a revolution, it was an example of the classic disruption of existing business model so much so that the hugely successful DVD chain Blockbuster went bankrupt. Agreed, it was a revolution at that time when it was so convenient to select DVD’s from your home, receive it at your door step and yeah no late fees, all for as much 7-9\$ per month. For the movie industry drowning in piracy and illegal streaming it was a lifesaver.

Now there are two key parts to their business, lets take it apart – DVD and streaming business. Firstly the DVD business, it is very restricted, the movie studios make money out of their DVDs a period after the movies are out of theatre and then they later make money by licensing to other stores. So the studios would have a very constraint time window when they can allow the DVDs to be rented by Netflix without sabotaging some of their avenues of revenue especially for new movies. Even Netflix agrees DVDs are not for them and that is slowly going to a sunset.

Ok so that brings the singular focus to streaming. One of the great strengths of netflix is that they are ubiquitous, they are in almost all internet based TV consoles you can buy – Apple TV, Google TV, Roku box, Microsoft Xbox, the list goes on. So you have a console at home where you can view internet media in TV , Netflix would be there to stream your movies. Now that strength can be their weakness too, remember they don’t own any of these boxes and they are competing with the same people who distribute them, they should be careful not to step on the new movies streamed by itunes, movie catalog in youtube so they really can’t stream everything without shooting themselves in the foot.

Now on the other hand time has not yet come for people to cut off the cable connections in their homes, they still want to watch their favorite games , the local news and guess what HBO or Star movies comes with it. If there is any price increase many would be wondering whether it is worth keeping Netflix given that they already have HBO, after all this is a luxury not a necessity. So they need to keep bidding high to get exclusive rights to the content for them to be irreplaceable and they have not started making that kind of money.

So who do I think is poised to win in this streaming business. I always thought Google since they already have Youtube and many people already watch movies there, but with all the rumors of Apple making a TV going on and their mastery of music business with itunes they could be a game changer too. I do see another lurking player who could be the third leg of the stool, Amazon , if they purchase Netflix , they have the content and users, they already have the technology (in fact they also have a tablet now), they have the big bucks and they can make their prime account a bit more attractive for their customers. It is similar to what google had always claimed that more people using internet is good for them for that implies more people will search, similarly more people with prime account is always good for Amazon for that implies they are going to shop more on Amazon.

[Netflix still has a strength , they can serve the long tail well though I am not sure whether they can make enough money with that, depending on how long the tail really is ]

Oct
18

# Window shopping the internet way

People love window shopping , I have seen people rushing in hordes to the new malls in rising cities in India just ‘for the feel’ of it. But is it of any good for the shops , if you believe many studies it is, as Leonardo DiCaprio would have said in Inception it plants the seed of a thought , a desire or a want. Slowly the items in window gets into your psyche , what was once stupid and expensive becomes not that stupid and could have. I remember the story somebody told me on how British introduced smoking cigarettes in India, where they used to have well dressed people in suits and hat, stand at public places like shops and bus stops, puffing stylishly from a cigar beautifully perched between their fingers, an image which slowly became a symbol of style and attitude. We humans are supremely adaptable to anything , even if that means taking in irritating smoke , once our mind has accepted it.

Ok, but the point of this post has nothing to do with the offline world, but something that stuck me when I heard the recent ‘Kindle Fire’ , the new Amazon tablet announcement. Many people have classified it as yet another tablet, perhaps as a cheaper alternative to Ipad, like many other Android ones, but I don’t think most have got the hidden ambition of Bezos (now clearly I have not seen Bezos mind though I wish I can ). It is another shopping device for amazon, they realize people are using more of these fancy mobile devices to browse internet , then why not give them one of these fancy devices with their own browser , so that they can shop more at amazon. Shopping literally at their finger tips, they finally got a window to their huge store for people to peep into, isn’t that next generation window shopping where the window is planted in each of our homes.

Oct
6

# Job Well Done Mr Jobs, Adieu

Yaksha : What is surprise?
Dharmaputra : The fact that people thinking themselves as stable and permanent, in spite of
seeing several deaths daily is surprising.
[From the great Indian Epic Mahabharata ]

The are a few moments in our lives when we are hit with flashes of realization on how temporary our lives are , how silly many things we hold dear to us really is , how stupid it was to run behind things that doesn’t matter at all in long run. Today is one such rare moment to me.

I had followed almost every story of Steve, read even the biography of Wozniak to understand how he had built the company with Steve, how the personal computer was born and how a legend our our times think. But over all what I take away is the realization that in our lives it is just the different trials and fights we had which is important but not the victories or failures that awaits our fights. Its only journey which is important destinations doesn’t matter.

Think of this great visionary , who wanted to created the greatest company in the world, and most his adult life he had created a very small company which reached the verge of bankruptcy , was marked as a failure, was kicked out of his own company and finally when he did create the most valuable company of the world , he was not there to really sit back and enjoy it , even for a few months.

But his contribution to the world would live forever , we would be telling our children we lived during the times of people like Steve Jobs who changed the way humans listened to music, read books, communicated to their friends and many many more. He will remain as one of the biggest inspirations in my life, this speech of his will remain motivating for generations to come. “Remembering that I’ll be dead soon is the most important tool I’ve ever encountered to help me make the big choices in life. Because almost everything — all external expectations, all pride, all fear of embarrassment or failure – these things just fall away in the face of death, leaving only what is truly important. Remembering that you are going to die is the best way I know to avoid the trap of thinking you have something to lose. You are already naked. There is no reason not to follow your heart.”

“Some men dream the future. He built it.”

Mar
1

# A picture is indeed worth a thousand words…

I was looking at the new connection visualization tool from linked in [ http://inmaps.linkedinlabs.com/ ] and literally felt why a picture conveys much more than any resume. I love visualization tools and this one was pretty well made, with the clusters of connections distanced very appropriately. Also the cluster sizes kind of corresponds to the time I have spend at different places and you can get the picture of my career so far (very small though) in one look .

Wonder what it will look like in 10 years, one giant cluster or many more smaller clusters ?

Aug
23

# Future of mobiles – Near Field Communication (aka Proximity apps)

Many ideas easily transform into prototypes but the journey from that to a product which normal users can readily use daily can be quite long. For instance take wireless chargers, nowadays all gadgets are so mobile the only wire pinning us down to our place are the chargers. There were prototypes of it shown in many places the most notable and credible I have seen was this presentation in TED. Researchers had talked about it for years , have demoed at different places, but working in a big company I now know the big effort required in transforming something that works a dozen times to something that can work reliably for millions of users. You need an ecosystem to make a successful product – users, reasonable cost, support system.

I digress, so let me come back to the title and how it is related to this prototype-product analogy. Over more than 6 years I have heard of people using mobile to just swipe for payments, mobile as RFIDs, mobile as credit cards, mobiles in ATMs to charge money by just getting the device near an ATM machine. It all uses a technology called Near Field Communication (NFC in short), which is a short range wireless communication which enables exchange of data between devices over about a 10 centimeter distance. But really it never happened in mainstream and I think it is about to break the tipping point to enter our lives, for real users at real places. I bet by 2011 we all will be shaking and rotating our mobiles in weird ways to get things done.

Why do I think so – signs everywhere. First comes the slew of patents from Apple (some of which I will be describing below) about different ways in which NFC can redefine some of our daily activities. Then comes the hiring of Benjamin Vigier and NFC expert to apple few days back and last week TechCrunch having an article about NFC based iphone prototypes. There are few times when you hear about a technology something suddenly clicks in your head and you whisper ‘that can be big’ (like when I first heard about the start up Siri) and I did hear myself whispering this time too. If you are wondering in a world of peer-peer wifi, bluetooth , how a 10cm communication technology can breakthrough let me give some sample applications

Redefining shopping experience or Point of Purchase –

What does a typical shopping process consists of ? You go to a super market, find the location of the item and if you are more of a tech user, scan the bar code of the item and get the comparison prices in shops around you , see the reviews in amazon and decide to purchase. But from the decision to finishing the purchase includes many more different systems (as merchants would call it point-of-purchase or POP) , one to scan your item to get its price and another device to collect your credit card info and transmit the info and collect your payment. Do you remember occasions when you decided to leave an item because the queue for sales was long or decided not to see a movie since you are too bored to stand in the queue. Think of a system which makes the whole transaction simple – use your mobile get the info the product , which contacts merchant’s system to give your purchase details , transfer money and grab the item and disappear. May be the shopping cart can do all these for you or there could be more innovative ways as this apple patent describes.

Redefine data transfer between devices –

Data transfer between devices is still a pain, what if transferring music from itunes to mobile is as simple as getting your mobile close to laptop. How many times do you have to mail the url or the map from laptop to mobile since there was no easy way to type that url or search in mobile. What if these transfers can be done by just bringing the devices close to each other. Get the digicam next to your laptop and the photo transfers starts, get your laptop close to your TV to get your photos on to TV, get your mobiles together to transfer money. Here NFC can work together with other high speed technologies like bluetooth but without the normal overhead of paring devices entering passwords etc.

Redefine traveling experience. [or may be a future iTravel app – swipe your mobile for travel tickets]

No better way to describe than this Apple patent summary – “The handheld device may store and transmit travel reservations and traveler identifications using a travel management application. Various methods may be employed to acquire the reservation and identification information on the handheld device. For example, travel reservations may be made via the management application or may be retrieved from an email, a website, another NFC-enabled device, or a carrier-provided confirmation number. User identification may be acquired by scanning a radio frequency identification tag embedded in a government-issued I.D. In another embodiment, an I.D. number may be entered via the travel management application, and the user’s identification information may be downloaded from the issuing authority.”

I bet iphone 5 would all about NFC, time to invest in apple stocks if you have not already done that

Other examples of NFC applications :

– Obviously no more credit cards – Just swipe your mobiles at the store.
RFID tag readers , this can be very interesting.
– Instant product research using NFC , Apple recently filed a very detailed patent (83 pages) on various possibilities on this , you can read about the details here.
– All identification documents detected automatically from mobile.

Aug
17

# Power corrupts ?

Anbody who has been following the current net neutrality proposal from Google-Verizon and the hoopla around it would find the below video hilarious. [Wondering what the hell net neutrality is read this quick intro.] The question which most people have to Google is – “Why? Why did you have take a U-turn on your own principles? What is this sudden love for telcos?”. I am sure there is more to it than trying to find a ‘way forward’.

Is it Android ? or Is it Google TV ? It would be interesting for anybody to run a cable TV set up over internet , given that the pipe is shared by everybody and there is no assurance of QoS.