Exercises for program assignment during interview

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

robust code, detection of point, boundary of variables

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

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.

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.
• 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
• 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.
• 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.

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;
    

• 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.

• 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;