Sunday, October 13, 2013
Two players play the following game: they pick a random number N (less than 2 billion) then, starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice). Whoever reaches N first wins. The candidate should write a function that given N decides who wins (first or second player)?
Thursday, October 3, 2013
Two strings can be chained if the first one ends with the same character second one starts with. Given set of 'n' strings, how can we verify efficiently, whether they can be chained or not?
e.g. cat, dog, toad answer is YES.
for tape ate ass answer is NO.
for tape ate ass answer is NO.
Wednesday, October 2, 2013
A circular array A[1, . . . , n] is an array such that n ≥ 3 and A[1] and A[n] are considered to be adjacent elements just like A[1] and A[2], A[2] and A[3], etc., are adjacent. We are given a circular array A[1, . . . , n] of non-negative integers. For any i, j ∈ {1, 2, . . . , n} such that i != j, dist(i, j) = max {|i − j|, n − |i − j|}. Design a linear time algorithm that computes a maximum number t such that for some i, j ∈ {1, 2, . . . , n}, i != j, t = A[i] + A[j] + dist(i, j).
Friday, September 20, 2013
Friday, September 13, 2013
Programmers Day Special : One of Worlds Finest Programmer , Mathematician and Man Behind Google :: Rajeev Motwani
Growing up
Rajeev Motwani, wanted to study mathematics and become another Gauss! His father, however, persuaded him to study computer science. Little did he know how closely the two are related? He graduated with B.Tech. in computer science from IITK in 1983 and PhD from Berkeley in 1988. Rajeev was a wise theoretician that had the rare knack and desire to turn theory into practical applications. Whenever you use a piece of technology, there is a good chance a little bit of Rajeev Motwani is behind it.
Rajeev played an important role in the founding of Google 15 years ago. He was snatched away from us on June 5, 2009, at the age of 47, in a drowning accident in the backyard swimming pool of his Atherton home after a party celebrating the end of the school year!
Growing up
Rajeev Motwani was born on March 24, 1962 in the Indian city of Jammu to Lt. Colonel
Hotchand Motwani, an officer in the Indian Army, and Namita Motwani. His family included brothers Sanjeev and Suneev. Given his father’s army career, Rajeev’s family moved often and lived in various parts of India before settling down in New Delhi.
When Rajeev was seven, his father was stationed in the scenic town of Devlali near Mumbai, India. His family would walk a kilometer to the local library to get books, and the seven-year-old Rajeev would be seen reading the books they had borrowed from the library as they walked home! His brothers recall that not a single day would pass when he did not read a whole book.
Young Rajeev wanted to be a mathematician, like Gauss. “This was partly shaped by the books I had at home. My parents for some reason had a lot of these books – 10 great scientists or five famous mathematicians – their life stories and so on. As a child, whatever heroes you read about you want to become,” adds Rajeev. Rajeev would read books of all types, including novels, comics, autobiographies and scientific books. Rajeev also loved music, particularly rock music. One of his favorite bands was Indian Ocean. His friend from Berkley days, Rathin Sinha recollects Rajeev’s love for books by Asimov, music by Pink Floyd, and canned chili and rice meals!
A turning point in Rajeev’s intellectual development came when his family moved to New Delhi in 1974. Rajeev’s father wanted to send his children to the prestigious St Columba’s High School in New Delhi. St Columba’s High School administered a difficult entrance exam to admit students, and Rajeev studied hard the night before taking the exam. Not only did Rajeev pass the exam, he did so well that the principal admitted all three brothers into the school!
Reluctant Computer Scientist
After 11th grade (in the 10+2 program) in 1978, he appeared in JEE earning third place in the northern zone of India. He did not stay at Columba’s to finish the 12th grade instead joined I I T Kanpur, which at that time had just started the undergraduate program in computer science. “I truly wanted to be a mathematician, and my parents were hesitant because how do you make money as a mathematician, how do you support a family. I was basically forced into going into computer science even though I did not want to, but it turned out to be a wonderful surprise that computer science is actually quite mathematical as a field,” recalls Rajeev in an interview.
Even though IIT Kanpur had an outstanding computer science faculty in the late 1970s, formal computer science education at the undergraduate level was still in its infancy in India. Rajeev was a member of the very first cohort of undergraduate computer science students at IIT Kanpur. Rajeev often recalled that IIT Kanpur had attracted an amazing group of people, and there could not have been a better environment for studying computer science in India. As a student, Rajeev was inspired by Professor Kesav Nori, who taught Rajeev’s first class on programming — TA 306: Principles of Programming. Rajeev recalls, “Wonderful thing about Prof. Nori is that he was a very inspiring person. He did more than just teach. He created such a wonderful ecosystem and developed a personal connection with his students.”
Prof. Nori thinks Rajeev gave him more credit than he deserves. It has been 35 years but he is still so enthusiastic talking about Rajeev – the chubby, smart boy. In a recent phone conversation one could sense enthusiasm in his voice when he said, “Rajeev knew that purpose of programing is not just coding; it is to formulate the problem. Rajeev’s thinking was clear; his expression direct. No unnecessary stuff. Rajeev had a knack for creating the most elegant and brief answers to the hardest of programming problems. It was a joy to read his papers.”
Another instructor at IITK recollects, “Anyone who had taught Rajeev could not but be impressed by his class. At the same time, he was not at all competitive — if he did well, which he did, it was because doing well was so natural for him.”
Gautam Bhargava, a classmate of Rajeev at IIT Kanpur remembers him, “As a fun loving, rock-n-rollin’ party guy, a super-smart classmate. Hardly anyone in IIT-days called him Rajeev. To us he was, and still is, Mots, which was not short for Motwani, as you would expect, but rather short for Motwayne! After the younger brother of the movie star John Wayne! But this alleged younger brother of John Wayne was never seen wearing a 10-gallon Stetson; rather he was most often seen in a kurta, jeans, chappals, with a cloth book-bag slung across his shoulder!
Rajeev’s amazing brilliance might lead you to believe that Rajeev was this immensely studious type who spent all his waking hours studying and hitting the books hard. On the contrary, Rajeev was an incredibly fun loving guy always ready for a party! In his dorm room, next to his bed would always be a stack of science-fiction books waiting for eager consumption. Rajeev would spend endless hours solving the hardest crossword puzzles, playing bridge or volleyball, and hanging out with friends — then he would show up for the tests and magically ace them! Now if a course were “crazy hard”, say, like the one on Number Theory, Rajeev would effortlessly breeze through, with amazingly elegant answers to even the toughest of problems. However, if the class were “easy”, Rajeev could easily lose some interest. Rajeev thought time could be better spent listening to music or hanging out at the canteen eating hakka chowmein or anda parathas.”
Gautam continues, “Rajeev was also quite a music lover with a particular fondness for Rock’n’Roll. During IIT years Rajeev was also the “Audio Club Secretary”. This was indeed a prestigious job as the Audio “Secy” controlled the keys to the Rock’n’Roll kingdom – and decided when and where the amps and the speakers and the other equipment would be made available. As usual, Rajeev took great joy in running that club and recruited a bunch of his friends to lug those heavy amps around! When this got too much he decided it was more fun to play the bass … his favorite tune for riffing on bass was “Badge”! Later he started doodling on the keyboard … and as our friend Madhavan recalls, they only played songs in the key of A-minor so Rajeev could just play on the white keys!!! Rajeev could also create musical wonders with another “instrument” – you just had to hear him use a wine glass and a fork to play the tune for the Bollywood hit Chura Liya Hai.”
Rajeev’s undergraduate thesis (joint with Chilukuri K. Mohan and Amitabh Shah; advised by Professor Somenath Biswas) was quite theoretical: “Specification and Verification of Computer Communication Protocols.” This simultaneous interest in theory and programming percolated through Rajeev’s career. Rajeev’s friends recall that in college he was not only brilliant, but also incredibly fun-loving and always ready for a party. There would always be a stack of science-fiction books waiting for eager consumption in his dorm room, and he would spend endless hours solving difficult crossword puzzles, playing bridge or volleyball, and hanging out with friends. He never lost this undergraduate spirit. Through his time at Berkeley and as a faculty member at Stanford, Rajeev approached research and entrepreneurship with joy.
Never do work today that you can defer to tomorrow
Everybody else was coming to the US for PhD or Masters or whatever. Actually Rajeev did not want to come to USA for some unexplainable reasons. He got a job at DCM Data Products because getting visas at that time (1983) was a big problem. He was also interviewed by the top three guys at Wipro – a small enterprise then. The interviewer said we would love to give you a job looking at your track record but isn’t every one with your kind of back ground going to the US on a scholarship? So have you applied to US? Rajeev said, “Yes I have an offer from Berkley.” He asked do you have a scholarship. Rajeev said, “Yes, but I am not sure if I will get a visa.” He got the visa and landed up at Berkley.
In 1983, Rajeev became a PhD student at UC Berkeley. He found Berkley to be a very politically charged university – he would call it the JNU of the US. For 3 years Rajeev had a blast. Did not do any work and fully enjoyed the environment. His advisor was Prof. Richard Karp, who won the Turing award – which is like the Nobel Prize in computer science in 1985-86. When Rajeev had finished those 3 years without publishing any papers, he thought that he was not doing anything and letting this man down. So from then on he worked really hard and was quite productive for the next two years.
In an advanced course on algorithms taught by Prof. Richard Karp the class was asked to solve a homework problem. With a fellow student and Prof. Karp, Rajeev developed this problem into a theory of deferred data structures: data structures that are built-up incrementally. This resulted in Rajeev’s first published paper, and he summarized it jokingly as his philosophy in life, with the words: Never do work today that you can defer to tomorrow.
This is how Rathin Sinha remembers his days with Rajeev at Berkley, “Rajeev was perhaps my closest friend in UC Berkeley. We arrived in the same August of 1983 and I remember spending countless evenings at his Durant apartment going through his full collection of Isaac Asimov, having tea and ending the evening with fried chili and rice. …and then we went our separate ways. I discontinued my PhD program, took up a job, but lived in the neighborhood.
When I got laid off in 1986, he helped me with my resume, in job search, and most importantly kept me motivated. He even gave me his answering machine in case an interviewer calls and I am not there to take the call. He was always smiling. Very mellow and soft spoken. I never saw him getting frustrated or rattled in spite of his heavy work load. He never complained about life, teachers, tests, or grades. He knew how to enjoy himself.
10 years later – one email and we were connected again. His first request to me was to see if I could help a budding entrepreneur who was looking for some technology. So was Rajeev. For me it was like growing up with Greatness. Rajeev was always ready to help. ”
In 1988 Rajeev was about to graduate from Berkley with PhD (His Dissertation: Probabilistic analysis of matching and network flow algorithms) and was wondering what to do next. Go back to India or stay in the US. Again other people made the decisions for him. Don Knuth, one of the founding fathers of computer science, came over to meet Rajeev’s advisor and told him that they wanted to hire someone young for algorithms at Stanford. So Karp suggested Rajeev’s name. Rajeev was then invited by Knuth at Stanford for lunch. Rajeev was wondering why this great man wants to have lunch with him. Anyway, Rajeev went to Stanford and met him at a restaurant near the church at the quad. He then told him to be with Stanford for a year and see if they liked him and vice versa after which if things worked out well they would hire Rajeev.
He was offered a visiting faculty position at Stanford. He did not want that job as he was getting better offers and permanent jobs at other places but since it was an offer by Knuth it was hard to turn down. Rajeev thought, “It’s the like Einstein inviting you to Princeton for a job!” He joined Stanford and taught several courses and had a very good time.
Stanford liked what they saw and he was appointed as tenure-track faculty. Based on his thesis work at Berkeley, Stanford realized that it was getting an extraordinary and promising theoretician in this 27 year old man. However, everyone underestimated the incredible scholar, teacher, advisor, colleague, entrepreneur, and friend that Rajeev would become.
3 – 4 months after his first year at Stanford he got married. Rajeev met his soon-to-be wife Asha Jadeja in May 1989. Asha graduated from the University of Southern California and relocated to the San Francisco Bay area. Rajeev and Asha were married on March 22, 1990 in Delhi. They liked living in Stanford, and decided to stay. Asha started graduate school at UC Berkeley in 1991, studying urban planning and urban transportation, and joined the department of political science at Stanford in 1994. Two daughters were born from their marriage, Naitri (b.1991) and Anya (b.2003). In their tribute to Rajeev, Asha’s younger brothers, Yashwant and Yogi said, “Rajeev, who we called Jamaisaheb, was to the world a famous scientist, entrepreneur, and mentor. For us, he was the rock star of an elder brother that we never had. When our dear sister Asha married Rajeev, we used to pinch ourselves and wondered how we ever got so lucky — that this brilliant, humble, and incredibly handsome man entered our family and immediately became part of a large, cantankerous family — with such ease. In our 20 years of close association, we never saw Rajeev ever lose his cool, was always generous even to people he did not know, and became the darling son of our parents, and all aunts and uncles in the family. He will be with us forever.”
Robots Taught Him Something Special
Rajeev enjoyed teaching at Stanford. Since so many people were retiring or leaving Stanford there were a lot of courses to be taught. Rajeev ended up teaching variety of courses. He even created and offered his own courses such as topography and algorithms and complexity theory. Since he did not know a lot of these areas but he learned a lot by teaching these courses. He did not get enough sleep! He used to say, “I am a perfectionist and I still get nervous to talk before a class even today. I get nervous, what if someone asks me a question and I find myself unable to answer it. So for this reason I always over prepare.”
The nervousness taught him more than what he learned as a student. He landed up working in many different areas and it broadened his thinking, knowledge, and experience. It also helped not get bored. He used to say, “I have tendency to get bored easily and so if I stay in one area for too long I quickly move over to another area. My threshold of working in one particular area is about 5 years.”
Jean Claude Latombe from France, in robotics area, inspired him to see robots from a very different angle. He told Rajeev that there were a lot of algorithms in robotics which are needed to plan the actions of the robot. Robots require very high dimensional planning. It is like having a starting point A and end point B in space, and moving from A to B without being hit by any obstacles. The same task would be easier with 2 points on the table. Rajeev worked on solving robot related problems for 5 years, putting high dimension geometry and randomization together. Seeing the robots move and perform using his algorithms, he realized that he could do something mathematical but practical. He realized that his ideas, his work could have practical implications.
He could now move over from the paper pencil world to the real world. He gave lot of credit to Stanford for creating an environment where people in different areas could work together making the whole greater than the sum of its parts. He spent one third of his time in doing his work in a theoretical and mathematical way and the rest in collaborating with people.
Pfizer wanted to fund research on computational drug design. And while finishing the work on random motion planning in robots he realized that molecules and robots actually behave in a very similar way. His team came up with software based on his theory and they added some new theories. The project was called RAPID (Randomized Pharmacophore Identification for Drug Design). It went very well. Rajeev learnt a lot. He said, “It was an intriguing experience. I had to go back and learn my high school chemistry and biology and the other fun stuff.” The software is being used by Pfizer labs for their drug design.
There wasn’t a startup he didn’t love
Rajeev was fascinated by the transformation of academic ideas into commercial ventures. To quote his friend and coauthor, Madhu Sudan from MIT, “Having worked with Rajeev at an early stage of my career I knew how smart he was, but it really took Stanford to bring out his true talent, which was the ability to recognize the importance of ideas quicker than anyone else around.”
Rajeev was active in the venture industry, and had a reputation of being extremely helpful to entrepreneurs. Rajeev’s students and industry colleagues remember him for his uncanny ability to connect people: he was a catalyst in bringing teams together and getting companies started with an element of inspiration and strategic guidance. Through Deutsche Bank, to which he had been an advisor, he became one of the first investors in PayPal, and Rajeev and Asha started a venture fund called Dot Edu Ventures in 2000. He was also a special advisor to Sequoia Capital, and was active in entrepreneurial student groups at Stanford, including Business Association of Stanford Engineering Students (BASES) and Stanford Student Enterprises.
Sep Kamvar, a student of Rajeev who later became an entrepreneur recalls, “Rajeev had a selfless heart. At one point early on in our company, I had a conversation with somebody who told me he thought our company wouldn’t succeed. Upset, I called Rajeev the next day, met up with him at the University Cafe, and told him about this conversation. After he listened to me rant for half an hour about how I was going to prove this guy wrong, he smiled and simply said: “Yes, you will. That’s why you’re an entrepreneur. Now your challenge is to use that energy to do something good for the world.”
Another former student and now an entrepreneur remarked, “His ability of porting ideas from one to the other was unparalleled.” Jennifer Widom, fellow faculty from Stanford in her tribute to Rajeev said, “In entrepreneurial circles, many call him “the world’s greatest connector.” He had an uncanny ability to recognize that by bringing together certain people, magical things would happen. On a smaller scale, I recently realized that’s exactly what he was doing in our research enterprise. He clearly had a knack for matchmaking. deeply thought-out insights on most any issue, a willingness to help anyone anytime, and an understated but ever-present sense of humor.
We faculty have a tendency to blather on. Rajeev, on the other hand, would sit quietly and then get right to the point. Rajeev left one hole that simply can’t be addressed. He forged a unique connection between the department and the entrepreneurial world—a connection that was broad, deeply technical, and full of integrity. That is something we simply can’t replicate with any other human being known to us.”
Ram Shriram, a family friend remembers, “Rajeev had a photographic memory and seemed to have a limitless capacity to remember people, numbers, events, companies and the like. He was always accessible and approachable. His business acumen rivaled his technical prowess which made him a unique and potent force in the venture community.”
Gaurav Garg noted, “Rajeev was one of those rare people who operated at the highest level of excellence in multiple disciplines. He was exceptionally observant, practical, thoughtful, yet decisive, with an unerring instinct for the right questions or issues around any topic, be it the game of cricket or a startup. I was always impressed by his kindness, fondness, and open door policy with young entrepreneurs.”
Rajeev was a nurturing force for many startups, according to a close friend and GigaOm editor Om Malik. As an investor and advisor, he sat on the boards of Google, Kaboodle, Mimosa Systems, Adchemy, Baynote, Vuclip.
Then Came the World Wide Web
Around this time the world wide web was coming up and Rajeev got sucked into it. Rajeev in his interview with Shivanand Kanavi in 2002 recollects, “There was this guy Jeff Ullman, another one of the grand old men of computer science, who retired this year. He was in the office next to me and was in database. I was talking to him and a new student – Sergey Brin, and I remember at that time we were using Mosaic, and we were looking at the web and I was sitting there and thinking that we could randomize the web in some way because that was going to grow and become big and randomness was going to be important; though I did not know how and why. So I thought about doing random walks on the web and there was this problem of crawling on the web. At that time a search engine called Inktomi had just come out of Berkley. Excite and Yahoo had come out from Stanford so we had seen the first signs of all of this.
I remember going to Inktomi and searching for the word Inktomi and it could not find itself. I don’t know if that is still true but at that time if you went to Inktomi and typed in the word it said no results found. My Godelian past induced me to do these self-referential queries but what amazed me was that this is a simple thing that people screw up on. So in the context of all this I was listening to some people from IBM talk on Data mining and Ullman had just introduced me to some problems in databases. I broke them down with a student and was getting pretty excited about the concept of databases. Ullman took me for this talk on data mining which sounded very interesting to me. So Sergey and Ullman and we decided to do some data mining on the web because it sounded like a nice mix. We then formed this research group called Midas which stood for Mining Data At Stanford. We did a lot of good work on data mining. Then there was this guy called Larry Page who wasn’t really a part of the Midas group but was a friend of Sergey and would show up for these meetings. He was working on this very cool idea of doing random walks on the web.
When I understood what the World Wide Web would look like, I knew I had to somehow force randomness into it. When Larry showed us what he was doing, it was like a complete epiphany, we thought it was absolutely the right thing to do. So Sergey got involved and it became a sub group inside Midas. I was really a good sounding board for Sergey and Larry and I could relate to what they were doing through randomness. They then created a search engine called Backrub. It was running as a search engine from Stanford just like Yahoo ran till the traffic got big and the IT guys sent it off the campus. So these 2 guys would come to the office and say “hey we need some more disc space”. They were completely non respectful of me, which was a wonderful thing. They treated me like an equal. These 21 year old guys were demanding things from me. They needed more disc space because it’s getting bigger. So we need more disc and more money. There are still pictures around the building of how they used to use Legos, to create a box inside which the discs were being put. These discs were those cheap ones bought from the back of a truck and were generating a lot of heat. So they put it in Legos to allow for air circulation.
For me it was a fun research project. We had a lot of ideas which we shared. At some point this thing started getting very serious and we wanted a better name for this than Backrub. So somebody came up with the name Google. Google means 10 raised to the power of 100. It is actually spelt as GOOGOL but somebody miss spelt it and that’s how the search engine got its name. Of course the official story is we deliberately spelt it that way but my guess is we miss spelt it.
So Google started and pretty soon everybody in the world was using Google. The results were much better than all the other search engines going around. It was by word of mouth like I tell my brother to use it, he would tell his wife, wife would tell her kids and so on. At some point these guys said we want to start a company. Everybody said it was not worth it. There were 37 search engines already there. How would you raise money? How would you form the company? But they decided to do it and they did it. There were some big names which supported the company. Andy Bechtolsheim, an ex-Stanford guy who along with Vinod Khosla had founded the Sun Microsystems, put in a little bit of money. They managed to raise a million dollars. They started the company and it was right here in the university avenue. It used to be on my drive home so I used to go and hang out with these guys. It used to be wonderful.
Then they took over the world!
Right now the other search engines don’t even compare and I remember people who I don’t want to name saying why do you need another search engine? Today it is the most used search engine. Feels like I was part of a little bit of history and contributed to that history.”
Sergy Brin and Larry Page founded Google on September 4, 1998.
In his tribute to Rajeev, this is what Sergy Brin said, “Officially, Rajeev was not my advisor, and yet he played just as big a role in my research, education, and professional development. In addition to being a brilliant computer scientist, Rajeev was a very kind and amicable person and his door was always open. No matter what was going on with my life or work, I could always stop by his office for an interesting conversation and a friendly smile.
When my interest turned to data mining, Rajeev helped to coordinate a regular meeting group on the subject. Even though I was just one of hundreds of graduate students in the department, he always made the time and effort to help. Later, when Larry and I began to work together on the research that would lead to Google, Rajeev was there to support us and guide us through challenges, both technical and organizational.
Eventually, as Google emerged from Stanford, Rajeev remained a friend and advisor as he has with many people and startups since. Of all the faculty at Stanford, it is with Rajeev that I have stayed the closest and I will miss him dearly. Yet his legacy and personality live on in the students, projects, and companies he has touched. Today, whenever you use a piece of technology, there is a good chance a little bit of Rajeev Motwani is behind it.
This is how Larry Page remembered him, “Rajeev was a wise theoretician that had the rare knack and desire to turn theory into practical applications. Rajeev was always willing to lend an ear and a brain to anyone, even to me as a confused student. With his always open door and clever insights, Rajeev was instrumental in the early work that led to Google.”
Ron Conway, early stage investor in Google, Ask Jeeves and PayPal, recollects, “Rajeev was always so generous with his time. I was talking last night to Rajeev’s brother, Sanjay, and we concluded that there must have been THREE of him!!! ….one was always at university café and another was always at Stanford and the other one at google!!”
Humble to the Core
David Hornik of August Capital remembered Rajeev as a friend, “It is one thing to be friendly with someone in the business world. It is another thing altogether to consider them a friend. Rajeev genuinely liked people and people genuinely liked him.”
One of his instructors from IITK recalls, “I met him only infrequently since 1983, but I’d get in touch with him whenever any need arose, either for myself or for a student. Rajeev would render his help promptly and he’d answer e-mails without any delay. Only now I realize, reading about him, how busy though he had been all through. I recall that in 1999 June I went to his office to meet him. When I reached, an undergraduate student of his theory of computation course was there to clear some doubts. From the questions the student was asking, it was evident that the student had put in hardly any effort in the course. Most of us would be very impatient with such students. Rajeev, however, was not only patient but also friendly– I still remember how beautifully, without using the whiteboard, Rajeev explained, just through words, why the problem of checking if an input TM would ever make a left move when started on a blank tape is decidable. I could see that the student understood the argument, and he left the office very happy. It was a lesson to me — I realized that people of true excellence have no problems at all in accepting shortcomings in others.”
When Rajeev received Godel Prize in 2001, this is what he so humbly said, “I got the Godel prize for my theoretical work. In science it is said that one guy stands on the shoulders of another and another on his and so on. The guy on top gets the prize. In my case I was on the tip of the pyramid and so got the prize. Everyone forgets the pyramid.”
Rajeev was a school mate of Shahrukh Khan, the Indian film star, at St Columba’s High School in New Delhi and had great admiration for him. In his self-effacing style he would say, ‘that guy (Shahrukh) is brilliant and will be the No.1 in anything he takes up’. Pushing into background his own remarkable intellectual achievements.
Not feeling so lucky!
Prakash Tripathi met Rajeev as a 17 year old at IIT Kanpur campus in 1979. Rajeev spoke to Prakash, ironically, by the IITK poolside.
“Can you jump into the waters?,” Rajeev asked.
“Yes, I can,” Prakash replied. Not because Prakash knew how to swim, but as a fresher in a campus of India’s engineering schools, in a hot summer afternoon in Kanpur, dying in a pool was a far dignified way to reject life’s conditions then to submit and surrender.
Rajeev didn’t tell Prakash whether he could swim. Nor Prakash had the courage to ask. But Rajeev inspired Prakash to convert our lies into truth as a homage to future. First thing Prakash did, after graduating from IITK, was to learn to swim in IIT Delhi pool. Prakash recollects, “It’s traumatic to me today that Rajeev didn’t. That was his failing as a human.”
Rajeev, 47, died June 5, 2009 in the backyard swimming pool of his Atherton home after a party celebrating the end of the school year. Rajeev’s blood alcohol level was .26 when he died, San Mateo County Coroner Robert Foucrault said. The legal limit for operating a motor vehicle is .08. Rajeev did not know how to swim.
On June 6, 2009, day after Rajeev’s death, Deepak Nayar, wrote, “I was one year senior to him at IITK and when he arrived at Berkeley, I picked him from the San Francisco airport and had a run-down room ready for him (next to our run-down room above Pasandrestaurant). Four of us lived above Pasand. He and his success were admired by so many of us. So many of us looked up to him and referred to him as an IIT Baap. We were proud of him. Sad it ended this way. This is not how it is supposed to be!!!!” In the classic American movie, It’s a Wonderful Life, the angel who has been sent to save George Bailey, says: “Strange, isn’t it? Each man’s life touches so many other lives. When he isn’t around he leaves an awful hole, doesn’t he?”
Rajeev’s life touched so many of us. His death has certainly left a big hole.
Every time you Google, you are in touch with Rajeev.
=============================
Rajeev Motwani graduated with BTech in Computer Science from IITK in 1983 and PhD from Berkeley in 1988. He taught at Stanford till his accidental death in 2009. A fun loving highly accomplished theoretician who could find practical application of his ideas was an early investor in several start-ups. He helped Brin and Page in 1998 to found Google. He received Godel Prize in 2001 and Distinguished Alumnus Award from IITK in 2006. A Computer Science Building at IITK in Rajeev’s name is being constructed through generous donation from his family.
This story has been prepared from personal interviews and by cutting and pasting material found through, interestingly, Google search! All credit to original contributors who are too many to be named individually.
Source : http://alumniconnect.wordpress.com/2013/09/10/rajeev-motwani-there-wasnt-a-startup-he-didnt-love/
Rajeev Motwani, wanted to study mathematics and become another Gauss! His father, however, persuaded him to study computer science. Little did he know how closely the two are related? He graduated with B.Tech. in computer science from IITK in 1983 and PhD from Berkeley in 1988. Rajeev was a wise theoretician that had the rare knack and desire to turn theory into practical applications. Whenever you use a piece of technology, there is a good chance a little bit of Rajeev Motwani is behind it.
Rajeev played an important role in the founding of Google 15 years ago. He was snatched away from us on June 5, 2009, at the age of 47, in a drowning accident in the backyard swimming pool of his Atherton home after a party celebrating the end of the school year!
Growing up
Rajeev Motwani was born on March 24, 1962 in the Indian city of Jammu to Lt. Colonel
Hotchand Motwani, an officer in the Indian Army, and Namita Motwani. His family included brothers Sanjeev and Suneev. Given his father’s army career, Rajeev’s family moved often and lived in various parts of India before settling down in New Delhi.
When Rajeev was seven, his father was stationed in the scenic town of Devlali near Mumbai, India. His family would walk a kilometer to the local library to get books, and the seven-year-old Rajeev would be seen reading the books they had borrowed from the library as they walked home! His brothers recall that not a single day would pass when he did not read a whole book.
Young Rajeev wanted to be a mathematician, like Gauss. “This was partly shaped by the books I had at home. My parents for some reason had a lot of these books – 10 great scientists or five famous mathematicians – their life stories and so on. As a child, whatever heroes you read about you want to become,” adds Rajeev. Rajeev would read books of all types, including novels, comics, autobiographies and scientific books. Rajeev also loved music, particularly rock music. One of his favorite bands was Indian Ocean. His friend from Berkley days, Rathin Sinha recollects Rajeev’s love for books by Asimov, music by Pink Floyd, and canned chili and rice meals!
A turning point in Rajeev’s intellectual development came when his family moved to New Delhi in 1974. Rajeev’s father wanted to send his children to the prestigious St Columba’s High School in New Delhi. St Columba’s High School administered a difficult entrance exam to admit students, and Rajeev studied hard the night before taking the exam. Not only did Rajeev pass the exam, he did so well that the principal admitted all three brothers into the school!
Reluctant Computer Scientist
After 11th grade (in the 10+2 program) in 1978, he appeared in JEE earning third place in the northern zone of India. He did not stay at Columba’s to finish the 12th grade instead joined I I T Kanpur, which at that time had just started the undergraduate program in computer science. “I truly wanted to be a mathematician, and my parents were hesitant because how do you make money as a mathematician, how do you support a family. I was basically forced into going into computer science even though I did not want to, but it turned out to be a wonderful surprise that computer science is actually quite mathematical as a field,” recalls Rajeev in an interview.
Even though IIT Kanpur had an outstanding computer science faculty in the late 1970s, formal computer science education at the undergraduate level was still in its infancy in India. Rajeev was a member of the very first cohort of undergraduate computer science students at IIT Kanpur. Rajeev often recalled that IIT Kanpur had attracted an amazing group of people, and there could not have been a better environment for studying computer science in India. As a student, Rajeev was inspired by Professor Kesav Nori, who taught Rajeev’s first class on programming — TA 306: Principles of Programming. Rajeev recalls, “Wonderful thing about Prof. Nori is that he was a very inspiring person. He did more than just teach. He created such a wonderful ecosystem and developed a personal connection with his students.”
Prof. Nori thinks Rajeev gave him more credit than he deserves. It has been 35 years but he is still so enthusiastic talking about Rajeev – the chubby, smart boy. In a recent phone conversation one could sense enthusiasm in his voice when he said, “Rajeev knew that purpose of programing is not just coding; it is to formulate the problem. Rajeev’s thinking was clear; his expression direct. No unnecessary stuff. Rajeev had a knack for creating the most elegant and brief answers to the hardest of programming problems. It was a joy to read his papers.”
Another instructor at IITK recollects, “Anyone who had taught Rajeev could not but be impressed by his class. At the same time, he was not at all competitive — if he did well, which he did, it was because doing well was so natural for him.”
Gautam Bhargava, a classmate of Rajeev at IIT Kanpur remembers him, “As a fun loving, rock-n-rollin’ party guy, a super-smart classmate. Hardly anyone in IIT-days called him Rajeev. To us he was, and still is, Mots, which was not short for Motwani, as you would expect, but rather short for Motwayne! After the younger brother of the movie star John Wayne! But this alleged younger brother of John Wayne was never seen wearing a 10-gallon Stetson; rather he was most often seen in a kurta, jeans, chappals, with a cloth book-bag slung across his shoulder!
Rajeev’s amazing brilliance might lead you to believe that Rajeev was this immensely studious type who spent all his waking hours studying and hitting the books hard. On the contrary, Rajeev was an incredibly fun loving guy always ready for a party! In his dorm room, next to his bed would always be a stack of science-fiction books waiting for eager consumption. Rajeev would spend endless hours solving the hardest crossword puzzles, playing bridge or volleyball, and hanging out with friends — then he would show up for the tests and magically ace them! Now if a course were “crazy hard”, say, like the one on Number Theory, Rajeev would effortlessly breeze through, with amazingly elegant answers to even the toughest of problems. However, if the class were “easy”, Rajeev could easily lose some interest. Rajeev thought time could be better spent listening to music or hanging out at the canteen eating hakka chowmein or anda parathas.”
Gautam continues, “Rajeev was also quite a music lover with a particular fondness for Rock’n’Roll. During IIT years Rajeev was also the “Audio Club Secretary”. This was indeed a prestigious job as the Audio “Secy” controlled the keys to the Rock’n’Roll kingdom – and decided when and where the amps and the speakers and the other equipment would be made available. As usual, Rajeev took great joy in running that club and recruited a bunch of his friends to lug those heavy amps around! When this got too much he decided it was more fun to play the bass … his favorite tune for riffing on bass was “Badge”! Later he started doodling on the keyboard … and as our friend Madhavan recalls, they only played songs in the key of A-minor so Rajeev could just play on the white keys!!! Rajeev could also create musical wonders with another “instrument” – you just had to hear him use a wine glass and a fork to play the tune for the Bollywood hit Chura Liya Hai.”
Rajeev’s undergraduate thesis (joint with Chilukuri K. Mohan and Amitabh Shah; advised by Professor Somenath Biswas) was quite theoretical: “Specification and Verification of Computer Communication Protocols.” This simultaneous interest in theory and programming percolated through Rajeev’s career. Rajeev’s friends recall that in college he was not only brilliant, but also incredibly fun-loving and always ready for a party. There would always be a stack of science-fiction books waiting for eager consumption in his dorm room, and he would spend endless hours solving difficult crossword puzzles, playing bridge or volleyball, and hanging out with friends. He never lost this undergraduate spirit. Through his time at Berkeley and as a faculty member at Stanford, Rajeev approached research and entrepreneurship with joy.
Never do work today that you can defer to tomorrow
Everybody else was coming to the US for PhD or Masters or whatever. Actually Rajeev did not want to come to USA for some unexplainable reasons. He got a job at DCM Data Products because getting visas at that time (1983) was a big problem. He was also interviewed by the top three guys at Wipro – a small enterprise then. The interviewer said we would love to give you a job looking at your track record but isn’t every one with your kind of back ground going to the US on a scholarship? So have you applied to US? Rajeev said, “Yes I have an offer from Berkley.” He asked do you have a scholarship. Rajeev said, “Yes, but I am not sure if I will get a visa.” He got the visa and landed up at Berkley.
In 1983, Rajeev became a PhD student at UC Berkeley. He found Berkley to be a very politically charged university – he would call it the JNU of the US. For 3 years Rajeev had a blast. Did not do any work and fully enjoyed the environment. His advisor was Prof. Richard Karp, who won the Turing award – which is like the Nobel Prize in computer science in 1985-86. When Rajeev had finished those 3 years without publishing any papers, he thought that he was not doing anything and letting this man down. So from then on he worked really hard and was quite productive for the next two years.
In an advanced course on algorithms taught by Prof. Richard Karp the class was asked to solve a homework problem. With a fellow student and Prof. Karp, Rajeev developed this problem into a theory of deferred data structures: data structures that are built-up incrementally. This resulted in Rajeev’s first published paper, and he summarized it jokingly as his philosophy in life, with the words: Never do work today that you can defer to tomorrow.
This is how Rathin Sinha remembers his days with Rajeev at Berkley, “Rajeev was perhaps my closest friend in UC Berkeley. We arrived in the same August of 1983 and I remember spending countless evenings at his Durant apartment going through his full collection of Isaac Asimov, having tea and ending the evening with fried chili and rice. …and then we went our separate ways. I discontinued my PhD program, took up a job, but lived in the neighborhood.
When I got laid off in 1986, he helped me with my resume, in job search, and most importantly kept me motivated. He even gave me his answering machine in case an interviewer calls and I am not there to take the call. He was always smiling. Very mellow and soft spoken. I never saw him getting frustrated or rattled in spite of his heavy work load. He never complained about life, teachers, tests, or grades. He knew how to enjoy himself.
10 years later – one email and we were connected again. His first request to me was to see if I could help a budding entrepreneur who was looking for some technology. So was Rajeev. For me it was like growing up with Greatness. Rajeev was always ready to help. ”
In 1988 Rajeev was about to graduate from Berkley with PhD (His Dissertation: Probabilistic analysis of matching and network flow algorithms) and was wondering what to do next. Go back to India or stay in the US. Again other people made the decisions for him. Don Knuth, one of the founding fathers of computer science, came over to meet Rajeev’s advisor and told him that they wanted to hire someone young for algorithms at Stanford. So Karp suggested Rajeev’s name. Rajeev was then invited by Knuth at Stanford for lunch. Rajeev was wondering why this great man wants to have lunch with him. Anyway, Rajeev went to Stanford and met him at a restaurant near the church at the quad. He then told him to be with Stanford for a year and see if they liked him and vice versa after which if things worked out well they would hire Rajeev.
He was offered a visiting faculty position at Stanford. He did not want that job as he was getting better offers and permanent jobs at other places but since it was an offer by Knuth it was hard to turn down. Rajeev thought, “It’s the like Einstein inviting you to Princeton for a job!” He joined Stanford and taught several courses and had a very good time.
Stanford liked what they saw and he was appointed as tenure-track faculty. Based on his thesis work at Berkeley, Stanford realized that it was getting an extraordinary and promising theoretician in this 27 year old man. However, everyone underestimated the incredible scholar, teacher, advisor, colleague, entrepreneur, and friend that Rajeev would become.
3 – 4 months after his first year at Stanford he got married. Rajeev met his soon-to-be wife Asha Jadeja in May 1989. Asha graduated from the University of Southern California and relocated to the San Francisco Bay area. Rajeev and Asha were married on March 22, 1990 in Delhi. They liked living in Stanford, and decided to stay. Asha started graduate school at UC Berkeley in 1991, studying urban planning and urban transportation, and joined the department of political science at Stanford in 1994. Two daughters were born from their marriage, Naitri (b.1991) and Anya (b.2003). In their tribute to Rajeev, Asha’s younger brothers, Yashwant and Yogi said, “Rajeev, who we called Jamaisaheb, was to the world a famous scientist, entrepreneur, and mentor. For us, he was the rock star of an elder brother that we never had. When our dear sister Asha married Rajeev, we used to pinch ourselves and wondered how we ever got so lucky — that this brilliant, humble, and incredibly handsome man entered our family and immediately became part of a large, cantankerous family — with such ease. In our 20 years of close association, we never saw Rajeev ever lose his cool, was always generous even to people he did not know, and became the darling son of our parents, and all aunts and uncles in the family. He will be with us forever.”
Robots Taught Him Something Special
Rajeev enjoyed teaching at Stanford. Since so many people were retiring or leaving Stanford there were a lot of courses to be taught. Rajeev ended up teaching variety of courses. He even created and offered his own courses such as topography and algorithms and complexity theory. Since he did not know a lot of these areas but he learned a lot by teaching these courses. He did not get enough sleep! He used to say, “I am a perfectionist and I still get nervous to talk before a class even today. I get nervous, what if someone asks me a question and I find myself unable to answer it. So for this reason I always over prepare.”
The nervousness taught him more than what he learned as a student. He landed up working in many different areas and it broadened his thinking, knowledge, and experience. It also helped not get bored. He used to say, “I have tendency to get bored easily and so if I stay in one area for too long I quickly move over to another area. My threshold of working in one particular area is about 5 years.”
Jean Claude Latombe from France, in robotics area, inspired him to see robots from a very different angle. He told Rajeev that there were a lot of algorithms in robotics which are needed to plan the actions of the robot. Robots require very high dimensional planning. It is like having a starting point A and end point B in space, and moving from A to B without being hit by any obstacles. The same task would be easier with 2 points on the table. Rajeev worked on solving robot related problems for 5 years, putting high dimension geometry and randomization together. Seeing the robots move and perform using his algorithms, he realized that he could do something mathematical but practical. He realized that his ideas, his work could have practical implications.
He could now move over from the paper pencil world to the real world. He gave lot of credit to Stanford for creating an environment where people in different areas could work together making the whole greater than the sum of its parts. He spent one third of his time in doing his work in a theoretical and mathematical way and the rest in collaborating with people.
Pfizer wanted to fund research on computational drug design. And while finishing the work on random motion planning in robots he realized that molecules and robots actually behave in a very similar way. His team came up with software based on his theory and they added some new theories. The project was called RAPID (Randomized Pharmacophore Identification for Drug Design). It went very well. Rajeev learnt a lot. He said, “It was an intriguing experience. I had to go back and learn my high school chemistry and biology and the other fun stuff.” The software is being used by Pfizer labs for their drug design.
There wasn’t a startup he didn’t love
Rajeev was fascinated by the transformation of academic ideas into commercial ventures. To quote his friend and coauthor, Madhu Sudan from MIT, “Having worked with Rajeev at an early stage of my career I knew how smart he was, but it really took Stanford to bring out his true talent, which was the ability to recognize the importance of ideas quicker than anyone else around.”
Rajeev was active in the venture industry, and had a reputation of being extremely helpful to entrepreneurs. Rajeev’s students and industry colleagues remember him for his uncanny ability to connect people: he was a catalyst in bringing teams together and getting companies started with an element of inspiration and strategic guidance. Through Deutsche Bank, to which he had been an advisor, he became one of the first investors in PayPal, and Rajeev and Asha started a venture fund called Dot Edu Ventures in 2000. He was also a special advisor to Sequoia Capital, and was active in entrepreneurial student groups at Stanford, including Business Association of Stanford Engineering Students (BASES) and Stanford Student Enterprises.
Sep Kamvar, a student of Rajeev who later became an entrepreneur recalls, “Rajeev had a selfless heart. At one point early on in our company, I had a conversation with somebody who told me he thought our company wouldn’t succeed. Upset, I called Rajeev the next day, met up with him at the University Cafe, and told him about this conversation. After he listened to me rant for half an hour about how I was going to prove this guy wrong, he smiled and simply said: “Yes, you will. That’s why you’re an entrepreneur. Now your challenge is to use that energy to do something good for the world.”
Another former student and now an entrepreneur remarked, “His ability of porting ideas from one to the other was unparalleled.” Jennifer Widom, fellow faculty from Stanford in her tribute to Rajeev said, “In entrepreneurial circles, many call him “the world’s greatest connector.” He had an uncanny ability to recognize that by bringing together certain people, magical things would happen. On a smaller scale, I recently realized that’s exactly what he was doing in our research enterprise. He clearly had a knack for matchmaking. deeply thought-out insights on most any issue, a willingness to help anyone anytime, and an understated but ever-present sense of humor.
We faculty have a tendency to blather on. Rajeev, on the other hand, would sit quietly and then get right to the point. Rajeev left one hole that simply can’t be addressed. He forged a unique connection between the department and the entrepreneurial world—a connection that was broad, deeply technical, and full of integrity. That is something we simply can’t replicate with any other human being known to us.”
Ram Shriram, a family friend remembers, “Rajeev had a photographic memory and seemed to have a limitless capacity to remember people, numbers, events, companies and the like. He was always accessible and approachable. His business acumen rivaled his technical prowess which made him a unique and potent force in the venture community.”
Gaurav Garg noted, “Rajeev was one of those rare people who operated at the highest level of excellence in multiple disciplines. He was exceptionally observant, practical, thoughtful, yet decisive, with an unerring instinct for the right questions or issues around any topic, be it the game of cricket or a startup. I was always impressed by his kindness, fondness, and open door policy with young entrepreneurs.”
Rajeev was a nurturing force for many startups, according to a close friend and GigaOm editor Om Malik. As an investor and advisor, he sat on the boards of Google, Kaboodle, Mimosa Systems, Adchemy, Baynote, Vuclip.
Then Came the World Wide Web
Around this time the world wide web was coming up and Rajeev got sucked into it. Rajeev in his interview with Shivanand Kanavi in 2002 recollects, “There was this guy Jeff Ullman, another one of the grand old men of computer science, who retired this year. He was in the office next to me and was in database. I was talking to him and a new student – Sergey Brin, and I remember at that time we were using Mosaic, and we were looking at the web and I was sitting there and thinking that we could randomize the web in some way because that was going to grow and become big and randomness was going to be important; though I did not know how and why. So I thought about doing random walks on the web and there was this problem of crawling on the web. At that time a search engine called Inktomi had just come out of Berkley. Excite and Yahoo had come out from Stanford so we had seen the first signs of all of this.
I remember going to Inktomi and searching for the word Inktomi and it could not find itself. I don’t know if that is still true but at that time if you went to Inktomi and typed in the word it said no results found. My Godelian past induced me to do these self-referential queries but what amazed me was that this is a simple thing that people screw up on. So in the context of all this I was listening to some people from IBM talk on Data mining and Ullman had just introduced me to some problems in databases. I broke them down with a student and was getting pretty excited about the concept of databases. Ullman took me for this talk on data mining which sounded very interesting to me. So Sergey and Ullman and we decided to do some data mining on the web because it sounded like a nice mix. We then formed this research group called Midas which stood for Mining Data At Stanford. We did a lot of good work on data mining. Then there was this guy called Larry Page who wasn’t really a part of the Midas group but was a friend of Sergey and would show up for these meetings. He was working on this very cool idea of doing random walks on the web.
When I understood what the World Wide Web would look like, I knew I had to somehow force randomness into it. When Larry showed us what he was doing, it was like a complete epiphany, we thought it was absolutely the right thing to do. So Sergey got involved and it became a sub group inside Midas. I was really a good sounding board for Sergey and Larry and I could relate to what they were doing through randomness. They then created a search engine called Backrub. It was running as a search engine from Stanford just like Yahoo ran till the traffic got big and the IT guys sent it off the campus. So these 2 guys would come to the office and say “hey we need some more disc space”. They were completely non respectful of me, which was a wonderful thing. They treated me like an equal. These 21 year old guys were demanding things from me. They needed more disc space because it’s getting bigger. So we need more disc and more money. There are still pictures around the building of how they used to use Legos, to create a box inside which the discs were being put. These discs were those cheap ones bought from the back of a truck and were generating a lot of heat. So they put it in Legos to allow for air circulation.
For me it was a fun research project. We had a lot of ideas which we shared. At some point this thing started getting very serious and we wanted a better name for this than Backrub. So somebody came up with the name Google. Google means 10 raised to the power of 100. It is actually spelt as GOOGOL but somebody miss spelt it and that’s how the search engine got its name. Of course the official story is we deliberately spelt it that way but my guess is we miss spelt it.
So Google started and pretty soon everybody in the world was using Google. The results were much better than all the other search engines going around. It was by word of mouth like I tell my brother to use it, he would tell his wife, wife would tell her kids and so on. At some point these guys said we want to start a company. Everybody said it was not worth it. There were 37 search engines already there. How would you raise money? How would you form the company? But they decided to do it and they did it. There were some big names which supported the company. Andy Bechtolsheim, an ex-Stanford guy who along with Vinod Khosla had founded the Sun Microsystems, put in a little bit of money. They managed to raise a million dollars. They started the company and it was right here in the university avenue. It used to be on my drive home so I used to go and hang out with these guys. It used to be wonderful.
Then they took over the world!
Right now the other search engines don’t even compare and I remember people who I don’t want to name saying why do you need another search engine? Today it is the most used search engine. Feels like I was part of a little bit of history and contributed to that history.”
Sergy Brin and Larry Page founded Google on September 4, 1998.
In his tribute to Rajeev, this is what Sergy Brin said, “Officially, Rajeev was not my advisor, and yet he played just as big a role in my research, education, and professional development. In addition to being a brilliant computer scientist, Rajeev was a very kind and amicable person and his door was always open. No matter what was going on with my life or work, I could always stop by his office for an interesting conversation and a friendly smile.
When my interest turned to data mining, Rajeev helped to coordinate a regular meeting group on the subject. Even though I was just one of hundreds of graduate students in the department, he always made the time and effort to help. Later, when Larry and I began to work together on the research that would lead to Google, Rajeev was there to support us and guide us through challenges, both technical and organizational.
Eventually, as Google emerged from Stanford, Rajeev remained a friend and advisor as he has with many people and startups since. Of all the faculty at Stanford, it is with Rajeev that I have stayed the closest and I will miss him dearly. Yet his legacy and personality live on in the students, projects, and companies he has touched. Today, whenever you use a piece of technology, there is a good chance a little bit of Rajeev Motwani is behind it.
This is how Larry Page remembered him, “Rajeev was a wise theoretician that had the rare knack and desire to turn theory into practical applications. Rajeev was always willing to lend an ear and a brain to anyone, even to me as a confused student. With his always open door and clever insights, Rajeev was instrumental in the early work that led to Google.”
Ron Conway, early stage investor in Google, Ask Jeeves and PayPal, recollects, “Rajeev was always so generous with his time. I was talking last night to Rajeev’s brother, Sanjay, and we concluded that there must have been THREE of him!!! ….one was always at university café and another was always at Stanford and the other one at google!!”
Humble to the Core
David Hornik of August Capital remembered Rajeev as a friend, “It is one thing to be friendly with someone in the business world. It is another thing altogether to consider them a friend. Rajeev genuinely liked people and people genuinely liked him.”
One of his instructors from IITK recalls, “I met him only infrequently since 1983, but I’d get in touch with him whenever any need arose, either for myself or for a student. Rajeev would render his help promptly and he’d answer e-mails without any delay. Only now I realize, reading about him, how busy though he had been all through. I recall that in 1999 June I went to his office to meet him. When I reached, an undergraduate student of his theory of computation course was there to clear some doubts. From the questions the student was asking, it was evident that the student had put in hardly any effort in the course. Most of us would be very impatient with such students. Rajeev, however, was not only patient but also friendly– I still remember how beautifully, without using the whiteboard, Rajeev explained, just through words, why the problem of checking if an input TM would ever make a left move when started on a blank tape is decidable. I could see that the student understood the argument, and he left the office very happy. It was a lesson to me — I realized that people of true excellence have no problems at all in accepting shortcomings in others.”
When Rajeev received Godel Prize in 2001, this is what he so humbly said, “I got the Godel prize for my theoretical work. In science it is said that one guy stands on the shoulders of another and another on his and so on. The guy on top gets the prize. In my case I was on the tip of the pyramid and so got the prize. Everyone forgets the pyramid.”
Rajeev was a school mate of Shahrukh Khan, the Indian film star, at St Columba’s High School in New Delhi and had great admiration for him. In his self-effacing style he would say, ‘that guy (Shahrukh) is brilliant and will be the No.1 in anything he takes up’. Pushing into background his own remarkable intellectual achievements.
Not feeling so lucky!
Prakash Tripathi met Rajeev as a 17 year old at IIT Kanpur campus in 1979. Rajeev spoke to Prakash, ironically, by the IITK poolside.
“Can you jump into the waters?,” Rajeev asked.
“Yes, I can,” Prakash replied. Not because Prakash knew how to swim, but as a fresher in a campus of India’s engineering schools, in a hot summer afternoon in Kanpur, dying in a pool was a far dignified way to reject life’s conditions then to submit and surrender.
Rajeev didn’t tell Prakash whether he could swim. Nor Prakash had the courage to ask. But Rajeev inspired Prakash to convert our lies into truth as a homage to future. First thing Prakash did, after graduating from IITK, was to learn to swim in IIT Delhi pool. Prakash recollects, “It’s traumatic to me today that Rajeev didn’t. That was his failing as a human.”
Rajeev, 47, died June 5, 2009 in the backyard swimming pool of his Atherton home after a party celebrating the end of the school year. Rajeev’s blood alcohol level was .26 when he died, San Mateo County Coroner Robert Foucrault said. The legal limit for operating a motor vehicle is .08. Rajeev did not know how to swim.
On June 6, 2009, day after Rajeev’s death, Deepak Nayar, wrote, “I was one year senior to him at IITK and when he arrived at Berkeley, I picked him from the San Francisco airport and had a run-down room ready for him (next to our run-down room above Pasandrestaurant). Four of us lived above Pasand. He and his success were admired by so many of us. So many of us looked up to him and referred to him as an IIT Baap. We were proud of him. Sad it ended this way. This is not how it is supposed to be!!!!” In the classic American movie, It’s a Wonderful Life, the angel who has been sent to save George Bailey, says: “Strange, isn’t it? Each man’s life touches so many other lives. When he isn’t around he leaves an awful hole, doesn’t he?”
Rajeev’s life touched so many of us. His death has certainly left a big hole.
Every time you Google, you are in touch with Rajeev.
=============================
Rajeev Motwani graduated with BTech in Computer Science from IITK in 1983 and PhD from Berkeley in 1988. He taught at Stanford till his accidental death in 2009. A fun loving highly accomplished theoretician who could find practical application of his ideas was an early investor in several start-ups. He helped Brin and Page in 1998 to found Google. He received Godel Prize in 2001 and Distinguished Alumnus Award from IITK in 2006. A Computer Science Building at IITK in Rajeev’s name is being constructed through generous donation from his family.
This story has been prepared from personal interviews and by cutting and pasting material found through, interestingly, Google search! All credit to original contributors who are too many to be named individually.
Source : http://alumniconnect.wordpress.com/2013/09/10/rajeev-motwani-there-wasnt-a-startup-he-didnt-love/
Monday, July 22, 2013
Optimize the cost of concatenation of all these strings into one big string.
You have n strings with their lengths. You are given an add(string s1,string s2) which would concatenate the string s2 with s1 and return s3. Optimize the cost of concatenation of all these strings into one big string.
Eg: 1,5,2 are the lengths of given strings.
1+5=6
6+2=8
total cost=14 can you Optimize this total cost?
Source : Sent by a reader named rahul.
Eg: 1,5,2 are the lengths of given strings.
1+5=6
6+2=8
total cost=14 can you Optimize this total cost?
Source : Sent by a reader named rahul.
Saturday, June 29, 2013
Print the objects of an array in the order of decreasing frequency. PS: Please make sure order of object should remain same
E.g. if array is of integer is given as 5 2 2 8 5 6 8 8, then we should get 8 8 8 5 5 2 2 6 , here freq. of 5 and 2 are same but 5 comes before 2 in array thus its should come before in output as well.
Here is the working code , let me know if it will fail for any test case and if we can improve it?
/********************************************************Time Complexity : O(n)+O(nlogn)+O(n)=O(nlogn)Space Complexity : Auxallery Space O(2n)= O(n)*********************************************************/Run Here http://ideone.com/FQ65xM
Wednesday, May 22, 2013
Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized
#include<stdio.h>
#define MAX(a,b) ((a>b)?(a):(b))
main()
{
int arr[]={-2, -3, 4, -1, -2, 1, 5, -3};
int len,i;
int max=0;
len = sizeof(arr)/sizeof(arr[0]);
max=arr[0];
int finalmax=0;
int start=0,end=0;
for(i=1;i<len;i++)
{
max = MAX(max+arr[i], arr[i]);
finalmax=MAX(max,finalmax);
}
printf("MAX:%d %d %d \n",finalmax, start ,end);
}
Example if you want to print array http://codepad.org/BhYxSlp4
Subscribe to:
Posts
(
Atom
)
