Aayush Bahuguna
BAN USERint minDepth(Node root){
if(root == null) return 1;
int l = minDepth(root.left);
int r = minDepth(root.right);
return 1 + Math.min(l, r);
}
We need to design a data structure:
Inserting an interval
Find if a point P belong to any interval
Delete an interval
Let's say we use balanced binary search tree:
Inserting an interval O(logn)
Find if a point P belong to any interval O(logn)
Delete an interval O(logn)
class Node{
double value;
int color; //1 for white, -1 for black
public Node(double value, int color){
this.value = value;
this.color = color;
}
}
class DataStructure{
BTree root; //Balanced binary search tree [RedBlack, AVL]
int e = 0.00001; //Limit
void insert(double a, double b){
root.insert(new Node(a - e, -1));
root.insert(new Node(a, 1));
root.insert(new Node(b - e, 1));
root.insert(new Node(b, -1));
}
void delete(double a, double b){
root.delete(new Node(a - e, -1));
root.delete(new Node(a, 1));
root.delete(new Node(b - e, 1));
root.delete(new Node(b, -1));
}
boolean find(double point){
//We will find two points in BST which is just smaller and just greater than point.
Node l = root.smaller(point);
Nodr r = root.greater(point);
if(l.color + r.color == 2) //Both are white
return true;
return false;
}
}
/*
* Note that insert, delete, smaller, greater of balanced tree can easily
* be implemented in O(logn) time
*/
You can merge starting from 2 lists and then continue. Since there are k lists logk merges are required each merge taking O(n) time. So run time complexity of algorithm is (Onlogk)
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if(lists.size() == 0) return null;
Queue<ListNode> q = new LinkedList<ListNode>();
for(ListNode n : lists){
q.add(n);
}
while(q.size() != 1){
ListNode l1 = q.remove();
ListNode l2 = q.remove();
q.add(merge(l1, l2));
}
return q.remove();
}
public ListNode merge(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
ListNode head = null;
if (l1.val < l2.val) {
head = l1;
l1 = l1.next;
} else {
head = l2;
l2 = l2.next;
}
head.next = merge(l1, l2);
return head;
}
}
public static HashSet<ArrayList<Integer>> allSequences(int N, HashMap<Integer, HashSet<ArrayList<Integer>>> cache){
if(N == 1){
HashSet<ArrayList<Integer> > h = new HashSet<ArrayList<Integer> >();
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
h.add(list);
return h;
}
HashSet<ArrayList<Integer> > allSequence = new HashSet<ArrayList<Integer> >();
for(int i = 1;i < N; i++){
HashSet<ArrayList<Integer>> set = null;
if(cache.containsKey(i)){
set = cache.get(i);
}else{
set = allSequences(i, cache);
cache.put(i, set);
}
for(ArrayList<Integer> list : set){
ArrayList<Integer> l = new ArrayList<Integer>();
l.add(N - i);
l.addAll(list);
allSequence.add(l);
}
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(N);
allSequence.add(list);
}
return allSequence;
}
Since every one has to play match with other.
Total number of matches = n(n-1)/2
Now,
If n is even:
We can schedule n/2 matches every day, completing all matches in n(n - 1)/2n = n - 1 days
If n is odd:
Scheduling n/2 matches one person is left out every time and so completing all matches will take one more day than when n is even
We can schedule matches in n days when n is odd.
Rather than generating all subsets in 2^n time we can do an C(n, k) algorithm for k size subset generation
- Aayush Bahuguna February 22, 2013