Thursday, September 8, 2016

Free memory allocated in a Binary Search Tree

A lot of times I have seen codes which are not written keeping memory in mind. A great example is dynamically allocating memory for data structure demonstration on many coding websites. Though they are not meant to demonstrate efficient use of memory, it doesn't take much effort to write codes which actually free the memory. For example, if you have a look on this code, which finds the inorder predecessor and successor of a key in a Binary Search Tree, you see that the call to 'free_all()' frees the memory allocated to demonstrate the actual problem at hand. The function has just two lines of recursive calls along with free() and an exit criteria, hence it doesn't take much effort to write such functions.

A valgrind analysis of the code without the call to 'free_all()' throws the following:

gcc -Wall inorder_successor_predecessor.c && valgrind --leak-check=yes ./a.out
.
.
20 30 40 50 60 70 80
The BST is created, enter the key for inorder successor and inorder predecessor: 30
The predecessor is: 20
The successor is: 40
.
.
84 (12 direct, 72 indirect) bytes in 1 blocks are definitely lost in loss record 7 of 7
.
.
LEAK SUMMARY:
   definitely lost: 12 bytes in 1 blocks
   indirectly lost: 72 bytes in 6 blocks
     possibly lost: 0 bytes in 0 blocks
   still reachable: 0 bytes in 0 blocks
        suppressed: 0 bytes in 0 blocks

For counts of detected and suppressed errors, rerun with: -v
ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)


Whereas, a valgrind analysis of the code with the call to 'free_all()' throws the following:

HEAP SUMMARY:
    in use at exit: 0 bytes in 0 blocks
  total heap usage: 9 allocs, 9 frees, 108 bytes allocated

All heap blocks were freed -- no leaks are possible

For counts of detected and suppressed errors, rerun with: -v
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)


Therefore, sometimes few lines can actually save a lot of memory.

Sunday, January 3, 2016

Two different times, two different places

December 23, 2015: The day came when I was supposed to leave Bangalore and start my journey to Goa to meet my college friends who were coming there. I had finished my work and started for the bus station where my bus was scheduled to leave from. Though it got little late due to heavy traffic, yet I reached the station before the bus had left. I was traveling alone this time and started a conversation with the guy sitting near to me on the window seat and got to know that he was pursuing MBA. He gave lots of information to me regarding MBA and its future prospects.The bus stopped at a place and we had dinner after which we started again and the bus reached Goa an hour late in the morning. 

My friend Abhilash was at the bus stand to receive me. In the evening a couple of friends arrived by which time I had moved to a GTDC hotel near Vasco-da-Gama railway station. I had visited Goa to meet high school friends in July, 2015 when heavy rain welcomed me. Whereas last time we hopped on beaches and visited forts, this time we spent more time on one or two beaches, ate near the beaches and visited Churches. My friend Jishnu drove the car. 

When I look back a week, I feel that Goa seemed to be different this time. It may be that I saw it with different eyes. Eyes which had seen it once, eyes which felt happy seeing friends but somewhere or the other it felt loneliness. I don't know what it was but when I reached about 100 metres above the sea level while parasailing, everything seemed to have stopped, still as if it never moved. I saw the sky, the distant water, other boats and there was no ground below my feet. That moment, I felt as if I am not even a pebble beside the sea. That was the time when flashes of memories came back to me and I remembered one of my friends who had told me about the thrill in paragliding. I felt the same and returned with lots of memories. 

There were two other friends who shared room with me. One of them was Amit, whom I saw after about five years. All of us shared lots of memories of college. We also visited Dona Paula, where we got an awesome panoramic view in the moonlight. The rays on the water surface seemed to have created a path in the water, a path which lead to somewhere unknown. 

At last, the day came when we had to return. I had spent four days in Goa but still I wanted to stay back with my friends. I knew that it was not possible and we had to separate one after another. I boarded on the bus to Bangalore on 27th. And thus ended my journey to Goa with lots of happiness but with heavy heart. 

Saturday, October 3, 2015

Difference between two numbers in a system with limited operation

One of my friends asked me a question today and he said that it was asked to him by one of his interviewers some time back. Here is the problem statement:

You are designing a new computing system in which following four operations are possible as of now:

(1) Assignment of a variable to another : x = y.
(2) Assignment of zero to a variable : x = 0.
(3) Increment a variable : x++.
(4) Looping in a way which takes a number (variable) as argument and loops for that number (variable) even if you change that variable's value inside the loop. You can't break out of the loop.

How to calculate difference of two numbers "x - y" in the above system?

After spending some time in thinking about the solution, here is what I came up with:

There is one more information given to us. The system is new and designed by us. Hence, we know the architecture of the system and hence the highest positive value possible in that system after which a variable becomes zero if incremented by 1. 
Now, we can assign the highest possible value for that architecture, say 65535 for 16-bit as we are allowed to assign a value to a variable. Then we can increment it twice to get the output as 1. We see that if we add 2 to the highest value we get 1, in a similar fashion, we can add 'n' to the variable having highest value to get 'n-1'. So, we see that in the first iteration, we start with 'n' and get 'n-1'. We can then start with 'n-1' and we will get 'n-2' and so on. We will get 'n-y' after 'y' iteration. Here we can take "x = n". 

Hence we will get "x - y" with the set of operation defined in the problem statement above and one more additional information about the highest number possible in the system. 

Saturday, August 22, 2015

Valley of Flowers and Badrinath journey

It is indeed a 'Devbhoomi' (Land of Gods). It is Uttarakhand in India. We returned from Valley of Flowers and Badrinath last weekend and I am writing down my experience and itinerary for the same. 

We had a flight to Delhi in the evening of 8th of August. Then we boarded on a train to Haridwar at night and reached there next morning. The railway station was full with pilgrims. We couldn't get a bus direct to Govindghat. Someone suggested to go to Rishikesh and from there we will get a bus to Govindghat. We went to Rishikesh and it took three hours to complete this journey through a bus. Though it should have taken only one but it was a festival season and there were thousands of pilgrims going to offer 'Ganga jal' (holy water of the river Ganga) to Lord Shiva in a temple nearby. I had a chat with one of the devotees and he said that they were going to a place called Neelkanth. The same offering happens at a place called Deoghar (Home of the Lord) now in Jharkhand (earlier in Bihar). So I was able to relate to the activities the pilgrims do and their dressings also which is of saffron color. 

Once we reached Rishikesh, we got to know that we won't get a direct bus to Govindghat but we will get a bus to Chamoli from where we will get a bus/ transporter car to Govindghat. Therefore, we boarded on the bus to Chamoli. There were five of us, three of whom were college friends including me. It was a wonderful journey to Chamoli. We enjoyed a lot and got to see a lot of places which we don't see in our city lives. The air was very soothing and pleasant. It was without the polluted city air. The bus stopped at place and we had lunch there. The food was good. People from several other countries also come and visit these places. The locals on those hilly areas also boarded on the bus now and then and I got a chance to hear their language and observed their lifestyle too. It was a great journey to Chamoli where we reached in the evening. Luckily, we got a vehicle to Joshimath where we reached soon enough to stay at night. We took government run hotel and a double bedroom costed us INR 660. Hot water was available in INR 25 each bucket the very next morning. 

Next morning we started our journey from Joshimath through a four wheeler vehicle (I have forgot the name) and reached Govindghat in an hour or an hour and a half. The trek to Ghangaria (which is a one-road village) started from Govindghat then. It is a 13 km trek mainly ascend alongside the river Lakshman Ganga. Though there are few descends and plain walks too. One can take mules/ porters for the backpacks or self. I took a mule in INR 700 for my backpack after trekking for about four kilometres. The walking stick which I bought from Govindghat in INR 20 helped me a lot throughout the trek. Along the way one can find several small villages where food is available at slightly higher price than plain lands. There was an old lady who was selling Apples along the way. We bought few kilos of apples from her and she seemed to be happy. She had told us about 2013 floods which washed her home away and they had nothing to do. She showed her home down the hill. There were few apple trees near to the river. We stayed in Ghangaria that evening. I got sick the next day and had to take bed rest the entire day. My friends went to Valley of Flowers (VoF) that day which is a 5 km trek from Ghangaria. I went to VoF the next day alone. Going there alone taught me several important aspects of life and I enjoyed it a lot. There were many other trekkers whom I got a chance to interact with along the way to VoF. One of them gave me two chocolates too, I think in courtesy to the water I gave him to drink. They talked to me in Bangla (a very popular language mainly spoken in the eastern part of India and across the globe now). The trekkers included folks from all stages in life. There were kids, old trekkers, and young ones too.  At the end of the trek to VoF I got a chance to talk to an old man who went there with his friends. Though he didn't complete his journey to the inside of VoF and he returned from the river at the perimeter of VoF, but he told me something which I can never forget. My old friend told me, "Though I am returning from here but you, my friend, go ahead and complete this journey". After that he patted on my back as an encouragement to complete the trek. We talked in Bangla and then I realized that many people who go there speak Bangla as I had interacted with few of them and heard others speaking in the same language. There were many groups on the trek like a group of boys and girls who seemed to be from a college, a Mahrashtrian family, many Sikh brothers, etc. 


The Valley of Flowers was covered with lots of flowers and many of them have great medical benefits. The flowers were of various colours ranging form Blue, Yellow, Pink, etc. There was a 25 minutes documentary which we watched the previous evening and it costed INR 30. It gave us good idea about the history of the place and information about the flowers. The VoF and Ghangaria are open to everyone only for a brief period of three months and I got to know from a guide that the flowers which bloom there in huge numbers also may vary in different times within those three months. Initially, there were very less clouds in the valley, but it started increasing as the day passed and it rained sometimes. I went inside the valley and used to stop and view the amazing valley along with its flowers and wonderful natural beauty. I didn't go till the end where there was a beautiful blanket of ice which I could see from a distance in the valley. I knew that I had to return sometime but I didn't want to. There were many waterfalls in the valley which were producing the sound which felt as if I always wanted to hear them. At the end I had to return half-heartedly as I wanted to see more but I was satisfied to some extent since I visited the place at least. Overall it was a wonderful and life-learning experience. 

My friends had gone to Sri Hemkund Sahib ji (which is a Gurudwara) that day and I heard that it was even more difficult trek than VoF. There is a temple called 'Lokpal' where a guide told me that 'Sheshnag' was granted the boon to have birth as 'Lakshman', the younger brother of Lord Rama. 

The day came when we had to trek back to Govindghat and it took about five hours for the same. We went to Badrinath from there through a hired vehicle and visited the temple there. The temple is a must visit holy place near to the river Alakananda and I enjoyed a lot there as very few people were there during that evening. Next morning, we boarded on a sharing vehicle to Joshimath. We also visited Lord Hanuman temple called "Hanuman Chatti" along the way. It is said that Lord Hanuman broke Bheem's ego there and taught him a lesson during Mahabharata times. We had to face landslides at two places. Finally we reached Joshimath and then took another sharing vehicle to Chamoli where we had lunch and took another sharing vehicle to Rishikesh. We reached at Rishikesh at night and then took a bus to Haridwar from where we had reservations in a train to Delhi where we stayed at a friend's appartment. We had flight back to Bangalore on Sunday and thus ended our nine days journey to "Valley of Flowers". 

Here is a list of places you need to be to reach VoF and Badrinath (optimized list which we couldn't follow):
Delhi to Haridwar : Night train
Haridwar to Govindghat: Bus
Govindghat to Ghangaria : Trek/ Mule 
Stay at Ghangaria (@ INR 600 double bed to INR1000 on average).
Ghangaria to Valley of Flowers : Trek (about 5 KM after 2013 floods).
Ghangaria to Hemkund : Trek/ Mule.
Ghangaria to Govindghat : Trek/ Mule.
Govindghat to Badrinath: Bus/ Sharing/hire vehicle.
Stay at Badrinath (@ 300 four bed, guest house near bus stop; other hotels available).
Visit temple and nearby places at Badrinath. 
Badrinath to Haridwar : Bus [or Badrinath to Joshimath/Chamoli and from there to Haridwar/Rishikesh]
Haridwar to Delhi : Train.

NOTE: Suggestion is to take medicines for common issues along with you during the trek on hilly areas and drink mineral water if the local water doesn't suite you.

Friday, June 5, 2015

InMobi hackathon

The day came when I had to go to participate in a Hackathon once again after a long period. It was Saturday and I woke up early morning so that I can reach at the venue on time. InMobi's office in Bangalore is a masterpiece, I must say. First line of selection process was online where our ideas were filtered and we were called at the facility after our ideas were chosen. I was joined by my friend Ravi and like every team we were allotted two cubes - the open cubes at InMobi. After Mohit's sesssion about the hackathon we went to our cubes and settled. All the teams had a mentor and we were asked to formalize our idea within a limited time. It was reviewed by our mentor after the time was over. Then we started thinking about how to approach the problem.

I got a chance to interact with Soumya during lunch. He works at InMobi on databases. He is a cool guy and we interacted a lot and shared some quality time on the lunch table. We went back to our cubes after lunch. I had few discussions with Ravi as he was facing some issues with his web interface. I was thinking about each of the modules of our idea and trying few things on linux and writng scripts for those. It was 3 in the afternoon and there was a laughter session by Sanjay Manaktala. We laughed a lot!! and it was really helpful in rejuvenating a new source of energy within us. We went back and resumed our work. After some time, we had few lines of codes working and we could actually showcase something of our idea. It was 7 in the evening and there was a third round of review by our mentor. We had a great support from Siva and his inputs were truly helpful. We had dinner after some time and I must say that the food was awesome like lunch and breakfast.

It was midnight and we decided to come back to our home and then go back to the arena next morning. We went back to the arena next morning and saw that few folks looked as if they didn't sleep at night. I met with my friend Tushar again in the morning. He had also participated in the Hackathon. It was a wonderful experience and a perfect refresher for me after college. We enjoyed the environment at InMobi a lot and I am eagerly waiting for the next one.  

Monday, March 9, 2015

The FREAK Attack

Last week saw one more security attack. It was named as the "FREAK" attack and is basically an MITM (Man In The Middle) attack which targets the "downgrade to weaker algorithm" property. It downgrades to export grade algorithm. As a countermeasure to this attack, the support for export cipher suites has to be disabled. Several write-ups are worth mentioning and the readers are suggested to go through each of the links mentioned in the references below in detail.  

References:

Saturday, January 24, 2015

virtualbox window resizing

From quite a few days I was annoyed with the small screen size of my Ubuntu installation in virtualbox. Tried a lot of package installations and reboots, but nothing worked. Finally, the following set of commands worked:

sudo apt-get install build-essential module-assistant
sudo m-a prepare
cd to VBOXADDITIONS which is there in /media/
sudo ./VBoxLinuxAdditions.run
sudo reboot

And the window should be fitting the screen after the reboot.

Wednesday, November 12, 2014

Wings of Fire - APJ Abdul Kalam

Recently I visited my home town after one year with my cousin brother and this time I booked train ticket from Bangalore. It has always been a great journey for me whenever I have travelled by train. Watching the fields, distant land, people working, trees, mountains and houses gave me a wonderful experience. I felt that my country indeed has lots to offer and great diversities. My journey started from south western part of India and ended in the eastern part and I reached my home after travelling through six states. It was a long journey of about two days and I was thinking what I should do during my travel. So, I looked into my stack of books and I found a book written by our ex-president, a great scientist and a great teacher, Dr. APJ Abdul Kalam. The book was "Wings of Fire". 

It is indeed a great book which not only gives us the experiences of Dr. Kalam but also motivates us to do the likes. Through his experiences he has imparted a sea of knowledge to us. Apart from all the events which he has beautifully written, I liked his scribbled poems. It felt difficult sometimes to fully understand what he actually meant but I gave sufficient time to each of his stanzas. The end result was that I ended the book while returning from home to Bangalore. An old Bengali gentleman, who was having his reservation in front of mine while returning, told me that he has read the book twice and described me his understandings of the book. He was a very friendly person and liked to talk much.

It was a great learning journey as I travelled by train for so long after three years. At the end I decided to take a book on every journey of mine now onwards. 

Wednesday, October 15, 2014

The POODLE attack on SSL 3.0

Google wrote on its blog about the POODLE attack which seems to be a concern now. Though nvd still says it is under review. One of the recommendations being to disable SSL 3.0 on client (or server or both). Readers are suggested to go through "Recommendations" section here for detailed explanation on the recommendation and "The POODLE Attack" section for explanation on how the attack works. Any comments are appreciated.

Sunday, October 12, 2014

Secure copy - an introduction

Secure copy  [scp] is a remote file copy program which comes as a sub-module in OpenSSH. It uses SSH as underlying protocol to transfer data and uses the same authentication. A simple command to copy a file to a remote host is:

scp file user@remote_ip:

There are several options which we can pass to scp [in the command-line itself] like options for ipv4 [-4], ipv6 [-6], option for enabling compression [-C], specifying per-user config file for ssh [-F ssh_config], etc which are passed to underlying ssh process. Additionally, options can be passed in the format used in ssh_config.

Scp works in source and sink modes i.e. 'from' and 'to' which can be seen in the codes and can be realized from the command line also. Users are suggested to go through its manual page. This can be found either by executing "man 1 scp" in the terminal or from the internet ex. 'manual' link of OpenSSH.

Sometimes we need to debug issues in scp for which we may need to see the process hierarchy. For this, we can have a look at "ps -elf" and "pstree -p" and grep for 'ssh' and 'scp' for knowing the process hierarchy in ssh and scp.

Readers are suggested to comment for any rectification on this post or suggestion.