# Exercises for program assignment during interview

## Table of Contents

## 1 General points

### 1.1 basic skills about programming

To get the offer, one has to have robust programming skills including comprehension of programming language, data structure and common algorithms.

### 1.2 high quality code

robust code, detection of point, boundary of variables

### 1.3 analyze problem, improve the algorithm (time and space)

### 1.4 communication skill

### 1.5 conclusion

I read the book for interview. As short term goal, I focus on the programming skills and robust code.

## 2 basic skills

### 2.1 language

The employer usually use C/C++ as the target language during the interview programming assignment. C/C++ is complex, I summarize the cases I read from the book below.

- construct function.
- the construct function can receive an object of its own type. One have to declare the object as const reference to avoid the recurrence construction because the C++ will copy the object when the argument is a variable instead of reference of variable. In this case, the copy operation will invoke the constructor again, which leads to the recurrence construction.

- = operator
- the return value should be reference of its own, which is *this.
- input argument is declared as reference. *In fact, the reference is always preferable is there is not other constraint, because pass variable will cost a copy operation.
- detect if the input argument is itself.
- release memory before allocating new. Optional: lock.

- singleton
- private constructor, static instance. better to initialize the instance during declaration.

- boundary problem in while loop of arrays using pointer.

### 2.2 data structure

this is a review of what I learned 6 years ago, which concerns the array, character chain, list, tree, pipe, etc.

- difference between array and pointer in C/C++. the pointer can point to the address of array, however, it is not an array, which contain the size information. In addition, the array argument is actually a pointer. That means, when you pass an array to a function and invoke sizeof() to the argument inside the function, you will not get the length of array. So the length of array is an obligated parameter for C/C++ to travel an array.
- array algorithms
- search ordered array

- character chain
- pay attention to the size of character array since the last character is '\0'
- replace character should begin from the end to avoid repeatedly moving the characters.
- character chain in character array is not constant, while assign character chain to pointer will assign a constant. Hence, character array will allocate new memory while character pointer will assign to the same memory.

- List
- pointer of pointer permit the function to modify the head of list
- detect if the pointer to head is NULL or the pointer to the pointer to head is NULL
- pay attention to the head when implementing the list operation.
- do not forget to release the memory during the deletion of list element. Assign NULL to the pointer that point to the deleted memory.
- use std::stack to avoid recursive function since too many recursive level will crash the program.

- Tree
- binary tree, massive pointer operation
- reconstruct binary from two array, which are generated from the binary tree using specific order.

- binary tree, massive pointer operation
- stack (first in, end out)
- use two stacks to implement pipe.

Initialize stack1, stake2.

append: new to stack1

get: if stack2 is empty, move stack1 to stack2, get from stack2

**draw graph to analyze the problem**

- use two stacks to implement pipe.
- pipe (first in, first out)
- use two pipes to implement stack.

Initialize pipe1, pipe2.

append: if pipe1.size()==0: add to pipe1; else add to pipe2

get: move elements from non-empty pipe to empty pipe, but return the last one.

- use two pipes to implement stack.
- conclusion
- pay attention to the size of the container, not enough or too small including empty and unity.
- pay attention to the pointer of current node and the pointer of next since both of them can be NULL.

### 2.3 algorithm

the common algorithms include ordering and search with common data structures.

- sorting of array
- quick sorting
- select a number, then put smaller number to left
and larger numbers to right.
int partition(int data[], int length, int start, int end){ int index = RandomInRang(start, end); Swap(&data[index], &data[end]); int small = start -1; for( index = start; index < end; ++index){ if (data[index]<data[end]){ ++ small; if (small != index) Swap(&data[index], &data[small]); } } ++ small; Swap(&data[small], &data[end]); return small;}

quick sorting can be done by recursively invoking the partition function. In addition, the partition function can be used to find the $k$th large number in the array or the k smallest/largest number.

- other sorting tasks
- put array into two parts, each part contains one kind of
element defined by function
`template<T> bool criterion(T element)`

template<T> void TwoParts(T[] list, unsigned int length, bool (*func)(T)){ T* headPointer = list; T* tailPointer = list+length-1; while(headPointer < tailPointer){ while(func(*headPointer)) headPointer++; while(!func(*tailPointer)) tailPointer++; T swap = *headPointer; *headPointer = *tailPointer; *tailPointer = swap; } }

- search ordered array O(log(n)), use binary search, which treats the middle element to narrow the search range. However, should pay attention to the condition when many elements are the same.
- bit operation
- integer power of number. first, consider the negative power and
zero cases. Second, use bit operation on the power number to
quickly get the result \(a^n=(a^{n/2})^2\).
double powerWithUnsignedExponent(double base, unsigned int exponent){ if (exponent == 0) return 1; if (exponent == 1) return base; double result = powerWithUnsignedExponent(base, exponent>>1); result *= result; if (exponent & 0x1) result *= base; return result;

- find the last bit that is 1 by
`a ^ (a-1)`

. First,`a-1`

will change the bits until the last 1; then xor operation will put the changed bits into 0.double numberOfOne(int n){ int count = 0; while (n){ count ++; n = n&(n-1); return count;

- integer power of number. first, consider the negative power and
zero cases. Second, use bit operation on the power number to
quickly get the result \(a^n=(a^{n/2})^2\).
- Fibonacci, model problem into Fibonacci problem
- A frog can jump one stair or two stair. How many methods when a frog jump to n stair? When the first step is one stair, the rest possible methods is the methods to jump (n-1) stairs. When the first step is two stair, the rest possible methods is the methods to jump (n-1) stairs. So, it is \(f(n) = f(n-1)+f(n-2)\), a Fibonacci function.
- An extension: if the frog can jump to \(n\) stairs, how many methods does it have? Analysis: for stair one, there is one methods, for stair two, there are two methods, for stair three, there are two+one+one. For stair n, there is \(f(n)=f(n-1)+f(n-2)+...+f(0)\) where \(f(0)=1\). \(f(n)=f(n-2)+...+f(0)+f(n-2)+...+f(0)=...=2^{(n-1)}\). Heavily reply on the mathematical induction method.

### 2.4 robust

- cannot use
`d==0`

for double type. - divide 0
int PowerWithUnsignedExponent(double base, unsigned int exponent){ if (exponent == 0) return 1; if (exponent == 1) return base; double result = PowerWithUnsignedExponent(base, exponent >> 1); result *= result; if (exponent & 0x1 ==1) result *= base; return result;