Microsoft visited our campus on 18th January, 2011 for campus placement. It was offering Internships to the pre-final year students. The whole 3rd year batch of IT & CSE was excited for this opportunity, and were looking forward to it. Finally the day came, and the PPT was scheduled at 12:00 AM, but it got postponed by a hour. We all were waiting for the PPT, but suddenly we got an announcement that the written exam will be held first, and then the PPT.
Written Exam : The papers were distributed, and we were given one and half hours for 11 questions. I'll try to summarize all the questions, as far as I remember.
No. 1) How will you sort an array of integers?
I was not sure what should I write in this, the code or just the algorithm. So I asked the Microsoft person, he said that code will be preferred but they will not look into the syntax. So wrote the code for Quick Sort ( with a time complexity of O(nlogn) ).
But I guess that they intended us to write the various sorting algorithms we will apply depending upon what type of input we get.
No. 2) Write a code to find the character which has the maximum occurrence in a string of ASCII characters, and print that maximum number.
This seemed pretty easy, I didn't think much into the complexity of the algorithm and wrote a O(n^2) algo. They intented us to write an O(n) algo, which was also easy to think. Just take an array of 256 (as there are 256 ASCII characters), and store the frequency of all the characters from input in this array. And then traverse this array, to find the character with maximum frequency.
No. 3) A code was given and we had to write the output.
This was simple, testing the basic concept of pointers. Only one twist was, which some of them got it wrong,
char c[]="TITAN";
void * vp;
vp = (char *)c;
printf("%s", vp+3);
The output will be "AN". Some of them wrote only "A", not looking that there was "%s", which will terminate with '/0'.
No. 4) A flowchart was given, showing steps of how a email is sent, there were some checking that if the email address is valid, and if the mail contained some matter. We had to write some cases to check if the system was working or not.
I had no idea about this, how to approach this problem. So I didn't attempt this question.
No. 5) Write test cases to test a web search engine?
I had no idea about this question. Test a web search engine, it just seemed out of domain.
Question no. 4 and 5 was for the testing people, and I was poor in testing :(
No. 6) There is a very complex software, which is made available for 90% of the time, and the MTBF ( Mean Time Between Failure) is 200 days. Now the company decides to make the software available for 95%, and hence the mean time for testing increases by 5 days, you need to calculate the new MTBF.
I converted the problem to mathematics, and tried to solve it.
No. 7) What is the disk access time?
It was a multiple choice question, and pretty simple for those who have studied OS.
No. 8) Find the next number in the series. 5,6,7,8,8,8,8,8, ?
It seemed tough, I tried to think of something and came up with an answer 9. Later came to know this infact was the correct answer. There were possibly two logic to solve this.
*)The most significant digit after decimal in n/(n+1) , where n>=1.
*)The series was part of the second order Josephus Problem, where every second person is marked, and last person remaining is eliminated. This continues till we have a single person.
No. 9) Given a red coloured cube, the cube is divided such that, after division the one edge of the cube has an edge one-third of the main cube. You need the find the number of cubes with 0 Faces, 1 Faces, 2 Faces, 3 Faces coloured. Why?
They wanted the correct answer and the approach was also important.
*)There will be one cube with 0 faces coloured, the one in the centre.
*)12 cubes with 2 faces coloured, since there are 12 edges in a cube, cube containing those edges will have 2 faces colored.
*)8 cubes with 3 faces coloured, there are 8 corners in a cube.
*)6 cubes with 1 faces colored, as there are 6 faces in a cube.
No. 10) This was a trouble shooting question. Suppose you are watching a video in your desktop, and suddenly the screen goes blank. What are the steps that you will take to find the faulty component?
I thought that there is some fault in hardware, nothing to do with software. Just mentioned some steps that I would take.
No. 11) You had to design a navigating system for a space research organization, that will monitor the take-off and landing of the space ship. Some more requirements were given.
I mentioned some points that came to my mind, mentioned that the system would keep track of the speed. There will be mechanism so that the crew members can interact with each other. Some more points.
Then we attended the PPT, it was a good one. I being a FOSS enthusiast asked then a question, How much is Linux a threat to Windows? , Why does government support FOSS?
After this was the wait for the results, which they said would come the same day. But it came on 19th, at around 12:30 PM. Ankit Arun the TPR of my department, called me up and informed me about the results. And said to come fast.
My interview experience in the next post... :)
Sunday, January 23, 2011
Finally "Passed System Test"
With two consecutive disappointments in SRM 492 and SRM 493, finally I code everything well and everything goes fine.
In SRM 492 the 250 problem seemed easy, I developed the logic pretty fast for this problem. Any line would pass through two points, so I fixed two points and calculated maximum number of trees such, that they were co-linear. I coded everything fine, but was missing a very important point. Double precision, I was working with dividing the value, and then comparing them.
If A and B are two double type variables, and they need to be compared for equality, then if we do
if(A == B) , then we may fail, because of floating point precision. Instead we should do if(abs(A-B) <= 1e-9) I failed system test due to this issue, just adding this condition passed system test in practice room.
In SRM 493 the 250 problem, seemed an easy game theory problem, with the concept that, if the first player can win in first chance, then he can win, and if he cant then if the second player can win in first chance then he is the winner. And in other cases there is a draw. I miss interpreted the question, it said reverse their order. There are some black and white stones suppose "OOOXO", where X represent a black stone and O represent a white stone. Reversing the order meant OOOXO --> OXOOO. I interpreted it as OOOXO --> XXXOX. The test cases were such that by writing the code thinking about this logic, it passed all the cases. I got one more wrong answer.
Finally after two failures SRM 494 the 250 seemed easy, I thought of the logic, and implemented the solution, was making some mistakes, fixed those bugs and the submitted. I wanted to get this right, so was coding the solution very patiently. Finally got it accepted, and increased my rating to 1296.
Now I'll practice more and try to get the 500 pointer. That will be my next target. And become top 50 in India.
In SRM 492 the 250 problem seemed easy, I developed the logic pretty fast for this problem. Any line would pass through two points, so I fixed two points and calculated maximum number of trees such, that they were co-linear. I coded everything fine, but was missing a very important point. Double precision, I was working with dividing the value, and then comparing them.
If A and B are two double type variables, and they need to be compared for equality, then if we do
if(A == B) , then we may fail, because of floating point precision. Instead we should do if(abs(A-B) <= 1e-9) I failed system test due to this issue, just adding this condition passed system test in practice room.
In SRM 493 the 250 problem, seemed an easy game theory problem, with the concept that, if the first player can win in first chance, then he can win, and if he cant then if the second player can win in first chance then he is the winner. And in other cases there is a draw. I miss interpreted the question, it said reverse their order. There are some black and white stones suppose "OOOXO", where X represent a black stone and O represent a white stone. Reversing the order meant OOOXO --> OXOOO. I interpreted it as OOOXO --> XXXOX. The test cases were such that by writing the code thinking about this logic, it passed all the cases. I got one more wrong answer.
Finally after two failures SRM 494 the 250 seemed easy, I thought of the logic, and implemented the solution, was making some mistakes, fixed those bugs and the submitted. I wanted to get this right, so was coding the solution very patiently. Finally got it accepted, and increased my rating to 1296.
Now I'll practice more and try to get the 500 pointer. That will be my next target. And become top 50 in India.
Thursday, October 28, 2010
Failed system test
26th October, 2010, my last day of stay in Siliguri(My home town) in the durga puja vacations. This was the second consecutive instance when there was a SRM on the same evening when I was to board a train. Fortunately both time my train was late (courtsey to Indian railways :P) and I was able to compete.
After my good performance in the last SRM I was again back to div-1. The first problem was of 300 points so it was harder than normal level 1 problem. It took me 30 mins to code I tried my best to think of all the cases.
The Question is as follows :-
Given two integer values start and terminate, you are required to perform certain operations on the start value. The operations were simple "*, +, /, -". You need to take the start value as the two operands and also store the result in the start value. If start=5, and you perform a "*" operation, then start=start*start, start becomes 25. You need to perform minimum number of operations to reach the terminating value, and concatenate the operators. If the minimum number of operations is same then return the lexicographically first string.
I thought and first thing that came in my mind was BFS. I coded a nice BFS solution, and then I thought that using the divide operation we can make the start value 1 and then we could reach the terminating value. So i applied BFS twice with the given start value and start value as 1. Everything seemed fine. I hoped it to pass the system test.
I had missed one critical thing, I was returning the answer if there was any with the given start value, but the answer with start value as 1 and "/" operation added to the beginning could be the answer with less number of operations. This cost me a couple of rating points, and my hope of entering top 100 in India :( :(. Its always better luck next time. I am still in div-1 :)
After my good performance in the last SRM I was again back to div-1. The first problem was of 300 points so it was harder than normal level 1 problem. It took me 30 mins to code I tried my best to think of all the cases.
The Question is as follows :-
Given two integer values start and terminate, you are required to perform certain operations on the start value. The operations were simple "*, +, /, -". You need to take the start value as the two operands and also store the result in the start value. If start=5, and you perform a "*" operation, then start=start*start, start becomes 25. You need to perform minimum number of operations to reach the terminating value, and concatenate the operators. If the minimum number of operations is same then return the lexicographically first string.
I thought and first thing that came in my mind was BFS. I coded a nice BFS solution, and then I thought that using the divide operation we can make the start value 1 and then we could reach the terminating value. So i applied BFS twice with the given start value and start value as 1. Everything seemed fine. I hoped it to pass the system test.
I had missed one critical thing, I was returning the answer if there was any with the given start value, but the answer with start value as 1 and "/" operation added to the beginning could be the answer with less number of operations. This cost me a couple of rating points, and my hope of entering top 100 in India :( :(. Its always better luck next time. I am still in div-1 :)
Saturday, August 28, 2010
My First Blog Post
I waited long for my first post, here it comes. It has to be about my passion "CODING".
I always liked programming back from my school days, but never got a platform where I could develope my coding skills, until I came to NIT Dgp.
I came to know about two platforms where I could develope my coding skills, http://topcoder.com and http://spoj.pl . The first year passed by without me being much involved in programming, apart from participating in junior codecracker organised by Linux Users' Group of my college.
In the winter break I took programming seriously and started participating in Topcoder. Initially in the SRMs I did not perform well, many a times I cracked the logic but due to some bug in my code it failed the system tests. It was a very slow start.
I participated in 15 SRMs in Topcoder and made my journey from grey to green. Then it was the 16th SRM in which I gave my best performance I was ranked 28th overall in div-2 and advanced to div-1. So the journey was from grey to green to blue. It feels good to be blue for the first time and be in div-1.
Theres a long and tough jounrney to make now from blue to yellow to "red", and a lot of effort to be put to do that. Hoping to perform well in the coming SRMs.
I always liked programming back from my school days, but never got a platform where I could develope my coding skills, until I came to NIT Dgp.
I came to know about two platforms where I could develope my coding skills, http://topcoder.com and http://spoj.pl . The first year passed by without me being much involved in programming, apart from participating in junior codecracker organised by Linux Users' Group of my college.
In the winter break I took programming seriously and started participating in Topcoder. Initially in the SRMs I did not perform well, many a times I cracked the logic but due to some bug in my code it failed the system tests. It was a very slow start.
I participated in 15 SRMs in Topcoder and made my journey from grey to green. Then it was the 16th SRM in which I gave my best performance I was ranked 28th overall in div-2 and advanced to div-1. So the journey was from grey to green to blue. It feels good to be blue for the first time and be in div-1.
Theres a long and tough jounrney to make now from blue to yellow to "red", and a lot of effort to be put to do that. Hoping to perform well in the coming SRMs.
Subscribe to:
Posts (Atom)