.dp-highlighter { font-family: "Consolas", "Monaco", "Courier New", Courier, monospace; font-size: 12px; background-color: #E7E5DC; width: 99%; overflow: auto; margin: 18px 0 18px 0 !important; padding-top: 1px; /* adds a little border on top when controls are hidden */ } /* clear styles */ .dp-highlighter ol, .dp-highlighter ol li, .dp-highlighter ol li span { margin: 0; padding: 0; border: none; } .dp-highlighter a, .dp-highlighter a:hover { background: none; border: none; padding: 0; margin: 0; } .dp-highlighter .bar { padding-left: 45px; } .dp-highlighter.collapsed .bar, .dp-highlighter.nogutter .bar { padding-left: 0px; } .dp-highlighter ol { list-style: decimal; /* for ie */ background-color: #fff; margin: 0px 0px 1px 45px !important; /* 1px bottom margin seems to fix occasional Firefox scrolling */ padding: 0px; color: #5C5C5C; } .dp-highlighter.nogutter ol, .dp-highlighter.nogutter ol li { list-style: none !important; margin-left: 0px !important; } .dp-highlighter ol li, .dp-highlighter .columns div { list-style: decimal-leading-zero; /* better look for others, override cascade from OL */ list-style-position: outside !important; border-left: 3px solid #6CE26C; background-color: #F8F8F8; color: #5C5C5C; padding: 0 3px 0 10px !important; margin: 0 !important; line-height: 14px; } .dp-highlighter.nogutter ol li, .dp-highlighter.nogutter .columns div { border: 0; } .dp-highlighter .columns { background-color: #F8F8F8; color: gray; overflow: hidden; width: 100%; } .dp-highlighter .columns div { padding-bottom: 5px; } .dp-highlighter ol li.alt { background-color: #FFF; color: inherit; } .dp-highlighter ol li span { color: black; background-color: inherit; } /* Adjust some properties when collapsed */ .dp-highlighter.collapsed ol { margin: 0px; } .dp-highlighter.collapsed ol li { display: none; } /* Additional modifications when in print-view */ .dp-highlighter.printing { border: none; } .dp-highlighter.printing .tools { display: none !important; } .dp-highlighter.printing li { display: list-item !important; } /* Styles for the tools */ .dp-highlighter .tools { padding: 3px 8px 3px 10px; font: 9px Verdana, Geneva, Arial, Helvetica, sans-serif; color: silver; background-color: #f8f8f8; padding-bottom: 10px; border-left: 3px solid #6CE26C; } .dp-highlighter.nogutter .tools { border-left: 0; } .dp-highlighter.collapsed .tools { border-bottom: 0; } .dp-highlighter .tools a { font-size: 9px; color: #a0a0a0; background-color: inherit; text-decoration: none; margin-right: 10px; } .dp-highlighter .tools a:hover { color: red; background-color: inherit; text-decoration: underline; } /* About dialog styles */ .dp-about { background-color: #fff; color: #333; margin: 0px; padding: 0px; } .dp-about table { width: 100%; height: 100%; font-size: 11px; font-family: Tahoma, Verdana, Arial, sans-serif !important; } .dp-about td { padding: 10px; vertical-align: top; } .dp-about .copy { border-bottom: 1px solid #ACA899; height: 95%; } .dp-about .title { color: red; background-color: inherit; font-weight: bold; } .dp-about .para { margin: 0 0 4px 0; } .dp-about .footer { background-color: #ECEADB; color: #333; border-top: 1px solid #fff; text-align: right; } .dp-about .close { font-size: 11px; font-family: Tahoma, Verdana, Arial, sans-serif !important; background-color: #ECEADB; color: #333; width: 60px; height: 22px; } /* Language specific styles */ .dp-highlighter .comment, .dp-highlighter .comments { color: #008200; background-color: inherit; } .dp-highlighter .string { color: blue; background-color: inherit; } .dp-highlighter .keyword { color: #069; font-weight: bold; background-color: inherit; } .dp-highlighter .preprocessor { color: gray; background-color: inherit; }

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