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

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…

Longest increasing subsequence

In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. algorithm: use an array for each element’s longest…

two stack for a queue

points: stack is First In Last Out while queue is First In First Out. stack1 used for push, stack2 used for pop. if we push a, b, c in stack1, when we pop, we push every element into stack2 for pop. when new element comes in, still use stack1 for push. when pop, if stack2…