Coding Interviews: Questions, Analysis & Solutions

1. Listing 3-1. C Code about Arrays and Pointers
   
2. int GetSize(int data[]) {
   
3.     return sizeof(data);
   
4. }
   
5. 
   
6. int _tmain(int argc, _TCHAR* argv[]) {
   
7.     int data1[] = {1, 2, 3, 4, 5};
   
8.     int size1 = sizeof(data1);
   
9. 
   
10.     int* data2 = data1;
    
11.     int size2 = sizeof(data2);
    
12. 
    
13.     int size3 = GetSize(data1);
    
14. 
    
15.     printf("%d, %d, %d", size1, size2, size3);
    
16. }

复制代码

1. Listing 3-2. Java Code to Get a Duplicated Number in an Array
   
2. int duplicate(int numbers[]) {
   
3.     int length = numbers.length;
   
4. 
   
5.     int sum1 = 0;
   
6.     for(int i = 0; i < length; ++i) {
   
7.         if(numbers[i] < 0 || numbers[i] > length - 2)
   
8.             throw new IllegalArgumentException("Invalid numbers.");
   
9. 
   
10.         sum1 += numbers[i];
    
11.     }
    
12. 
    
13.     int sum2 = ((length - 1) * (length - 2)) >> 1;
    
14. 
    
15.     return sum1 - sum2;
    
16. }

复制代码

1. Listing 3-3. Java Code to Get a Duplicated Number in an Array
   
2. int duplicate(int numbers[]) {
   
3.     int length = numbers.length;
   
4.     for(int i = 0; i < length; ++i) {
   
5.         if(numbers[i] < 0 || numbers[i] > length - 1)
   
6.             throw new IllegalArgumentException("Invalid numbers.");
   
7.     }
   
8. 
   
9.     for(int i = 0; i < length; ++i) {
   
10.         while(numbers[i] != i) {
    
11.             if(numbers[i] == numbers[numbers[i]]) {
    
12.                 return numbers[i];
    
13.             }
    
14. 
    
15.             // swap numbers[i] and numbers[numbers[i]]
    
16.             int temp = numbers[i];
    
17.             numbers[i] = numbers[temp];
    
18.             numbers[temp] = temp;
    
19.         }
    
20.     }
    
21. 
    
22.     throw new IllegalArgumentException("No duplications.");
    
23. }

复制代码

1. Listing 3-4. Java Code to Search in a Sorted Matrix
   
2. boolean find(int matrix[][], int value) {
   
3.     int rows = matrix.length;
   
4.     int cols = matrix[0].length;
   
5.     int start = 0;
   
6.     int end = rows * cols - 1;
   
7. 
   
8.     while (start <= end) {
   
9.         int mid = start + (end - start) / 2;
   
10.         int row = mid / cols;
    
11.         int col = mid % cols;
    
12.         int v = matrix[row][col];
    
13. 
    
14.         if (v == value)
    
15.             return true;
    
16. 
    
17.         if (v > value)
    
18.             end = mid - 1;
    
19.         else
    
20.             start = mid + 1;
    
21.     }
    
22. 
    
23.     return false;
    
24. }

复制代码

1. Listing 3-5. Java Code to Search in a Partially Sorted Matrix (Version 1)
   
2. boolean find_solution1(int matrix[][], int value) {
   
3.     int rows = matrix.length;
   
4.     int cols = matrix[0].length;
   
5.     return findCore(matrix, value, 0, 0, rows - 1, cols - 1);
   
6. }
   
7. 
   
8. boolean findCore(int matrix[][], int value, int row1, int col1, int row2, int col2) {
   
9.     if(value < matrix[row1][col1] || value > matrix[row2][col2])
   
10.         return false;
    
11. 
    
12.     if(value == matrix[row1][col1] || value == matrix[row2][col2])
    
13.         return true;
    
14. 
    
15.     int copyRow1 = row1, copyRow2 = row2;
    
16.     int copyCol1 = col1, copyCol2 = col2;
    
17. 
    
18.     int midRow = (row1 + row2) / 2;
    
19.     int midCol = (col1 + col2) / 2;
    
20. 
    
21.     // find the last element less than value on diagonal
    
22.     while((midRow != row1 || midCol != col1)
    
23.             && (midRow != row2 || midCol != col2)) {
    
24.         if(value == matrix[midRow][midCol])
    
25.             return true;
    
26. 
    
27.         if(value < matrix[midRow][midCol]) {
    
28.             row2 = midRow;
    
29.             col2 = midCol;
    
30.         }
    
31.         else {
    
32.             row1 = midRow;
    
33.             col1 = midCol;
    
34.         }
    
35. 
    
36.         midRow = (row1 + row2) / 2;
    
37.         midCol = (col1 + col2) / 2;
    
38.     }
    
39. 
    
40.     // find value in two sub-matrices
    
41.     boolean found = false;
    
42.     if(midRow < matrix.length - 1)
    
43.         found = findCore(matrix, value, midRow + 1, copyCol1, copyRow2, midCol);
    
44.     if(!found && midCol < matrix[0].length - 1)
    
45.         found = findCore(matrix, value, copyRow1, midCol + 1, midRow, copyCol2);
    
46. 
    
47.     return found;
    
48. }

复制代码