1.Given a doubly linked list, copy the list.
Struct node
{
node *pNext;
node *pPrev;
node *pRandom;
};

pRandom has connection to any random nodes.
Write a program to clone this list.
Solution: If extra memory is allowed then the hash table will work

  1. Create a copy of an original list setting up only prev and next pointers
  2. While doing #1 create a map keyed on nodes in original list and valued on corresponding nodes in cloned list
  3. Iterate through both lists at the same time and set:
    NodeInClonedList.random = map[NodeInOriginalList.random]

Without extra memory you have to modify the original list so the “prev” pointer would point to a cloned node.

 

2.Given an unsorted list with each node having a random pointer to another node, sort the list such that each node points to the next node in the list (n1->n2->n3).
Solution:

void bubble_sort(Node* head)
{
   if(head == NULL || (head)->next == NULL)
       return;
   int count = 0;
   Node* temp = head;
   while(temp != NULL)
   {
       count++;
       temp = temp->next;
   }
   Node *p = NULL;
   Node *q = NULL;
   bool flag = false;
   for(int i = count-1; i > 0; --i)
   {
       p = head;
       q = head->next;
       flag = false;
       for(int j = 0; j < i; j++)       
         {   if(p->data > q->data)
            {
               flag = true;
               swap(p->data,q->data);
             }
          p = p->next;
          q = q->next;
       }
       if(flag == false) break;
   }
}

 

3. Given a graph where every two nodes are either friends or enemies with each other. Find a way to go from one node to the other.
Restrictions:

  1. You can also travel from one node to next if they are friends with each other
  2. You have some “magic potions”. You can convert an enemy path to a friend path with a magic potion.

Solution: This can be solved easily using DFS or BFS.

if(next node is a fried)
       travel and add in stack 
if(next node is enemy)
     pop and go to previous friend node on the next path if there are more paths, else keep on popping to  previous friend nodes 
eventually if there exists a path it will be found......

 

4. Given a BST, find out the minimum length form root to leaf with sum S. Note that:

  1. Path from root to leaf node.
  2. Sum of node of the path is S.
  3. if multiple such path exist, print minimum length path.
  4. What is advantage of BST rather than BT used for this algorithm, how it improve the performance. in BST, is it required to explore both side ?
  5. Write working codes for it.

Solution:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std; 
typedef struct tree 
{ 
struct tree *left; 
struct tree *right; 
int item; 
}nod; 
void create ( nod **root,int num ) 
{ 
nod *t, *u; 
t = *root; 
if ( t == NULL )
 { 
   u = new nod; 
   u -> right = NULL; 
   u -> left = NULL; 
   u ->item = num; 
   *root = u; 
 }
else if ( t -> item <= num )   
         create ( & ( t -> right ), num ); 
else if ( t -> item > num ) 
         create ( & ( t -> left ), num ); 
 
} 
bool check_sum ( nod *root, int sum)
{ 
   if ( root != NULL )
      { 
         printf("%d\t%d\n", root ->item, sum); 
         if ( root ->left == NULL && root ->right == NULL && (sum - root->item == 0))
           { 
              printf ( "found\n"); 
              return true; 
           } 
        check_sum ( root ->left, sum - root ->item); 
        check_sum ( root ->right, sum - root -> item); 
     }     
} 
void preorder ( nod *root ) 
{ 
   if ( root != NULL ) 
      { 
         printf ( "%d->", root -> item ); 
        preorder ( root -> left ); 
        preorder ( root -> right ); 
     } 
} 
int main() 
{ 
   int n, num; 
   nod *root = NULL; 
   scanf ( "%d", &n ); 
   for ( int i = 0; i < n; i++ ) 
      { 
       scanf ( "%d", &num ); 
       create ( &root, num ); 
      } 
   preorder ( root ); 
   int sum; 
   printf( "enter sum\n"); 
   scanf( "%d", &sum); 
   if (check_sum(root, sum)) 
       printf("sum exist"); 
   else  
      printf("not exist"); 
   return 0; 
}

 

5. A quadra tree is a tree where each node has atmost 4 child nodes(similar to a binary tree which has atmost 2 child nodes). A monitor screen (black and white) is represented by a quadra tree in the following way:
case 1: If the entire screen is white then the value in the root node is white.
similarly if the entire screen is black then the root stores black.

case 2: If the screen is neither completely black nor white then the screen is divided into 4 quadrants and the node has 4 child nodes each representing one of the quadrants.( the screen is recursively divided into subscreens).

Now given two screens represented by two quadra trees, return a quadra tree which represents the overlapping of the two screens (assume when white and white overlaps results in white,black and white overlap results in black , black and black overlap results in black).
Solution: We may divide the problem into two parts:

  1. mix each subtree according to the colors of nodes
  2. try to concetrate those nodes whose children have same color.
/*********************** definitions **************************/
#define SCREEN_DIVISION	4
enum Color{
	unknown,
	white,
	black	
};
typedef struct ScreenNode{
	Color color;
	struct ScreenNode* child[SCREEN_DIVISION];
} ScreenNode;
/********************** general function ***********************/
int isLeaf(const ScreenNode* p)
{
	if(!p) return false;
	for(int i = 0; i < SCREEN_DIVISION; ++i)		
               if(p->child[i]) return 0;
	return 1;
}
void freeChildren(ScreenNode* parent)
{
	if(!parent) 
            return;
	for(int i = 0; i < SCREEN_DIVISION; ++i)
   	    if(parent->child[i])
            {
		free(parent->child[i]);
		parent->child[i] = NULL;
	    }
	
}
ScreenNode* cloneScreen(const ScreenNode* p)
{
	if(!p) return NULL;

	ScreenNode* t = (ScreenNode*)malloc(sizeof(ScreenNode));
	t->color = p->color;
	for(int i = 0; i < SCREEN_DIVISION; ++i)        
            t->child[i] = cloneScreen(p->child[i]);
	
	return t;
}
/******************* get overlapped screen *********************/
ScreenNode* mixLeafWithTree(const ScreenNode* leaf, const ScreenNode* tree)
{
	if(leaf->color == Color.black) return cloneScreen(leaf);
	else return cloneScreen(tree);
}
ScreenNode* overlap(const ScreenNode* a, const ScreenNode* b)
{
	if(!a) return cloneScreen(b);
	if(!b) return cloneScreen(a);
	if(isLeaf(a)) return mixLeafWithTree(a, b);
        if(isLeaf(b)) return mixLeafWithTree(b, a);
	ScreenNode* p = (ScreenNode*)malloc(sizeof(ScreenNode));
	for(int i = 0; i < SCREEN_DIVISION; ++i)	
        	p->child[i] = overlap(a->child[i], b->child[i]);
	return p;
}
/********************* concentrate subscreen *********************/
int canBeConcentrated(const ScreenNode* parent)
{
/* In given condition: all children are leaves && all children has same color */
if(parent->child[0] && !isLeaf(parent->child[0])) return parent;
	for(i = 1; i < SCREEN_DIVISION; ++i)
         {      if(!parent->child[0]) 
                   continue;
		if(isLeaf(parent->child[i]) ||  parent->child[i]->color != parent->child[i-1]->color)
		   return 0;
	 }
	return 1;
}
Color getConcentratedColor(const ScreenNode* parent)
{
/* In given condition: parent's color is first child's color */
	for(int i = 0; i < SCREEN_DIVISION; ++i)
        {   if(parent->child[i]) 
                return parent->child[i]->color;
	}
	return Color.unknown;
}
ScreenNode* concentrate(ScreenNode* p)
{
	if(!p || isLeaf(p)) 
             return p;
	for( int i = 0; i < SCREEN_DIVISION; ++i)		
            p->child[i] = concentrate(p->child[i]);
	if(canBeConcentrated(p))
         {
		p->color = getConcentratedColor(p);
		freeChildren(p);
	}
	return p;
}

/********************** interface to outside ***********************/
ScreenNode* getOverlappedScreen(const ScreenNode* a, const ScreenNode* b)
{
	return concentrate(overlap(a, b));
}