CareerCup

Could you please explain how dequeu would help in getting min and max elements for the last k days ?

dude this is not the complete code; just a function. I am not sure how you coded the whole program. The function is in Java. You will have to create a class Node and then write the code for linked-list creation.

Node reverseAlterante ( Node head) {
if ( head == null || head.next == null )
        return head;
Node r = reverseAlternate(head.next.next);
Node t = head.next ;
t.next = head;
head.next = r;
return t ;
}

@codeAddict: not necessarily. If there is some other mechanism available for protection then paging won't be required. In fact since we have infinite memory, a process need not change its location in the memory. Then even the older protection methods such as base and limit register can be used.

1) if value == node.data then break
2) if(value < node.data )
a. if node is a right child of its parent and value is less than parent.data , move to parent
else
move to left subtree of the node

3) if(value > node.data)
a. if node is a left child of its parent and value is greater than parent.data, move to parent
else
move to right subtree of the data

4) continue until node is null or node.data == value

this would find a path whether the value exits in the subtrees of the node or anywhere else.

void findPath(Node node, int value) {
          
     if(node == null )
           throw new RtE();
             
     while(node != null) {
           
            System.out.println(node.data);
            if (node.data == value)
                     return;
          
             boolean isLeftChild = false, isRightChild = false;
          
             Node parent = node.parent;
             if(parent != null) {
                
                 if( parent.left == node)  
                           isLeftChild = true; 
                 else 
                          isRightChild  = true;  
              }
              if( value < node.data) {
                
                  if(isRightChild && value < parent.data)
                             node = parent;
                  else
                          node = node.left; 
               } else {
                   if(isLeftChild && value > parent.data )
                           node = parent;
                  else
                           node = node.right;
              }                         
    }

}

Paging provides 3 things :
1) creates illusion that each process has infinite memory by moving pages to and from disk
2) eliminates external fragmentation thereby saving space
3) memory protection among processes.

If there is infinite memory, 1) and 2) won't be a matter of concern.
However 3) would still be required.
So paging would be required for protection.

- Consider the two paths as two linked lists
- find the length of both the lists and get the difference in length
- move the pointer of longer list by the difference and add every node to the path
- move pointers to both the lists till they meet and add nodes to respective paths
- if the meeting point is root add root to both the paths
- display the paths

void printPath (Node node1, Node node2) {
          if(node1 == null && node2 == null)
              return ;
         
         int len1 = 0, len2 = 0;
      
         Node temp = node1;
         
         while(temp != null) {
             temp = temp.parent; 
            ++len1;
         }
         
       temp = node2;

       while(temp != null) {             
              temp = temp.parent; 
             ++len2;
       }

        StringBuffer path1 = new StringBuffer();
        StringBuffer path2 = new StringBuffer();

        if(len1 > len2 ) {              
            for(int i = 0; i < len1 - len2 ; i++) {
                  
                  path1.append(node1.data);
                 node1 = node1.parent;
               }                  
         }else {

               for(int i = 0; i < len2 - len1 ; i++) {
                  
                  path2.append(node2.data);
                 node2 = node2.parent;
               }                   
          }
          
         while(node1 != node2) {
                path1.append(node1.data);
                path2.append(node2.data);     
                node1 = node1.parent;
                node2 = node2.parent;
          }
         
        if(node1 == root) {
                 path1.append(root.data);
                 path2.append(root.data):
        }
        
       System.out.println(path1.toString());
       System.out.println(path2.toString());

 }

- If root is equal to M , root is answer return root
- if root is less than M, M cannot fit in root , move to right
- if root is greater than M, root can be the best fit , save root, move left

Integer getBestFit ( Node root, int M){
    
    if(root == null)
         return null;
   Node lastBestFit = null;
    while(root != null) {
    
     if(root.data == M)
            return root.data;
  
     if(root.data < M)
           root  = root.right;
     else{
         lastBestFit = root;
         root = root.right;
      }
    }
    
   if(lastBestFit == null)
        return null;
   return lastBestFit.data;
 }

boolean containsDups(Node slist){
  
       Node curr = slist;
       HashSet<Integer> set = new HashSet<Integer>();
       do{
          
            if(set.contains(curr.value))
                return true;
            else { 
                 set.add(curr.value);
              } 
           curr = curr.next;
         } while(curr != slist);

      return false;
 }

- Create a hashmap of <element, count> pairs from the first array.
- Iterate through the second array and find matching elements.
- If the count of the matching element is greater than 0, print the element and
decrease the count in the map by 1.

static void commonElements(int[] arr1, int[] arr2){
        HashMap<Integer, Integer> countMap = new HashMap<Integer, Integer>();
        for(int e : arr1){
            if(countMap.containsKey(e)){
                int count = countMap.get(e);
                countMap.put(e, count + 1);
                
            }else{
                countMap.put(e , 1);
            }
            
        }
        
        for(int e : arr2){
            if(countMap.containsKey(e)){
                int count = countMap.get(e);
                if(count > 0){
                    System.out.println(e);
                    countMap.put(e , count - 1);
                }
            }
            
        }
        
    }

@amit- Thanks for pointing that out. I have corrected it.

int findLastOccurrence(int[] arr, int num){
   int i = 0;
   int index = 0;
   while(arr[index] <= num) {
     index = 1 << i;
     ++i;
   }
   
   int left = index/2 ;
   int right = index;
   
   while(left < right){
     int mid = (left + right)/2;
     if(arr[mid] == num){
       
        if( (arr[mid + 1] )!=num){
          return mid;
        }else{
          
          left = mid + 1;
        }
     }else if(arr[mid] < num){
         left = mid + 1;
     }else{
     
         right = mid - 1;
     } 
   
   }

Cool!