Skip to content

Instantly share code, notes, and snippets.

@flexelem
flexelem / DoubleStack.java
Last active February 20, 2020 01:07
Two stacks in one array
import java.util.NoSuchElementException;
/**
* CLRS - Introduction to Algorithms Ex.10.1-2
* Explain how to implement two stacks in one array A[1..n] in such a way that
* neither stack overflows unless the total number of elements in both stacks together is n.
* The PUSH and POP operations should run in O(1) time.
*
* There are two stacks in one array which the first one grows upwards ( A[1..N] ),
* and the second one grows downwards ( A[N..1] ).
@flexelem
flexelem / QueueWithTwoStack.java
Created May 4, 2014 20:54
Queue implementation with using two stacks
import java.util.NoSuchElementException;
import java.util.Stack;
/**
* CLRS - Introduction to Algorithms Ex.10.1-6
*
* Show how to implement a queue using two stacks. Analyze the running time of the queue operations
*
* */
public class QueueWithTwoStack {
@flexelem
flexelem / StackWithTwoQueue.java
Created May 4, 2014 22:34
Implement a stack using two queues
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
/**
* Show how to implement a stack using two queues. Analyze the running time of the queue operations.
*
*/
public class StackWithTwoQueue {
@flexelem
flexelem / CountConnectedComponents.java
Created May 11, 2014 21:56
Compute the number of connected components of an undirected graph
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
* This class will compute the number of connected components of an un-directed graph. If graph is fully connected than it will return 1.
*
* @author buraktas
*
*/
@flexelem
flexelem / DFSNonRecursiveTest.java
Created May 18, 2014 18:11
Non-Recursive DFS implementation by using a Stack
package graph.search.dfs;
import static org.junit.Assert.assertEquals;
import graph.entity.Vertex;
import java.util.ArrayList;
import java.util.Arrays;
import org.junit.Before;
import org.junit.Test;
@flexelem
flexelem / ComputeSCC.java
Created May 19, 2014 21:41
Kosaraju's algorithm to find Strongly Connected Components
package compute_strongly_connected_components;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;
public class ComputeSCC {
@flexelem
flexelem / BinarySearchTree.java
Last active August 29, 2015 14:02
Binary Search Tree implementation
public class BinarySearchTree {
private Node root;
public BinarySearchTree() {
this.root = null;
}
public BinarySearchTree(Node root) {
@flexelem
flexelem / minHeap.java
Created June 8, 2014 15:32
A min heap implementation in java.
import java.util.ArrayList;
public class MinHeap {
private ArrayList<Integer> list;
public MinHeap() {
this.list = new ArrayList<Integer>();
}
@flexelem
flexelem / FindNextGreatestGivenArray.java
Last active August 29, 2015 14:02
Given an array of number find the next greater no in the right of each element.
import java.util.Stack;
public class FindNextGreatestGivenArray {
// works in O(n*n)
public int[] findNextGreatestNumbers(int[] numbers) {
if (numbers == null) {
throw new IllegalArgumentException("Given array is null");
}
@flexelem
flexelem / LinkedList.java
Created June 13, 2014 10:46
Reverse a LinkedList
public class LinkedList {
public class Node {
int data;
Node next;
public Node(int item) {
this.data = item;