Sort By Frequency - Hashing Problem

Problem : Sort elements by their frequency.

Following is the implementation where we store the frequency in hashmap:

Print Non-repeated Elements - Hashing Problems

Problem : Print the non-repeated elements of an array.

Following is the implementation:

Zero Sum Sub-arrays Count - Hashing Problems

Problem : Find the number of sub-arrays whose sum evaluates to zero.

Following is the implementation:

Decimal To Binary Conversion Using Stack

Stack can be used to convert a number into it's binary form.

1. Push the remainder into stack after dividing the number by 2.
2. Keep doing 1, till number>0.
3. Pop the binary remainders 1/0 to get the binary form.

 Following is the program:

 

Arithmetic Expression Evaluation Using Stack

Arithmetic expressions can be evaluated using two stacks - one for operands and other for numeric values.

Algorithm:

1. If element is numeric, push to numeric stack.
2. If element is operand, push to operand stack.
3. If element is "(", ignore. 
4. If element is ")", pop operand from operand stack and pop two numerics from numeric stack - perform the operation and push the result back into numeric stack. 

 Following is the program based on the generic stack implementation using arrays.

Generic Queue Using Resized Array And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a queue from client, we can use Generics and Iterator.

Following is the program:

Generic Stack Using Resized Array And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a stack from client, we can use Generics and Iterator.

Following is the program:

Queue Using Array Resizing - Coursera Algorithms

Queues follow FIFO standard. To implement, we need to maintain two indices to first and last elements of the array, for enqueue and dequeue operations.

Following is the program:

Related Posts: 

Queue Using Linked List - Coursera Algorithms

Stack Using Array Resizing - Coursera Algorithms

When implementing stacks using arrays, we may run into overflow and underflow problems. We can resize the array on need basis by doubling the array in push op when the array has reached it's limit and by halving the array in pop op when the array is just 25% utilized. 

This will result in constant amortized time operations, but ~N in worst case.

Linked list on the other hand has constant time even in worst case. But still, linked list may take more time and memory because of the links. 

If occasional slow ops are bearable, then arrays would be a better option than linked lists. 

Following is the complete program:

Related Posts:  

Stack Using Linked List - Coursera Algorithms

Stack Using Array - Coursera Algorithms

Stack Using Array - Coursera Algorithms

Stack works in a LIFO order. It supports insert, remove, iteration and test for empty operations.

They can be represented using array. An initial capacity for this array is taken as input. We manipulate an index variable for push and pop, instead of actually deleting items from stack.

If using objects in stack, avoid loitering(holding references to objects and preventing GC) by using following code in pop operation:

public String pop() { String item = s[--N]; s[N] = null; return item; } 

Following is the complete program:

Related Posts:  

Stack Using Linked List - Coursera Algorithms