Google campus interview

1. Design a web application system. What you need to take care
Guess:   Scalability/ loading balancer, security, robust(network failure /disconnection), database atomicity, compatibility

2. Write a function do print all combination of a string like "ABC" -> {"ABC", "ACB", "BAC",...}
look PIE

3. Write a function computes the mirror of a 1-bit image array (each pixel is one bit). The mirror is an output image which is right-side-left to its central axis.
I die in this question.
At least you need to mention what will happen when byte is not align.
Guess: create helper function:
ReverseBits( int start_bit_offset, int end_bit_offset) and use it on every row.

Microsoft campus interview

1.a Given an int array with size 1001, and each element is an integer from 1 to 1000. There is only one duplicate number in the array. Design a function find such number as fast as possible.
Hint: Sum

1.b How about now the array can has any number of duplicates? How do you find all number has duplicates?
Guess: I use hash table. Not sure if there is better way

2. Suppose you are a tester, you want to design 10 test cases for a function:
    int my_atoi( char*) {}
Hint: your test cases need to include at least: positive/negative, decimal, comma( like '1,000'), illegal char or space, long string for memory leaking testing, a string represents a number larger than MAX_INT

Yahoo phone interview

1. Given an int array, verify if there exist a pair of numbers which has sum to 100. For example,
    {1, 5, 99} -> True
    {1, 5, 100} -> False
    Hint: Sort & use two cursor in opposite direction. One from begin, one from end

2.a Thee is a currency system has 1 cent, 5 cents, 10 and 25. Design a function compute minimum number of coins for an amount of money. For example, f(7) = 3 for {1,1,5}
    Hint: Greedy

2.b Give a currency system that cannot be solved by greedy algorithm
2.c How do you solve the problem in 2.b? DP      

QRM phone interview

1. Obj Oriented
- what is O-O
- what is polymorphism
- what is overwrite/ overload functions
2. Have you ever use any design patterns?
What is singleton
3. Database
- what is identification column
- what is inner / outer join
4. Java
- Abstract keyword
- Have you ever use Java Unit Test?
There is also a program assignment.. I can mail the .doc to you if you need

NVIDIA Interview Question (2)

1. How do you give comments about the following code:
   int f (int x)
   {
        return x = << 3 / 2;   // it's amazing that  divide has higher priority than shifting!
    }

2. If there is rubric cube has 100x100x100 small cubes, how many of them are never touch by player?

3. Will the following code has infinite loop?
    void f( )
    {
          double x = 0;
          double y;
          do{
                y = x ++;
          }while( y -x ! = 0)  // think about 0 and 0.0, and also the floating precision issue
    }

NVIDIA Interview Question (1)

1. what this function do:
    int f (int a){
        int b = 0;
        while( a>>=1)
        {
             b ++;
        }
        return b;
   }
 
   and what input will cause an infinite loop?

2. You have a producer and a consumer. The producer produce 1 elements per cycle for 8 cycles then idle 2 cycles. The consumer consumes 1 elements per cycle for 80 cycles then idle 20 cycles.
What is the bandwidth?
How do you achieve the bandwidth with implementing a queue? and the queue size?

3. Implement a cache interface
    (God this kills me)