Skip to content

Instantly share code, notes, and snippets.

@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 / 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 / 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 / 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 / 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 / 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 / NArrayTreeSerDe
Created September 13, 2016 14:40
Serialize and DeSerialize of N-Array Tree
//Class Represent NArrayTreeNode
public class NArrayTreeNode<E> {
private E data;
private List<NArrayTreeNode<E>> childs = new ArrayList<>();
public NArrayTreeNode(E data) {
this.data = data;
}
public NArrayTreeNode<E> addChild(NArrayTreeNode<E> child){
@deyindra
deyindra / ClosableResourceIterator
Created October 20, 2016 21:26
FileContentIterartor
import java.io.Closeable;
import java.util.Iterator;
/**
* Iterator which used some resource needs to be closed after execution
* <em>Any concrete {@link ClosableResourceIterator} class either must be initialized with
* try with resource or should call {@link ClosableResourceIterator#close()} after complele
* execution.</em>
* @see Iterator
* @see Closeable
@deyindra
deyindra / isPalinDrome
Last active January 14, 2017 18:36
Given a String return true if any permutation of the String is palindrome
public static boolean isPalinDrome(String str){
if(str==null || str.length()==0){
throw new IllegalArgumentException("Invalid words");
}else{
str = str.trim();
char[] array = str.toCharArray();
Set<Character> sets = new HashSet<>();
for(char ch:array){
boolean add = sets.add(ch);
if(!add){
@deyindra
deyindra / FindPivote
Created January 15, 2017 17:24
Find Pivote of Sorted Array (Rotated or Non Rotated)
//O(log(N)) complexity
public <T extends Comparable<T>> static in findPivote(T[] array){
int low = 0;
int hight = array.length - 1;
while(array[low].compareTo(array[high])>0){
int mid = low + (high -low)/2;
if(array[mid].compareTo(array[high])>0){
low = mid + 1;
}else{
high = mid;