lordzuko
BAN USERThere will be three cases
input <--value whose ceil is to be searched
1) either the root.key == input --> in this case return the root.key
2) either the root.right < input --> in this case root will be in the right subtree
3) else the root will be in the left subtree or will be equal to root.key
class node{
int key;
node left;
node right;
public node(int val){
key = val;
left = null;
right = null;
}
}
public class ceil{
public static int Ceil(node root, int input){
if(root == null)
return -1;
if(root.key == input)
return root.key;
if(root.key < input)
return Ceil(root.right, input);
int ceil = Ceil( root.left , input);
return (ceil >= input) ? ceil : root.key;
}
}
/*
I read it from here once : Java Generics and collections --> page 229
We can use make a class that extends class LinkedHashMap, it has a function removeEldestEntry which we can override.
The Idea behind implementation is to have a map and let it grow till it reaches its capacity. Then we can remove the oldest element from the map which is exactly like removing the least recenty element from cache.
Following is the implementation:
*/
class LRUCache<K,V> extends LinkedHashMap<K,V>{
private int maxEntries;
public LRUCache(int maxEntries){
super(16,0.75f,true); // 16 is initial capacity and 0.75f is load factor
this.maxEntries = maxEntries;
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
return size() > maxEntries;
}
}
/*
We can use some data structure which protects the order like LinkedList.
Here I am marking all negatives with 1 and positives with 2 and corresponding to that I am maintaining a linkedlist which we can print at end.
Basically Map one linkedlist to 1 i.e. the mark for negatives and
one with 2 i.e. the mark for positives now print them separately preventing their relative order
*/
import java.util.*;
public class test{
public static void main(String[] args){
LinkedHashMap<Integer,LinkedList<Integer>> m = new LinkedHashMap<Integer,LinkedList<Integer>>();
int a[] = {-1,1,2,-3,2};
for(int i = 0; i< a.length; i++){
if(a[i] < 0){
if(!m.containsKey(1)){
LinkedList<Integer> temp = new LinkedList<Integer>();
temp.add(a[i]);
m.put(1,temp);
}else{
m.get(1).add(a[i]);
}
}else{
if(!m.containsKey(2)){
LinkedList<Integer> temp = new LinkedList<Integer>();
temp.add(a[i]);
m.put(2,temp);
}else{
m.get(2).add(a[i]);
}
}
}
LinkedList<Integer> l = m.get(1);
Iterator i = l.iterator();
while(i.hasNext()){
System.out.print(i.next()+" ");
}
l = m.get(2);
i = l.iterator();
while(i.hasNext()){
System.out.print(i.next()+" ");
}
}
}
Following is a simple merge routine as in mergerSort
- lordzuko October 08, 2015