## 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…

## 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…

## 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…

## 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…

## 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….

## 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 =…