Programming Interview Questions (2)

Q: Implement a k-reverse function for reversing the elements of a linked list.
A:

Nodeptr ReverseN(Nodeptr head, int number) {
 
    if(number < 2) 
        return head;
    
    Nodeptr pre_sub_list_tail = NULL;
    Nodeptr curr_ptr = head;
    Nodeptr reversed_list_head = NULL;
    
    while(curr_ptr) 
    {
        Nodeptr prev_ptr = NULL;
        Nodeptr nxt_ptr = NULL;
        Nodeptr sub_list_tail = NULL;
        Nodeptr sub_list_head = NULL;
        
        int count = number;
        while(curr_ptr && count) 
        {
            if(number == count) 
                sub_list_tail = curr_ptr;
            
            nxt_ptr = curr_ptr->nxtptr;
            curr_ptr->nxtptr = prev_ptr;
            prev_ptr = curr_ptr;
            curr_ptr = nxt_ptr;
            --count;
            if(curr_ptr == NULL) 
                sub_list_head = prev_ptr;
            else if(count == 1) 
                sub_list_head = curr_ptr;
        }
           
        if(pre_sub_list_tail) 
        {
            pre_sub_list_tail->nxtptr = sub_list_head;
        }
        else 
        {
            reversed_list_head = sub_list_head;
        }
        pre_sub_list_tail = sub_list_tail;
    }
    return reversed_list_head;
 
} 

Q: write a program to find the nth left-truncatable prime.
A:

#include <vector>
#include <iostream>
#include <boost/date_time/posix_time/posix_time_types.hpp>
#include <boost/assign/std/vector.hpp> // for 'operator+=()'
#include <boost/optional.hpp>


///works for p > 2
///we check all single digit truncatable primes in nth_truncatable_prime function below
bool is_prime(long p)
{
    for (long i = 2; i * i <= p; i = (i + 1) | 1)
        if (p % i == 0) 
            return false;

    return true;
}

boost::optional<long> nth_truncatable_prime(long nth_truncatable)
{
    if(nth_truncatable <= 0)
        return boost::optional<long> ();

    typedef std::vector< long >::size_type size_type;
    const size_type initial_size = 200;

    std::vector<long> last_primes;
    last_primes.reserve( initial_size );

    using namespace boost::assign;
    last_primes += 2,3,5,7;

    if(nth_truncatable < 5)
        return boost::optional< long > (last_primes[ nth_truncatable -1 ] );

    ///number of truncatable primes so far 4, i.e., (2, 3, 5, 7)
    int truncatable_primes = 4;
    const int max_power = 9;

    ///iterate through powers (10s, 100s, 1000s, etc.)
    for(int power = 1, mult_factor = 10; power <= max_power; ++power, mult_factor *= 10)
    {
        std::vector< long > current_primes;
        current_primes.reserve( initial_size );

        ///iterate through smaller powers inside the outer power (10s in 100s, 100s in 1000s)
        for(int i = 1; i <= max_power; ++i)
        {
            ///construct a new truncatable prime from previous truncatable primes 
            std::vector<long>::const_iterator itEnd = last_primes.end();
            for(std::vector<long>::const_iterator itBegin = last_primes.begin(); itBegin != itEnd ; ++itBegin)
            {
                const long result = mult_factor * (i) + *itBegin;

                if(is_prime( result ) )
                {
                    ++truncatable_primes;
                    if(truncatable_primes == nth_truncatable)
                        return boost::optional<long> (result);
                    
                    current_primes.push_back( result );
                }
            }
        }
        last_primes = current_primes;
    }
    return boost::optional<long> ();
}

Q: Reverse a linked list
A:

//--------------------------------
//Reverse a linked list
void reverseLinkedList(node **head)
{
    node* tmp = *head;
    node* prev = NULL;
    node* next;

    while(tmp)
    {
        next = tmp->next;
        tmp->next = result;
        result = tmp;
        tmp = next;
    }
    *head = result;
}

Q: Remove the characters in str2 which are in str1
A:

//------------------------------------
//remove the characters in str1 which are in str2
//untested
void stringRemove(char * str1, char * toRemove)
{
    //put the in array
    int a[256], index =0;
    const static unsigned size = 2
    
    for (int i=0; i < 255; i++)
        a[ i ] = 0;

    for (int i=0; i<strlen(toRemove); i++)
        a[ toRemove[ i ] ]=1;

    for (int i=0; i<strlen(str1); i++)
    {
        if ( a[str1[i]] == 1) // to remove
            continue;
        else
            str1[index++] = str1[i];
    }
    str1[index] = '\0';
}

Q: Perform binary search on a sorted but rotated array.
A:

int binary_search(int sortedArray[], int first, int last, int key) 
{

   if (first <= last) {
       int mid = (first + last) / 2;  
       if (key == sortedArray[mid]) 
           return sortedArray[ mid ];   // found it.
       else if (key < sortedArray[mid]) 
           return binary_search(sortedArray, first, mid-1, key);
       else
           return binary_search(sortedArray, mid+1, last, key);
   }
   return -(first + 1);    // failed to find key
}
//-----------------------------
int rotate_search(int sortedArray[], int first, int last, int key) 
{
    if(first <= last)
    {
        int mid = (last + first) / 2;
        
        if(key == sortedArray[ mid ])
            return sortedArray[ mid ];

        int sort_start;
        int sort_end;

        int unsort_start;
        int unsort_end;

        if (first < mid)
        {
            sort_start = first;
            sort_end = mid;

            unsort_start = mid;
            unsort_end = last;
        }
        else 
        {
            sort_start = mid;
            sort_end = last;

            unsort_start = first;
            unsort_end = mid;
        }
        if (key <  sortedArray[ sort_end ])
            return binary_search(sortedArray, sort_start, sort_end - 1, key);
        else
            return rotate_search (sortedArray, unsort_start + 1, unsort_end, key);
    }
    return -1;
}

Q: Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.

int countDuplicates(int* a, int N)
{
    int dup = 0;
    for(int i = 0; i < N; ++i)
    {
        if(a[ a[i] - 1 ] == -1)
        {
            dup++;
            continue;
        }
        a[ a[i] - 1] = -1;
    }
    return dup;
}

Q: Write a program to check whether the given two logical addresses are in the same page.

A: Since the page boundaries are at 0, 4, 8k …we can see that the page size is equal to 4K. Now assuming we have a 32 bit address space, bits 31-20 will always be the same for one block of 4k bytes of memory since 4k is equal to 4*1024 which is equal to 12 lower order bits of the address. Given two addresses the only thing to be checked is their bits from 31-20. If they are same that means both the addresses lie in the same page. (Assuming int size is 4 bytes else we will use long to store the address)

bool AreOnSamePage (int *a, int *b)
{
    return (a & 0xFFFFF000) == (c & 0xFFFFF000);
} 

Q: Count the number of SET bits in an integer

//Count the number of SET bits in an integer (32-bit)
//Method 1

unsigned int count;
for (unsigned int v = 0; v; v >= 1)
    count += v & 1;

//a better way. Goes through the loop as many as there are set bits.
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
    v &= v - 1; // clear the least significant bit set
}

Q: I want to see if all the ones in a number appear on the right side of the number and all zeros appear on the left, how can I do this most efficiently? (e.g, 00000111 is true but 100010 is false)

    On the right: (x + 1) & x == 0;
    On the left:  (~x + 1) & ~x == 0;

Q: Implement a function to generate fib sequence.
A:

unsigned int fib(unsigned int n)
{
    if(n < 2)
        return n;

    unsigned int i_1 = 1;
    unsigned int i_2 = 0;
    unsigned sum = 0;
    for(unsigned int i = 2; i <= n; ++i)
    {
        sum = i_1 + i_2;
        i_2 = i_1;
        i_1 = sum;
    }
    return sum;
}

unsigned int fibR(unsigned int n)
{
    if (n < 2)
        return n;
    return fib(n - 1) + fib ( n - 2);
}

Q: Print a matrix in a spiral way (i.e., top row, right col, bottom row, left col)
A:

void printSpiral(int a[][6], int rows, int cols)
{
    int topRow = 0;
    int rightCol = cols - 1;
    int bottomRow = rows - 1;
    int leftCol = 0;

    while(topRow <= bottomRow && leftCol <= rightCol)
    {
    //top left to right. TopRow Fixed
        for(int i = leftCol; i < rightCol; ++i)
            std::cout << a[ topRow ][ i ] << std::endl;
        
        for(int i = topRow; i < bottomRow; ++i)
            std::cout << a[ i ][ rightCol ] << std::endl;

        for(int i = rightCol; i > leftCol; --i)
            std::cout << a[ bottomRow ][ i ] << std::endl;

        //left col. bottom to top
        for(int i = bottomRow; i > topRow; --i)
            std::cout << a[ i ][ leftCol ] << std::endl;

        topRow++;
        rightCol--;
        bottomRow--;
        leftCol++;
    }
}

Q: Code to remove spaces from a string.

void removSpaces(char *s)
{
    int i, j = 0;
    
    for (i = 0; s[i]; i++)
    {
        if (isspace(s[i]))
            continue;

        s[j++] = s[i];
    }
    s[j] = 0;
}

Q: Merge two sorted arrays.

//untested
int* merge_arrays(int* dst, const int* src, int size_dst, int size_src)
{
    dst = static_cast<int*>(::realloc(dst, size_dst + size_src) );
    
    while(size_dst > 0 || size_src > 0)
    {
        if(dst[ size_dst ] >= src[ size_src ] )
        {
            dst[ size_dst + sirce_src ] = dst[ size_dst ];
            size_dst--;
        }
        else
        {
            dst[ size_dst + sirce_src ] = src[ size_src ];
            size_src--;
        }
    }
    return dst;
}

Q: Implement preorder, post order and inorder traversals in a single algorithm

traverse(s)
{
    if(s) 
    {
        preorder_queue.add(s);
        traverse(s->left);
        inorder_queue.add(s);
        traverse(s->right);
        postorder_queue(s);
    }
}

Q: Reverse bits in an integer...

unsigned int reverse_bits(unsigned int a)
{
    unsigned int result = 0;
    unsigned int tmp = a;
    while(tmp)
    {
        result = ( 1 << j ) | (tmp & 1);
        tmp >>= 1;
    }
    return result;
}

Q: implement in-place swap:

void my_swap(int& a, int& b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}

Proof: http://en.wikipedia.org/wiki/XOR_swap

Q: Print a tree level by level (BFS algorithm)
A:

//print a binary Tree level by level
//Essentially doing a breadth first search
void BFS(NODE *root)
{
    if (!root)
        return;

    Queue q = new Queue();

    q->Enqueue(root);
    do
    {

        NODE *curr = q->Dequeue();
        print(curr->val);

        if (curr->left)
            q->Enqueue(curr->left);
        if (curr->right)
            q->Enqueue(curr->right);

    }
    while (!q->Empty());
}

Q: Implement a function that returns true if a binary tree is a BST.
A:

/*
 Returns true if the given tree is a binary search tree
 (efficient version).
*/
int isBST2(struct node* node) {
  return(isBSTUtil(node, INT_MIN, INT_MAX));
}

/*
 Returns true if the given tree is a BST and its
 values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
  if (node==NULL) return(true);

  // false if this node violates the min/max constraint
  if (node->data<min || node->data>max) return(false);

  // otherwise check the subtrees recursively,
  // tightening the min or max constraint
  return
    isBSTUtil(node->left, min, node->data) &&
    isBSTUtil(node->right, node->data+1, max)
  );
} 

Q: Count the number of SET bits in an integer.

//Count the number of SET bits in an integer (32-bit)
//Method 1

unsigned int count;
for (unsigned int v = 0; v; v >= 1)
    count += v & 1;

//a better way. Goes through the loop as many as there are set bits.
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
    v &= v - 1; // clear the least significant bit set
}

Q: Get the depth of a binary tree (recursively)
A:

int get_three_depth(Node* root)
{
    if(!root)
        return 0;
    
    return 1 + max( get_three_depth(root->right), get_three_depth(root->left) );
}

Q: Get the depth of a tree iteratively
A:

void BFS(NODE *root)
{
    if (!root)
        return;

    int depth = 1; //root has depth 1
    Queue q = new Queue();

    q->Enqueue(root);
    NODE* nextLevel = NULL;
    if(root->left)
        nextLevel = root->left;
    else if(root->right)
        nextLevel = root->right;
    else
        return depth;

    do
    {
        NODE *curr = q->Dequeue();
        print(curr->val);

        if(nextLevel = curr)
        {
            depth++;
            nextLevel 
        }
        if (curr->left)
            q->Enqueue(curr->left);
        if (curr->right)
            q->Enqueue(curr->right);

        if(!nextLevel)
        {
             if(curr->left)
                 nextLevel = root->left;
             else if(curr->right)
                 nextLevel = root->right;
        }

    }
    while (!q->Empty());
}