Given the heads of two linked lists, find whether they have any common node. If yes, find the common node.
Try to solve it as elegantly as possible.


Solution:

1. Subtract the length of smaller list from the larger one.
2. Move a pointer ahead on larger list by the difference of lengths.
3. Now put a pointer on head of smaller list.
4. More two pointers together.
5. The point at which they meet is the point where they short.

Code:
 

Node *getShortedNode(Node *list1, Node *list2){

int d = length(list1) - length(list2);

if(d < 0){
   d = d * (-1);
   Node *tmp = list1;
   list1 = list2;
   list2 = tmp;
}

Node *ptr1 = list1;
for(int i=0; i<d; i++)
{
   ptr1=ptr->next;
}

Node *ptr2 = list2;
while(ptr1 != NULL){
 if(ptr1 == ptr2)
   break;
 ptr1 = ptr1->next;
 ptr2 = ptr2->next;
}
return ptr1;
}

int length(Node *list){
int count = 0;
while(list != NULL){
 list = list->next;
 count++;
}
return count;
}

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;
}

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. 

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.