CareerCup

Given an array arr[] of size n. Three elements arr[i], arr[j] and arr[k] form an inversion of size 3 if a[i] > a[j] >a[k] and i < j < k. Find total number of inversions of size 3


e.g.

Input: 23, 10, 24, 7, 12, 19
Ans: 23, 10, 7

You toss a fair coin 400 times. What’s the probability that you get at least 220 heads? Round your answer to the nearest per cent.

You have a binary search tree and you have to return the two nodes such that there sum i equal to ‘K’. Pseudo code is to be given.

O(n)time & O(n) sppace is easy but challenge O(n) time & O(1) space.

You are given a 2D Array that contains only 0s and 1s in sorted order. i.e. First Os and then 1s.

Array:
0 0 0 1
1 1 1 1
0 0 1 1
0 1 1 1

You have to figure out the row that contains maximum number of 1s.

e.g. in above case we have row 2 as the answer.

In Amazon's interview, Round 2 they asked question:

Write a program to print inorder traversal of two trees.

Both values must be printed alternatively.

e.g. if inorder traversal of tree 1 is 10, 15, 20 and tree 2 is 100, 150, 200 then it should print
10, 100, 15, 150, 20, 200.

I tried printing it recursively by calling 2 functions recursively (f1 calls f2, then f2 calls f1 and so on).

I don't know where my approach is going wrong? I know there are other ways to do it as well but in this approach what is the mistake?

public class HelloWorld{

 //this is the Node used in the tree
    static class Node{
        private int data;
        private Node left;
        private Node right;
        public Node(int data){
            this.data = data;
            left = null;
            right = null;
        }
        public void setLeft(Node left){
            this.left = left;
        }
        public void setRight(Node right){
            this.right = right;
        }
        public Node getLeft(){
            return this.left;
        }        
        public Node getRight(){
            return this.right;
        }
        public int getData(){
            return this.data;
        }
        public boolean equals(Node n){
            if(this.data ==(int) n.getData()) return true;
            else
                return false;
        }
    }

    public static void main(String[] args){
        HelloWorld bts = new HelloWorld();
        bts.run();
    }
    //execute the test case
    public void run(){
        Node root = new Node(10);
        insert(root,new Node(20));
        insert(root,new Node(50));
        insert(root,new Node(40));
        insert(root,new Node(15));
        
        
        Node node2 = new Node(100);
        insert(node2,new Node(200));
        insert(node2,new Node(500));
        insert(node2,new Node(400));
        insert(node2,new Node(150));
        
        
        //inOrderTraverse(node2);
        
        inOrderTraverse1(root, node2);
    }
     
    // insert a node to the binary search tree
    public void insert(Node root, Node n){
        if(root == null|| n == null) return;
         
        if(root.getData() > n.getData()){
            if(root.getLeft() == null){
                root.setLeft(n);
            }else{
                insert(root.getLeft(),n);
            }
 
        }else if(root.getData() < n.getData()){
            if(root.getRight() == null){
                root.setRight(n);
            }else{
                insert(root.getRight(),n);
            }             
        }
    }
    
    public void inOrderTraverse(Node node){
        if(node != null){
            if(node.getLeft() != null)
            inOrderTraverse(node.getLeft());
            System.out.print("  "+node.getData());
            if(node.getRight() != null)
            inOrderTraverse(node.getRight());
        }
         
    }
    
    //in-order Traversal
    public void inOrderTraverse1(Node node1, Node node2){
        if(node2 != null){
            inOrderTraverse2(node1, node2.getLeft());
            System.out.println("  "+node2.getData());
            inOrderTraverse2(node1, node2.getRight());
        }
    }
    
    public void inOrderTraverse2(Node node1, Node node2){
        if(node1 != null ){
            inOrderTraverse1(node1.getLeft(), node2);
            System.out.println("  "+node1.getData());
            inOrderTraverse1(node1.getRight(), node2);
        }
    }