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