Skip to content

Instantly share code, notes, and snippets.

@deyindra
deyindra / Custom List
Last active September 9, 2016 15:21
Write A Custom List which will not allow any duplicate and perform add, contains, delete and random operation in O(1) time
public class CustomList<T> {
private Map<T, Value<T>> map = new HashMap<T, Value<T>>();
private List<Value<T>> list = new ArrayList<>();
private static final Random RANDOM = new Random();
public boolean add(T object){
Value<T> value = map.get(object);
//This mean key does not exists
if(value==null){
value = new Value<>(object,list.size());
@deyindra
deyindra / Instanceof
Created July 27, 2016 04:25
Java instanceOf implementation without using isInstance or isAssignableForm method
public static <T> boolean instanceOf(T object, Class<?> clazz){
if(object==null){
return false;
}else{
Class<?> baseClass = object.getClass();
if (baseClass.isArray() && clazz.isArray()) {
return instanceOf(baseClass.getComponentType(), clazz.getComponentType());
} else
return !(!baseClass.isArray() && clazz.isArray())
&& !(baseClass.isArray() && !clazz.isArray())
@deyindra
deyindra / LCA
Last active July 15, 2016 16:45
Given 2/N distinct Nodes of the BinaryTree (They may or may not exist) find Lowest Common Ancestor of the all these nodes
/** Tree Node class **/
public class TreeNode<E> {
private E data;
private TreeNode<E> left;
private TreeNode<E> right;
public TreeNode(E data) {
this.data = data;
}
@deyindra
deyindra / BinTreeIterator
Last active June 6, 2016 15:35
In Order, Pre Order,Post Order,Level Order and Level Order till certain depth Iterators for Binary Tree
public abstract class AbstractTreeIterator<E> implements Iterator<E> {
protected AbstractTreeIterator(TreeNode<E> root){
assert(root!=null);
}
@Override
public void remove() {
throw new UnsupportedOperationException("remove is not supported");
}
@deyindra
deyindra / ArrayOfClustering
Created June 3, 2016 06:18
Given MXN metrics find number of group of similar Object (cluster of Object) which satisfy a given function
private static <T> boolean isSafe(
final T array[][],
final int rowIndex,
final int colIndex,
final boolean visited[][],
final Predicate<T> predicate){
final int ROW = array.length;
final int COL = array[0].length;
@deyindra
deyindra / KthElement
Last active May 30, 2016 04:28
Find Kth largest or Kth smallest element using Median of Median algorithm
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
public class KthElement {
private static <T extends Comparable<T>> T getMedian(List<T> list){
Collections.sort(list);
@deyindra
deyindra / PrimeNumberIterator
Created May 15, 2016 03:31
PrimeNumberIterator
package org.idey.algo.iterator.generic;
import java.util.BitSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class PrimeNumberIterator implements Iterator<Integer>{
private int upperLimit;
private BitSet bitSet;
private int nextNumber;
@deyindra
deyindra / WorkBreak
Created April 19, 2016 18:44
Word Breaking
public static List<String> wordBreak(String str){
if(str==null){
throw new IllegalArgumentException("Invalid String");
}
List<String> wordList = new ArrayList<>();
String subString="";
boolean isQuoteFound=false;
for(char c:str.toCharArray()){
if(c!=' ' && c!='"'){
@deyindra
deyindra / StringPermutationCombination
Last active April 17, 2016 19:56
String Permutation and Combinarion
public static void generatePermutation(String str, final int index, final String prefix, List<String> list,
final char[] allChars, final char replaceAbleChar){
if(str.equals("")){
list.add(prefix);
}else{
char[] array = str.toCharArray();
if(array[index]!=replaceAbleChar){
generatePermutation(str.substring(index+1),0,prefix+array[index],list,allChars,replaceAbleChar);
}else{
@deyindra
deyindra / MedianIterator
Created April 6, 2016 05:18
MedianIterator
import java.util.Collections;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
public class MedianIterator<T extends Comparable<T>> implements Iterator<T>{
private int size;
private T[] array;
private T median;
private int currentIndex;