algorithm101

Solution to different algorithm problems

Problems

1. Permutation:

Check whether the second string is the permutation of the first one

package: com.permutation

2. Sort:

Different sort implementation

package: com.sort

3. Custom Stack:

Implementation of a custom stack that provide all standard methods (e.g. push, pop, peek, size) of a stack. Moreover, this stack should expose a method called 'peekMax' that should peek the maximum value from the stack with a time complexity of O(1)

package: com.stack

4. Expression Evaluator:

Implementation of binary expression evaluator that adhere to 'Order of Operation'

package: com.expression

5. Island counter:

Count island of earth

package: com.island

6. LRU Cache:

LRU Cache implementation

package: com.cache

7. Excel column name:

MS Excel columns has a pattern like A, B, C, … ,Z, AA, AB, AC,… , AZ, BA, BB, … ZZ, AAA, AAB etc. In other words, column 1 is named as "A", column 2 as "B", column 27 as "AA".

Given a column number, generate its corresponding Excel column name. Following are more examples:

Input  Output
 26 	Z
 51 	AY
 52 	AZ
 80 	CB
 676	YZ
 700	ZX
 702	ZZ
 705	AAC

package: com.excel

8. Find duplicate:

Find duplicate entries in a given integer array.

package: com.dup

9. Expense calculator:

n number of friends went for a trip. Each person spent money on the trip. At the end of the trip they want to settle the expense. Write a method that take the expenses as input and return the list of settlement transactions so that number of settlement transaction should not exceed n

package: com.expense

10. Combination calculator:

Given two int 'n' and 'r', find how many ways you can select 'r' items out of 'n'.

package: com.combination

11. Predictive Search:

Predictive search in sorted List of String.

package: com.predictivesearch

12. Shortest path in maze:

A maze(M) is represented by n-by-n matrix, each cell has a value of either 0 or 1. A cell indicates a wall if its value is 1. give the length of the shortest path from M[0][0] to M[n-1][n-1]. You can move either up, down, left or right

package: com.maze