.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; }

Sunday, July 22, 2012

Interview

Q: Shuffle a deck of cards (52 integers) - Microsoft

A:
///random shuffle of a pack of cards.
void shuffle(int arr [], size_t size)
{
srand(std::time(NULL));
for(int i = size - 1; size >= 0; --i)
{
int k = rand() % i;
std::swap(arr[i], arr[k]);
}
}


Q: Find if the binary representation of a number is a palindrome.
A:

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


Q: Convert a decimal number to its equivalent Roman Numeral.
A:
std::string toRoman(int n)
{
std::string r;

struct TO_ROMAN {
int num;
const char *str;
} to_roman[] = {
{ 1000, "M", },
{ 900, "CM", },
{ 500, "D", },
{ 400, "CD", },
{ 100, "C", },
{ 90, "XC", },
{ 50, "L", },
{ 40, "XL", },
{ 10, "X", },
{ 9, "IX", },
{ 5, "V", },
{ 4, "IV", },
{ 1, "I", },
};

for (int q = 0; q < sizeof(to_roman) / sizeof(to_roman[0]); ++q)
{
TO_ROMAN *t = &to_roman[q];

while (n >= t->num)
{
n -= t->num;
r += t->str;
}
}

return r;
}


Q: Implement sqrt function.
A: Using the NewTon method of approximation

///using NewTon's method
//make a guess: old_guess
//new_guess = (old_guess + value/old_guess) / 2
//if old_guess increases, the value/old_guess decreases
//however if old_guess increases, the value/old_guess decreases

double my_sqrt(double value)
{
const static double eps = 0.0005;
double old_guess = value / 2;
double new_guess = 0;
do
{
new_guess = (old_guess + value / old_guess ) / 2;
old_guess = new_guess;
double d = abs(new_guess * new_guess - value);
if( d < eps)
d = d;
else
d = d;
}
while( abs(new_guess * new_guess - value) > eps);

return new_guess;
}


Q: Reverse words in a string.
A:
void reverse_words(char * ptr)
{
size_t size = strlen( ptr );
//reverse all characters first
reverse_chars(ptr, 0, size - 1);

int word_start = 0;
int word_end = 0;
char* tmp = ptr;
while(*tmp)
{
word_start = word_end; //or eat up spaces
while(*tmp && *tmp != ' ') //assuming white space separator
{
word_end++;
++tmp;
}
//reverse each word. Do not use space.
reverse_chars(ptr, word_start, word_end - 1);
word_end++; //skip space. Assuming just one space.
++tmp;
}
}


Q: Amazon - Implement an algorithm to generate the prime numbers in the range 1 - 101
A:
void generate_primes()
{
const static int N = 101;
int numbers [ N ] = {0};

for(int i = 2; i <= N / 2; ++i)
for(int j = 2; j <= N / i; ++j)
numbers[ i * j ] = 1;

for(int i = 2; i < N; ++i)
{
if(!numbers[ i ])
std::cout << i << "\n";
}
std::cout << std::endl;

}


Q: Find if a string a is a substring of another string b.
A:
bool is_substr(const char* a, const char* b)
{
size_t size_a = strlen( a );
size_t size_b = strlen( b );

int j = 0, i = 0;
for( i = 0, j = 0; i < size_a, j < size_b; ++i, ++j)
{
if(a[ i ] == b[ j ]) //matching. Keep going
continue;

i = i - j; //return i to the next character after the prev match
j = -1; //reset j = -1, it'll become zero on loop increment

}
return j == size_b;
}


Q: Google - implement a memcpy function.
A:
void* my_memcpy(void * dst, const void* src, int size)
{
char* dst_ptr = (char*)dst;
const char* src_ptr = (char*) src;

while(size--)
*dst_ptr = *src_ptr;

return dst_ptr;
}


Q: Given a number (say, 7251), write a code to give the number of digits it has (i.e. 4 for 7251).

A:
int countDigits(int n)
{
int count = 0;
do
{
++count;
n /= 10;
}
while (n);

return count;
}

//second version. Find the dot and remove it from the count
int countDigits1(double n)
{
std::ostringstream ss;
ss << n;
return ss.str().size();

}



Q: Bloomberg LP: What is a seg fault? Show with code

A: Accessing memory that does not belong to your process. See my blog.

void foo()
{
char* p;
char c;

p = (char*) 0;
c = *p; //generates seg fault
}


Q: Bloomberg - //Bloomberg LP: What does this code do?
void bar()
{
int *p=0;
double *q=0;
printf("%u %u\n",p,q);
p++;
q++;
printf("%u %u\n",p,q);
}

A: It prints 0 0 4 8. First it initialize both pointers to NULL. Increment both pointers. First is int, increments by 4, sizeof(int), second by 8 (size of double).

Q: Amazon. Find out if a tree is a mirror of another tree

boolean isMirror(node1,node2){
if(node1==null){if(node2==null)return true; else return false;}
if(node2==null) return false;
if(node1.data!=node2.data)return false;
if(isMirror(node1.left,node2.right) && isMirror(node1.right,node2.left)) return true;
return false;
}


Q: Write a function that converts an integer into a hex string.
A:
std::string getHex(unsigned int num)
{
static const char* hex_values = "0123456789ABCDEF";
std::string ret;
int i = 0;
for(int i = 0; num; i++, num >>= 4)
{
ret += hex_values[ num & 0xF ];
}
//reverse string
std::string::size_type end = ret.size() - 1;
for(int i = 0; i < end; ++i, --end)
std::swap(ret[ i ], ret[ end]);
return ret;
}


Q: Implement addition without using any loops and without using +.
A:
int add(int p, int q)
{
if(q == 0)
return p;

int k, r;
k = p ^ q; //XOR is called addition modulo 2.
r = p & q; //this is the carry.
return add(k, r<<1);
}

Friday, December 25, 2009

Binding to member variables.

When we use boost::bind to bind to a member function, things are pretty easy. You're making a function object of a usually stand-alone or a member function. But when you bind to a member variable of a class, things get a little hazy. When binding to a member variable, usually, you get a member pointer to the type of the member variable. And if you are using this bind in the context of a STL algorithm, then you apply this data member pointer to the passed in argument. This makes absolutely no sense, but see the code below, and it will hopefully make more sense.


struct entry
{
typedef std::pair<int, bool> conn_type;
entry(int i, bool c) : conn_pair(i, c ) { }
// bool get_connecting() const { return connecting; }
conn_type conn_pair;
};

int main()
{
std::vector<entry> vec;
vec.push_back(entry(1, false));
vec.push_back(entry(2, false));
vec.push_back(entry(3, true));
vec.push_back(entry(4, false));


/// boost::bind(&entry::connecting, _1
/// Make a function object that willa lways return ***connecting***
/// member variable of the passed in object...
/// make a predicate that returns entry::connecting
/// create a member pointer. In this case of type
/// entry::*connectingPtr = &entry::connecting
/// returns _1.*connecting

if(std::find_if(vec.begin(), vec.end(), boost::bind(
&std::pair<int, bool>::second,
boost::bind(&entry::conn_pair, _1))) != vec.end())
{
std::cout << "Hey. Found one" << std::endl;
bool std::pair<int, bool>::*connectingPtr = &std::pair<int, bool>::second;
std::cout << std::boolalpha << vec.front().conn_pair.*connectingPtr << std::endl;
}

return 0;
}


And if you are one of those who think pointers to data members are not useful, think again. The benefit of them is that once you declare a pointer to point to a data member of a type, you can use on different instances of that type. This link explains it clearly: http://stackoverflow.com/questions/670734/c-pointer-to-class-data-member

int main()
{
int Car::*pSpeed = &Car::speed;
Car myCar;
Car yourCar;

//access different instances using the same pointer.
int mySpeed = myCar.*pSpeed;
int yourSpeed = yourCar.*pSpeed;

assert(mySpeed > yourSpeed); // ;-)

return 0;
}



You might argue that you can always add a getter function that returns to you the value you pointed to, and do without pointers headaches. Not so. Like I showed in the example above, sometimes you are using pre-existing classes, like std::pair, and have no better way to have succinct code, except to bind. Oh well.

Friday, September 4, 2009

Un-install a program programmatically (C++ on Windows)

Ever wondered how a program is uninstalled when we remove a program from the control panel? Every installed program stores an uninstallString which is a command to un-install itself in the registry. If you can locate your program by searching for its name (I am using the name 'My Program' here), or if you know the product code, it really is a piece of cake....

Here is a sample program to search the registry for a program called My Program and uninstall it.

#include <iostream>
#include <algorithm>
#include <string>
#include <windows.h>
#include <winreg.h>
#include <iostream>
#include <cstdlib>

bool uninstallMyProgram(HKEY hRootKey,const wchar_t *wzKey);

bool search(HKEY hRootKey, const wchar_t *wzKey)
{
const int KeyNameBufferSize = 512;

LONG result = ERROR_SUCCESS;
TCHAR keyName[KeyNameBufferSize];
DWORD index = 0;
DWORD nameLength = KeyNameBufferSize;
FILETIME lastWriteTime;

HKEY hRegKey;
if(::RegOpenKeyEx(hRootKey, wzKey, 0L, KEY_READ , &hRegKey) != ERROR_SUCCESS)
return false;

while (result == ERROR_SUCCESS)
{
nameLength = KeyNameBufferSize;
result = ::RegEnumKeyEx(hRegKey, index, keyName,
&nameLength, 0, NULL, NULL, &lastWriteTime);

if (result == ERROR_SUCCESS)
{
std::wstring str = wzKey ;
str += keyName;
if(uninstallMyProgram(hRegKey, str.c_str()))
return true;
}

index++;
}
RegCloseKey(hRootKey);
return (result == ERROR_NO_MORE_ITEMS) ? true : false;
}

bool uninstallMyProgram(HKEY hRootKey,const wchar_t *wzKey)
{
const int KeyNameBufferSize = 1024;
wchar_t valueBuffer[ KeyNameBufferSize ];
valueBuffer[0]=0;

DWORD dwType = REG_SZ;
BYTE abValueDat[ KeyNameBufferSize ];
DWORD dwValDatLen = sizeof(abValueDat);
HKEY hKey;

if(::RegOpenKeyEx(HKEY_LOCAL_MACHINE, wzKey, 0, KEY_QUERY_VALUE, &hKey) != ERROR_SUCCESS)
return false;

if(::RegQueryValueEx(hKey, L"DisplayName", 0L, &dwType, abValueDat, &dwValDatLen) != ERROR_SUCCESS)
return false;

wsprintf(valueBuffer,L"%s", (wchar_t*) abValueDat);
if(::_wcsnicmp(L"My Program", valueBuffer, 14) == 0)
{
wchar_t uninstallCommand[ KeyNameBufferSize ];
BYTE retValueDat [ KeyNameBufferSize ];
dwValDatLen = sizeof(retValueDat);

if(::RegQueryValueEx(hKey, L"UninstallString", 0L, &dwType, retValueDat, &dwValDatLen) == ERROR_SUCCESS)
{
::wsprintf(uninstallCommand,L"%s", (wchar_t*) retValueDat );
if(-1 == ::_wsystem(uninstallCommand)) //execute the command to uninstall My Program
{
RegCloseKey(hKey);
return false;
}
RegCloseKey(hKey);
return true;
}
}
RegCloseKey(hKey);
return false; //My Program is not installed
}

int main()
{
const wchar_t* path = L"SOFTWARE\\Microsoft\\Windows\\CurrentVersion\\Uninstall\\";
bool removed = search( HKEY_LOCAL_MACHINE, path);
if(!removed)
removed = search( HKEY_CURRENT_USER, path);
}

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

Monday, June 22, 2009

boost intrusive_ptr

boost::intrusive_ptr is one of the six smart pointer class templates provided by boost. It is interesting in that it is widely used as shared_ptr, but sometiems very useful. It relies on the stored object to provide its own reference counting semantics using two functions that must be called: intrusive_ptr_add_ref and intrusive_ptr_release. These functions take a pointer argument to the pointer that is to be managed and must be defined in the boost namespace, or if the compiler supports Koenig lookup, in the namespace where the arguments are defined.

Read more about intrusive_ptr here: http://www.boost.org/doc/libs/1_39_0/libs/smart_ptr/intrusive_ptr.html

Here is a simple Example I put together for myself to understand how this works.

First, this is a base class that provides reference counting support by defining the intrusive_ptr_add_ref and intrusive_ptr_release. functions.

#include <ostream>
#include <boost/checked_delete.hpp>
#include <boost/detail/atomic_count.hpp>

template<class T>
struct intrusive_ptr_base
{
intrusive_ptr_base(): ref_count(0)
{
std::cout << " Default constructor " << std::endl;
}
//only construct an intrusive_ptr from another intrusive_ptr. That is it.
intrusive_ptr_base(intrusive_ptr_base<T> const&)
: ref_count(0)
{
std::cout << " Copy constructor..." << std::endl;
}

///does nto support assignment
intrusive_ptr_base& operator=(intrusive_ptr_base const& rhs)
{
std::cout << " Assignment operator..." << std::endl;
return *this;
}

friend void intrusive_ptr_add_ref(intrusive_ptr_base<T> const* s)
{
std::cout << " intrusive_ptr_add_ref..." << std::endl;
assert(s->ref_count >= 0);
assert(s != 0);
++s->ref_count;
}

friend void intrusive_ptr_release(intrusive_ptr_base<T> const* s)
{
std::cout << " intrusive_ptr_release..." << std::endl;
assert(s->ref_count > 0);
assert(s != 0);
if (--s->ref_count == 0)
boost::checked_delete(static_cast<T const*>(s));
}

boost::intrusive_ptr<T> self()
{
return boost::intrusive_ptr<T>((T*)this);
}

boost::intrusive_ptr<const T> self() const
{
return boost::intrusive_ptr<const T>((T const*)this);
}

int refcount() const
{
return ref_count;
}


private:
///should be modifiable even from const intrusive_ptr objects
mutable boost::detail::atomic_count ref_count;
};




By inheriting publicly from intrusive_ptr_base, we make available the essential reference counting functions: intrusive_ptr_add_ref and intrusive_ptr_release. Notice that we defined these arguments in the base class, so we defined these arguments int he namespace where the parameters are defined, and the best way to guarantee that the compiler finds them is to put them as friend functions in the base class. We put them as friends to give them access to the private data members. Notice that if we defined them as member functions, they will take the *this pointer and they won't match the expected signature that boost::intrusive_ptr requires. The output statements provided in the class are just for debugging purposes.

To test it:

#include <boost/intrusive_ptr.hpp>
#include "intrusive_ptr_base.hpp"

class Connection : public intrusive_ptr_base< Connection >
{
public:
Connection(int id, std::string tag)
: connection_id( id )
, connection_tag( tag ) {}

Connection(const Connection& rhs)
: connection_id( rhs.connection_id )
, connection_tag( rhs.connection_tag) {}

const Connection operator=( const Connection& rhs)
{
if(this != &rhs)
{
connection_id = rhs.connection_id;
connection_tag = rhs.connection_tag;
}
return *this;
}

private:
int connection_id;
std::string connection_tag;
};

int main()
{
std::cout << "Create an intrusive ptr" << std::endl;
boost::intrusive_ptr< Connection > con0 (new Connection(4, "sss") );
std::cout << "Create an intrusive ptr. Refcount = " << con0->refcount() << std::endl;
boost::intrusive_ptr< Connection > con1 (con0);
std::cout << "Create an intrusive ptr. Refcount = " << con1->refcount() << std::endl;
boost::intrusive_ptr< Connection > con2 = con0;
std::cout << "Create an intrusive ptr. Refcount = " << con2->refcount() << std::endl;

std::cout << "Create an intrusive ptr. Refcount = " << con2->refcount() << std::endl;
std::cout << "Destroy an intrusive ptr" << std::endl;
return 0;
}


We notice that when we construct an object or assign to it, boost::intrusive_ptr calls our functions to increment the reference count.

boost::intrusive_ptr has the same memory footprint as a raw ptr, and can be constructed from any T* raw pointer.

Also, shared_ptr if not used carefully can cause subtle crashes and bugs as I already discussed in this post here. That is, you should never create two shared_ptr objects using the same raw pointer, if you do, the destructor for the controlled resource will be called twice when the shared_ptr objects are destroyed. Instead, copy the first shared_ptr object to create a second shared_ptr object that controls the resource. To avoid it, always create a shared_ptr from another shared_ptr that points to that resource already. But if we use an intrusive_ptr, that problem goes away.

So use intrusive_ptr....

Thursday, March 12, 2009

postmortem debugging (WinDbg)

We write high quality code, but a crash is always possible. So what do you do if it your program crashes? Simple, you analyze the crash dumps, find out where and why it is crashing and fix it. But, what if the crash is not repeatable? Be prepared. The best thing to do is to install a crash dump tool on the computer where the software is going to be run/tested.

When a program error occurs in Windows, the operating system searches for a program error handler to deal with the error. If the system does not find such a handler, the system verifies that the program is not currently being debugged, and if not, it considers the error to be unhandled. The system then processes unhandled errors by looking in registry for a program error debugger. An example error handler is dr watson.

To install Dr. Watson as your crash dump analysis tool, follow these simple instructions here

To install Debugging tools for windows as your crash dump tool, do the following:

  • Download debugging tools for windows from here
  • Install it into your folder of choice, example: C:\Program Files\Debugging Tools for Windows.
  • Register Debugging tools for windows as your default debugger, by running this command from the command prompt: "C:\Program Files\Debugging Tools for Windows\WinDbg" -i" You should see this message confirming that WinDbg is your postmortem debugger:


  • Run regedit (from start->run) and modify this key: HKLM\software\microsoft\windows nt\currentversion\aedebug. Change the value of the key Debugger (creating it if necessary) to the following:
  • "C:\Program Files\Debugging Tools for Windows\cdb.exe" -p %ld -c ".dump /ma /u C:\Dumps\Crash.dmp; q" -e %ld –g

Any dump files from any programs from now on, will be put in C:\dumps\ with a .dmp extension.

Now that you have the dump file, take the .exe and .pdb files of the crashing program, drop them in your code's output directory and double click on the .dmp file. Visual studio will open a dump project for you. Start debugging your program, and it will show you where it crashes. This assumes that you built your program with debug symbols and moderate optimization (or no optmization). If you don't know how to do that, well, ask Google.

Wednesday, March 11, 2009

Add code expiry for hacks in your projects

Sometimes we are under tight deadlines to finish things, and we are forced to put in some hacks and quick fixes int he code, hoping to fix them later and write them propertly. You can add \\todo comments, and other stuff to remind you, but there is nothing better than a compilation error after a certain date.

I found this bit of code online, and just modified it slightly. You can put a compilation timebomb in your code, and once a certain date passes, your code will no longer compile. You'll be reminded to fix what you wanted to fix.

An example is provided here:

#include <iostream>
#include <sstream>

void assert_fail(const char* expr, int line, char const* file, const char* function);
#ifdef WIN32
#define CUSTOM_ASSERT(x) do { if (x) {} else assert_fail(#x, __LINE__, __FILE__, __FUNCTION__); } while (false)
#else
#define CUSTOM_ASSERT(x) do { if (x) {} else assert_fail(#x, __LINE__, __FILE__, __PRETTY_FUNCTION__); } while (false)
#endif //WIN32

/////////////////////////////
#define YEAR ((((__DATE__ [7] - '0') * 10 + (__DATE__ [8] - '0')) * 10 \
+ (__DATE__ [9] - '0')) * 10 + (__DATE__ [10] - '0'))

#define MONTH (__DATE__ [2] == 'n' ? (__DATE__ [1] == 'a' ? 1 : 6) \
: __DATE__ [2] == 'b' ? 2 \
: __DATE__ [2] == 'r' ? (__DATE__ [0] == 'M' ? 3 : 4) \
: __DATE__ [2] == 'y' ? 5 \
: __DATE__ [2] == 'l' ? 7 \
: __DATE__ [2] == 'g' ? 8 \
: __DATE__ [2] == 'p' ? 9 \
: __DATE__ [2] == 't' ? 10 \
: __DATE__ [2] == 'v' ? 11 : 12)

#define DAY ((__DATE__ [4] == ' ' ? 0 : __DATE__ [4] - '0') * 10 \
+ (__DATE__ [5] - '0'))

#define DATE_AS_INT (((YEAR - 2000) * 12 + MONTH) * 31 + DAY)YEAR - 2000) * 12 + MONTH) * 31 + DAY)

#define UNIQUE_NAME( Y,M,D ) ReviewBefore##_##Y##_##M##_##D##_##line
#define REVIEW_DATE( YYYY, MM, DD ) (((YYYY - 2000) * 12 + MM) * 31 + DD)
#define COMPILE_DATE (((YEAR - 2000) * 12 + MONTH) * 31 + DAY)

#define REVIEW_BEFORE( YYYY, MM, DD ) \
static const struct UNIQUE_NAME(YYYY,MM,DD)##__LINE__ { UNIQUE_NAME(YYYY,MM,DD)##__LINE__() { \
assert( COMPILE_DATE < REVIEW_DATE(YYYY, MM, DD) ); \
} } UNIQUE_NAME(YYYY,MM,DD)##__LINE__

#define EXPIRED "This code has expired"
#define REVIEW_BEFORE_STMT( YYYY, MM, DD ) \
CUSTOM_ASSERT(COMPILE_DATE < REVIEW_DATE(YYYY, MM, DD) )

void assert_fail(const char* expr, int line, char const* file, const char* function)
{
std::cerr << "Code obselete" << std::endl;
std::ostringstream str;
str << "Expresion: " << expr << "\n"
<< "line: " << line << "\n"
<< "file: " << file << "\n"
<< "function: " << function << "\n";

std::cerr << str.str() << std::endl;
}

int main()
{
REVIEW_BEFORE_STMT(2000,1,1);
std::cout << COMPILE_DATE << std::endl;

return 0;
}