Posted tagged ‘grandpa’

Sum it Up

August 24, 2011

Problem: you are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number? what if i give you the constraint that you can’t use a dynamic amount of memory (i.e. the amount of memory you use can’t be related to n)?
what if there are two repeating numbers (and the same memory constraint?)

Solution

as a programmer, my first answer to this problem would be make a bit vector of size n, and every time you see the number, set its correspond index bit to 1. if the bit is already set, then that’s the repeater. since there were no constraints in the question, this is an ok answer. its good because it makes sense if you draw it for someone, whether they are a programmer, mathemetician, or just your grandpa. its not the most efficient answer though.

now, if i add the constraint that you can only use a fixed amount of memory (i.e. not determined by n) and it must run in O(n) time… how do we solve it. adding all the numbers up from 1 to n-1 would give us a distinct sum. subtracting the total sum of all the numbers from the sum of n to n-1 ( which is (n)(n-1)/2 ) would give us the secret extra number.

what if you can only use a fixed amount of memory, and TWO of the numbers are repeated? we know that the numbers have a distinct sum, and the difference would be equal to the sum of our unknowns
c = a + b
where c is the sum and a and b are the unknowns – c is a constant
if we had another similar formula we could solve the two unknown equations. my first thought was that the numbers would have a distinct product – (n-1)!
if we divide the total product by the (n-1)! product, we would get another equation
c2 = ab
we could then solve the two equations to get them into quadratic formula notation
0 = ax^2 + bx + c
and solve for the two values of x. this answer is correct but factorial grows really fast.

some sort of sum would be better. the sum of the squares from n-1 to 1 would work. that would yield a function of the form
c2 = a^2 + b^2
which could also be solved by using the quadratic equation.

i think its fine to remind someone of the quadratic equation… (maybe only because i myself had to look it up to solve the problem) i mean really though, the last time i used it was probably in 10th grade. as long as they get the idea that given two unknowns and two equations you can solve for the unknowns – thats the point.

Pilot to Mechanical engineer-the story so far.

August 23, 2011

“What do you want to become when you grow up, a doctor or an engineer?” asked my grandpa when I was a four year old. A question that evolved from a typical malayali mindset. Most of the mallu kids are taught to reply either doctor or engineer if somebody asks. My answer was pilot. A couple of trips to Trivandrum airport and my favorite toy aeroplane might have struck the spark in me. The ‘pilot bug’ gradually died down as it was replaced by police,inspired by some action movies.


I imitating a policeman ( Cops never aim & salute simultaneously :-P)

Quite ironically another movie which I saw when I was 7-8 years old, made me quit the desire to become a policeman. The movie was ‘Nanma niranjavan sreenivasan’ ( a Malayalam movie, Jayaram starrer). The hero of the movie was a police constable and in one particular incident the hero had to guard a deadbody, alone throughout a night. The next morning he was shivering with fever. That scene made an impact on my ‘weak heart’.

I fell in love with science @ school in 3rd or 4th standard. I dreamt of becoming a scientist . I stood odd in my class when teachers asked about ambition. The funniest part of ‘scientist story’ was that I did some experiments hoping serendipity.I still remember trying to burn various shrubs and grasses to discover biofuels when the hyped story of Ramar Pillai’s biopetrol was at its peak. Though I wanted to become a scientist, my mind wandered between astronomy, biology and geology.

I wrote the entrance exam for admission in Sainik school (9th std) and got shortlisted for the interview and medical checkup. To be frank I was more interested in the discipline , the sports and games and the huge campus, than becoming a defense personnel. The ‘scientist bug’ didn’t leave me. It was time for the interview and I had to strike a balance between ‘scientist’ and ‘defense personnel’. The interview panel consisted of three people, all of them defense staff. They shot the ‘ambition question’ and my answer was scientist in defense sector. They asked ” what do you mean ?” . I answered ” just like A.P.J Abdul Kalam”. Pokhran II and my interview happened in the same week and I went not stop about fission, fusion etc. They asked “what will you do if you don’t become a scientist?”. I replied ” I will join the defense services”. It didn’t convince them and finally I didn’t make it. They were interested in future soldiers, not scientists.

My grandpa’s question again came back when I finished 10th standard. This time from my parents. I changed my mind to engineer from scientist, but my parents wanted me to become a doctor( guess they were attracted by the social status and moreover my grandpa’s wish). I was in a reluctant mood , wrote the medical entrance and ended up in failure. After that I went for 1 year medical entrance coaching at a reputed coaching center . I neither gave 100% commitment to it nor dishearten my parents by saying a ‘no’ to the medical stream. I couldn’t get enough rank the second time also. The truth was that I often went in a ‘stealth mode’ practicing some maths problems which helped me fetch a fair rank in engineering entrance exam. Now there weren’t many options left other than joining bachelors degree course in engineering. I never blame my parents for the ‘lost’ 1 year, In fact I say I am responsible for the good or the bad that happen in my life.I should have taken a bold step. People (friends, relatives etc.) call it ‘lost’ year , but I never felt so and moreover learnt a couple of lessons in life.

Now it was time to choose the branch of engineering. The general trend was choosing electronics and communication . I was also in the mood until I got enlightened about Mechanical engineering by Dr. S. Jose , my relative and academic guru. Himself being a Mechanical engineer and Asst Professor, threw insight to the various aspects of mechanical engineering and I never thought twice to choose my stream. Mechanical engineering, being a ‘broad’ stream of engineering rendered me numerous options to choose- energy sector,oil and gas ,automobiles, aeronautical, aerospace,thermal.

I never had an interest in computer programming. I still remember, how tough the C++ programming was in 3rd semester for me, just managed to fetch a pass in that subject. 90% of the companies which came to my college for campus recruitment were IT companies. All the placement activities started in 7th semester. Though I wasn’t interested, just for the sake of attending tests and interviews, I participated in the drives. 3-4 companies came and I didn’t manage to get 1. Finally I got a job in a reputed IT company .I never wanted to join that company and told my intentions to parents. They advised it will be utter foolishness if I don’t join the IT firm, without having another job in hand. I was mentally preparing for a fight with them, thought of firing all guns to get a job in core field. I continued writing exams and attending interviews, and got a job in one of the fields which I dreamt of getting into- Oil & gas industry.My parents were happier than me. Thanks to all. Presently, striving hard to achieve my goals, and will be writing a part 2 to this post some years later. 🙂