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