My Placement Experience

It's been a long time since I last posted here. A lot has happened during this time. The hectic end to 6th sem, my Summer Internship at Facebook (I had to mention this at least once :P), the whole 7th sem; but as always, I was too lazy to write about anything. I've wanted to write something for long, but why write when I can waste time watching a TV show?

Now since I'm finally done with the 7th sem and have too much time to spare (at least for a few days), I decided to come back here. I can't get all the credit though. I got inspiration from Sujeet and SRG, who both have written about their placement experiences. I saw this as a good opportunity to get back in the game, and also to (hopefully) get more views on my blog ;-)

Background Information
There is a good chance that some of you would've left this page after the first paragraph. So, I have to make sure that the rest of the brave souls who stayed, don't leave too. Hence, some info on what all offers I got during placements.

Some of you might already know that I'm a student in Computer Science and Engineering department of IIT Madras. On day 1 of placements, I got following 4 offers:

1. Goldman Sachs

2. Samsung R&D (US & South Korea)

3. Samsung India Software Operations

4. Samsung India Electronics

Well, that's a lot of Samsung. I ended up choosing Goldman Sachs over all Samsung profiles including the one with the highest paying job in IITM(probably in all IITs, I'm not sure).
So, here is the story of placements.

Before Placements
I applied to a lot of companies(Around 20) mostly core companies like Adobe, Microsoft, Linkedin, Amazon, Yahoo etc. along with big finance companies like Morgan Stanley and Goldman Sachs. A lot of my friends said that for a CS 9 pointer, I was applying to too many companies, but I just believed in what Spock said "It was logical to cultivate multiple options". I will be lying if I say that I wasn't scared of screwing up in all the interviews. There were times when I screwed up placement tests, and feared that I might not get any job in first 4 days. Since I had not written CAT or GRE, I had no back-up. I started thinking that I should have applied to even more companies, even those which I didn't really find interesting.

During all these tests, I realized that I needed to revise topics like OS, Compilers, and Networks. I wasn't super confident in Data Structures and Algos either, but my practice on SPOJ had made me somehow confident in those.

Week before Placements
During Endsems week, I had lots of breaks between the exams. I guess I should've utilized that time by doing some revision. That was actually my original plan. But, I ended up watching 6-7 movies. I re-watched the whole Lord of The Rings series. Even after Endsems, I had to follow the great tradition of Computer Science Department where you have to finish assignments after Endsems(Unless you are MVK, who finishes everything at least a week before deadlines). So, next 3 days went in finishing assignments and writing placement tests. 2 days before placements, Flipkart conducted a test. Out of the 2 coding questions, I couldn't solve even one. That was a big blow to my confidence. I decided to put as much effort as possible on the last night. But, I was so tired that I just slept off early and decided to get up early and read something.

The Day (December 1st)
Interviews were supposed to start at 7am. I had somehow managed to qualify for Google, Samsung(3 profiles), Goldman Sachs, and Directi. I decided to get up at around 4, and revise. But as it always happens with a lazy fellow like me, I couldn't. Before leaving, I just had 20 minutes to revise, during which I chose to read up on hash tables.

I was nervous, yes. I was worried at my insufficient knowledge of some topics. But strangely, I was not scared anymore. My father always asks me to think about "what is the worst that can happen?" in tensed situations like this. So, that's what I did. The worst that could happen was that I wouldn't get a job on day 1. I guess that should be a scary thought, but for me it was a bit of relief. I got into my "Jo hoga dekha jaayega" mode.

Morning Session
The big day started with Google interviews. I had 2 back to back interviews. I felt I screwed up one, and did okayish in the other. Bad start. Then came Goldman Sachs, and Samsung US. After 2 interviews with Samsung and 5 interviews with GS, I was 80% sure that I was going to get selected for both. I started wishing that these two companies declare their results soon, so that I can go and sleep. Little did I know that they were not allowed to announce their results before 10pm. Since I had already had 9 interviews, I had no enthu to sit for another. But I had to sit through all the interviews in the afternoon session also. :(

Special thanks to all the placement coordinators at that time. They were really helpful and encouraging. Google's second interview took up my GS interview slot. The Samsung interview was scheduled in the next slot, but GS people were also calling me to come for that interview. At that time, the placement coordinators really helped me manage the situation. They ensured that I could sit for both the interviews without any trouble.  

Afternoon Session
Afternoon session started with Microsoft test from which they were going to select people for interviews. During that test only, I got calls for Directi and Samsung interviews. This was gonna be a painful session. After 3 more interviews for 2 profiles of Samsung India, I found out that I didn't get through for MS interview. I didn't know whether to feel disappointed or relieved. By 6:30, I was done with all the interviews except Directi. I was hoping to get done with it quickly. I was daydreaming about food and sleep. But, 2 Directi interviews lasted for 3 hours, and I was stuck in the interviews hungry and sleepy. Finally at 10pm, it was over. I had survived through 14 interviews in one day.

Result Time
After all this fight, I wanted to know the results as soon as possible. So, instead of waiting for results to come on placement website, my friend Sagar and I went to placement office to find out results as soon as possible. And yay, I got offers from Goldman Sachs, and all 3 Samsung profiles.

It was pretty awesome to see that so many of my friends had got great job offers. Almost everyone in class was placed on day 1. 6 guys were placed from my hostel wing that day.

Moral(s) of the story 
1. Have confidence in what you know. There were a lot of things I didn't know. I hadn't really prepared properly. I am not encouraging anyone to go unprepared or partially prepared like me. What I want to say is that having confidence in whatever you know, does help a lot.

2. Don't let bad performance in one interview affect the other.

3. Having so many interviews in such a short period, means there will be conflicts in timings. Naturally, you will be late for some of the interviews. But, make sure that you are not too late for any of the interviews. If you are late by say 2 hours, your chances will be pretty bad. It's like designing a good Scheduling Policy.

4. If you don't know something, ask for a hint or something. Don't try to fake your way through it. Particularly, if the question is about some core CS concept or about finding a good algorithm. I personally don't like the HR type interviews where you have to sell yourselves. It's not that I'm bad at those(actually it turned out that I'm pretty good at those), but it's easier to put fart there. They obviously won't buy everything, but you can still do a decent job of faking knowledge there. At the other hand, if the interviews check your knowledge of Algorithms and other core concepts, it is very difficult to fake it.

5. Most importantly, having good friends help a lot. There were times during this sem when I was low in confidence, when I was scared. At those times, good friends like Prateek, Vaibhav, MVK, Saheel, Ashu etc (can't type all the names, so 'etc') were a great help. Although they basically accused me of being over-dramatic (Saale sab kamine hain :P), it was really great to see so many people believing that I could do well.

6. Placements are not end of life. Enough Said.

P.S. : This post is a blatant attempt to get more hits on this blog. :-P

CS Rage 3

Dedicated to Computer Vision Victims of our class.
Context : Exams for self-study course Computer Vision.

For the uninitiated : 

CS Rage 1

CS Rage 2

Idea Courtesy : Vijay (MVK)

P.S. :- Those of you who don't know who SRG is, the hint is 'He is to our class what SRT is to Cricket'.

The Human Hero

"If I have to put anyone to bat for my life, it’ll be Kallis or Dravid". - Brian Lara

      It was summer of 2006. A 15 year old boy was in hospital. He couldn't watch the last test of India-West Indies test series there. First 3 matches had been draw. And last match was on uneven pitch of Jamaica. If India could win this match, it would be their first series victory on West Indian soil after 1971.

      The fact that Chris Gayle made a pair on his home ground is good enough to give us a picture of the pitch. It was late in a night that boy was listening to commentary, when that historical moment came. India won a test series in West Indies after 35 years, second time only in the history. For a few minutes he forgot everything about health. For some time every Indian forgot about all their problems. That victory gave that boy the strength to fight his illness.

      Rahul Dravid's career is full of such inspiring moments. Whether it is his hundred at Headingley, or his partnerships with VVS Laxman in Kolkata and Adelaide, or his fifties in Jamaica. Rahul Dravid is not God. He was never a God. He didn't have the perfection of Tendulkar or Stroke Play of Lara. He has always been a Human. And a great one.

      Where is the fun in being God? They have it easy (generally, I think). The best thing about being a human is the struggle and challenge that is the part of our very existance. And that is where Rahul Dravid teaches us the most important lesson. It's more than cricket. It's about anything we do in our life. We all have our limitations, but with a fighting attitude, we can overcome them. Thanx to Rahul Dravid for this important lesson.

      For most of his career he was overshadowed by others. His 95 on his debut at Lords was overshadowed by Ganguly's hundred. His 180 at Eden Gardens overshadowed by Laxman's 281. For most of his career his contribution to the team was overshadowed by more pleasing and attractive game of others. But he was a complete gentleman. Such small stuff never affected his personality, or his game.


"Rahul Dravid is a player who would walk on broken glass if his team asks him to" - Navjot Singh Sidhu


      An ideal selfless team player he was. He opened in test cricket when team needed him to. He took role of wicket-keeper when team needed him to do that. He was considered unfit for ODIs, the man has more than 10,000 runs in the shorter format of the game. He holds record for second fastest fifty in one-dayers for India. The man just loved challenges. There was nothing that he couldn't do.

     Of all his innings, his 233 at Adelaide is my favorite. That was Rahul Dravid at his best. What a great effort it was. With that innings he saved the match, and with his 72* in the second innings, he went on to win the match for India. The best part of that innings was the way he got his 100, by pulling Gillespie for six. And people thought only Virendra Sehwag could do that.


"All this going around is not aggression. If you want to see aggression on cricket field, look into Rahul Dravid’s eyes" - Mathew Hayden

       Apart from his performance on the field, Rahul Dravid was a perfect gentleman and great ambassador of the game. He can be counted as one of the last true gentlemen of the gentlemen's game. One of the finest batsmen of his generation. He was in the league of Tendulkar, Lara and Ponting. The best number 3 batsman in the history of Indian cricket. And as Harsha Bhogle once wrote that whenever an all time India team will be chosen, along with opening position and number 4 position, number 3 will also be already taken.

       Today when he has said good bye to the game, the game has got poorer. It won't be same without him. Indian cricket won't be same without him. The Mr. Dependable for last 16 years has left the stage empty. And on this day, that boy gives his tribute to Rahul Dravid, a true genius. Thanx for the memories. It was an honor watching you play. We'll miss you.

He is a perfect role model for youngsters. He has set a great example for all of us to follow. We are all trying to follow that path," - Sachin Tendulkar
     

Inheritance in JavaScript

         JavaScript is a funny language. For a few weeks I have been reading the book "JavaScript : The Good Parts" by Douglas Crockford. This is the first time I've tried to look at javascript as more than a language just for browser. Syntactically javascript is pretty much like C, but it has much more in common with Lisp than with C. For someone familiar with languages like C and Java, it can be pretty weird at first reading.        
         One of those weird/funny things is that JavaScript has Class-free objects. There is no class hierarchy, objects inherit from objects. JavaScript provides prototypical inheritance. Every function object in javascript has prototype property whose value is an object containing a constructor property whose value is the function object.
          this.prototype = {constructor : this};
          The language attempts to provide pseudoclassical inheritance so that programmers used to the classical style don't feel bad. But in that attempt, the language has become even more complex and messy. Here is an example from the book :


        //define constructor for the pseudoclass
         var Mammal = function (name) {
                   this.name = name;
         };
         //augment its prototype
         Mammal.prototype.get_name = function ( ) {
                   return this.name;
         };
         Mammal.prototype.says = function ( ) {
                 return this.saying || '';
         };
         //we can make an instance:
         var myMammal = new Mammal('Herb the Mammal');
         var name = myMammal.get_name( ); // 'Herb the Mammal'





         //make another pseudoclass that inherits from Mammal

         var Cat = function (name) {

                this.name = name;

                this.saying = 'meow';

         };

         // Replace Cat.prototype with a new instance of Mammal

         Cat.prototype = new Mammal( );




        // Augment the new prototype with get_name method.

        Cat.prototype.get_name = function ( ) {

                return this.says( ) + ' ' + this.name +

                      ' ' + this.says( );

        };







        var myCat = new Cat('Henrietta');

        var says = myCat.says( ); // 'meow'

        var purr = myCat.purr(5); // 'r-r-r-r-r'

        var name = myCat.get_name( );

        //'meow Henrietta meow'

                So as we can see this code looks quite arbit and weird. So, instead of using this pseudoclassical complicated approach, we can try to use Prototypical inheritance as it should be used. The author has provided some good ways to get rid of this mess. One way is to define a method like following :

                Object.beget = function(o) {
                        var F = function () {};
                        F.prototype = o;
                        return new F();
                };

               Now we can just write :
              new_object = Object.beget(old_object);


       And then we can make changes to the new object without affecting the old one. This is called differential inheritance.


        In all these techniques, there is something quite important that  we haven't yet paid attention to. That is the idea of encapsulation. Here we use closures fundaes. Let's revisit the cat and mammal example : 
          




       var mammal = function (spec) {
            var that = {};
            that.get_name = function ( ) {
                return spec.name;
            };


            that.says = function ( ) {

                return spec.saying || '';

            };

            return that;

       };

       var myMammal = mammal({name: 'Herb'});




       var cat = function (spec) {

           spec.saying = spec.saying || 'meow';

           var that = mammal(spec);

           that.purr = function (n) {

               var i, s = '';

               for (i = 0; i < n; i += 1) {

                   if (s) {

                       s += '-';

                   }

                   s += 'r';

               }

               return s;

           };

           that.get_name = function ( ) {

               return that.says( ) + ' ' + spec.name +

                    ' ' + that.says( );

            }

            return that;

       };

       var myCat = cat({name: 'Henrietta'});




             I've given brief description here. If someone wants more details, they can visit
             http://www.crockford.com/javascript/inheritance.html
             http://javascript.crockford.com/prototypal.html

Fermat's Little Theorem

           It's been around 9 months since my first and last post. (Just checked the date, exactly 9 months). I had said that I'd try to be regular, but if someone really trusted me on that, it's their fault.

           So, as I said that I'd write about interesting stuff I come across, this post is about an interesting theorem I recently came across, called Fermat's Little Theorem. 

           The statement of the theorem is pretty simple like most of the theorems by Fermat.

                      For a prime number p and a whole number n, n^p - n is divisible by p.   

          And like most of his theorems, Fermat didn't leave any proof.
          The theorem was first proved by Leibniz around 1683, but he never published it. The first published proof came from Euler. Both Leibniz and Euler gave essentially same proof. I decided to give it a try on my own before looking at their proof.

          First thing that I did was to factorize the expression.
                               n^p - n = n (n ^ (p - 1) - 1)
          So, the case when n is divisible by p becomes trivial. Now, the goal was to prove that
                          n ^ (p - 1) - 1 is divisible by p, if n is not divisible by p.
           The idea that came to my mind was induction.
          But before that, I thought of trying to do some arbitrary geometric series stuff, but made a stupid mistake in that and ended up wasting time because I found some impossible results. I tried to prove it using induction and binomial theorem, but no success. Even Prateek Agrawal tried something similar, but that didn't work.
         After wondering for some time, I finally decided to try induction on original problem and the following proof came out.

To Prove :  For a prime number p and a whole number n, n^p - n is divisible by p.
Base step : The proof for n = 0, and n = 1 is trivial.
Induction Step : Assume statement is true for n and try to prove for n+1.
                         So we assume that  n^p - n is divisible by p
                              i.e. n^p -  n = k*p, k is a whole number.
                         Now goal is to prove that (n+1) ^ p - (n + 1) is divisible by p.
Proof :  Expand (n + 1) ^ p using binomial theorem
             We'll get
                        (n^p - n)  + p*n^(p - 1) + p*(p - 1)*n^(p - 2)/2 + ..... + p*n
             n^p - n in this step is divisible by p(as assumed), for the remaining part we can write it as
                          p*(n^(p - 1) + (p - 1)*n^(p - 2)/2 + .... + n)
            Now if we can write it as k*p. All we need to show is that k is an integer. Here we can use the fact that p is prime, and claim that k is integer. And woah, our proof is done. That wasn't too difficult.
            If you want a more awesome proof, you can check the proof by Leibniz here.

            There are a lot of other interesting things related to this theorem like Fermat Primality Test which is based on converse of this theorem (which is not true), so it's a probable primaliaty test. The biggest problem for this test comes from Carmichael Numbers. These are composite numbers and for all n co-prime to them, n^p - n is divisible by p, where p is the Carmiachael Number.
            Also encryption program PGP used Fermat Primality test because the probability of generating a Carmiachael number is pretty small.
            I guess that's it for today. Will try to post something else soon. If someone finds some flaw in the proof, please let me know.
P.S. :- Thanx to Prateek Agrawal for his help with the proof.