Amazon or Microsoft programming interview questions and solutions: August 2012

Monday, 20 August 2012

N QUEEN PROBLEM: On a NxN board place N queens such that no queen is under attack where a queen can move any steps horizontally, vertically and diagnolly.


public class Nqueen {

      private final int dim = 8;
      private final int queen = 1;
      private int[][] chessBoard  = new int[dim][dim];
      private int count = 0;
      private int startrow = 0;
   
      public void initialize()
      {
            setUpBoard();
            solve(0); 
            System.out.println("\n\nTOTAL NO. OF SOLUTIONS : " + count);
      }
   
 
   /*
         * This function checks whether a queen can be place in cell marked by (row,col)
         * If yes then returns true
         * Else returns false
   */
      public boolean isSafe(int row, int col)
      {
            for(int i=0; i<dim ; i++)
            {
                  if(chessBoard[i][col] == queen && i!= row)
                      return false;
                  if(chessBoard[row][i] == queen && i != col)
                      return false;
            }
         
            //diagnol check
            int i = row-1 , j= col-1;
            while(i>=0 && j>=0)
            {
                  if(chessBoard[i][j] == queen)
                      return false;
                  i--;
                  j--;
            }
         
            i = row+1;
            j=col+1;
            while(i<dim && j<dim)
            {
                  if(chessBoard[i][j] == queen)
                      return false;
                  i++;
                  j++;
            }
         
            i= row-1;
            j = col+1;
            while(i>=0 && j<dim)
            {
            if(chessBoard[i][j] == queen)
           return false;
            i--;
            j++;
            }
         
            i = row+1;
            j = col-1;
            while(i<dim && j>=0)
            {
                  if(chessBoard[i][j] == queen)
                       return false;
                  i++;
                  j--;
            }
            return true;
      }
   
 
   /*
         * This function initialized board to all 0's
   */
      public void setUpBoard()
      {
            for(int i=0; i<dim ; i++)
            {
                  for(int j=0; j<dim ; j++)
                  {
                      chessBoard[i][j] = 0;
                  }
            }
      }
   
 
   /*
         * This function place a queen at row, col position
   */
      public void placeQueen(int row, int col)
      {
            chessBoard[row][col] = queen;
      }
   
 
   /*
         * This function removes a queen placed at row, col position
   */
      public void removeQueen(int row, int col)
      {
            chessBoard[row][col] = 0;
      }
   
 
 
   /*
         * This function displays the chess board.
   */
      public void displayChessBoard()
      {
            for(int i=0 ; i< dim  ; i++)
            {
                  System.out.println();
                  for(int j=0 ; j<dim ; j++)
                  {
                      System.out.print(chessBoard[i][j] + "  ");
                  }
            }
      }
   
   
   /*
         * This function uses backtracking approach and check all possible test cases.
   */
      public void solve(int col)
      {
            if(col >= dim)
            {
                  count++;
                  System.out.println();
                  displayChessBoard();
                  return;
            }
            for(int row =startrow ; row<dim ; row++)
            {
                  if(isSafe(row,col))
                  {
                      placeQueen(row,col);
                      solve(col+1);
                      removeQueen(row,col);
                  }
            }
      }
   
 
      public static void main(String args[])
      {
            Nqueen n = new Nqueen();
            n.initialize();
      }
}

Sunday, 12 August 2012

Given an array containing only 0's and 1's, now we have to find the maximum subarray which contain equal no of 0's and 1's. Time complexity O(n).

/*
Logic for this program is taken from a post on geeksforgeeks.
I couldn't deduce an O(n) logic.
*/

#include<conio.h>

#include<iostream.h>

void main()

{

clrscr();

int array[]={1,0,0,1,0,1,1};

int len = sizeof(array)/sizeof(int);

int *sum = new int[len];

sum[0]=((array[0]==0)?-1:1);

int min=array[0],max=array[0];

for(int i=1;i<len;i++)

{

sum[i]=sum[i-1]+((array[i]==0)?-1:1);

if(sum[i]>max)

max=sum[i];

if(sum[i]<min)

min=sum[i];

}

int *hash = new [max-min+1];

int maxsize =-1,startindex;

for( i=0;i<max-min+1;i++)

hash[i]=-1;

for(i=0;i<len;i++)

{

if(sum[i]==0)

{

maxsize=i+1;

startindex=0;

}

if(hash[sum[i]-min]==-1)

hash[sum[i]-min]=i;

else

{

if((i-hash[sum[i]-min]) > maxsize)

{

maxsize=i-hash[sum[i]-min];

startindex = hash[sum[i]-min];

}

cout<<"\n START : "<<startindex;

cout<<"\n END : "<<maxsize+startindex-1;

getch();

}

Wednesday, 8 August 2012

Without using extra space place all zeroes to left and 1's to right from an array of Zero's and 1's as below 011001 ans. 000111

#include<iostream.h>

#include<conio.h>

void main()

{

clrscr();

int a[]={0,1,1,0,0,1};

int n=sizeof(a)/sizeof(int);

int i=0,j=n-1;

while(i<j)

{

if(a[i]==0)

i++;

if(a[j]==1)

j--;

if(a[i]==1 && a[j]==0)

{

a[i]=0;

a[j]=1;

i++;

j--;

}

for(i=0;i<n;i++)

cout<<" "<<a[i];

getch();

}

Find the subset of an array having maximum sum

#include<iostream.h>

#include<conio.h>

void main()

{

clrscr();

int a[]={1,3,-8,2,-1,10,-2,1};

int n=sizeof(a)/sizeof(int);

int sum=a[0];

int max=-1;

int start,end,s=0,e=0;

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

{

if(sum>=max)

{

start=s;

end=e;

max=sum;

}

if(sum<0)

{

s=e=i;

sum=a[i];

continue;

}

sum+=a[i];

e=i;

}

cout<<max;

getch();

}

There is an integer array consisting positive and negative integers. Find maximum positive difference S defined as: S = a[i] - a[j] where i>j and S > 0

#include<iostream.h>

#include<conio.h>

void main()

{

clrscr();

int arr[] ={-3,5,2,-2,1,0,-6,7,-8,2};

int n=10,min=arr[0],max=-32767 ;

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

{

if(arr[i]<min)

{

min=arr[i];

continue;

}

if(arr[i]-min>max)

max=arr[i]-min;

}

cout<<"MAX DIFFERENCE IS : "<<max;

getch();

}

Find 3 numbers in the given array such that their sum is equal to a given number.

#include<iostream.h>

#include<conio.h>

int array[]={10,20,30,40,50,60,70,80,90};

int n=9;

int check(int k,int val)

{

int i=0,j=n-1;

static int flag;

while(i<j)

{

if(i==k)

{

i++;

continue;

}

if(j==k)

{

j--;

continue;

}

if(array[i]+array[j]==val)

{

cout<<"\n"<<array[i]<<" + "<<array[j]<<" + "<<array[k]<<" = "<<val+array[k];

flag++;

i++;

j--;

}

else if(array[i]+array[j]>val)

j--;

else

i++;

}

return flag;

}

void main()

{

clrscr();

int val,flag;

cout<<"Enter the value ";

cin>>val;

cout<<" \n\n";

for(int i=0;i<n;i++)

flag=check(i,val-array[i]);

if(flag==0)

cout<<"\n No such elements ";

getch();

}

Inorder and Preorder tree traversal without recursion.

#include<iostream.h>

#include<process.h>

#include<math.h>

#include<conio.h>

class node

{

public:

node *left;

node *right;

int data;

node()

{

left=NULL;

right=NULL;

}

}*root=NULL;

int flag=0;

void add(node *parent,node *r,int d,int level,int item)

{

if(r!=NULL)

{

add(r,r->left,d+1,level,item);

add(r,r->right,d+1,level,item);

}

else if(d==level && flag!=1)

{

flag=1;

node *newnode = new node;

newnode->data=item;

if(parent->left==NULL)

parent->left=newnode;

else

parent->right=newnode;

}

void npreorder()

{

node *ptr=root;

int top=-1;

node **stack = new node*[50];

while(1)

{

if(ptr!=NULL)

{

cout<<" "<<ptr->data;

if(ptr->right!=NULL)

stack[++top]=ptr->right;

ptr=ptr->left;

}

else

{

ptr=stack[top--];

if(top==-2)

return;

}

void ninorder()

{

node **stack= new node*[50];

int top=0;

node *ptr=root,*process=NULL;

while(top>=0)

{

if(ptr && process!=ptr)

{

stack[++top]=ptr;

ptr=ptr->left;

}

else

{

ptr=stack[top--];

process=ptr;

cout<<" "<<ptr->data;

if(ptr->right)

ptr=ptr->right;

}

void main()

{

clrscr();

int ch,item;

cout<<"1.ADD\n2.PREORDER\n3.DEPTH\n4.NO OF ELEMENTS\n5.TRACE";

cout<<"\n6.BFS AND DFS\n7.EXIt";

while(1)

{

cout<<"\nchoice? ";

cin>>ch;

switch(ch)

{

case 1: cout<<"ITEM :";

cin>>item;

flag=0;

if(root==NULL)

{

node *newnode = new node;

newnode->data=item;

root=newnode;

}

else

{

maxdepth=0;

depth(root,0);

int level;

int elements=count(root);

if(elements==(pow(2,maxdepth+1)-1))

level=maxdepth+1;

else

level=maxdepth;

add(root,root,0,level,item);

}

break;

case 2: ninorder();

//npreorder();

//preorder(root);

break;

case 3: maxdepth=0;

depth(root,0);

cout<<maxdepth;

break;

case 4: cout<<count(root);

break;

case 5: equal=0;

cout<<"ITEM TO TRACE : ";

cin>>item;

trace(root,item);

break;

case 6: cout<<"\nBFS\n";

bfs();

cout<<"\nDFS\n";

dfs();

break;

case 7: exit(0);

}

Count the number of elements in a binary tree.

int count(node *r)

{

if(r==NULL)

return 0;

else

{

int c=1;

c+=count(r->left);

c+=count(r->right);

return c;

}

calculate the depth of the binary tree.

int maxdepth=0;

void depth(node *r,int d)

{

if(r!=NULL)

{

if(maxdepth<d)

maxdepth=d;

depth(r->left,d+1);

depth(r->right,d+1);

}

In a binary tree given any node, trace its path from root node.

//set equal=0 before calling trace function.

int equal=0;

void trace(node *r,int item)

{

if(equal==1)

return;

if(r->data==item)

equal=1;

if(r!=NULL)

{

trace(r->left,item);

trace(r->right,item);

if(equal==1)

cout<<" "<<r->data;

}

Print bfs and dfs traversal of binary tree.

void bfs()

{

if(root==NULL)

{

cout<<"\nEMPTY LIST";

return;

}

node **queue = new node*[count(root)];

int front=0;

int rear=0;

queue[front]=root;

node *pnode;

while(front<=rear)

{

pnode=queue[front++];

cout<<" "<<pnode->data;

if(pnode->left!=NULL)

queue[++rear]=pnode->left;

if(pnode->right!=NULL)

queue[++rear]=pnode->right;

}

void dfs()

{

if(root==NULL)

{

cout<<"\nEMPTY LIST";

return;

}

node **stack = new node*[count(root)];

int top=0;

stack[top]=root;

node *pnode;

while(top>=0)

{

pnode=stack[top--];

cout<<" "<<pnode->data;

if(pnode->left!=NULL)

stack[++top]=pnode->left;

if(pnode->right!=NULL)

stack[++top]=pnode->right;

}

Monday, 6 August 2012

In a linked list print odd nodes first and then even nodes and also sort a linked list

#include<iostream.h>

#include<process.h>

#include<conio.h>

class node

{

public:

node *next;

int data;

node()

{

next=NULL;

}

}*start=NULL;

void display()

{

if(start==NULL)

{

cout<<"empty list";

return;

}

node *ptr=start;

while(ptr!=NULL)

{

cout<<" "<<ptr->data;

ptr=ptr->next;

}

void insert(int item)

{

node *newnode = new node;

newnode->data=item;

if(start==NULL)

{

start=newnode;

return;

}

node *ptr=start;

while(ptr->next!=NULL)

ptr=ptr->next;

ptr->next=newnode;

}

void del(int item)

{

if(start->data==item)

{

start=start->next;

return;

}

node *pre=NULL,*ptr=start;

while(ptr!=NULL)

{

if(ptr->data==item)

{

pre->next=ptr->next;

return;

}

pre=ptr;

ptr=ptr->next;

}

cout<<"ITEM NOT IN LIST";

}

void sort()

{

node *min,*parmin;

for(node *ptr1=start,*parptr1=NULL;ptr1->next!=NULL;)

{

min=ptr1;

for(node *ptr2=ptr1->next,*save=ptr1;ptr2!=NULL;)

{

if(ptr2->data<min->data)

{

min=ptr2;

parmin=save;

}

save=ptr2;

ptr2=ptr2->next;

}

if(min!=ptr1)

{

parmin->next=min->next;

min->next=ptr1;

if(parptr1==NULL)

{

start=min;

parptr1=min;

}

else

{

parptr1->next=min;

parptr1=min;

}

else

{

parptr1=ptr1;

ptr1=ptr1->next;

}

void main()

{

clrscr();

cout<<"1.INSERT\n2.DELETE\n3.DISPLAY\n4.ALL ODD FIRST\n";

cout<<"5.SORT\n6.REVERSE\n7.ALTERNATE REVERSE\n8.Nth ELEMENT FROM LAST\n9.Exit\n";

int ch,item;

while(1)

{

cout<<"\nchoice? ";

cin>>ch;

switch(ch)

{

case 1: cout<<"ITEM TO INSERT";

cin>>item;

insert(item);

break;

case 2: cout<<"ITEM TO DELETE";

cin>>item;

del(item);

break;

case 3: display();

break;

case 4:// sort();

evenodd();

display();

break;

case 5: sort();

display();

break;

case 6: //node *ptr=reverse(start);

// ptr->next=NULL;

i_reverse();

break;

case 7: kreverse(4);

//altreverse();

break;

case 8: int n;

cout<<" ENTER N ";

cin>>n;

fromlast(n);

break;

case 9: exit(0);

}

Pages

Monday, 20 August 2012

Sunday, 12 August 2012

Wednesday, 8 August 2012

Monday, 6 August 2012