MakeMyTrip Experience

Written

Q1. An array is rotated at a random point, find the smallest element in array with minimal complexity.

Q2. Write a code using threads to print even and odd numbers in a way that 1 thread prints even and other prints odd and so on.

public class Printer {
    boolean isOdd = false;
   
    synchronized void printEven(int number) {
        while (isOdd == false) {
            try {
                wait();
            }
            catch(InterruptedException ex) {
                ex.printStackTrace();
            }
        }
        System.out.println(Thread.currentThread().getName());
        System.out.println("Even : " + number);
        isOdd = false;
        notify();
    }
   
    synchronized void printOdd(int number) {
        while (isOdd == true) {
            try {
                wait();
            }
            catch(InterruptedException ex) {
                ex.printStackTrace();
            }
        }
        System.out.println(Thread.currentThread().getName());
        System.out.println("Odd : " + number);
        isOdd = true;
        notify();
    }
}



public class TaskEvenOdd implements Runnable {
    
    private int max;
    private Printer print;
    private boolean isEvenNumber;
    
    TaskEvenOdd(int max, Printer print, boolean isEvenNumber) {
        this.max = max;
        this.print = print;
        this.isEvenNumber = isEvenNumber;
    }

    @Override
    public void run() {
        
        int number = isEvenNumber == true ? 2 : 1;
        
        while (number <= max) {
            
            if (isEvenNumber) {
                print.printEven(number);
            }
            else {
                print.printOdd(number);
            }
            number = number + 2;
        }
    }
}



public class PrintEvenOddTester {
    public static void main(String[] args) {
        // TODO code application logic here
        Printer print = new Printer();
        Thread t1 = new Thread(new TaskEvenOdd(10, print, false), "Odd Thread");
        Thread t2 = new Thread(new TaskEvenOdd(10, print, true), "Even Thread");
        
        t1.start();
        t2.start();
    }
}

Interview - 1

Q1. Code to print bottom view of a Binary Tree
Answer
The basic logic here revolves around the horizontal distance from the root.
1. The tree data structure will contain an integer field to store the horizontal distance (initially 0)
2. Perform a level order traversal of the tree such that - The root will have horizontal distance of 0, its left node will have horizontal distance of HD(root)-1 and right node will have HD(root)+1.
3. Also put the node that is under traversal into a TreeMap data structure to maintain the set of nodes that are visible from bottom of the tree. (TreeMap has horizontal distance as the key and node data as its value)
4. After completion of the level order traversal, Iterate over your treemap and print the nodes

Q2. Reverse linked list in blocks of k

Q3. Given a chess board of 8x8, traverse the knight throughout the board marking the position the knight has been and increment it accordingly

Q4. What is a HashMap? How does it work?
What is a TreeSet and HashSet

Q5 What is left outer join in SQL

Q6. Iterative preorder traversal of binary tree.

Q7. Difference between Comparator and Comparable.

Interview - 2

Q1. Given a binary tree, write the code to print the node pairs whose sum is k in least complexity

Q2. Write the code to print the right view of a binary tree.

Q3. What is final and static in Java, can we have static class.

Q4. What is anonymous class in Java? Write an example.

Q5. Implement your HashMap in Java

Q6 What is the difference between mutex and semaphore.