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