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)

[iOS] The best way to embed a UITextField in UITableViewCell

    Recently I was struggling in how to put UITextField into UITableViewCell in my application. The target is to let the user to edit text fields in a table and be able to scroll the table at the same time. The idea is very simple, but there comes some challenges if you just directly put a UITextField into a UITableViewCell:

    1. The keyboard presented up will hide the cell (and also the textfield) you choose -- you CANT see what you typed! Even you put scrollTocell method in the text field event handler, it still cant scroll to correct position due to the table does not auto resize itself.
    2. Texts inside the cells will disappear when the user scroll up and down when the keyboard is not resigned.

    Problem 1 is coming from the stupid behavior of iOS keyboard. The keyboard does not care whether it will hide something important. It just showed up.
    Problem 2 is due to the UITableView tends to release cells( and text field inside) automatically when they are out of screen. So if the application does not save the text field data before its releasing, you will loss what you have type. Moreover, because the application loss the pointer to the cell, any methods that trying to access such pointer will crash (like resignFirstResponder).

    After googling for a while, I found the most simplest solution:
   To solve problem 1, just subclass your view controller from UITableViewController UITableViewcontroller will help you doing the table frame resizing and auto scrolling. It will help you auto scrolling to the text field. So the keyboard wont hide. You can also register keyboard event handler and do the resizing yourself.
   To solve problem 2, I write a UITextFieldDelegate which intercept textDidChanged event and save the current string in text field into another data structure. Synchronzing view and model in MVC model can avoid data lossing.

   This instruction is very high level and not clear enough. I will post my sample code later if I have time.

[Objective C] Memory management note(1)

Objective C的memory management 在我看來其實跟C++是一致的。alloc對應到new, dealloc對應到delete。不過因為Objective C又使用了garbage collection，所以我們其實不會真正的用到dealloc來消滅物件，我們只要維持好一個instance的reference counting，GC會在恰當的時間( 也就是物件變成沒人要的小孩，ref. count == 0)時為我們自動dealloc該物件。這樣做的好處是什麼？不讓programmer直接dealloc物件可以相當程度的避免crash。同時memory management也可以保證沒有leakage -- 如果ref.count維持的正確的話。 programmer可以利用retain/ release來手動增減ref. count，雖然不如java/ C#方便，而且大部份初學者都會在這邊浪費一堆時間，但總之還是一個行得通的方法。