Microsoft Freshers Latest Interview Questions Papers

There will be 3 interviews:- The first two are compulsory, if you do well in these, you will be called for the 3rd one.

First Interview:

1. If the Fibonacci series is 1,2,3,5,8,13,..... then 10 can be written as 8 + 2 ==> 10010 and 17 can be written as 13 + 3 + 1 ==> 100101. Got it??
   The Question was, given n, I need to get all possible representations of n in Fibonacci Binary Number System.
   as 10 = 8 + 2 ==> 10010
   also 10 = 5 + 3 + 2 ==> 1110
   
2. I have a file in which there are supposed to be 4 billion numbers, starting from 1 to 4,000,000,000 but unfortunately one number is missing,i.e there are only 3,999,999,999 numbers, I need to find the missing number. In this question he asked me concepts like fopen, what will be the size of such a file and how such a big file will get loaded into RAM,and also concepts of logical/virtual/physical memory and memory paging.
   
3. I have an array consisting of 2n+1 elements. n elements in it are married, i.e they occur twice in the array, however there is one element
   which only appears once in the array. I need to find that number in a single pass using constant memory. {assume all are positive numbers}
   
   Eg :- 3 4 1 3 1 7 2 2 4
   Ans:- 7
   
4. There is a temple, whose premises have a garden and a pond. It has 4 idols, each of Ram, Shiv, Vishnu and Durga. The priest plucks x flowers from the garden and places them in the pond. The number of flowers
   doubles up, and he picks y flowers out of them and goes to offer it to Lord Ram. By the time he reaches to the pond, he finds the remaining flowers also have doubled up in the meantime, so he again picks up y from
   the pond and goes to Lord Shiv.This process is repeated till all the Gods have y flowers offered to them, such that in the end no flower is left in the pond. Find x and y.
   

Second Interview :

 

1. Asked About My Btech Final year Project. Design your own compiler that does trace back optimization.Give hypothetical test cases for your compiler.
   
2. There is a central server and some clients connected to it. All the changes made to data occur at the server, and all the clients have just read access.
   You have two options:-
   1. Push :- The server keeps pushing data to the clients.
   2. Pull :- The client keeps requesting the server to send data.
   
   What are the advantages and disadvantages of each type.Design a system which uses both the push as well as pull strategy.
   
3. Implement atof function.Write solid secure code only.
   

Third Interview:

 

1. a) What is your CGPA?
   
   b )What are your immediate goals?
   
   c) What are your long term goals?
   
   d) And some more questions on academics.
   
2. Find the first unrepeated character in a string of English language in O(n).
   
3. Simple questions on Probability.
   
4. Difference between a 32-bit OS and a 64-bit OS. Some questions on address space and fetch cycles/ Instruction Set of a processor.
   

technical questions with answers, explantions

A normal search across a BST (Binary Search Tree) would look like this

bool BinaryTree::Search (int data )

{

Node *current = this->root;

 

 

while ( current != NULL )

{

if (current->data < data)

{

current = current->left;

}

else if (current->data > data)

{

current = current->right;

}

else if ( current->data == data )

{

return true;

}

}

 

 

return false;

}

You keep going down the tree, until you find a node whose value is equal to one you are looking for, or you bail out when you hit a leaf (NULL) node. If you look at the number of statements, there is one conditional check on the while, and an average of 1.5 conditional checks inside the loop. That makes it a total of 2.5 checks every iteration. On a tree with a 1000 nodes, that's 2500 checks.

Let's see how we can improve this. I am using the sentinel node technique for this purpose. In this case static Node * Leaf;

This is how the search will look like

 

static Node* Leaf;

 

 

bool BinaryTree::Search (int data )

{

Node *current = this->root;

 

 

Leaf->data = data;

 

while ( current->data != lead->data )

{

if (current->data < data)

{

current = current->left;

}

else

{

current = current->right;

}

}

 

return (current != Leaf);

 

 

}

The sentinel is a static node, and while building the tree, you point all the leaf nodes to this sentinel node instead of NULL. Before you start the search, you set the value of the sentinel node to the data you are searching for. This way you are guaranteed to get a hit. You just need to do one extra check at the end to see if the Hit node was a Node in the tree or the sentinel node. If you look at the number of conditional statements in the loop, there is one in the while statement and one inside the loop, that makes it 2 searches every iteration. You just saved half a conditional statement. Don't underestimate this improvement. E.g. In a 1000 iteration loop you saved 500 checks.

This is extremely useful with large trees or when you are searching the tree several times or any other scenario where this call happens in a hot section.

Technical questions with answers, explanations c c++ java

void swap(int &i, int &j)

{

   int temp = i;

   i = j;

   j = temp;

}

Instead of writing a separate function for each data type, you could write a MACRO or templatize the function.

Swapping without using a temporary variable is an age old trick and there are a few ways to do this. You could use of the basic arithmetic operations like +,-,/,*

1: void swap(int &i, int &j)

2: {

3:     i=i+j;

4:     j=i-j;

5:     i=i-j;

6: }

The technique involves storing the sum of variables in one of them and then extracting it back by subtracting the other number. There are different variants to this technique. E.g, instead of starting by storing the sum, you could store the difference, product or the quotient. The last two could lead you to round-off and integer division errors. However all of them have one fundamental flaw. Its in line 3, and the issue is that this could lead to an overflow error.

This is another technique the gets you around these issues; the XOR Swapping technique

void swap(int &i, int &j)

{

     i = i ^ j;

     j = j ^ i;

     i = i ^ j;

}

This is an elegant technique and should work well with any primitive data type and you could write a simple MACRO like

 

 

define SWAP(i, j) (((i) ^= (j)), ((j) ^= (i)), ((i) ^= (j)))

 

 

Although, the XOR technique gets rid of the other issues like overflow and round off errors that we encountered in the previous technique, the lands in into yet another issues; This does not work when you try to swap the same memory location. However if can get around this by a simple 'if' check or a more elegant OR check like

 

 

define SWAP(i, j) ( (i==j) || ((i) ^= (j)), ((j) ^= (i)), ((i) ^= (j)))

 

 

The first OR condition (i == j) is checked before the actual SWAP. (You do not need a SWAP if the both memory locations hold the same data) without additional space

Technical Interview Questions Exception Handling in Constructors

Constructors do not have return type and so they cannot return error codes. How are errors or exceptions handled in constructors? What if the calls that you make in the constructor can actually throw exceptions? How do you let the caller know something bad happened in a constructor?

There are a few ways to do robust error/exception handling in constructors

1. Do as little in the constructor has you can. Then provide an Init() function in the constructor, which does the normal initialization stuff. The user can then call this function after creating an object. The problem here is, its up to the user to actually call the Init() function. The user could potentially miss this step, making this method error prone. However, there are a lot of places where this methodology is used. You are trying to eliminate error handling in the constructor by using this method
   
2. Another way to do this is by putting the object in a Zombie state. This is one approach you can take especially if you do not have the option of using exceptions. When you go with this option, you will also to do provide a function that will check the state of the object after construction. The downsides to this option is that, its up to the user to do these checks and the users will need to do this every time one attempts to create an object. It's usually always better and cleaner to throw an exception instead. Use the Zombie option as a last resort.
   
3. The downsides to the above methods can be reduced by making the constructor private or protected, expose a CreateInstance() public method, and do all the error handling here rather than leave it to the user. But sometimes, its not possible to handle all the error conditions in a generic manner and you will need to throw an exception.
   
4. If an exception is thrown in the constructor, the destructor will not get called. So you need to handle and clean up as much as you can before you leave the constructor. The best way to do this is using the "resource allocation is initialization" technique. I will cover this topic separately in a future post. But the basic idea is to assign resource allocation and cleanup to other objects. Basically, you are trying to get allocation out of the way (indirect) so that you don't have to do it explicitly. When you don't allocate something directly, you don't have to release it either because it will be done by the component or class who deals with it. E.g. If you need to allocate some memory or open up a file, You can use smart objects (smart pointer, auto_ptr, smart file handlers etc..) instead of calling new or fopen directly. When you do this, and if an exception is thrown in your constructor, the smart objects will automatically release the resources it acquired, as the stack unwinds. If you do not use the "resource allocation is initialization" technique, the user will need to wrap the statements in try/catch block and rethrow after cleaning up the mess, something like what the finally block does in Java or C#. Although this works in theory, it's up to the user to make this work and it also always a source of errors and bugs (esp. memory and handle leaks) and is messy
   

As you have seen, there is no "one size fits all" rule to do error/exception handling in constructors. I have listed the most commonly used methods and one of these should work most of the time.

Technical Interview Questions C++

As the name suggests, a copy constructor is called whenever an object is copied. This happens in the following cases:

• When an object is create from another object during initialization (Class a = b)
  
• When an object is created from another object as a parameter to a constructor (Class a(b))
  
• When an object is passed by value as an argument to a function (function(Class a))
  
• When an object is return from a function (Class a; … return a;)
  
• When an exception is thrown using this object type (Class a; …. throw a;)
  

Whenever an object copying scenario like the ones above is encountered, the copy constructor is invoked. A copy constructor can be either user defined or compiler defined. If the user does not define a copy constructor, then the default compiler defined copy constructor will be invoked during object copy scenarios. The default copy constructor is a bit-by-bit (member wise) copy. But often you will encounter situations where this is not desirable since this is just a shallow copy and sometimes you do not want an exact copy or you may want to do some custom resource management. 

 

Class t1;

Class t2=t1; // Copy Constructor is invoked

Class t3;

t3=t1; // Assignment Operator is invoked

 

In the Code snippet above, the constructor is invoked twice, during the creation of objects t1 and t3. (Creation of t2 invokes the copy constructor). The destructor is invoked 3 times though. In cases like these, if the constructor allocates memory and the destructor frees it, you will see the t2's destructor will try to delete already deleted memory, if t1 is destroyed before t2 or vice-versa. Meaning, you are hosed. To prevent this, a user defined copy constructor needs to be provided. which doesn't do a simple bit-by-bit but rather assigns memory specifically for the object and does a deep copy if required.

To define a copy constructor for a class T, a constructor of the following format needs to be defined.

 

Class T

{

…

T(const T& t)

…

}

 

You need a reference because if it were T(T t), it would end in a infinite recursion. (Was that an oxymoron?). const because you are not changing the object in the constructor, you are just copying its contents

Some Rules of Thumb:

• Don't write a copy constructor if a bit-by-bit copy works for the class
  
• If you defined your own copy constructor, it probably because you needed a deep copy or some special resource management, in which case, you will need to release these resources at the end, which means you probably need to define a destructor and  you may also want to think of overloading the assignment operator (beware of self-assignment)
  

Data Structures and Programming - DSPM Paper 1

Data Structures and Programming Methodology
(B.Tech 3rd Semester, 2122)
Time : 3 Hours Maximum Marks : 60
NOTE:- This paper consist of Three Sections. Section A is compulsory. Do any Four questions from
Section B and any two questions from Section C

Section-A Marks : 20
1(a) Define the term Data Structure.
(b) What is recursion and advantages ?
(c) Define full tree and complete tree.
(d) Write infix equvilent of :
abc * c/-d+
(e) What is Priority Queue ?
(f) Whay do we go for dynamic data storage ?
(g) What is the criteria behind the design of hash function ?
(h) Name various application of Stacks and Queues.
(i) What are the various ways to store the Graphs in Memory ?
(j) Whay are the advantages of circular link list ?
Section-B Marks:5 Each
2. Write an algrothim to check whether a given string is palindrom or not using stacks.
3. in what way, double linked listis better than single link list. Give example.
4. Construct a binary tree whose nodes are in two orders as under :
inorder : B, C, E, D, F, A, G, H
Preorder : A, B, C, D, E, F, G, H
5. Compare the time complexity of various sorting algrothims (Best and Worst case).
6. Write a non-recursive algrothim to insert a node into a single-lin list.
Section-C Marks : 10 Each
7.(a) What is Graph ? Can a tree can be Graph ? Name various applications of Graph.
(b) Write a function to delete a node from a binary search tree.
8.(a) An array contains 25 elements. Write an algo to print all pirs whose sum is 20.
(b) Define Garbage Collection. When it takes place and how ?
9. Write short notes on the following :
(a) Operations on sets
(b) Methods for Hash functions

Data Structures and Programming

DATA STRUCTURES & PROGRAMMING METHODOLOGY (CS-207)
Time: 03 Hours Maximum Marks: 60
Instruction to Candidates:
1) Section - A is compulsory.
2) Attempt any Four questions from Section - B.
3) Attempt any Two questions from Section - C.
Section - A
Ql)

a)What is Non -Linear Data structure?
b)What is Sorting and Merging?
c)Explain operations on Data Structures.
d)Write a short note on Linear search.
e)Explain about Binary tree.
f)Explain Representing the graph.
g)Explain Depth - First search.
h)Define Stack.
i)Write a short note on Bubble sort.
j)What are the Advantages of Data structure?
Section - B

Q2) What is recursion? What are the Advantages of recursion? Write a procedure
to implement. Quick sort using recursion?
Q3) Write a program for the Evolution of post fix expression.
Q4) What is tree? Explain the type of Branches of a tree.
Q5) What is hashing? Explain various Hashing Techniques.
Q6) Explain the concept of stack along with it's Applications.
Section - C

Q7) What is linked list? Write an Algorithm to insist, delete and modify operations
on Double linked list.
Q8) What is binary tree? Write a program to create a tree and display it in (a) in -order
(b) pre-order
( c ) post-order.
Q9) Define Stack? How stacks are implemented using linked list?