Balanced Tree detection

Implement a algorithm to check if a tree is balanced, given its root node. i.e. "no two leaf nodes should differ in distance from the root by more than one". use the function prototype- bool IsBalanced(node *root)

             3
           /  \
          8    8
         / \   /
        5   5 7

Answer:


Solution 1:
Using Level Order traversal,

bool IsBalanced(Node *root)
{
    Queue q;
    size_t prev_depth = 0;
    // We add the node, and the depth at which it
    // occurs
    q.enqueue( make_pair(root,0) );
    while ( !q.isempty() )
    {
        pair node_depth_info = q.dequque();
        Node* node = node_depth_info.first;
        size_t cur_node_depth = node_depth_info.second;
        if ( !node->left && !node->right )
        {
            // leaf!
            if (prev_leaf_depth != cur_node_depth)
            {
                // previous leaf depth is not same as the current one
                return false;
            }
            prev_leaf_depth = cur_node_depth;
        }
        // Add the children 
        if ( node->left )
            q.enqueue( make_pair(node->left, cur_node_depth + 1) );
        if ( node->right)
            q.enqueue( make_pair(node->right, cur_node_depth + 1) );
    }
    return true; // hurray!
}

Solution 2:

Do a traversal, pass the depth of prev tree node and current depth info to next traversal

bool __isBalanced(Node *root, size_t &prev_tree_depth, size_t &cur_depth)
{
    if ( root )
    {
        if ( !root->left && !root->right )
        {
            bool isLeftBalanced, isRightBalanced;
            if(!prev_tree_depth) prev_tree_depth = cur_depth; // first time init
            else
            {
                if (cur_depth != prev_tree_depth) return false; // does not match
                prev_tree_depth = cur_depth; // update
            }
        }
        cur_depth += 1;
        isLeftBalanced = __isBalanced(root->left, prev_tree_depth, cur_depth);
        if ( isLeftBalanced )
            isRightBalanced = __isBalanced(root->right, prev_tree_depth, cur_depth);
        else
            return false;
        return isLeftBalanced && isRightBalanced;
    }
    return true;
}

bool isBalanced(Node *root)
{
    size_t prev_tree_depth = 0, cur_depth = 1;
    return __isBalanced(root, prev_tree_depth, cur_depth );
}

Min element in a sorted array

Given an array, which has been sorted in ascending order and rotated, how will you go about
finding the min element in it.

Answer:

Let original array be 10 20 30 40 50 , so on rotation it become 40 50 10 20 30
40 50 10 20 30
 ^  ^
Up Down

up = array.begin();
down = Up+1;

while(down != array.end() )
{
  if(*down < *up ) then *down is the smallest element
  ++up;
  ++down;
}

Combinations of Brackets

Develop an algorithm to find out all valid combinations of n brackets. Like for n =3 possible combinations can be ((())) or ()()() or (()()) and so on.
Answer:

Use a stack. 
while( not end of input )
{
  ch = input character
  if ( ch is '(' ) then push it to stack.
  else pop from stack., and if the poped item is not '(' then error.
}
The stack should be empty now.

permutations

In how many ways can n professors sit around a cirular table? Consider two seatings to be the same if one can be rotated to form the other
Answer:

Total No of Permutation - Number of Circular Permutations = n! - n

Split a sentence on a word

Token a string on the basis if a given delimiter.
e.g S is the base string and D is the delimiter (could be a sequence of
any valid chars)
S = ["who is the man who saw the eagle today went the wrong way?"]
D = ["the"]
Result = ["who is ", " man who saw ", " eagle today went ", " wrong way?"]

Answer:
Solution 1: Represent the words as a linked list, then when the node does not match
the delimiter, output it. We can use a hash value stored along with the nodes to help in better comparision.

cyclic permutations of a string

Write and algo to check if two strings are cyclic permutations of each other?
Ex : "abcde" and "deabc"

Answer:

1. Append the second the string with itself, we get, deabcdeabc O(n)
2. When we do step 2, notice that the first string occurs as a substring.
3. Search for the original string in the appended string. (O(2n) for space + O(n) time if suffix trees are used and this step depends on which sub string search algo we use)

|---||---|
deabcdeabc
  ^^^^^

Maximum depth of a tree

Write algo to find the max depth of a binary tree.
Answer:

size_t MaxDepth(Node *root)
{
  if(root)
  {
     return max( MaxDepth(root->left) , MaxDepth(root->right) ) + 1;
  }
  return 0;
}

Intersection of two arrays.

Given two arrays of signed integers, give an approach to find the
intersecting set of the two arrays.

Answer:


Solution 1: O(nlog(n)) solution

void ArrayIntersection(int *a, int*b , size_t sizeA, size_t sizeB)
{
    sort(a,sizeA);
    sort(b,sizeB);
    for(size_t i =0, j=0; i < sizeA && j < sizeB; )
    {
        if (a[i] == b[j])
        {
            /* Add a[i] to output intersection list */
            ++i;++j;
            continue;
        }
        else if (a[i] < b[j] )
        {
            ++i; continue;
        }
        else if (a[i] > b[j] )
        {
            ++j; continue;
        }
    }
}

Solution 2: O(n) solution but requires at least O(n) space.
1. Scan the first array and add the elements to a lookup.
2. Scan the second array and if the element is present in the
lookup then add it to the intersection list.

Subarray with a given sum

Given an array, how will find a subarray with a required sum.

Answer:

Solution 1:
Recursively computing the array sum is one of the options, but no optimal.
The trick is to build the array iteratively from the previous results,
for ex: A[0..4]= a[0..3] + A[4]
Complexity : O(m*n/2)

#include 
#include 
#include 
#include 
using namespace std;

int main(int argc, char *argv[])
{
    if (argc <= 1)
        return -1;

    vector a(argc);
    int s[10][10]={};
    const int n = argc-1;

    for(int i = 1; i< argc; ++i)
        a[i] = atoi(argv[i]);

    copy(a.begin(), a.end(), ostream_iterator(cout, " "));
    cout << endl << "----" << endl;

    for(int i = 1; i<= n; ++i)
        s[i][i] = a[i];

    for ( int i = 1; i <= n; ++i )
    {
        for (int j = i+1; j <=n; ++j)
        {
            s[i][j] = s[i][j-1] + a[j];
            printf("[%d][%d] = %d ", i, j, s[i][j]);
            /* if s[i][j] is the required result print it, 
             * and the sub array is [i,j]
             * */
        }
        printf("\n");
    }
    return 0;
}

Find lowest value in BST >= value

Find the lowest valued node in a Binary Search Tree (BST) greater than
or equal to a a certain value.

                    30
                   /  \
                  20  50
                 /   /  \
                15  40  60
                   /  \
                  35  46
                        \
                        47

Solution 1:
O(n) solution:

/*
 * Do a infix traversal of the BST and the moment we get 
 * a node such that >= given value we have the answer.
 * */

void InfixTraversal(Node* root, int value, Node** n)
{
  if(root)
  {
    InfixTraversal(root->left);
    if (root->value >= value) 
    {
      *n = root;
    }
    InfixTraversal(root->right);
  }
}

Solution 2:
O(log(n)) solution:

/*
 * Use the property of the tree, i.e values on the right > root and 
 * values on the left < root.
 * */

void FindNode(Node *root, int value, Node **n)
{
  if(root)
  {
    // move right if the node val is less than reqd value.
    if (root->val < value ) return FindNode(root->right, value, n);
    // the condition is met and the current value is better than than 
    // previously set value.
    if ( (root->val >= value) && (*n && (*n->value > root->value)) )
    {
        *n = root;
    }
    // check in the right subtree for a better value.
    return FindNode(root->left, value, n);
}

/* Let the value = 46 and trace for the above tree */

Products in an array

There are a set of 'n' integers. Describe an algorithm to find for each of all its subsets of n-1 integers the product of its integers.

For example, let consider (6, 3, 1, 2). We need to find these products :

- 6 * 3 * 1 = 18
- 6 * 3 * 2 = 36
- 3 * 1 * 2 = 6
- 6 * 1 * 2 = 12

Answer:

Solution 1:

Find the product of all elements in the array.
for ( i=0 to n-1)
{
  compute product/a[i];
}

Solution 2:
Find the combinations, nCn-1 = n and compute the product for each combination.

Merge unsorted linked lists

Write the algorithm to merge two unsorted linked lists.

Answer:^[1]

The bucket sort will give the best performance.

Add both the linked lists to a bucket data structure and then its simple to perform the bucket sort.

The complexity depends on the input values and how well they can be uniformly distributed among the buckets.

Implement a Queue using two stacks.

Write and algorithm to implement a Queue using 2 Stacks.

Answer:

class Queue
{
    private:
        Stack s[2];
    public:
        Enqueue(T item)
        {
            if ( last operation was enqueue )
            {
                S[1].push(s[0].pop());
                s[0].push(item);
            }
            else
            {
                while( !s[0].isempty() )
                {
                    s[1].push( s[0].pop() );
                }
                s[0].push(item);
            }
        }

        Dequeue()
        {
            if( last operation was dequeue)
            {
                return s[0].pop();
            }
            else
            {
                while(!s[1].isempty())
                {
                    s[0].push( s[1].pop() );
                }
                return s[0].pop();
            }
        }

};

processor problem

40% of a program will not benefit from additional processors because it is inherently sequential. How many processors are needed to execute a program in 150 seconds, if it required 300 seconds with 1 processor.

Answer:

40% of a program will not benefit => 40% of 300 seconds = 120 seconds cannot be reduced.
the remaining 180 seconds should be brought down to 30 seconds, to make it, 120 + 30 = 150 seconds.
This needs 180/30 = 6 processors

Deleting a node in circular linked list in constant time

You are given a circular single linked list of sufficiently many number of nodes(in the millions). You need to delete a node say P and you are given a pointer to P in the circular single list. Suggest the most efficient methodology of deleting the node P from the circular single linked list without rounding about the circular single linked list.

Answer :
Copy the contents of the next node
tmp = cur->next;
cur->next = this->next->next;
delete tmp

Reverse the words in a string

Given an array of characters which form a sentence of words, give an
efficient algorithm to reverse the order of the words (not characters)
in it.

Answer:^[1]

Method 1:
I am a good boy
<------------->

yob doog  a   ma   I
<-> <--> <->  <-> <->

boy good a am I

Method2
Another way to do it is, allocate as much memory as the input for the final output. Start from the right of the string and copy the words one by one to the output.


Input  : I am a good boy
                     <--
                <-------
              <---------
           <------------
         <--------------
  

Output : boy
       : boy good
       : boy good a 
       : boy good a am 
       : boy good a am I 


The only problem to this solution is the extra space required for the output and one has to write this code really well as we are traversing the string in the reverse direction and there is no null at the start of the string to know we have reached the start of the string!. One can use the strtok() function to breakup the string into multiple words and rearrange them in the reverse order later.


Method3

Create a linked list like


+---+    +----------+    +----+    +----------+    +---+    +----------+ 
| I | -> |  | -> | am | -> |  | -> | a | -> |  | --+
+---+    +----------+    +----+    +----------+    +---+    +----------+   |
                                                                           |
                                                                           |
 +-------------------------------------------------------------------------+
 |
 |     +------+    +----------+    +-----+    +------+
 +---> | good | -> |  | -> | boy | -> | NULL | 
       +------+    +----------+    +-----+    +------+



Now its a simple question of reversing the linked list!. 

Array Rotation

Rotate an n-element vector left by i positions in time proportional to n with just a dozen bytes of extra space. For instance, with n=8 and i=3, the vector abcdefgh is rotated to defghabc

Answer:

Step 1: reverse the array.
abcdefgh -> hgfedcba
Step 2: reverse 0 to n-i-1
hgfedcba -> defghcba
Step 3: reverse n-i to n
defghabc

Serializing a Binary Tree

Design an algorithm and write code to serialize a binary tree. Discuss
various solutions

Answer:

Possible answer : Traverse the tree in inorder and store the numbers onto the disk.
then read the numbers and use the logic to create a binary tree from a sorted array.
Like this we will be creating a balanced tree when we deserialize the tree.

Paths of a robot

Consider a point P(n,n) in the cartesian co-ordinate system
A robot has to start from the origin and reach this point. The only steps
the robot can take are :
1 unit right
1 unit up.

How many different paths can the robot take to point P.
Is there an optimal path to point P. (both up and right steps incur the same
cost).

Answer:

/*
 * Paths to (x,y) = Paths to the previous point to left i.e (x-1,y) +
 *                  Paths to the point below i.e (x, y-1) +
 *                  two paths from (x-1, y) and (x,y-1)
 *  */
int Getpaths(Point p)
{
    int paths = 0;
    if ( y > 0 )
        paths += Getpaths( Point(p.x, p.y -1) ) + 1;
    if ( x > 0 )
        paths += Getpaths( Point(p.x-1, p.y) ) + 1;
    return paths;
}

Data structure for elements of 0 - N-1

Propose a data structure for the following:
- The data structure would hold elements from 0 to N-1.
There is no order on the elements (no ascending/descending order
requirement)

The complexity of the operations should be as follows:
* Initialization - O(1)
* Insertion of an element - O(1)
* Deletion of an element - O(1)
* Finding a element - O(1)
* Deleting all elements - O(1)

answer:

use an array (dynamically alloced) of size n.
and array[n] will indicate the count of an element.

n elements are same in a array

Given an array of 2n elements of which n elements are same and the
remaining n elements are all different. Write a C program to find out the
value which is present n times in the array.

Solution:

1. Sort the array - O(nlog(n))
2. Linear algo to find the dup:

for(int i = 0, j=i+1; j < 2n; ++j)
{
  if( a[j] != a[i] )
  {
     if ( (j-i) == n )
       /* a[i] is the required number */
     else
     {
       /* proceed further */
       i = j;
       j+= 1;
     }
  }
}

Tree, Linked list creation problem

Imagine you have an unbalanced binary search tree. Now make a linked list of all the nodes at every depth(level) of the tree. Assume every node along with a left and a right pointer also has a next pointer. To make the linked list inside the binary tree for every level, the next pointer of the first node at every depth should point to the next node at the same depth in the tree and so on for the other nodes. What is the complexity of your algorithm.

            10
         /      \
        5         20
      /    \    /
     3     6   15

         ~~~~ TO ~~~~
            10
         /      \
        5 ----> 20
      /    \    /
     3---> 6-->15

Answer:

Here is a solution of time and spacecomplexity O(n)
Here we do a breadth first search using a queue, and maintain the previous
node and its depth to create the linked list.

struct Node
{
    int val;
    Node *next;
    Node *left;
    Node *right;
};

void LinkifyTree(Node* root)
{
    Queue q;
    // contains the node and the depth at which the node occurs.
    typedef pair NodeInfo;
    // the previous node and its depth.
    Node *prev_node = NULL;
    int prev_depth = -1;

    q.enqueue(make_pair(root,0));
    while( !q.isempty())
    {
        NodeInfo ni = q.dequeue();
        if (prev_node && (prev_depth == ni.second) )
        {
            /* previous node exists and the depth of the previous
             * node is equal to the current node
             * */
            prev_node->next = ni.first;
        }
        else
        {
            ni.first->next = NULL;
        }
        prev_node = ni.first;
        prev_depth = ni.second;

        /* add the child nodes along with the depth */
        q.enqueue( make_pair(ni.first->left, ni.second+1) );
        q.enqueue( make_pair(ni.first->right, ni.second+1) );
    }
}

Least Common Ancestor in a tree

Given two nodes of a tree, find the least common ancestor.

Case I : Each node has a pointer to its parent node.

Case II : A Binary Search Tree.

Case III : A Normal Binary Tree.

Example:

                          10
                        /     \
                       5       20
                    /    \       \
                   3     6        [21]
                                 /   \
                                15    {30}
                              /  \     /  \
                            13   {16} 25  35
                                   \
                                    17

Least common ancestor of 16, 30 is 21.

Solution:

Case I: Similar to finding the intersection of two linked lists. O(log(n)) complexity

Case II:

/**
 * Find the least common ancestor in a Binary search tree, 
 * assuming n1->val < n2->val
 * NOTE : In a BST there can be only one node between two given values.
 * */
Node* FindLCA_BST(Node *root, Node *n1, Node *n2)
{
    if ( !root )
        return NULL;
    if ( (root->val <= n2->val) && (root->val >= n1->val) )
        return root;
    else if (root->val < min)
    {
        /* goto right, a higher value */
        return FindLCA_BST(root->right);
    }
    else
    {
        return FindLCA_BST(root->left);
    }

}

Case III:

/** Find the Least common ancestor for any given binary tree
 * and two nodes n1, and n2 and either n1 or n2 can be an ancestor
 * of one another.
 * */
bool FindLCA(Node *root, Node* n1, Node* n2, Node** lca)
{
    if(!root)
        return false;
    else
    {
        // Is the current node one of the required nodes;
        bool isCur = (n1 == root) || (n2 == root);
        // check the left subtree
        bool isLeft = FindLCA(root->left, n1, n2, lca);
        // check the right subtree
        bool isRight = FindLCA(root->right, n1, n2, lca);

        if ( (isLeft && isRight)  // both the nodes occur as the children of given node
                || (isCur && isLeft) // either of n1 or n2 is the ancestor of the other.
                || (isCur && isRight) 
            )
        {
            *lca = root;
            return true;
        }
        else
            return isLeft || isRight || isCur; // Let the parent decide the result.
    }
}

Heap problem

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x . You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage.

Solution:

The Heap has n elements,

n n-1 n-2 .....k....3 2 1
               ^^^^^^^^^^
               The Kth largest element happens somewhere in this range, 
               because it is a heap, and every parent >= child.

Possible solution, copy the last k elements to the temporary structure,
and build a heap which will take O(k) time and compare the root with the number x.

Removing duplicates in a sorted array

Write the code to remove duplicates in a sorted array.

Answer:

Method 1^[1]

int removeDuplicates(int a[], int array_size) 
{ 
  int i, j;
  
  j = 0; 


  // Print old array...
  printf("\n\nOLD : ");
  for(i = 0; i < array_size; i++)
  {
     printf("[%d] ", a[i]);
  }
  
  
  // Remove the duplicates ...
  for (i = 1; i < array_size; i++) 
  { 
    if (a[i] != a[j]) 
    { 
      j++; 
      a[j] = a[i]; // Move it to the front 
    } 
  } 

  // The new array size..
  array_size = (j + 1);


  // Print new array...
  printf("\n\nNEW : ");
  for(i = 0; i< array_size; i++)
  {
     printf("[%d] ", a[i]);
  }
  printf("\n\n");



  // Return the new size...
  return(j + 1); 
}

Method 2:
Use the algorithm unique.^[2]

converting from infix to prefix

How do you convert a infix express to prefix.
Ex: a+b*c -> +a*bc

Solution:

1. Scan the expression backwards, and use the same logic as that of conversion to postfix algo. Then reverse the constructed string.
or
2. Using two stacks.^*

Condition variables

Explain condition variables, and how they are used in conjuction with a mutex.

Answer:[1][2][3]

Difference between fork(), clone().

What is the difference between fork(), clone(), and pthread_create() system calls.?

Answer:

Excepts from the manpage:⁺⁺

clone() creates a new process, in a manner similar to fork(). It is actually a library function layered on top of the underlying clone() system call, hereinafter referred to as sys_clone.

Unlike fork(), these calls allow the child process to share parts of its execution context with the calling process, such as the memory space, the table of file descriptors, and the table of signal handlers.

The main use of clone() is to implement threads: multiple threads of control in a program that run concurrently in a shared memory space.

When the child process is created with clone(), it executes the function application fn(arg). (This differs from fork(), where execution continues in the child from the point of the fork() call.) The fn argument is a pointer to a function that is called by the child process at the beginning of its execution. The arg argument is passed to the fn function.

See also:[2]

Subset trees

Given a big tree and a small tree, give an algo to find if the small tree is a subset of the big tree.

Solution 1:

//Time Complexity : O(mn) , where is m and n are the number of nodes in the trees.
bool isSubtree(Node* bigTree, Node* smallTree)
{
    if(!bigTree && !smallTree)
        return true;
    else if( (!bigTree && smallTree) ||
            (bigTree && !smallTree)
           )
        return false;

    if ( bigTree->node == smallTree->node )
    {
        /* If the node value matches, then check the left and right
         * subtrees
         * */
        bool isLeftSubTree = isSubtree (bigTree->left, smallTree->left);
        if (isLeftSubTree)
            isRightSubTree = isSubtree (bigTree->right, smallTree->right);
        if (isLeftSubTree && isRightSubTree )
            return true;
    }
    /* we need to check in left subtree and right subtree */
    isLeftSubTree = isSubtree(bigTree->left, smallTree);
    if (isLeftSubTree )
        return true;
    else
        return isSubtree(bigTree->right, smallTree);

}

Solution 2:

Use a suffix tree.
1. do a traversal { takes O(m) } for the larger tree and create a suffix tree.{ takes O(m) time + O(m) space }

2. do a traversal { takes O(n) } for the smaller tree and check if this pattern exists in the suffix tree. { O(n) time }

Find first non-duplicate character in a string

Find first non-duplicate character in a string.

Solution:

lookup['z'-'a'] = {0}
Pass 1: Traverse the string, and perform ++lookup[string[i]];
Pass 2: Traverse the string, and the first char for which lookup[string[i]] == 1 is the required char.

Reverse a Stack using Recursion

Write a Code to reverse a stack using recursion.

Answer:

template <typename T>
void ReverseStack(Stack s)
{
    if ( s.isEmpty() )
        return; // nothing to do
    else
    {
        T elem = s.Top();
        s.Pop();
        ReverseStack(s);
        s.Push(elem);
    }
}

combinations

Print all combinations of M members of a set of N elements in a sequence such that each set can be obtained from the previous set by deleting one member and adding one member.

or Rather print ⁿC_r

Answer:

#include "stdio.h"
#include "iostream"
#include "algorithm"
#include "iterator"
#include "assert.h"
using namespace std;

int main(int argc, char *argv[])
{
    const size_t n = atoi(argv[1]);
    const size_t k = atoi(argv[2]);
    cout << "N = " << n << " k = " << k << endl;
    assert ( (k <= n) && (k > 0));
    size_t *array = new size_t[n];
    size_t up = 0;
    size_t down = 0;
    int i = 0;
    // Initialize the arrray
    for (i = 1; i <= n; ++i) array[i-1] = i;

    for ( up = 0 , down = up+k-1; down < n; ++up , ++down)
    {
        printf(" \n up %d down %d \n", up, down);
        for( i = down; i < n; ++i )
        {
            swap( array[down], array[i] );
            //--- Print the combination ---
            for(int k = up; k<=down; ++k)
                cout << array[k] << " ";
            cout << endl;
            //--- End Print the combination ---
            swap( array[i], array[down] );
        }

    }
    return 0;
}

Weird expressions (Maximal Munch)

Is the expression a+++++b valid? Similarly is a++++ valid?

Answer:^[1]

for discussion on a+++++b, see [1]

a++++ is invalid, because, a++ returns a rvalue, so the next ++ operator cannot be applied
on the rvalue.

Finding the Minimum element of a stack in O(1) time

Write the algo to return the Minimum element of a stack in O(1) time.

Answer:


Along with the normal stack, use another stack called the min stack.
The top of the min stack is ensured to have the min element as follows.
The elements are added to the min stack as follows:
During Push:
1. If the min stack is empty, then push the element that is being pushed into regular stack.
2. If the min stack is not empty, then if the element being pushed is <= MinStack.Top(), then push the element to MinStack.
During Pop:
3. If the element being popped from the normal stack is < element on min stack, then pop the element from min stack as well, or else leave the min stack untouched.

Ex: 6  8  2 3 7 1 9

After Push:

Regular stack:
6 8 2 3 7 1 9
Min Stack:
6 2 1

After Poping 9:
Regular stack:
6 8 2 3 7 1
Min Stack:
6 2 1

After Poping 1:
Regular stack:
6 8 2 3 7
Min Stack:
6 2

After Poping 3 , 7:
Regular stack:
6 8 2
Min Stack:
6 2

After Poping 2:
Regular stack:
6 8
Min Stack:
6

:
:
:
:
so on

References in C++

Does a reference have a memory location associated with it in C++?
Answer:^[1]

No, for ex:

int a;
int &ra = a;
int *pa = &ra;
*pa = 3;

A ref does not have a seperate memory location and for the same reason you cannot declare a
ptr to ref, for ex:
int &* pra; is illegal.

Strongly, weakly, Dynamic, static typed languages

Explain Strongly, weakly, Dynamic, static typed languages

Answer:[1] [2][3]

Overloading on Return values

In C++ can the functions be overloaded only on return values.

solution:

No, the compiler will flag an error, even if they are simply declared.
For ex:

int Foo();
bool Foo();
int main()
{
}

will generate,

overload.cpp:2: error: new declaration ‘bool Foo()’
overload.cpp:1: error: ambiguates old declaration ‘int Foo()’

Setting row and column to zeros

You are given a 2-dimensional integer array Arr[M][N]. A few of the
elements in this array are zero. Write an algorithm such that if
A[i][j] is zero, all the elements in row i and all the elements in
column j should be set to 0. In other words, if any element is zero,
its entire row and column should be zero.

Answer:

Solution in O(mn) time.

Step 1: Init array[m] = {-1}

Step 2:
for ( i = 0; i< m; ++i )
  for ( j = 0; j < n; ++j)
  {
    if ( matrix[i][j] == 0 )
       array[i] = j;
       break;
  }

Complexity : O(mn)

step 3:
for ( k = 0; k < m; ++k)
{
  if(array[k] != -1)
  {
    for( i = 0; i < m; ++i)
      matrix[k][i] = 0;
    for( i = 0; i < n ; ++i)
      matrix[i][array[k]] = 0;
  }
}

complexity: O(m(m+n))

Total complexity = O(mn) + O(m^2) + O(n)

Sorted Array to Binary Tree

Given a sorted (non-decreasing order) array, write an algorithm to
create a binary tree with minimal height. Do this in O(n).

Answer:

The trick is to add the mid element of the array first, because if the elements are sequentially , then the tree will resemble a linked list.

Node* CreateTree(int* array, size_t begin, size_t end)
{
  if( begin > end )
   return NULL;
  size_t mid = (begin+end) / 2;
  Node* n = CreateNode(array[mid]);
  n->left = CreateTree( array, begin, mid-1 );
  n->right = CreateTree( array, mid+1, end );
  return n;
}

Casts in C++

What are the different types of casts in C++?

Answer: ^{See C++ primer}

Restrictions on overloading operators in C++

What are the restrictions on operator overloading in C++?
Which operators cannot be overloaded in C++ ?

Answer:^[1]

1. It must have at least one user defined type. To prevent overloading of default types.
2. You cannot use an operator that violates the normal usage syntax, for ex: "% userDefinedType" is invalid.
3. The following operators cannot be overloaded, sizeof() typeid() :: . .* ?: const_cast dynamic_cast reinterpret_cast static_cast.

Initialization of a Virtual Base Class.

In a Inheritance hierarchy including virtual base classes, for ex:

           A
          / \  (virtual inheritance of B,C)
         /   \
        B     C
         \   /
          \ /
           D

class A{};
class B : virtual public A{};
class C : virtual public A{};
class D : public B, public C{};

Since the A base class occurs twice in class C, how is it ensured that its initialized or contructed only once, and not twice ( via B's and C's ctor )?

Answer:*

In this case, class D (the most derived class) can make direct calls to the ctor of its super base class A (which is not allowed in cases not involving virtual inheritance ). If this is not done, then the default ctor of class A will be called and then the ctors of B and C are called.

 1 class A
  2 {
  3     public:
  4         A(int a){}
  5         A(){}
  6 };
  7 class B : virtual public A{};
  8 class C : virtual public A{};
  9 class D : public B, public C{
 10     public:
 11         D():A(1),B(),C(){} 
 12 };
 13     
 14 int main()
 15 {
 16     D d;
 17 }

If the inheritance was not virtual, then D's ctor cannot access A's ctor.

Order of Initialization of Base Classes

What is the Order of Initialization of base classes for in a C++ class?

Answer:*



1. Virtual base class subobjects, no matter where they occur in the hirearchy.

2. Non Virtual immediate base classes, in the order they appear in the base class list.

3. Data members of the class in the order they are declared.

Constructor Initilization list vs Initializing in the Ctor body

What is the difference between initializing in Constructor Initialization list Vs Initializing in the body.

Answer:^*

1. "Initializing" in the ctor initalization list is truly initialization, but doing the same in the body of a Ctor is "assignment"
2. The member fields such as const, ref, other objects can only be initialized in a ctor initialization list.
3. More optimal, for example if the "assignment" is done in the ctor body, then the object is already constructed and hence less efficient.
4. Static objects and arrays cannot be initialized in the Ctor Init list.

overloading operator && in C++

Why is it usually discouraged to overload operator && in C++?

Answer:^{[1] [2]}

We can overload the && operator to accept two objects as follows:

bool operator &&(const Thing &, const Thing &);

However, developers will assume short circuting behavior which not work when operator overloading is enabled.

Ex:

Thing& tf1();
Thing& tf2();
if ( tf1() && tf2() ) // ...

will get translated to,

if ( operator &&(tf1(), tf2()) ) // ...

Now the functions tf1 and tf2 both will be called, and the order in which they are called is not fixed. (the arguments to a function can be evaluated in any order according to standard.) Also another problem is that short-circuting behavior of the built-in operator does not occur and is misleading to developers.

Function Overloading

Regarding Function overloading,

- why cannot it be done on return values?

- will simply declaring functions with only different return values, but same args cause any problems?

Difference between mutex and a semaphore

What is the difference between a mutex and a semaphore?

Answer:

According to Operating Systems by William Stallings (2008)^*
-

Mutex is a binary semaphore (A semaphore that takes on only the values 0 and 1). The Key difference between the two is that the process that locks the mutex (sets the value to zero) must be one to unlock it (sets the value to 1).

According to "Professional C# 2005 with .NET 3.0
By Christian Nagel, Bill Evjen, Jay Glynn, Karli Watson, Morgan Skinner" -

A Semaphore can be used by mutliple threads (depending on the count) at once.

In brief,^*
- By semaphore we actually mean counting semaphore. By mutex we actually mean mutex semaphore. A mutex is essentially a binary semaphore. You can replace any Mutex with a Semaphore of MaxCount 1.


- Mutexes are usually more efficient than binary semaphores.


- Mutex has an owner concept: unlocking a mutex can be only done by the thread that locked (or, equivalently, "owns") the mutex.

Given the Infix and Postfix traversal, construct the tree

Given the Infix and Postfix traversal, construct the tree

Answer:
Possible only in cases where there are unique elements.

/**
 * Program to construct a tree from a Infix and prefix traversals.
 * */
#include 
using namespace std;

struct TreeNode
{
    char node;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char ch)
    {
        this->node = ch;
        this->left = 0;
        this->right = 0;
    }
};
template 
TreeNode* CtorTree(RandIter infix_begin, RandIter infix_end, RandIter postfix_begin, RandIter postfix_end)
{
    /* Nothing to add */
    if( (infix_begin == infix_end) || (postfix_begin == postfix_end) )
        return NULL;
    /* The current element in the postfix becomes the root */
    TreeNode *tnode = new TreeNode(*postfix_begin);
    /* Search for the root in infix representation from reverse */
    RandIter j = infix_end;
    while( j>= infix_begin )
    {
        --j;
        if (*j == *postfix_begin)
            break;
    }
    ptrdiff_t num_nodes = j - infix_begin;
    ++postfix_begin;

    /* we have found the corresponding root at location j */
    TreeNode *left_subtree = CtorTree(infix_begin, j, postfix_begin , postfix_begin + num_nodes);
    TreeNode *right_subtree = CtorTree(j+1, infix_end, postfix_begin + num_nodes , postfix_end );
    tnode->left = left_subtree;
    tnode->right = right_subtree;
    return tnode;
}

void Infix_traversal(TreeNode* n)
{
    if (n)
    {
        Infix_traversal(n->left);
        cout << n->node;
        Infix_traversal(n->right);
    }
}

int main(int argc, char ** argv)
{
    if ( argc != 3 )
    {
        cerr << "Usage:" << argv[0] << " infix prefix " << endl;
    }
    else
    {
        char *infix = strdup(argv[1]);
        char *prefix = strdup(argv[2]);
        TreeNode *tree = CtorTree(infix, infix+strlen(infix), prefix, prefix + strlen(prefix));
        cout << endl << "The Infix traversal of the constructed tree : " << endl;
        Infix_traversal (tree);
        free (infix);
        free (prefix);
    }
    return 0;
}

Reverse a singly linked list

Write the code to reverse a singly linked list, using recursion.

Answer:

Node* __reverse(Node *n, Node *next)
{
    if (!n) return NULL;
    if (!next) return n;
    Node *tmp = next->next;
    next->next = n;
    return __reverse(next, tmp);

}

Node* ReverseLinkedList(Node* head)
{
    if (!head) return NULL;
    Node *rev_head = __reverse( head, head->next );
    head->next = NULL;
    return rev_head;
}

Finding anagrams

Do do you check if two strings are anagrams??

Answer O(n) solution:

bool lookup[26] = {false}
scan the first string and initialize the lookup
scan the second string and check if all the alpahbets are present.

Find longest run of a letter in a string

Write a function that returns the longest run of a letter in a string. e.g. cccc in the string abccccdef.

Answer:
O(n) solution which sweeps thru the array..

cur next
 |  |
accccefgggggg

GetRepSeq(const char* str, char **start, size_t *len)
{
    const char* next = str + 1;
    const char* cur = str;
    size_t cur_len = 1;
    *start = 0;
    *len = 1;
    while (*next)
    {
        if ( *next == *cur )
        {
            ++next;
            ++cur_len;
        }
        else
        {
            /* we just encountered a non equal char */
            if ( cur_len >= *len )
            {
                *len = cur_len;
                *start = cur;
            }
            cur = next;
            ++next;
        }
    }
}

Alternative Answer : Sufix trees

Longest Panlindrome in a string

Write a function that returns the longest palindrome in a given string. e.g "ccddcc" in the string "abaccddccefe"

Answer (select to see):

Use Suffix trees (http://www.allisons.org/ll/AlgDS/Tree/Suffix/)

Longest common Substring

Given 2 input strings, find the longest string that occurs in both.

Answer (select to see):

Use Suffix trees (http://www.allisons.org/ll/AlgDS/Tree/Suffix/)

Two numbers in a array that add up to a given number

You are given a array, and a number M. Your goal is to find out which two numbers in the array when added up gives M.

Answer:

Step 1. Sort the array in O(n log (n) )
Step 2. Assuming the number is 50,

Optimization of Step 1:
Instead of sorting the complete array,
- Create the heap
- Remove the root until we hit a number k, such that k >= M
- This will be better than sorting the entire array.

down     up
|         |
10 15 20 30 [50] 90

while ( down < up )
{ 
  if ( a[down] + a[up] > a[num] ) --up;
  else if ( a[down] + a[up] < a[num] ) ++down;
  else /* we found a pair */
}

Permutations

Given n,k, write code to give all permutations of numbers of length 'k', where each 'individual' number can be in the range '1 to n'

Intersection of two arrays

Given two arrays of signed integers, give an approach to find the intersecting set of the two arrays.

sub array with largest sum

You're given an array containing both positive and negative integers and required to find the sub array with the largest sum in O(N) time or rather in single pass.

Answer:

#include 
void FindLargestSubarray( int *a, size_t n)
{
    size_t start = a[0];
    int sum = a[0];
    size_t end = 0;
    int intr_sum = 0;
    for ( int i = 1; i < n; ++i)
    {
        intr_sum += a[i];
        if ( (sum+intr_sum) >= sum )
        {
            sum += intr_sum;
            end = i;
            intr_sum = 0;
        }
        else if ( a[i] > sum )
        {
            start = i;
            end = i;
            sum = a[i];
            intr_sum = 0;
        }
    }
    printf("Start %d End %d Sum %d \n", start, end, sum);
}

int main()
{
    int a1[] = {10, -20, 30, -60, 50, 80, 0, -60};
    int a2[] = {10, 20, 30};
    int a3[] = {-99, -5, -1, -100};
    FindLargestSubarray(a1, sizeof(a1)/sizeof(a1[0]) );
    FindLargestSubarray(a2, sizeof(a2)/sizeof(a2[0]) );
    FindLargestSubarray(a3, sizeof(a3)/sizeof(a3[0]) );
    return 0;
}

K smallest numbers

Given N numbers in an unsorted array, find the K smallest numbers.

placing 0s and 1s in even and odd positions

you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s excedd no. of 1s or vice versa then keep them untouched. Do that in one pass without extra memory.
Ex:
input array: {0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array: {0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }

n similar elements in an array

Given an array of 2n elements of which n elements are same and the remaining n elements are all different. Write a C program to find out the value which is present n times in the array.
(In linear time, constant extra space)

Array subset with sum closest to given number

Given an array, Design an algorithm to find the sub vector with the sum closest to zero.
extenstion: What if we wished to find the sub vector with the sum closest to a given real number t?

Find the repeating number

You are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number? what if i give you the constraint that you can't use a dynamic amount of memory (i.e. the amount of memory you use can't be related to n)?
what if there are two repeating numbers (and the same memory constraint?)

Merging two arrays

Given two sorted integer arrays and the larger array has room for the second. Merge the smaller array into the larger one, in O(n) time and O(1) space.

Answer:

l_begin     l_end         free
 |            |            |
[4][6][8][10][22][ ][ ][ ][ ]

sml_begin small_end
 |        |
[1][2][3][20]

void InplaceMerge(int * l_up, int * l_down, int* s_up, int* s_down)
{
    int* free = l_down + (s_down-s_up);
    while(s_end <= s_begin)
    {
        while(*l_end >= *s_end)
        {
            *free = *l_end;
            --free; --l_end;
        }
        while (*s_end >= *l_end)
        {
            *free = *s_end;
            --free; --s_end;
        }
    }
}

Majority Element of an Array

A majority element in an array A, of size N is an element that appears more than N/2 times (and hence there is atmost one such element)

Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:

I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE

Duplicates in an array

Given an array of length N containing integers between 1 and N, determine if it contains any duplicates.

Array Rotation

Rotate an n-element vector left by i positions in time proportional to n with just a dozen bytes of extra space. For instance, with n=8 and i=3, the vector abcdefgh is rotated to defghabc

unique elements in an array

Implement an algorithm to take an array and return one with only unique elements in it.

Multiplication of numbers

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).