## 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); ++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 decreasesdouble 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 countint 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);}``