interview-summary

Posted on

I recently finished a tech interview with a local small company. Here is a brief summary for the questions in the interview.

  1. There are n couples invited in a party, husband must come with wives, wives may come alone, what is number of possible gathering?

solution:

we inspect a single family - there are 3 cases:

  1. no one comes
  2. only wife comes
  3. both of them comes

so the number of possible gathering is 3^n.

  1. Detect cycle in a linked list with constant space complexity

Solution:

use the fast/slow pointer idea.

1
2
3
4
5
6
7
8
9
bool hasCycle(ListNode *head) {
    ListNode* slow = head, *fast = head;
    while(slow && fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
  1. Find within a binary array (sorted) the number of 0

Case:

0 0 0 0 0 1
0 1 2 3 4 5

1 1 1 1 1 1
0 1 2 3 4 5

Solution:

use binary search.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int getNumberOfZero(vector<int> array){
    int l = 0, r = array.size();

    while(r - l > 1) {
        int mid = (r+l)/2;
        if (array[mid] == 0) {
	    l = mid;
        }
        else {
	    r = mid;    
        }
    }

    if (array[l] == 0) { 
       return l+1;
    }
    else {
       return l;
    }
}

  1. there is an array,only one element is not repeated;the other elements are repeated and repeated elements are next to each other; find not repeated element.

Case:

4 4 2 2 0 3 3 1 1
0 1 2 3 4 5 6 7 8

Solution:

inspect a property that

before single element: array[x] == array[x+1] if (x % 2 == 0)

after single element: array[x] != array[x+1] if (x % 2 == 0)

use binary search to secure the single element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findNotRepeatedElement(vector<int> array) {
    int l = 0, r = array.size();

    while(r-l > 1) {
	int mid = (r+l)/2;
	if (array[mid] == array[mid^1]) {
	     l = mid;	
        }
	else {
	     r = mid;
	}
    }
	
    return array[r+1];
}
  1. there is a square matrix, rotate it by 90 degree, do it in-place

Case:
1 2 3
4 5 6
7 8 9
=>
3 6 9
2 5 8
1 4 7

Solution:

first doing a mirror image by swapping every column, then swap by diagnoal line.

1
2
3
4
5
6
7
8
9
void rotateBy90Degree(vector<vector<int>>& matrix) {
    int n = matrix.size();   
    for (int i = 0; i < n; i++)
	reverse(matrix[i].begin(), matrix[i].end());
    
    for (int i = 0; i < n; i++)
	for (int j = i+1; j < n; j++)
	    swap(matrix[i][j], matrix[j][i]);
}

6.
extension of N lion-goat-hay problem.

The size of the boat has to be at least $floor(\frac{N}{2})$ to solve this.

Assuming the items are indexed as $N_1, N_2, … N_n$ .

For the case which $n$ is an even number, it requires a constant move of 3 to solve this puzzle.

  1. move with all even-indexed items.
  2. go back with an empty boat.
  3. move with all odd-indexed items.

This is quite straight forward.

For the case which $n$ is an odd number, It requires a constant move of 7 to solve this puzzle.
The key concept is to take $N_1$ as the “lion”, even-indexed items as the “goat”, odd-indexed items except $N_1$ as the “hay”. In short, no matter how large $n$ is, the moves required is always 7. In other words, with a constant time complexity of $O(1)$.

  1. move with all even-indexed items(“goat”).
  2. go back with an empty boat.
  3. move with all odd-indexed item except $N_1$(“hay”).
  4. go back with all even-indexed items(“goat”).
  5. move with $N_1$(“lion”).
  6. go back with an empty boat.
  7. move with all even-indexed items(“goat”).

Step 3 and step 5 can be swapped. The total number of moves should not be changed by this. Moreover, odd-indexed items can be splited arbitrarily into two non-empty groups and be treated as “lion” and “hay”. The conclusion and steps remain the same.

  1. clarification of class/interface/abstract class in Java.

class: A bunch of properties and methods that are common to all the objects that are of the same type.

interface: A blueprint of class with ONLY abstract methods. It describes the general idea for a class to be made and cannot have concrete methods.

abstract class: A class with abstract keyword. It is different from normal class that it should have at least one abstract(not-yet-implemented) method. Or it can be considered as an interface with some concrete method.

In a way, the idea of interface can be described as “pure abstract class” or to say that abstract class is a halfly implemented class; but interface and abstract class are used for different purposes. Abstract class is mainly used for inheritance and it is relatively faster; interface are used for future enhancement and it is relatively slow. A class can implement multiple interface, but one class can only extend from a certain abstract class.