## Tuesday, August 11, 2009

### 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 belowbool 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> ();}``

A:
``//--------------------------------//Reverse a linked listvoid 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//untestedvoid stringRemove(char * str1, char * toRemove){    //put the in array    int a, 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 1unsigned 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 vunsigned int c; // c accumulates the total bits set in vfor (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[], 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.

``//untestedint* 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 searchvoid 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 1unsigned 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 vunsigned int c; // c accumulates the total bits set in vfor (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());}``

#### 1 comment :

redi said...

Hi

I read this post two times.

I like it so much, please try to keep posting.

Let me introduce other material that may be good for our community.

Source: Computer interview questions

Best regards
Henry