CareerCup

package LRU_Cache;


/*Implement_LRU_Cache
A cache is a mechanism by which future requests for that data are served faster
and/or at a lower cost.
Requirements
1. Fixed size: The cache needs to have some bounds to limit memory usage.
2. Fast access: O(1) cache insert and lookup operations.
3. Entry replacement algorithm: When the cache is full, the less useful cache
entries are purged from cache. The algorithm to
replace these entries is Least Recently Used (LRU)
or the cache entries which have not been accessed recently will be replaced.
 */
import java.util.*;

public class leetcode_Implement_LRU_Cache {

    public static void main(String[] args) {
        // Test case 1.
        LRUCache lrucache = new LRUCache(2);

        print(lrucache.get(1) == -1);

        lrucache.set(2, 1);
        lrucache.printDLL();
        lrucache.set(1, 1);
        lrucache.printDLL();
//        print(lrucache);
        print(lrucache.get(2) == 1);
        lrucache.printDLL();
//        print(lrucache);

        lrucache.set(4, 1);
        lrucache.printDLL();
        print(lrucache.get(1) == -1);
        print(lrucache.get(2) == 1);
        lrucache.printDLL();
    }

    public static void print(Object obj) {
        System.out.println("print :: " + obj);
    }
}

class LRUCache {

    private int capacity;
    private HashMap<Integer, LRUNode> cache; // HashMap to support O(1) get.
    private LRUNode anchor; // Root of DLL

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<Integer, LRUNode>();

        this.anchor = new LRUNode(Integer.MAX_VALUE, Integer.MAX_VALUE);
        this.anchor.left = this.anchor;
        this.anchor.right = this.anchor;
    }

    public int get(int key) {
        LRUNode node = this.cache.get(key);
        if (node != null) {
            moveToTop(node);
            return node.value;
        } else {
            return -1; // Check the requirement. Normally it returns null.
        }
    }

    public void set(int key, int value) {
        LRUNode node = this.cache.get(key);
        if (node != null) {
            moveToTop(node);
            node.value = value;
        } else {
            LRUNode newNode;
            if (this.cache.size() >= this.capacity) {
                // Unlink from ddl and reuse the object.
                System.out.println(" anchor.left.key :: " + anchor.left.key);
                newNode = remove(this.anchor.left.key);
                newNode.key = key;
                newNode.value = value;
            } else {
                newNode = new LRUNode(key, value);
            }
            linkAsTop(newNode);
            this.cache.put(key, newNode);
        }
    }

    private LRUNode remove(int key) {
// Remove a key/value node from cache.
        LRUNode node = this.cache.get(key);
        this.cache.remove(key);

// Unlink and remove from dll.
        LRUNode left = node.left;
        LRUNode right = node.right;
        left.right = right;
        right.left = left;
        return node;
    }

    private void linkAsTop(LRUNode node) {
        // Link node to anchor'right in dll.
        LRUNode anchor = this.anchor;
        LRUNode anchor_right = anchor.right;

        node.left = anchor;
        node.right = anchor_right;
        anchor_right.left = node;
        anchor.right = node;
    }

    private void moveToTop(LRUNode node) {
        // Unlink node from its current position.
        LRUNode left = node.left;
        LRUNode right = node.right;
        left.right = right;
        right.left = left;
        linkAsTop(node);
    }

    public String toString() {
        String ret = "";
        LRUNode node;
        for (int key : this.cache.keySet()) {
            node = this.cache.get(key);
            ret += "<" + key + ", " + node.value + ">\n";
        }
        return ret;
    }

    public void printDLL() {
        LRUNode cursor = this.anchor;
        while (cursor.right != this.anchor) {
            System.out.print(cursor.right + " ");
            cursor = cursor.right;
        }
        System.out.println();
    }

    public void clear() {
        this.cache.clear();
        this.anchor.left = this.anchor;
        this.anchor.right = this.anchor;
    }
}

class LRUNode {

    public LRUNode left;
    public LRUNode right;
    public int key;
    public int value;

    public LRUNode(int key, int value) {
        this.left = null;
        this.right = null;
        this.key = key;
        this.value = value;
    }

    public String toString() {
        return "<" + this.key + ", " + this.value + ">";
    }
}

This question is not clear to me. If possible can you please explain the question in brief manner. Seems like it is a system design question

package FindingSumOfSmallerElementsOnLeft;

public class FindingSumOfSmallerElementsOnLeft {

    public static void main(String[] args) {
     int[] Arr = { 2, 3, 8, 6, 1 ,10};

            //Sum of prev small numbers in arr
            BST ob = new BST();
            for (int i = 0; i < Arr.length; i++)
            {
                System.out.println(ob.AddNodeAndReturnSumOfPrevSmallNumInArr(Arr[i]));
            }
            
            ob.inOrder();
    
}
}


class BST
    {
        class TreeNode
        {
            public int data;
            public TreeNode left;
            public TreeNode right;
            public int Sum; //for SumOfPrevSmallNumInArr

            public TreeNode(int val)
            {
                this.data = val;
                this.left = null;
                this.right = null;
                this.Sum = 0;
            }

            public TreeNode(int val, int index)
            {
                this.data = val;
                this.left = null;
                this.right = null;
                this.Sum = 0;
            }

            public TreeNode()
            {
                this.data = 0;
                this.left = null;
                this.right = null;
                this.Sum = 0;
            }
        }

        TreeNode Root;
        public BST()
        {
            Root = null;
        }

        public int AddNodeAndReturnSumOfPrevSmallNumInArr(int val)
        {
            TreeNode Node = new TreeNode(val);
            if (Root == null)
            {
                Root = Node;
                return 0;
            }

            TreeNode cur = Root;
            TreeNode Prev = null;
            int Sum = 0;

            while (cur != null)
            {
                Prev = cur;
                //If moving towards right add the current node's value and its 
                //sum value to the sum being calculated to return.
                if (val >= cur.data)
                {
                    Sum += cur.data + cur.Sum;
                    cur = cur.right;
                }
                //If moving towards left add the value to current node's sum.
                else
                {
                    cur.Sum += val;
                    cur = cur.left;
                }
            }
            if (val >= Prev.data)
                Prev.right = Node;
            else 
                Prev.left = Node;
            
            return Sum;
        }
        
         public void inOrder(){
             inOrder(Root);
         }
        
        public void inOrder(TreeNode t){
            if(t==null) return;
            
            inOrder(t.left);
            System.out.print(t.data + " ");
            inOrder(t.right);
        }
}

Fully working Code in java :::

Time Complexity :: O(n) Bottom Up Approach
Space Complexity :: O(1) not considering recursion stack space

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author nikhil.agrawal
 */
public class UnivaluedSubTree {
    
    public static void main(String[] args) {

        TreeNode root = new TreeNode(2);
        TreeNode r2 = new TreeNode(2);
        TreeNode r3 = new TreeNode(2);
        TreeNode r4 = new TreeNode(3);
        TreeNode r5 = new TreeNode(3);
        TreeNode r6 = new TreeNode(3);
        TreeNode r7 = new TreeNode(3);
        
        root.left=r2;
        root.right=r3;
        
        r2.left=r4;
        r2.right=r5;
        r3.left=r6;
        r3.right=r7;
        
        
        countingUnivaluedTree(root);
        
    }
    
    
    static int count =0;
    
    static void countingUnivaluedTree(TreeNode root)
    {
        
        countingUnivaluedTreeUtil(root);
        
        System.out.println("Number of univalued trees :: " + count);
    }
    
    
    static boolean  countingUnivaluedTreeUtil(TreeNode r )
    {
        
        if(r==null) return true;
        
        boolean lB = countingUnivaluedTreeUtil(r.left);
        boolean rB = countingUnivaluedTreeUtil(r.right);
        
        if(lB && rB && (r.left==null || r.val==r.left.val) && (r.right==null || r.val==r.right.val))
        {
            count++;
            return true;
        }
        
        return false;
        
    }
    
    
    
    


}


class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int x) { val = x; }
}

Question is not clear . Please explain.

Complete Running code in java ::

1. Time Complexity :: O(n)
2. Space Complexity :: O(n)

class InternalNode {
    int low;
    int high;
    int max;
    InternalNode left;
    InternalNode right;

    @Override
    public String toString() {
        return "InternalNode{" +
                "max=" + max +
                ", low=" + low +
                ", high=" + high +
                '}';
    }
}

public class IntervalTree {

    public InternalNode insert(InternalNode root, int low, int high) {
        if(root == null) {
            InternalNode node = new InternalNode();
            node.low = low;
            node.high = high;
            node.max = high;
            return node;
        }

        if(low < root.low) {
            root.left = insert(root.left, low, high);
        } else {
            root.right = insert(root.right, low, high);
        }

        root.max = Math.max(root.high, high);
        return root;
    }

  public InternalNode isOverlap(InternalNode root, int low, int high) {
        if(root == null) {
            return null;
        }

        if(root.high >= low && root.low <= high) {
            return root;
//            return root;
        }

        if(root.left != null && root.left.max > low) {
            return isOverlap(root.left, low, high);
        } else {
             return isOverlap(root.right, low, high);
        }
    }
    
    public int isOverlapWithCount(InternalNode root, int low, int high , int count) {
        if(root == null) {
            return 0;
        }

        if(root.high >= low && root.low <= high) {
            return 1+ (isOverlapWithCount(root.left, low, high , count) +
                    isOverlapWithCount(root.right, low, high, count)
                    );
        }

        if(root.left != null && root.left.max > low) {
            return isOverlapWithCount(root.left, low, high , count);
        } else {
             return isOverlapWithCount(root.right, low, high, count);
        }
    }

    public static void main(String args[]) {
        IntervalTree it = new IntervalTree();
        InternalNode root = null;
        root = it.insert(root, 10, 15);
        root = it.insert(root, 11, 13);
        root = it.insert(root, 18, 21);
        root = it.insert(root, 20, 25);
        root = it.insert(root, 0, 7);

        System.out.println(it.isOverlap(root, 8, 9));
        System.out.println(it.isOverlap(root, 17, 17));
        System.out.println(it.isOverlap(root, 21, 22));
//        System.out.println(it.isOverlap(root, 21, 22));
        System.out.println(it.isOverlap(root, 12, 18));
        System.out.println(it.isOverlap(root, 24, 26));
        System.out.println("total count = " + it.isOverlapWithCount(root, 10, 12,0));
    }

}

Complete running Code in java ::

1. Time Complexity - O(nLogn)
2. Space Complexity - O(1) (Not considering recursion stack in space complexity)

public Node sortedListToBst()
    {
        Node temp=h;
        int n=countNodes();
       
       return formBalancedBST_inPlace_nlogn(temp,n);
//    return formBalancedBST_outPlace_n(temp, n);//formBalancedBST_inPlace_nlogn(temp,n);
    }
   
    
    // In place conversion of DLL to Balanced BST
   // Space Complexity : O(1)  
   // Time complexity: O(n)   
    //In-place conversion of Sorted DLL to Balanced BST
    // The tree must be constructed in-place (No new DoublyLinkedNode should be
    //allocated for tree conversion)
    public Node formBalancedBST_inPlace_nlogn(Node head,int n)
    {
        // Base case
        if(n<=0)
            return null;
        
         else if(n==1)
         {
            head.next = null;
            head.prev = null;
            return head;
         }
        
         int i=1;
        Node current = head;
        
         while(i <= n/2)
         {
            current = current.next;
            i++;
         }
          current.prev= formBalancedBST_inPlace_nlogn(head, i-1);
          current.next = formBalancedBST_inPlace_nlogn(current.next, n-i);
                
          return current;
    }

Complete running code in java ::




public class TernaryTree2DLL{
// Demonstrate tree->list with the list 1..5
public static void main(String[] args) {


//-------------------------------------------
BTOperation ob=new BTOperation();

TernaryTreeNode r5 = new TernaryTreeNode(5);
TernaryTreeNode r6 = new TernaryTreeNode(6);
TernaryTreeNode r7 = new TernaryTreeNode(7);
TernaryTreeNode r8 = new TernaryTreeNode(8);
TernaryTreeNode r9 = new TernaryTreeNode(9);
TernaryTreeNode r10 = new TernaryTreeNode(10);
TernaryTreeNode r11 = new TernaryTreeNode(11);
TernaryTreeNode r12 = new TernaryTreeNode(12);
TernaryTreeNode r13 = new TernaryTreeNode(13);

TernaryTreeNode r2 = new TernaryTreeNode(2,r5,r6,r7);
TernaryTreeNode r3 = new TernaryTreeNode(3,r8,r9,r10);
TernaryTreeNode r4 = new TernaryTreeNode(4,r11,r12,r13);
TernaryTreeNode root = new TernaryTreeNode(1, r2, r3, r4);


// ob.treeInsert(root,16);
// ob.treeInsert(root,18);
// ob.treeInsert(root,17);
// ob.treeInsert(root,20);
// ob.treeInsert(root,6);
// ob.treeInsert(root,7);
// ob.treeInsert(root,3);
// ob.treeInsert(root,13);
// ob.treeInsert(root,9);
// ob.treeInsert(root,2);
// ob.treeInsert(root,4);
//-------------------------------------------


System.out.println("tree:");
// ob.printTree(root); // 1 2 3 4 5
// System.out.println();


System.out.println("Inorder traversal of tree:");
ob.inOrderTree(root);


TernaryTreeNode head = ob.treeToList(root); // treeToDLL(root);
// TernaryTreeNode head = ob.toList(root);
System.out.println("DLL traversal: ");
ob.printList(head); // 1 2 3 4 5 yay!

}
}
class TernaryTreeNode
{
int data;
TernaryTreeNode left;
TernaryTreeNode middle;
TernaryTreeNode right;

public TernaryTreeNode(int v)
{
this.data=v;
}

public TernaryTreeNode(int v , TernaryTreeNode small, TernaryTreeNode middle , TernaryTreeNode large) {
this.data=v;
this.left = small;
this.middle = middle;
this.right=large;
}

}
class BTOperation {

public TernaryTreeNode treeToList(TernaryTreeNode root)
{
// base case: empty tree -> empty list
if (root==null)
return(null);

// Recursively do the subtrees (leap of faith!)
TernaryTreeNode aList = treeToList(root.left);
TernaryTreeNode bList = treeToList(root.middle);
TernaryTreeNode cList = treeToList(root.right);

// Make the single root node into a list length-1
// in preparation for the appending
root.left = root;
root.right = root;

// At this point we have three lists, and it's
// just a matter of appending them together
// in the right order (aList, root, bList)

aList=append(aList, bList);
aList=append(aList, cList);
aList = append(aList,root );


// root = append(root, bList);


return(aList);
}


public TernaryTreeNode append(TernaryTreeNode a, TernaryTreeNode b)
{
// if either is null, return the other
if (a==null) return(b);
if (b==null) return(a);

// find the last node in each using the .previous pointer
TernaryTreeNode aLast = a.left; // small;
TernaryTreeNode bLast = b.left; // small;

// join the two together to make it connected and circular
join(aLast, b);
join(bLast, a);

return(a);
}

public void join(TernaryTreeNode a, TernaryTreeNode b) {
a.right = b;
b.left = a;
}



/*
Given a non-empty tree, insert a new node in the proper
place. The tree must be non-empty because Java's lack
of reference variables makes that case and this
method messier than they should be.
*/
public void treeInsert(TernaryTreeNode root, int newData) {
if (newData<=root.data)
{
if (root.left!=null)
treeInsert(root.left, newData);
else
root.left = new TernaryTreeNode(newData);
}
else
{
if (root.right!=null)
treeInsert(root.right, newData);
else
root.right = new TernaryTreeNode(newData);
}
}


// Do an inorder traversal to print a tree
// Does not print the ending "\n"
public void printTree(TernaryTreeNode root) {
if (root==null) return;
printTree(root.left);
System.out.print(root.data+ " ");
printTree(root.right);
}


// postorder travseral of tree
public void inOrderTree(TernaryTreeNode root)
{
if(root==null) return;


inOrderTree(root.left);
inOrderTree(root.middle);
inOrderTree(root.right);
System.out.print(root.data+" ");

}



// Do a traversal of the list and print it out
public void printList(TernaryTreeNode head) {
// System.out.println(" head :: " + head.right.right.data);
TernaryTreeNode current = head;

while (true)
{
System.out.print(current.data + " ");

current = current.right;

if(current==head)
{
break;
}
}

System.out.println();
}


}

Can you please explain your code. I am unable to understand it.

The upper bound (for worst case) on number of comparison is log(n) , and lower bound(for best case i.e, when all elements are same) is O(1) , so overall complexity will be O(logn) , NOT theta(n) because its not a tight bound.
Correct me if I am wrong

Note: Java Code & running for all cases:
Case 1: Negative number
Case 2: 0<=n<=1
Case 3: n>1

public static double sqrtMethod3(double a)
    {
        //firstly check if a is non-negative value
    if(a<0)
        return -1;
    
    //also check if a==0 or a==1 because in these two cases sqrt(a) = a
    if(a==0 || a==1) return a;

    //now start the core part of the code
    double precision = 0.0000000000001;//define the precision, so we stop when precision is achieved
    
    double start = 0;
    double end = a;
    
    //we define these two start/end values because usually 0<sqrt(a)<a
    //however, if a<1; then 0<a<sqrt(a)
    if(a<1)
        end = 1;

    //define a loop to continue if the precision is not yet achieved
    while(end-start>precision)
    {
       // System.out.println("end-start = "+(end-start));
      //  System.out.println("precision = "+precision);

    double mid = (start+end)/2;
    double midSqr = mid*mid;
    
    if(midSqr==a)
        return mid;//we find the exact sqrt value!
    else if(midSqr<a)
        start = mid;//we shift our focus to bigger half
    else 
        end = mid;//shift focus to smaller half
    }

    
    //if we did not find exact sqrt value, we return the approxiated value with the defined precision
    return (start+end)/2;
   
  }

1. Threads are easier to create than processes since they
don't require a separate address space.

2. Multithreading requires careful programming since threads
share data strucures that should only be modified by one thread
at a time. Unlike threads, processes don't share the same
address space.

3. Threads are considered lightweight because they use far
less resources than processes.

4. Processes are independent of each other. Threads, since they
share the same address space are interdependent, so caution
must be taken so that different threads don't step on each other.
This is really another way of stating #2 above.

5. A process can consist of multiple threads.

Java version: Working for all kinds of test cases:

public static void printMatrix_Spiral_form(int a[][])
      {
          if(a==null)
              return ;
          
         // int column=a.length; 
          int row=a.length-1;  // correct answer
          
          int column=a[0].length-1;  // correct answer
          
          // first printing row then printing column
          int i=0,j=0,k=0,p=0;
          
          while(j<=column && i<=row)
          {
              k=j;
              while(j<=column)
              {
                  System.out.print(a[i][j]+"  ");
                  j++;
              }
              
              i++;
              j--;
              p=i;
              while(i<=row)
              {
                  System.out.print(a[i][j]+"  ");
                  i++;
              }
              
              i--;
              j--;
              while(j>=k)
              {
                  System.out.print(a[i][j]+"  ");
                  j--;
              }
              i--;
              j++;
              while(i>=p)
              {
                       System.out.print(a[i][j]+"  ");
                       i--;
              }
              i++;
              j++;
              
              column--;
              row--;
          }
          
      }

The only solution possible for LC substring between two strings is : Manacher’s Algorithm

// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
  int n = s.length();
  if (n == 0) return "^$";
  string ret = "^";
  for (int i = 0; i < n; i++)
    ret += "#" + s.substr(i, 1);
 
  ret += "#$";
  return ret;
}
 
string longestPalindrome(string s) {
  string T = preProcess(s);
  int n = T.length();
  int *P = new int[n];
  int C = 0, R = 0;
  for (int i = 1; i < n-1; i++) {
    int i_mirror = 2*C-i; // equals to i' = C - (i-C)
    
    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
    
    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
      P[i]++;
 
    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }
 
  // Find the maximum element in P.
  int maxLen = 0;
  int centerIndex = 0;
  for (int i = 1; i < n-1; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  delete[] P;
  
  return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}

Source: Refer to leetcode.com

I also thought of same procedure of maintaining an auxiliary space of 10 digits and then taking each digit of each element in BST.

Time Complexity: O(Summation of digits of all elements in BST)
Space Complexity: O(10) // Since there are 10 digits

Edit:
(1). Whether the input numbers are given in form BST, unsorted array or anything else complexity can't be reduced further.
(2). Please some one explain essence of BST in this question.

Method 1: Using HashTable. (Not so efficient because of limited memory constrains)

Method 2: Using Trie and Heaps. (Memory Efficient)

Source : geeksforgeeks

This question is already asked in CareerCup. For more details refer to question with id= 183797

i think ur distribution is correct but there would be some minor changes:
public int my_rand(int n)
{
int i;
int a=randomNumber(n)+1;
int b=randomNumber(n)+1;

System.out.println("a="+a);
System.out.println("b="+b);

i=a +b; // 2 to 10
i=i-1;
if(i==8 || i== 9)
return my_rand(n);

return i;

// return my_rand(n);

}

Two solution possible depending on situation:
Solution 1: More time complexity and less space complexity
Use Max-Heap of size k.
Time complexity: O(n*logk)
Space complexity: O(k)
Solution 2: Same time complexity and more space complexity
Use Map<Cordinate,distance> of size n.
Time complexity: O(n)+O(nlogk)
Space complexity: O(n)

@Praveen-
Complexity for your solution- O(log n)
Complexity of sharath hari solution- O(1)

U can compare

@learner- Does that mean that paging is always required irrespective of size of memory available so as to maintain protection among the processes?

@hardy. I am sorry to say but question is contradictory in itself. Please check or remove the question.

thanks

Let total possibility be p:
Case 1: 1c,1a p1= N;
Case 2: 1c,2a p2= N*(N-1)/2
Case 3: 1c,1b p3= N
Case 4: 1a,1b,1c p4= N*(N-1)
Case 5: 2a,1b,1c p5= N*(N-1)*(N-2)/2

Total possibility p=p1+p2+p3+p4+p5