1.Print combinations of strings from List of List of String.
Example input: [[quick, slow], [brown, red], [fox, dog]]
Output:

  • quick brown fox
  • quick brown dog
  • quick red fox
  • quick red dog
  • slow brown fox
  • slow brown dog
  • slow red fox
  • slow red dog

Solution:

vector<vector> sets;
vector cs;
void print(int k) {
	if(k == sets.size()) {
		for(auto &x : cs) {
			cout << x << " ";
		}
		cout << endl;
	}
	else 
      {
		for(int i = 0; i < sets[k].size(); i++)
             {	cs.push_back(sets[k][i]);
			print(k+1);
			cs.pop_back();
		}
	}
}
int main () {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	sets = {{"quick", "slow"}, {"brown", "red"}, {"fox", "dog"}};
	print(0);
	return 0;
}

 

2.Consider the following class definition:

class Node { 
List<Node> children; 
void addChild (Node child); 
} 

Assume you have a node object like above. This node object can contain a child node object. Assuming you are given one of these objects, write a function to determine the maximum path length from the root node to the most distant remote node.
Solution:

public class Node where T : IComparable
    {
        public T Data { get; set; }
        public List<Node> Childern { get; set; }
        public Node(T data)
        {
            this.Data = data;
            this.Childern = new List<Node>();
        }
        public void AddNode(Node n)
        {
            this.Childern.Add(n);
        }
        public int FindMaxDepth()
        {
            return FindMaxDeptOnNode(this);
        }
        private int FindMaxDeptOnNode(Node n)
        {
            if (n == null)
            {
                return 0;
            }
            int kidDepth = 0;
            int maxDepth = 0;
            for (int i = 0; i < n.Childern.Count; i++)          
            {    kidDepth = FindMaxDeptOnNode(n.Childern[i]) + 1;      
                 if (kidDepth > maxDepth)
                {
                    maxDepth = kidDepth;
                }
            }
            return maxDepth;
        }
    }

Both BFS and DFS should work.

 
3.Swap 2 nodes in a Binary tree(May or Maynot be a BST). Swap the nodes NOT just their values.
example:


     5 
   /   \ 
  3     7 
 / \   / 
2   4 6

swap 7 and 3


     5 
   /   \
  7     3
 /     / \ 
6     2   4

Solution:

#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct node {
    int value;
    struct node *left;
    struct node *right;
    explicit node(int value) : value(value),
    left(nullptr), right(nullptr) {}
};
void tree_insert(node **root, int value) {
    if (*root == nullptr)
    {
        *root = new node(value);
    }
    else if ((*root)->value > value) 
    {
        tree_insert(&(*root)->left, value);
    }
    else {
        tree_insert(&(*root)->right, value);
    }
}

void tree_print(node *root) 
{
    if (root == nullptr) return;
    cout << root->value << " ";   
    tree_print(root->left);
    tree_print(root->right);
}
void tree_free(node **root) 
 {
    if (*root == nullptr) return;
    tree_free(&(*root)->left);
    tree_free(&(*root)->right);
    delete *root;
}
void find_node(node **root, int value, node **target)
 {
    if (*root == nullptr) 
   {
        *target = nullptr;
    }
    *target = *root;
    while (*target != nullptr && (*target)->value != value) 
    {
        if ((*target)->value > value) 
            *target = (*target)->left;
        else 
            *target = (*target)->right;
    }
}
void find_parent(node **root, node *node_1, node **parent) 
{
    if (*root == nullptr)
        *parent = nullptr;
    node *target = *root;
    while (target != nullptr && target->left != node_1 && target->right != node_1)
     {
        if (target->value > node_1->value) 
            target = target->left;
        else 
            target = target->right:
    }
    *parent = target;
}
void swap_nodes(node **node_1, node **node_2) 
{
    swap((*node_1)->left, (*node_2)->left);
    swap((*node_1)->right, (*node_2)->right);
    swap((*node_1)->value, (*node_2)->value);
}
void swap_root_node(node **root, node **node_1)  
{
    /* std::cout << "Pointer address node_1 = " << static_cast<void*>(*node_1) << std::endl; */ 
    node *parent_node_1 = nullptr;     
    find_parent(&(*root), *node_1, &parent_node_1); 
    if (parent_node_1->left == *node_1)
     {
        swap_nodes(root, node_1);
        parent_node_1->left = *root;
    }
    else
    {
        swap_nodes(root, node_1);
        parent_node_1->right = *root;
    }
   *root = *node_1;
}

void swap_root_root_child(node **root, node **root_child) {
    if ((*root)->left == *root_child)
    {
        swap_nodes(root, root_child);
        (*root_child)->left = *root;
    }
    else
    {
        swap_nodes(root, root_child);
        (*root_child)->right = *root;
    }
    *root = *root_child;
}

void swap(node **root, node **n1, node **n2)
 {
    if(*root == *n1 || *root== *n2)
 {
        // root -> root_child.
        if(*n1 == *root && (*n2 == (*n1)->left  || *n2 == (*n1)->right))
            swap_root_root_child(root, n2);
       else if(*n2 == *root && (*n1 == (*n2)->left || *n1 == (*n2)->right)) 
            swap_root_root_child(root, n1);
      else {
            // root -> node.
            if(*n1 == *root) 
                swap_root_node(root, n2);
            else 
                swap_root_node(root, n1);
            
        }
    } 
   else
   {
        // node -> node
       swap_nodes(n1, n2);
    }
}
int main() {
    node* root = nullptr;
    tree_insert(&root, 5);
    tree_insert(&root, 10);
    tree_insert(&root, 3);
    tree_insert(&root, 1);
    tree_insert(&root, 4);
    tree_insert(&root, 9);
    tree_insert(&root, 15);
    tree_print(root); 
    cout << endl;
    node *node_1 = nullptr;
    node *node_2 = nullptr;
    find_node(&root, 3, &node_1);
    find_node(&root, 10, &node_2);
    swap(&root, &node_1, &node_2);
    tree_print(root); 
    cout << endl;     
    tree_free(&root);
    return 0;
}

 

4.Given a Binary Search tree of integers, you need to return the number of nodes having values between two given integers. You can assume that you already have some extra information at each node (number of children in left and right subtrees !!)
Solution: You don’t need to keep any extra information. (e.g., size of the left subtree) This is a BST after all and you can use a modified inorder traversal to print the range.
Code:

/* The functions prints all the keys which in the given range [k1..k2].The function assumes than k1 < k2 */
void printRange(struct node *root, int k1, int k2)
{ /* base case */ 
  if ( NULL == root ) return;
/* Since the desired o/p is sorted, recurse for left subtree first If root->data is greater than k1, then only we can get o/p keys in left subtree */
  if ( k1 < root->data )
     printRange(root->left, k1, k2);
   /* if root's data lies in range, then prints root's data */
   if ( k1 <= root->data && k2 >= root->data )
     printf("%d ", root->data );
  /* If root->data is smaller than k2, then only we can get o/p keys in right subtree */
   if ( k2 > root->data )
     printRange(root->right, k1, k2);
}

B.On a balanced BST, this algorithm takes O(log N) time.

struct TreeNode 
{
    TreeNode * left, * right;
    int val, left_subtree_size;
};
int getLess(TreeNode* node, int v) 
{
    if (node == NULL)
        return 0;
    if (v <= node->val)
        return getLess( node->left , v);
    return 1 + node->left_subtree_size + getLess(node->right, v);
}
int Solve(TreeNode * root , int from, int to) 
{
    return getLess(root, to+1) - getLess(root, from); // to+1 to get #values <= to
}

 

5.For a given node in binary search tree find a next largest number in search tree.
Solution:
Algorithm:
The key in this problem is to clarify whether there are parent pointers because parent pointers are not necessary for BST.

  1. Has parent pointers.
    1. The leftmost child of the right child, if your current node has a right child.
    2. If not, find a parent whose left child is the node you’re currently at.
    3. If not, there is no successor.
  2. No parent pointers.
    1. Keep a global variable, say “find_the_node”, and initialized as “false”.
    2. DO “in-order traversal method”.
    3. If find, set “find_the_node” to be true.
    4. The next traversal node is the successor. Otherwise, no successor.

Complexity:

  1. Big-O worst case: O(log(n))
  2. Big-O worst case: O(n)