Reverse a stack, using just push(), pop(), top() operations, in its place itself.
You can not assign any known memory address.

Solution: 

Simple methodology for this problem is, take last element from the stack i.e. you need to empty the stack [do it recursively, keeping other elements in memory].
Push the last element in the stack again.
Now while pushing each of earlier elements, first empty whole stack and then push them.
This will ultimately turn into reversed stack.

Code: 
Code is pretty much intuitive and not exactly executable in the current condition, so make yourself do some work and write something on your own. :)

void reverse(Stack st)
{
  int m = (int)st.Pop();
  if (st.Count != 1)//checking for last element
  reverse(st);//popping out all the elements for reversing
  Push(st , m);//now the last element popped out i.e. the bottom element will be pushed to stack, which is now empty
}


void Push(Stack st , int a)
{
  int m = (int)st.Pop(); // if stack has already some elements then pop them out
  if (st.Count != 0)
    Push(st , a); // new items will be pushed to the bottom-most position.
  else
    st.Push(a); 
  st.Push(m); //now atlast push the item popped out first i.e. the last element from original stack
} 

1).merge two height balanced binary trees to get another height balanced

 binary tree.

--------------------------------------------------------------
2).given an unsorted array of n integers, find that pair of integers
which gives the maximum sum.
--------------------------------------------------------------------------------------------
3) slight modification.(use heap) find the maximum sum giving combination of k integers.
--------------------------------------------------------------------------------------------
4)sudoku solver
--------------------------------------------------------------------------------------------
5)How do you find  a loop in a linked list?


               1) ptr method
               2) Go on reversing the linked list.
                     If you reach the head again, the list has a loop
--------------------------------------------------------------------------------------------
6) construct a n element binary tree from its inorder and preorder traversals kept in two arrays A[n] and B[n].
{ u can get the roots of each subtree in preorder array. Then we can partition the inorder array into left and right subtrees. Thus this problem can be solved recursively...}


--------------------------------------------------------------------------------------------
7)we are given the answers to a crossword puzzle...we need to generate the blocks...that is the question is to be framed..what data structure do u think should we use for this????(may be trie,linked list.??)
----------------------------------------------------------------------------------------------------
8)how can we reverse a sentence.its not string reversal
example;
given input "this is me"
the output should b "me is this"
{Use a stack !! first "push" every word in correct order.. then "pop" them out... the resulting string will be in reverse order !}
------------------------------ ----------------------------------------------------------------------
9)def. of tree, graph, linked list and many more
----------------------------------------------------------------------------------------------------
10) How do you find a loop in a Binary tree in a most efficient way.
{ by maintaining flag variable in node data.if already traversed ,flag value z true,otherwise  false.
suppose recursive function access the already traversed node,then we can conclude that this tree is having loop.}
----------------------------------------------------------------------------------------------------
11) If 'n' is even donfiltered=n/2
Else if 'n' is odd donfiltered=3*n+1.
If you keep on doing above said operations 'n'will converge to 1 at some point.
You are given a set of numbers (say 65 to 125.Give an efficient solution to find out which number converges to 1 the quickest.
----------------------------------------------------------------------------------------------------
 12) sort an array having elements only 0 and 1 in O(n)time and sorting should terminate immediately after array gets sorted.(1. find the first occurrence of
 1. now find the first occurrence of 0.
2. when u are having two marker one at first 1 and other at first 0. swap  them.}
----------------------------------------------------------------------------------------------------
13)find out the median of two sorted arrays as if this is one sorted array with O(1) space constraint.
----------------------------------------------------------------------------------------------------

Read more »

I am attaching a bunch of DS questions.This will give you an idea of questions asked at MS internship interview.
Try to write executable code for each question (very important, dont just discuss the algo, code it),because that is what is asked to do in the interview.Loads of material is available on the internet as well.

Please discuss these questions.

a) Write a function that validates whether a tree is a BST or not.

b) Write a function to find the common ancestor of two given nodes of binary tree.

c) In a BST, value of  two of the nodes got exchanged by mistake. Write a function to correct the BST.

d) In a array, there exists a majority element(a no. repeated atleast n/2 + 1 times) and rest of the no.s can be anything. find that majority element in a single pass without using extra space.

e) Find the no. of root nodes in a Binary tree.

f) write a function to create  a mirror image of  a given binary tree without using recursion.

---Written---

 
    1) aptitude
    2) Engineering: easy questions test of speed
        2a) complexity of a given algorithm?
        2b) given grammar draw automata
        2c) draw binary tree from preorder and in-order etc.
       
    3) programming: easy questions test of accuracy/corner cases
        3a) check overflow of sum of two numbers

int a,b;//two nums 
int c=0; 
int count=0; 
while((a>0)&&(b>0)) 
{ 
    count++; 
    c=c|(a&1)&(b&1); 
    a>>1; 
    b>>1; 
    if((count==32)&&(c==1))    
    printf("overflow"); 
}

        3b) sorting array of 0 and 1

Counting sort will be helpful or just count the number of 0's in one pass and in next pass put as many 0's as the count in the array and rest of the element be 1.
The sort is O(2n)=O(n)
 

        3c) anagram of given string
        3d) simple question on pointer to pointer...etc

    P.S search google for adobe written paper questions. Questions remains almost same generally.
 

---Interview---- 
1)HR
        1a)Tell me about yourself
        1b)Extra-curricular activities from CV, what you did in school
        1c)How many lamp-posts are in India? Tell how to solve?
        1d)Anything else you want to share

    P.S In questions of type 1c whatever logic you give try to avoid backing out of what you stated earlier. Try to give reasoning for whatever you say. Eg . I would google this and that . And infer this. He will ask you supporting reasons.     
 

2) Tech1
 
        2a) Will ask to explain questions from written paper.
           What is your favorite subject?
        2b) Tell me something about memory mgmt, how virtual memory,
           page faults.

mem management: All process requires resources to be allocated to them which must reside in the main memory for the process to run properly. Memory management is a way to manage the allocation of the process and the resources in and out of the main memory. Once the process is allocated memory, it fights for CPU allocation where CPU management comes into play. Till the process is not in main memory its the job of memory management algorithm to efficiently allocate resources for the process and their resources.

virtual memory: Virtual memory is a way in which the process is allowed to execute although only partial process resides in main memory. The user is able to run the process even if the size of the process exceeds memory size, as the portions of process is brought in memory as and when required,thus excluding the need for complete process to reside in memory.

Read more »

Questions asked to Mr. Anshul Omar:

Technical interview 1:

1. Tell something that happened in your life that made you feel exhilarated or tell about one of your achievements that you are proud of.
2.  Data Structures...stack and queues basic questions  //code
3. Dynamic programming  //code
4. Fibonacci algorithm (efficiently)  //code
5. Puzzle: Match box..weigh exactly once
6. How would you ascertain whether a given list is a circular list most efficiently?   //code
7. Operating Systems fundamental questions

Technical interview 2:

1. Data structures implementation or practical applications
2. What are your favourite data structures and why?
3. Implementation of stacks dynamically, and code for push and pop operation incorporating exception handling
4. How to deallocate memory after pop operation...code for it including functions and return types
5. A string is given and print it by removing all duplicated letters most efficiently
   for e.g. " Hello world"....ans: Helo wrld..order doesn't matter.....I did it in O(nlogn) time.  //code
6. Questions on coding in C/C++
7. Database management basics
8. Ques on projects....everything associated with it
9. JSP, mySQL, AJAX etc. web development tools used in project
10. OOP concepts
11. Features of OOP model
12. Types of programming languages
13. What is the thing that excites you the most about GS?

and some more....

HR interview:

1. Tell us about yourself
2. Introduce yourself in context of academic background
3. Scholarships that you have got in your entire scholastic career
4. Why do you want to do an intern in GS?
5. Why GS, why not any other corporation that has a mix of technological core and business analysis?
6. What is investment banking, securities?
7. What do you know about market analysis, shares,commodities etc.?
8. Why should we take you?
9. How would you benefit GS?
10. What do you expect from us while doing an intern in GS?
11. Extra-curricular

Questions asked to Mr. Shivasheesh :

Read more »

I'll post interview questions of DeShaw for internship in 2010. They have some kind of affection with Polymorphism.

Arvind Mohan:

Telephone Round:

1. What is a virtual destructor? What is its use?

2. What is a Virtual base class?

3. Reverse a Singly Linked List.

4. How to find a loop in a linked list?

5. What are the differences between pointer and reference?

Face to Face Interview:

1. Tell me about yourself technical which is not in your CV.

2. What do you understand by Polymorphism?

3. Pointers and References

4. In a binary tree, Information about parent is given. Find common ancestor of two nodes.

5. In how much time google.com loads.

6. You are provided with marks of students in physics, chemistry, maths and total marks along with their name. What type of data structure will you use to store this data and to give the rank to students. If two students with same total marks then tie will be broken by marks in Chemistry, then Physics and then maths.

#include<iostream>
using namespace std;
int main()
{
     cout<<"Testing my new code highlighter\n";
     return 0;
}

Written:

1) A code was given and we had to print output. Had something to do with pointers to character array.

2) A code was given which finds the successor to any node in a BST, we have to find bugs in it.

3) A simple question about sorting. 

4) Given a function NextDate( string currentDate, int n ), which takes in current date and n and returns the date n days ahead of it, 

write the test cases you would test it with.

5) You are to design a system for elevators in a 100-storey building, what information you think you need before-hand to get started.

Interviews:

Round 1: 8 of us were seated at same time, a problem was explained and we were asked to code on paper.

Question: Given a structure consisting of numbers which is sorted row-wise and column-wise.

for ex:     1 ---> 2 ----> 5

               |

               6 ---> 8 ---> 10 --> 12

               |

               15 -->20

Length of each row can't be more than 5. You have to write code to insert any given number in this structure maintaining it's property. 

Try to code as cleanly and correctly in first attempt.

Round 2:

1) Given a sorted array of size m and another sorted array of size m+n, where the 2nd array contains only n elements, merge the arrays to create a sorted array.

They were interested in code that would do as little computations as possible, ie, for 2 algorithms with same complexity, the one doing fewer computations is better.

2) Classical Red Ball, Blue ball, mixed ball and wrong labels puzzle.

3) Another classical 12 ball 1 heavy problem. :)

Round 3:

1) Implement case insensitive strcmp function. Try to code correctly in first attempt.

2) In a Binary tree, the balance of each node is defined as ( maximum height - minimum height ) <=1. Write a function to check if a given tree is balanced or not.

At Microsoft:

Round 1) Given a string, like abcdaddee, find all possible palindromes that can be formed by interchanging the positions of the characters present. You can't add or delete more characters and have to use all the characters. Write the code. for ex with abab, one can form abba and baab. 

Round 2) In a BST, the values of 2 nodes are swapped. Write the the code to find those values, O(n) complexity

9 balls are given and 1 is defective, however u don't know the type of defect. Use minimum weightings to find the defect and defective ball. Ans: 3

Round 3)

1) Given 2 different matrices, Column 1 of both matrices contain similar type of entries. You can assume that Matrix A contains Roll no and Names of some students and 

Matrix B contains Roll No and Grades of same students, however, the order of roll no can be different, ie, Roll 1 can be at position i in Matrix 1 and at any position j in Matrix B. You have to create a new matrix with the information merged, i.e, Matrix C will contain 3 columns-Roll no, Names and grades. [ Much like join operation in databases ].

After I proposed the solution, he asked if there are many merge operations going on, what changes could be done to make this efficient ?

2) Given a string a[] and a character ch, modify the string a[] so that there no instances of ch present. Keep in mind that there should be no blank spaces.

3) Given an array, which is sorted but rotated, like 4 5 6 1 2 3, find any element in it. O( lg(n) ).

4) Some discussions about compilers and pointers and other things. Fattebazi hui dono side se :)

1. You need to find leftmost right cousin of a node in a binary tree.

Leftmost of all the nodes present on the right side of the input node with the same height is called Leftmost Right Cousin.


2. void replace(int list[], int data, int pos)

This function takes a list of integers, an integer data, another integer pos.

It searches data in the list and after finding it, deletes the node containing data. Then it replaces the value present a index pos of the list with data.

You need to write test cases as the values of list, data, pos.


3. There is a call center. For any specific subject, there are agents. Any agent can help only one user at a time. Any agent can go to a break or full off for the day.
Answer the following:
a) Write down the agent's state machine.
b) What algorithm will you use to assign a proper agent to a user.
c) In case of the request sent by user is lost as the agent just went to the leave before getting message from server about the user. How will you handle this race condition.






p.s. : Please suggest to update any of these questions, if you find anything wrong in them.

1. Given a string s[1...n] and a reverse function reverse(s, i, k) which reverses the character sequence from i to k (inclusive of both) in string s, determine what the following operations result in.
1<k<n

reverse(s, 1,  k)
reverse(s, k+1, n)
reverse(s, 1, n)

a) Reverses the string
b) Rotates the String left k positions
c) Rotates the String right k positions
d) None of the above


Answer: b)

2. If len is the length of the string and num is the number of characters printed on the screen. Give the relation between num and len.

void abc (char *s){
if(s[0]=='\0')
return;

abc(s+1);
abc(s+1);
printf("%c ", s[0]);

}

a) num=2^len
b )num=2^len-1
c) num=2*len-1
d) None of the above




Answer: b)




3. Which of the following numbers cannot be represented accurately in binary?
a) 0.1  b) 6.5 c) 1/16 d)1.32 e) 0.590625 (not sure abt option e)

1. a only
2. a and b
3. a, b and d
4. a, b and e




Answer: a) and d) should be the answer



4. A process doesn't require additional processors to carry out 40% of it's execution since 40% is mostly sequential. Determine how many processors are required to execute the process in 150s if
the process takes 300s to execute on a single processor.

a)5
b)8
c)6
d)7


Answer: c)

5. Time complexity of a function f(m) is O(m). If the array[i...n] contains either 1 or 0 in each of it's locations, determine the worst case time complexity of the following piece of code written in C-like
language.


counter=0;
for(i=0; i=n; i++){
if(a[i]==1)
counter++;
else{
f(counter);
counter=0;

}
}

* i=n was given in the condition of for loop
a) O(n^2)
b) O(n^2 logn)
c) O(nlogn)
d) O(n)




Answer: d) if assuming everything else to be alright.




6. Increasing the RAM increases the efficiency of the CPU. The reason
is
a) Virtual memory increases
b) Number of page Page faults decreases
c) Page segmentation decreases
d) Increasing the amount of memory increases the speed of fetching
data.


Answer: b)


7. If a dice is thrown three times, what is the probability that a "six" comes atleast once.
a) 125/216
b) 25/216
c) 91/216
d) 1/216

Answer: c)

Find lowest common ancestor of two given nodes in a Binary Search Tree.

Hint for a corner case : Instead of some trivial solutions please keep in mind that value of nodes can be same in a BST.

You are given an array of N numbers. Shuffle the numbers in the array such that all permutations have equal probability.

You are given a dictionary of say N words. Find all words having a given Prefix.

Write a function for a biased coin on the basis of a fair coin.

Find whether a string is palindrome or not. Given that string consists of punctuation marks as well.

Implement sqrt() function without using math.h header file.

You have a set of N numbers. Print all subsets out of these numbers that contains exactly k numbers.

Level Order Traversal of a Tree.


p.s. Solutions will be posted soon.

From now, I'll be posting interview questions for Computer Engineering of several companies that visit our campus at Institute of Technology, Banaras Hindu University. A collection kind of thing.

Please let me know about any question that you want to share at this place. Mail me at arvind.mohan.cse08@itbhu.ac.in

Be Curious!