Microsoft Placement Interview

After the failed attempt at trying to land a summer internship at Microsoft, I was back with hopes of a job now. Here is how the entire process went –

Day 1

On August 4, we had our MCQ round in the morning. As the last year, it was hosted on cocubes.com and we were given 30 minutes to answer 15 questions. Majority of the questions were based on pointers. The results of the first round were announced by 4 p.m and we had our second round, online coding, at 5. There were different sets of questions. The two questions that I got were –

1. Maximise the value of an array
Two arrays, num and rep were passed to a function. num was to be treated as a number, and we had to maximise its value by replacing its digits with the digits in rep.
E.g: if num={3,0,6,5} and rep={7,9,2,4}, the value of num can be maximised by replacing 3 and 0 with 9 nd 7 to form 9765.

2. From the leaf nodes of a binary tree, form a singly linked list going from the leftmost leaf node to the rightmost leaf node.

Day 2

After this round, I was shortlisted for both MSIDC and MSIT on August 7. We then had the group fly round of MSIDC at 1 p.m. There were 2 questions, which we hd to code using pen and paper.

1. Given a singly linked list representing a number in forward direction, add 1 to the number.
E.g: If the list is 4->3->1->5, the output produced should be 4->3->1->6.

2. Given 2 arrays in sorted order which can contain repeated elements, find the kth smallest element.
E.g: arr1={1,3,3,8} and arr2={4,5,7} if k=3 the output should be 4.

Later the same day

After making us wait till 7 p.m. a few of us who had not had their interviews for MSIDC were told to go back s IDC was closed now. Since my name was in the list for MSIT, I went for its group fly round. The 2 questions asked were –

1. A frog can move 1″ or jump 2″. A pond is 20″ away. Print all possible combintions of the moves he may make to get to the pond.

2. Print the given pattern using only 1 loop –

I qualified the group fly and went on for my technical interview. This interview went very well. I was asked a lot of questions based on the projects mentioned in my resume. So here’s a tip – always be thorough with what you’ve mentioned in your resume. If you’ve mentioned a project on web dev and haven’t been in touch with it for a while, go through your project again, or remove it from your resume.
That was it for the day. The rest of the interview would continue the next day.

Day 3

I was one of the 8 people who were directly sent for the final round, the AA interview after last day’s technical interview. Around 12 people were waiting for a second tech interview. I was extremely nervous bout the AA interview since I had also reached it lst time, but couldn’t get through it. The AA, or As Appropriate interview is a very semi-formal interview with the General Manager who has casual talk with you about your summer projects and internships, asks HR questions like “Why do you want to work for Microsoft?”, “Where do you see yourself in 5 years?” etc.
So if you reach this round, congratulations. You are among some of the top students in your college. What are the appropriate answers in this round, has to be tailored by you. This is it, the final bang. Do practice HR questions, think about your strengths and weaknesses and don’t give highly ambitious answers. Do a reality check, stay grounded and answer appropriately.
All the best!

I/O Questions #3

This is going to be a very short post, with just 1 question I thought I should address. Arrays and their initializations have long been a source for confusion. One important thing to know is –

1. Determine the o/p-

int main{
    int a[5]={2,3};
    cout<<a[2]<<a[3]<<a[4];
    return 0;
}

o/p: 000

Explaination: When an array is partially initialized, the rest of its elements are automtically initialized to 0.

I/O QUestions #2

I came across an interesting question today, and realized a lot of people make mistakes in switch statements. So here are 2 variations of a normal switch i/o question –

1. Determine the o/p:

#include<iostream>
using namespace std;

int main(){
     int i=3;
     switch(i){
        cout<<i<<endl;
case 1: cout<<"one\n"; break;
case 2: cout<<"two\n"; break;
case 3: cout<<"three\n"; break;
}
return 0;
}

o/p: three

Explaination: The switch statements does not execute any statements outside the ‘case’ and ‘default’ blocks. Hence, the statement cout<<i<<endl; will not be executed. Also, note that the default block is optional.

2. Determine the o/p:

#include<iostream>
using namespace std;

int main(){
    int i=1;
    switch(i){
        default: cout<<", Harry!\n";
        case 1: cout<<"Yer ";
        case 2: cout<<"a ";
        case 3: cout<<"wizard ";
    }
    return 0;
}

o/p: Yer a wizard

Explaination: On fall through (execution of subsequent statements on absence of a break), the default statement is not executed. It is only executed when the all of the other cases fail to match. Also, placing the default statement at the beginning, or any other place in the block will not make a difference. Default will not be executed before the other cases are checked.

I/O Questions #1

1. What is the output of the following:

int main(){
     static int i=5; 
     if(--i){
        main();
        cout<<i;
    }
    return 0;
}

o/p: 0000

Explaination: Since i is static, its value is shared between function calls, even in recursion. So, when the last main returns, the value of i has become 0 and will be printed all 4 times.

2. What is the output of the following:

#include <stdio.h>
int a, b, c = 0;
void prtFun (void);
int main ()
{
    static int a = 1; /* line 1 */
    prtFun();
    a += 1;
    prtFun();
    printf ( "\n %d %d " , a, b) ;
}

void prtFun (void)
{
    static int a = 2; /* line 2 */
    int b = 1;
    a += ++b;
    printf (" \n %d %d " , a, b);
}

o/p: 4 2
6 2
2 0

Explaination: The local variables hide the global variables. Also, the static keyword preserves the value of the variable only between tha calls to that function. So the static variable in prtFun and in main can and will hold different values.

3. What is the output of the following:

#include <stdio.h>
int main(void)
{
    int i = 10;
    const int *ptr = &i;
    *ptr = 100;
    printf("i = %d\n", i);
    return 0;
}

o/p: Compiler error

Explaination: const int *ptr is apointer to a constant. So, ptr cannot be used to change the value it points to.

Source: GeeksforGeeks

Questions in C/C++ #2

Another interview favorite is: Determine if a given number is a power of 2.

There is a very simple trick to solve this question.

Consider n = 4. In binary representation, n = 100.
n-1 = 3, in binary will be 011.
So, if a number is a power of two, subtracting 1 from it will result in the bits being toggles. So, performing a bitwise AND operation will result in 0. This will hold true for all numbers that are a power of 2.
Also, the number must be greater than 0.

So, a simple, short code for this problem is –

bool powOfTwo(int n){
if(n>0){
return !(n & (n-1));
}
else return false;
}

Can you write a C program without main()?

Among the very first things we learn when we begin programming, is that the function main() is where our code begins its execution. Without it, there will be no way to tell the OS where the program execution must start from. So is it really possible to do away with this crucial function?
Of course not! A program can not be executed without main(). However, it can be made to look like it does not use main. The gears of the I-want-to-complicate-things-a-little-this-is-too-simple brain spring into action.

The first way that I found was using the preprocessor #define to rename main. The code goes like this –
#include <stdio.h>
#define start main

int start()
{
printf(“I can see main right there!\n”);
return 0;
}

Frankly, I found this solution very irritating. I am a programmer. I can see right there that you have just renamed main to start. I don’t even have to make an effort, it’s right in front of me!

But after a little more digging, I found a solution that satisfied me.

#include <stdio.h>
#define decode(s,t,u,m,p,e,d) m##s##u##t
#define begin decode(a,n,i,m,a,t,e)

int begin()
{
printf(“Okay. This is more satisfying.\n”);
return 0;
}

I look at the program, I see what you did there, but I’m satisfied because I don’t see a main. Anyone who is not aware of what ## does will not know that this is just a fancy way of writing the code in the first example.

So how does this work?
The ## operator is called the token pasting or token merging operator. By using this, one can merge two or more tokens. So when I write, say f##o##o##l##i##n##g##y##o##u, I am writing foolingyou in a less evident manner.

In the above code, the second preprocessor, #define decode(s,t,u,m,p,e,d) m##s##u##t is forming msut, which is basically merging the 4th, 1st,3rd and 2nd arguments to decode.
Hence, the third preprocessor, #define begin decode(a,n,i,m,a,t,e) will use the macro decode to form main by merging its 4th, 1st,3rd and 2nd arguments.

So, when we type int begin(), we are indirectly typing int main().

And voila!

Source: www.gohacking.com

Questions in C/C++ #1

There are a few common questions which may be asked in interviews for your Computer Society in college, or a company! So if have an interview lined up, go through these. All the best!

1. Write a program to print “Hello world!” without using a single semicolon.

void main()
{
if(printf(“Hello world!\n”))
{}
}

Explanation: The printf() function returns the number of characters it has printed. Since that is an integer, it can be used in combination with the if statement to printf the desired result without using a semicolon.

2. Swap 2 integers without using a temporary variable.

A common solution is,

a = a+b
b = a-b
a = a-b

Example: Let a=5 and b=7.
On a=a+b, a=12 and b=7.
On b=a-b, a=12 and b=5.
On a=a-b, a=7 and b=5.
Both the numbers have been swapped.

Copy contents of a file in reverse order using lseek()

The following is a C code for copying the contents of one file in reverse order in another file. It is fairly easy, once you understand how lseek works.

#include <stdio.h>
#include <stdlib.h>
#include<fcntl.h>

char buffer[1];

int main()
{
int fd1,fd2; //the two file descriptors
char file1[50],file2[50];
printf(“Enter file to reverse: “);
gets(file1); //Input path of first file
if((fd1=open(file1,O_RDONLY))==-1) //open will return -1 if there is an error
{
printf(“File does not exist\n”);
return -1;
}
printf(“Enter file to output in: “);
gets(file2); //Input path of second file
fd2=open(file2,O_RDWR | O_CREAT,0777); // will open file in read-write mode or create it if it does not exist
int size=lseek(fd1,0,SEEK_END); //to find the size of the file
printf(“%d”,size);
int i;
for(i=1;i<=size;i++)
{
if((lseek(fd1,-i,SEEK_END))==-1) //will point to position -i from the end of the file fd1
{
printf(“%s\n”,strerror(errno));
}
int rd=read(fd1,buffer,1); //read one char at a time from file1 (use fd1)
int wr=write(fd2,buffer,1); //write one char at a time to file2 (use fd2)
if(wr==0)
{
printf(“Did not write to file\n”);
return -1;
}
}
return 0;
}

Disclaimer: This code is inefficient and is meant for homework assignments and lab excercises. It cannot be used in real world problem since reading and writing chars one at a time is a wasteful approach.

The Travelling Salesman Problem (Exhaustive Approach)

For those of you who don’t know what this problem is about, here is the problem statement:
You are given a list of cities and the distances between all connected cities. Find the shortest path that visits each city exactly once and returns to the origin city.

To approach this problem using exhaustive search, we need all permutations of the cities and find out which path through them is the shortest. Here is my approach, using the next_permutation() function:

#include <iostream>
#include<algorithm>
using namespace std;

char nodes[]={‘A’,’B’,’C’,’D’,’E’}; //names of cities
int node[]={0,1,2,3,4,5}; //to permute numbers
int cities=5; //change this number for more or less cities
int distance_mat[10][10]; // the distance matrix from city[i] to city[j]

int min_cost=10000; //arbitrary large value which will be replaced
char min_path[6];

//take distance input in the form of a matrix

void createGraph()
{
cout<<“\tA\tB\tC\tD\tE\n”;
for(int i=0;i<cities;i++)
{
cout<<nodes[i]<<“\t”;
for(int j=0;j<cities;j++)
{
cin>>distance_mat[i][j];
}
}
}

int shortest(int a,int b) //find a path from the last visited city to the origin city
{
static int cost=0;
if(distance_mat[a][b]!=0)
return distance_mat[a][b];

for(int j=0;j<cities;j++)
if(distance_mat[a][j]!=0)
return cost+=distance_mat[a][j]+shortest(j,b);
}

void findcost() //calculate cost/distance
{
int cost=0,cnt=1;
char path[6];
path[0]=nodes[node[0]];
for(int i=0,j=1;j<cities;i++,j++)
{
if(distance_mat[node[i]][node[j]]!=0)
{
path[cnt++]=nodes[node[j]];
cost+=distance_mat[node[i]][node[j]];
}
}
if(cnt<cities)
return;
cost+=shortest(node[cities-1],node[0]);
path[cnt++]=nodes[node[0]];

if(cost<min_cost)
{
min_cost=cost;
for(int i=0;i<cities+1;i++)
{
min_path[i]=path[i];
}
}
}

int main()
{

cout<<“Create Graph\n\n”;

createGraph();
do{
findcost();
}while(next_permutation(node,node+cities)); //will generate all permutations. In-built function in algorithm.h

cout<<“Minimum distance: “<<min_cost<<endl;
cout<<“Path Followed: “;
for(int i=0;i<cities+1;i++)
{
cout<<min_path[i]<<“\t”;
}
cout<<endl;
return 0;
}

The Microsoft Internship Interview

Our college conducted a Microsoft Internship test for 3rd year students, and the placement test for final year students. It was a 3-day process, at the end of which, 19 students were selected in total, for the internship and final placement.

Day 1

On the first morning, we had our first online round. It consisted of 15 MCQs which we had to attempt in a time duration of half an hour. There was no negative marking. For this round, they had a pool of Aptitude, Logical reasoning and C Programming questions, mostly on pointers. The assessment was hosted on cocubes.com and each student got any 15 questions from the pool.
My questions were all on pointers, except for one, which was logical. The questions were pretty easy, and intelligent guessing did the trick for some.

Results for the first round came out the same afternoon. Out of 350 or so students, 101 had been shortlisted for the next round, which was to be held at 4.45 pm on the same day.

The second round constituted of 2 coding questions and a time of 1 hour 5 minutes was given to us. The questions weren’t very tough. They just needed a little bit of logic.
We had an option to code in either C, C++ or Java.
1. You are given a sorted array of strings, interspersed with empty strings. Find a given string in this array.
(Since time and space complexity also determine the results for this round, try not to use linear search. Anyone can find a given string from an array using linear search.)

2. You are given an array of integers. The numbers are repeated an odd number of times, except for 3 of them, which appear an even number of times. Print out these 3 numbers n the order of their occurrence from the 0th index.

During this round, they also asked to give a preference between MSIT and MSIDC. Make sure you search about these two departments before the test and give your preference accordingly.

Day 2

After a day, we had a seminar by Microsoft employees in which they gave us an insight into life at Microsoft. After this, they announced the list of shortlisted students for the third round. 29 people were selected for MSIDC, and 14 for MSIT, including me.
The students shortlisted for MSIDC were asked to stay back. They had a group interview/ discussion with the MS representatives. They were asked questions based on Graphs – shortest path, diameter etc. The list of 10 shortlisted students came out the very same night.

The students who were shortlisted for MSIT were asked to come for their Technical Interviews on the next day.

Day 3

This was it. The day at the end of which we would know if we were capable enough to join the world’s largest software company.

First, we had a 1 hour one-on-one Technical interview. I was asked questions from OOP, Data Structures and RDBMS. These are a few which i remember:
1. Given a string, output the letters which have been repeated, and how many times.
2. Design a class Car, using all OOP features.
3. Reverse a linked list, with a header node.
4. Swap two numbers without using any additional variable.
5. Given a database of students, output the details of the student with the 9th highest GPA.
There were some theoretical questions, like What is indexing? , What is pinging? , Why do we need an IP address?

The interviewer was very impressed with me and i was pushed to the next round. This was the AA (as appropriate) interview, in which the General Manager interviews you to determine if you are suitable to be a Microsoft hire.
In this round, he asked very general questions. He tested my communication skills and gave me a few scenarios. All you need to do to clear this round, is be confident, and yourself. Unfortunately, I didn’t come out very well in this round. So I couldn’t get the internship. Though you never actually know what went wrong in a general behavioral interview, below are a few tips to do well.

Tips:

1. Know your strengths and weaknesses.

This is a very common interview question. Directly, or indirectly, the interviewer will ask you your positives and negatives to see how you perceive yourself. Make sure you introspect and give genuine points. Don’t make things up to yourself look good. It’s not difficult to call bluff on it.

2. Know exactly why you want to join the company

Another common question. Don’t assume you can tell them why at that moment. In there, you might be nervous. Clear these points in your mind before the interview itself.

3. Know your projects inside out.

Make sure to go through your project reports before the interview and refresh your memory. Think about what you loved most about the project, and what you found the most challenging.

To everyone who is attempting the internship test, All The Best! This is wonderful opportunity. Give it your best.