Dejavu : Finding a loop in a link

The linked list data structure we discussed in my last post in this category is really nice for sequential data. Insertion and deletion is also nice and simple. There is one problem though. If you want to go to the nth node in the linked list, you have to start from the first node and move one node at a time to your node. What if your node is the last node? You will have to start from the first node and traverse the entire list to get to your node.

Suppose you have the following linked list at hand and you want to go to the node Museum which is the last node. You will have to traverse through the entire list before you can get to it.

A simple Linked List

Okay, I know you love The link so much that you are ready to compromise and are OK with this tedious traversal. But the problem doesn't end there.

Me: Consider the following list. Try traversing through it.

Linked List with a Loop

The Link Fan: What's the big deal here? Here I go: Chocolate, Apple, Table, Shoe, Museum, Apple, Table, Shoe, Museum, Apple. Hold on, I feel like I have been here before, I can feel the word Apple coming again. Is it Dejavu?

Me: My friend, you are not in a Matrix and this isn't Dejavu. What you are feeling is a cycle (or a loop) in a linked list. And you were able to notice it because you are Neo, the one or at least a human, if that gives you any pride. But The Matrix (a computer program of-course) will not be able to detect this cycle and will continue to traverse through this list until it runs out of its resources (Only if Neo new this trick, he could have broke the Matrix in no time and there would not have been a need for all that machine war).

Is that what you want? Of-course not. Not in the real world not of The Wachowski brothers.

Then we must find a way to detect this cycle thingy and if possible, a way to get rid of it.

So lets first try to detect the loop.

• Let's start simple, if the link is empty, it cannot have a loop. So we are good there.
• If there is only one node which points back to start, you know that there is a loop.
• Now if there are more nodes, we need something to detect a loop.

We will use an algorithm called a "Two pointers algorithm". This is also called a "Hare and tortoise Algorithm" because one of the pointers is slow while the other one is fast.

So lets get started, if there are two or more nodes, start the tortoise pointer at the first node and the hare pointer at the second node. Now we will continuously advance the tortoise pointer by 1 node and the hare pointer by two nodes (You see? Hare is faster than the tortoise).

If there is a loop in our linked list, at one time both the hare and the tortoise will point to the same node (In the real Hare and Tortoise story, the hare stops and rests because he underestimates the tortoise. Our hare here is honest as god, it will loop indefinitely if you don't ask it to stop. So, unless there is a loop, our hare and tortoise will never cross each other.). If that happens, you can be sure that there is a loop in your linked list and terminate the traversal.

If there is no loop in the linked list, the hare will eventually point to the end of the link(hare = null) or in case where there are even number of nodes in the linked list, you would not be able to complete the step hare = hare.next.next because hare.next is null (in other words, you would not be able to advance hare by 2 nodes because there is only one node before you hit the end of linked list).

To try the above scenario, remove museum node from the above linked list without a loop.  The hare can only be advance once(when it points to shoe) before hare.next is null.

Lets see if that works:

In our linked list with Dejavu, the hare and tortoise will have following stages during their traversal.

Tortoise and Hare on loop

If we remove the loop and run our algorithm (Linked list with odd number of nodes), it works something like this:

Tortoise and Hare on a straight highway

So this is how you find a loop in the linked list so that you can avoid running out of resources while traversing through a list that never ends.

I hope you enjoyed this post. And I was able to express the algorithm in a way that will stick to your grey matter. Also, do let me know if you think there is a better solution to this problem.

As usual, comments/appreciation/criticism (a constructive one of course) everything is most welcome and appreciated.

In the next post, we will discuss how to get rid of this loop. 

Until then,

Happy Learning!

Banyan Bat

Trick to an easy knot to an inflated balloon

As I told in my last post, I was attending a birthday party for one of my friend's daughter. It was a friend's daughter's birthday, so this uncle had to do something to help the overworked father complete the necessary arrangements. So, I chose the simplest of the tasks, well I thought so. Inflating balloons!! You would say, its not that easy, you have to exhaust your lungs. Haha... I am smart. I had already noticed that he had the pump to do that job, so I thought it would be fun. But I missed one important part. The inflated balloon needs to be tied so that it does not loose its air. How could I miss that? And (not so) surprisingly I was worst in doing that until that day.

So I shared my misery with my friend engaged in the same endeavour of helping the overworked father. Luckily he knew just how to do that. He courteously shared the steps with me and helped me learn it too. Thanks to him, it was a joy to inflate those balloons and tie knots on them.

Here are the steps for people like me (unless you all know it very well). Steps courtesy: The Friend: Rahul.

Step 1: Inflate the balloon using a pump or your own lung capacity. Make sure you don't blow it to explosion (Trust me, it happens. We exploded a bunch of them :) and we kinda loved it.).

Step 2: Hold the balloon in your left hand like so. Notice the index finger and thumb pointing up.

Step 3: Pull the open end of the balloon as far as you can safely holding it with index finger and thumb of your right hand.

Step 4: Now, pushing the balloon down with the three fingers of your right hand, push the stretched end of the balloon from above the balloon besides/along with the index finger of your left hand as shown in the pictures below. (Forgive me if I could not put it in words correctly. Believe me, I tried real hard.)

Step 5: Now, pull the open end of balloon slowly taking the index finger of your left hand out. The smooth and shiny nails really come in handy here.

And here's your inflated balloon with its knot tied securely.

Do let me know what do you think about these steps and let me know if these instructions could have been better.

As usual, comments/appreciation/criticism(a constructive one of course) everything is most welcome and appreciated.

Until then,

Happy Learning!

Banyan Bat

My journey through sketching .....from nothing to ...wait for it .......beginner.

childhood memory

I am writing this post because if someday, I become good at sketching, I will remember that I had a humble beginning and I was nowhere close to perfect and will not be perfect anytime soon. Another reason I am writing this post is that if someone who reads this post (if at all anybody does), wants to start something new and is afraid of it because they are not sure how good they are at it and how far they can go, they can get some motivation. Another reason I dared to actually post this is that I have just been to a birthday party for the 2 year old daughter to one of my friends. And can you imagine, what I could give her apart from blessings? I gave her a portrait of herself.

Drawing a portrait of someone you know is an entirely different experience than drawing a portrait from an unknown image and its hard to put in words. The sketch starts with relatively vague and strange looking shapes, but as things start getting shape piece by piece, the character of the person you know starts building up. When you show this image to someone and they instantaneously recognize the person from the sketch, it feels like winning a gold medal.

And after all, this blog is all about my endeavours of learning new things.

Ohkay!!! Enough of prologue(s). Lets get started. The story goes back about 18 to 20 years when I was still a child. Back then I had scribbled a few cartoons and a few scenes. My favorite was one particular scene involving two pointed mountains, a smiling sun, three four birdies, a coconut tree and a river flow which probably every child does in his/her childhood. But apart from that I drew nothing that would grab anybody's reasonable attention. A few pats on the back form the nearest and dearest who would appreciate even if I scratched my belly with a pen is all I got. This would be while I was not even in my teens.

As it was not worth anybody's attention anyway, it simply went dormant in the background until I was well 29. In these 17 years or so, I never sketched a thing as if I had no idea about it. I do not remember any other art that allowed me to come near itself. I am deliberately not mentioning my buying a black acoustic guitar and a guitar tuner because that affaire did not even last a couple of weeks. Though I still miss that black beauty. (Yes, the answer to the question: "Does it come in black?" is YES). I gave away that guitar to one of my friends who actually knew how to play one. Thats the only good thing I did to my guitar. Yeah I know, and I appreciate your keen observation. But I could not resist to mention my guitar.

Then one fine day while I was getting bored in my apartment in Mumbai, out of extreme boredom, I scribbled something on an empty envelope laying around in the dust. Here's the picture for your reference:

My First Sketch

It sucked. I knew and that was perfectly fine because I was not into sketching anyway. But then I thought why not give it a try. In today's world of internet and YouTube, its really not hard to find any kind of help you need. If you want to learn something new, you are just a few clicks away from some of the best teachers/gurus on any subject what so ever. So I just did a Google search and I got something to start with. I started with something like: "how to draw a face". Another thing great about Google is that once you search one thing, it kind of puts you into an information loop which literally has the ability to advance you from novice to beginner to expert. This ability of internet is only limited by the limitations you put on yourself.

So, using these intuitively ordered recommendations from Google and some of my own interest and enthusiasm, I was quickly able to draw a few specific versions of faces.

Not my first Sketch

This was interesting and intriguing. Still because I was not crazily in love with drawing and sketching, I had to push myself to start drawing. But once I started, time would fly. I thought why not try some cartoons and that was good too. They may not be perfect but each drawing gave me a sense of achievement.

As Steve Jobs says, every artist signs his work. So I started dating and signing my work :). I know there are millions of artists out there who can draw much better than me and my scribbles are nothing more than a bud. I don't know if these will ever become trees, but I know one thing for sure, if I nurture and water them regularly, they are bound to grow. That's all that matters to me.

I also wanted to put my drawing to some productive use so that I get motivated to draw more often. Nothing came to my mind as such, until I thought about starting this blog and my friend Sabyasachi suggested me that I can use this to enhance my blog and since then drawing became an integral part of my routine.

Now I have a few focus areas I would like to work on for drawing and sketching:

• Keep drawing at least one picture per blog post.
• Learn to draw portraits by looking at the person's face instead of a picture.
• Try to avoid the use of eraser as much as I can.

With the hope that my journey of learning could be of help to someone, I will keep posting my strategies/progress and any other new things I learn as part of this process. I would really love to hear from you about your experience of learning a new thing. And if you could guide me in progressing through my endeavours of learning sketching, nothing could be greater than that.

As usual, comments/appreciation/criticism(a constructive one of course) everything is most welcome and appreciated.

Until then,

Happy Learning!

Banyan Bat