Given an array of integers and a number N. [Consider array to be sorted]
Find out all pairs of numbers of the array whose sum is N.
Simply find out all integers a, b of array such that a + b = N


Solution:

Algorithm:

1. Take two variables that holds the value of First and Last index of array.
2. Loop while First < Last:

Now sum value stored in First and Last index of the array.

If sum is greater than N

decrease Last by 1.

If sum is less than N, 

increase First by 1.

If sum is equal to N, 

print values stored at First and Last index. 
Decrease Last by 1 and Increase First by 1.

This is quite intuitive after reading and this solution is taking advantage of Sorted Array.
 

Majority Element is an element of an array that occurs more than half the number of times in the array.Easy Problem: 
Assume that an integer array A[1..n] has a majority element and elements other than majority element are distinct. How to find majority element. What's the space and time complexity of the algorithm ?Hard Problem: 
Assume that an integer array A[1..n] has a majority element and elements other than majority element need NOT be distinct. How to find majority element. What's the space and time complexity of the algorithm ?

Both easy and hard may be solved using the following solution in ~(n-1) comparisons.

Solution (HARD) :

This algorithm uses an observation that if we consider our array to be list of voters and array value is the candidate to whom they are voting, then majority element is the winning candidate.

Additionally, if all other candidates are merged to form one candidate then still it will fail to defeat the majority element candidate (hence the name majority element).

So we can think of it this way. Assuming a negative vote decrease the count of majority element then still the count of majority element would be atleast 1.

int majority_hard(int[] input, int n){

int element = input[0];
int votes = 1;

for(int i=1; i<n; i++){

if(input[i] == element)

votes++;

else if(votes > 0)

votes--;

else {

element = input[i];
votes = 1;

}

}
return element;

}

However, the easy problem may be solved using ~n/2 comparisons using the pigeon hole principle :

Solution (EASY) :

If the total size N is even then, the majority element must duplicate in consecutive positions in some pairs of positions. If N is odd, then it must either duplicate in consecutive positions or must be the last element.

int majority_easy(int[] input, int n){

for(int i=0; i<N; i+=2){

if(input[i] == input[i+1])

return input[i];

}

return input[N];

}

Try to study the solutions and practice writing compact and elegant code. You'll automatically get efficiency with elegance.


Courtesy: Vibhaj

Find second smallest element in an array A[1..N] of size N. (We would like to do in much less than 2N comparisons if possible).


Solution:

I suppose the method to solve is mentioned in Cormen and it takes n + log(n) - 2 comparisons. (Tournament style with saving elements that lost to minima; then searching for second minima in them)

Similar method is using Heap data structure to do it in n + log(n) comparisons. (Build heap in n and Min heapify in log(n))

The question does not end here as the above solutions use comparisons to get 2nd and in general kth minima. We can use other methods without comparisons (at the cost of space) to get kth minima.

I thought of using Trie data structure to get it done easily. We simply assume the maximum digits in the elements in the array and padd them with 0's at the beginning to make them D digits large. We insert each into D level trie and the pre-order traversal gives all elements in correct sorted order.

Bucket sort, Radix sort are other possibilities. Try to learn about these methods.


Courtsey: Vibhaj
 

This is today's problem :

Given an array of N integers (both positive and negative), find the sub-sequence with largest sum.

For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest sum is 10 (start index = 3, end index = 6)
{4 5 -1 2}


Solution :

A simple linear algorithm will work by keep track of the current subsequence sum. If that
sum ever drops below zero, that subsequence will not contribute to the subsequent maximal subsequence since it would reduce it by adding the negative sum.

#include<iostream>
using namespace std;
int main()
{
int input[10], i, sum = 0, start = -1, end = -1, current = -1, max = -1;//testing for an array of 10 elements
for(i =0;i<10;i++)
      cin>>input[i];
for(i=0; i<10; i++)
{
 sum += input[i];
 if(sum < 0)
 {
        sum = 0;
        current = i+1;
 }
 if(sum > max)
 {
        max = sum;
        start = current;
        end = i;
 }
}
cout << "Start : " << start << " End : " << end << endl<<"Elements are : ";
for(i = start;i <= end;i++)
cout<<input[i]<<" ";
return 0;
}

You are given a number N which will be large (within limits of machine representation of long integer)
You need to find the total trailing zeros in N! (factorial)
Give attention to time complexity. Reduce it as far as possible.

Eg, 
N = 6 
N! = 720
Count = 1 (trailing means to the end)



Solution:

Keep on dividing N by 5 repeatedly and add the quotient each time until number becomes 0. The sum of all the quotients will be the number of trailing zeros.
Code:

#include<iostream>
using namespace std;
int main()
{
int N;
cin>>N;
int count = 0;
while(N > 0)
{
    count += N/5;
    N = N/5;
}
cout<<count; 
return 0;
}

For beginners :

Implement Stack and Queue by yourself. Many of you have not done it yet. Implement all the primitive operations on Stack and Queue. Try to implement it without using an Array.

For others:

1. Implement a Stack using 2 Queues.
2. Implement a Queue using 2 Stacks. [Implementing any structure means all the primitive operations have to be performed].

Code it.


P.S. - Its not bad to be a beginner :)



Solution :


Basically in this problem, You need not to be efficient in terms of time and space complexity. You just need to think how this goal will be achieved. 
For Stack using 2 Queues basic idea is, 
For PUSH operation:
ENQUEUE all the elements in only one of the Queue [after first PUSH, insert into non-empty Queue] (using flag is an option or you may check this as a condition of emptiness).
For POP operation:
DEQUEUE all the elements except one from the non-empty Queue and ENQUEUE all of these De-queued elements of first Queue into the second one making first Queue empty.

Similarly for Queue using 2 Stacks. 

You have 25 horses and 5 tracks and you need to find out top 3 horses. What is the minimum number of races required to do this ?







p.s. - Answer will be posted after 2 days from respective questions. Although we're always open for discussion in comments :)






Solution:


For 1st question:
Group 25 horses in 5 groups:

A : A1, A2, A3, A4, A5 [Decreasing order of speeds]

B : B1, B2, B3, B4, B5

C : C1, C2, C3, C4, C5

D : D1, D2, D3, D4, D5

E : E1, E2, E3, E4, E5

Five races will have to take place for ranking in groups themselves.

One race for A1, B1, C1, D1, E1 for ranking of the groups.

Now A1>B1>C1>D1>E1

So A1 is the topper. We now need to find 2 more horses for 2nd and 3rd position.

Here is the key observation.

Selection by Elimination  [We need to find 2 more horses, if any horse is slower than 2 horses except A1 then it can not be included in the solution]

1. D1 and E1 can not be included in the solution as both of them are slower than B1 and C1

and hence their whole group is eliminated as they were best from their groups.

2. A4, A5 can not be included in the solution as they are slower than A2 and A3.
3. B3, B4, B5 can not be included in the solution as they are slower than B1 and B2.

4. C2, C3, C4, C5 can not be included in the solution as they are slower than C1 which is slower than B1 itself.

So we are now having only 5 possible horses for 2 positions which can be found out in just one race. [A2, A3, B1, B2, C1] Top 2 of this group will be ranked 2nd and 3rd after A1.

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.