Minimal Number of Coins for Change

Problem: Please implement a function which gets the minimal number of coins, whose value is v1, v2, …, vn, to make change for an amount of money with value t. Any coin with value vi may duplicate for any times to make change.
For example, the minimal number of coins to make change for 15 out of a set of coins with value 1, 3, 9, 10 is 3. We can choose two coins with value 3 and a coin with value 9. The number of coins for other choices should be greater than 3.
Analysis: Firstly let us define a function f(t) which is the minimal number of coins to make change for total value t. If there are n different coins, we have n choices to make change for value t: we can add a coin with value v1 into a set of coins whose total value is t-v1. The minimal number of coins to get value t-v1 is f(t-v1). Similarly, we can add a coin with value v2 into a set of coins whose total value is t-v2. The minimal number of coins to get value t-v2 is f(t-v2)…
Therefore, we divide a problem to calculate f(t) into n sub-problems: f(t-v1), f(t-v2), …, f(t-vn). We can get a formal equation for f(t) as the following accordingly:
This equation can be implemented with recursion easily. However, the recursive solution will cause serious performance issues since there are overlaps when we divide this problem into n sub-problems. A better solution is to utilize iteration, and store the result of sub-problems into a table (as the Table 1).
In the Table 1, each column except the first one is to denote the number of coins to make change for a specific value. We can calculate the numbers in the Table 1 from left to right, to simulate the iterative process to get the result of f(15).
For instance, there are two numbers 4 and 2 under the column title “6”. We have two alternatives to make change for 6: the first one is to add a coin with value 1 to a set of coins whose total value is 5. Since the minimal number of coins to get value 5 is 3 (highlighted number under the column tile “5”), the number in the first cell under column title “6” is 4 (4=3+1). The second choice is to add a coin with value 3 to a set of coins whose total value is 3. Since the minimal number of coins to get value 3 is 1 (highlighted number under the column tile “3”), the number in the second cell under column title “6” is 2 (2=1+1). We highlight the number 2 in the column under tile 6 because 2 is less than 4.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
0
1
2
3
2
3
4
3
4
5
2
2
3
3
4
5
3
0
1
2
3
2
3
4
3
4
5
2
2
3
3
9
0
1
2
3
2
3
4
3
10
0
1
2
3
2
3
4
Table 1: The iterative process to calculate the minimal number of coins to make changes for 15.
Even though we have a 2-D matrix to show the iterative process, it only requires a 1-D array for coding, because it is only necessary to store the minimal number of coins to make change for each total value. The sample code is shown below:
int GetMinCount(int total, int coins[], int length)
{
    int* counts = new int[total + 1];
    counts[0] = 0;
    const int MAX = 0x7FFFFFFF;
    for(int i = 1; i <= total; ++ i)
    {
        int count = MAX;
        for(int j = 0; j < length; ++ j)
        {
            if(i – coins[j] >= 0 && count > counts[i – coins[j]])
                count = counts[i – coins[j]];
        }
        if(count < MAX)
            counts[i] = count + 1;
        else
            counts[i] = MAX;
    }
    int minCount = counts[total];
    delete[] counts;
    return minCount;

}

Advertisements

Maximum Sum of All Sub-arrays

Question: A sub-array has one number of some continuous numbers. Given an integer array with positive numbers and negative numbers, get the maximum sum of all sub-arrays. Time complexity should be O(n).
For example, in the array {1, -2, 3, 10, -4, 7, 2, -5}, its sub-array {3, 10, -4, 7, 2} has the maximum sum 18.
Solution : Analyze arrays number by number
store 1st element as the largest, add the 2nd, if sum is smaller the the current number, discard the current largest and use the current number.
class MaxSub{
 public int findMaxSub(int[] a){
 if(a== null || a.length == 0) return new ImporperInputException();
 if(a.length == 1) return a[0];
 int tempMax=a[0], startIndex=0, endIndex=0; sum=a[0];
 for(int i=1; i<a.length; i++){
 sum=a[i]+tempMax;
 if(a[i] >= tempMax){
 tempMax=a[i]
 startIndex = i;
 endIndex = i;
 sum=a[i];
} else{
 if(sum>tempMax){
 tempMax=sum; endIndex=i;}
}
}
 return tempMax;
}
}

The Least k Numbers

Question: Please find out the least k numbers out of n numbers. For example, if given the 8 numbers 4, 5, 1, 6, 2, 7, 3 and 8, please return the least 4 numbers 1, 2, 3 and 4.
Analysis: The naïve solution is sort the n input numbers increasingly, and the least k numbers should be the first k numbers. Since it needs to sort, its time complexity is O(nlogn). Interviewers will ask us explore more efficient solutions.

1.    use a k data container, and take first k numbers in. then compare the max in the container with the coming numbers, if coming number is smaller then replace. otherwise, next.

 if we use binary search tree, find&insert&delete would be logk, , the complexity would be O(nlogk).
 If max heap, O(1) to get max, but logk to insert and delete.

2. use the partition function which returns the index of pivot in quick sort.

 until we get the index = k-1, we have all the k-1 numbers in the left which are smaller than the pivot(kth number).
void GetLeastNumbers(int[] input, int n, int[] output, int k)
{
    if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
        return;
    int start = 0;
    int end = n – 1;
    int index = Partition(input, n, start, end);
    while(index != k – 1)
    {
        if(index > k – 1)
        {
            end = index – 1;
            index = Partition(input, n, start, end);
        }
        else
        {
            start = index + 1;
            index = Partition(input, n, start, end);
        }
    }
    for(int i = 0; i < k; ++i)
        output[i] = input[i];
}

Post-order Traversal Sequences of Binary Search Trees

Problem: Determine whether an input array is a post-order traversal sequence of a binary tree or not. If it is, return true; otherwise return false. Assume all numbers in an input array are unique.
For example, if the input array is {5, 7, 6, 9, 11, 10, 8}, true should be returned, since it is a post-order traversal sequence of the binary search tree in Figure 1. If the input array is {7, 4, 6, 5}, false should be returned since there are no binary search trees whose post-order traversal sequence is such an array.
Analysis: The last number is a post-order traversal sequence is the value of root node. Other numbers in a sequence can be partitioned into two parts: The left numbers, which are less than the value of root node, are value of nodes in left sub-tree; the following numbers, which are greater than the value of root node, are value of nodes in right sub-tree.
every left and right part need to be “true”.
boolean VerifySquenceOfBST(int sequence[], int length)
{
    if(sequence == NULL || length <= 0)
        return false;
    int root = sequence[length – 1];
    // nodes in left sub-tree are less than root node
    int i = 0;
    for(; i < length – 1; ++ i)
    {
        if(sequence[i] > root)
            break;
    }
    // nodes in right sub-tree are greater than root node
    int j = i;
    for(; j < length – 1; ++ j)
    {
        if(sequence[j] < root)
            return false;
    }
    // Is left sub-tree a binary search tree?
    bool left = true;
    if(i > 0)
        left = VerifySquenceOfBST(sequence, i);
    // Is right sub-tree a binary search tree?
    bool right = true;
    if(i < length – 1)
        right = VerifySquenceOfBST(sequence + i, length – i – 1);
    return (left && right);

}

First Character Appearing Only Once

Problem: Implement a function to find the first character in a string which only appears once.
For example: It returns ‘b’ when the input is “abaccdeff”.
Analysis: Our native solution for this problem may be scanning the input string from its beginning to end. We compare the current scanned character with every one behind it. If there is no duplication after it, it is a character appearing once. Since it compares each character with O(n) ones behind it, the overall time complexity is O(n2) if there are n characters in a string.
better way: a hashTable, key is the character, value is the occurrence. go through the list 2 times:
  1. if 1st time, add into the table, otherwise, add the value.
  2. find the 1st 1 occurrence character

Fibonacci Sequences

Recursive (bad performance):

class Fibonacci{

public int getFibonacci(int n){

if(n==0) return 0;

if(n==1) return 1;

return getFibonacci(n-1) + getFibonacci(n-2)

}

}

Iterative ( O(n) )

class Fibonacci{

public int getFibonacci(int n){

int firstNumber = 0; int secondNumber = 1;

int total = 0;

for(int i = 0; i<=n; i++){

total = firstNumber + secondNumber;

firstNumber = secondNumber;

secondNumber = total;

}

}

}

 

Reverse a Linked List

algorithm: a temp to store previous node, pointing to that in iterator

class ReverseList{

public List reverse(List l){

Node firstNode = l.getFirst();

Node temp = firstNode.next;

firstNode.next = null;

if(l == null || l.isEmpty)

throw new NotValidException();

Node previousNode = firstNode;

Node nextNode = temp;

while(nextNode != null){

nextNode  =  temp.next;

temp.next = previousNode

previousNode = temp;

}

return l;

}

}