Saturday, April 22, 2017

Projectile Motion


Find the minimum number of train platforms needed in each direction

Given the arrival time, departure time and direction of trains, find the minimum number of platforms needed in each direction to accommodate all trains such that no train has to wait.
Arrival time Departure time Direction
11:00 11:15 Up
11:05 11:20 Up
11:00 11:10 Down
11:15 11:25 Down

Sample Output:
2 platforms are needed in Up direction.
1 platform is needed in Down direction.

Vertical Order Traversal of Tree


Java Program using HashMap:
public class TreeTraversalPrograms {
    private static Map<Integer, List<TreeNode>> treeNodeVerticalLevelMap = new TreeMap<>();

    public static void main(String[] args) {
        // Tree construction
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.right.left.right = new TreeNode(8);
        root.right.right.right = new TreeNode(9);

        verticalOrderTraversal(root, 0);
        SortedSet<Integer> keys = new TreeSet<Integer>(treeNodeVerticalLevelMap.keySet());
        for (Integer key : keys) {
            List<TreeNode> treeNodesList = treeNodeVerticalLevelMap.get(key);
            for (TreeNode treeNode : treeNodesList) {
                System.out.print(treeNode.data + ",");
            }
            System.out.println();
        }
    }
    public static void verticalOrderTraversal(TreeNode node, int width) {
        if (node == null) {
            return;
        }
        if (treeNodeVerticalLevelMap.containsKey(width)) {
            List<TreeNode> treeNodesList = treeNodeVerticalLevelMap.get(width);
            treeNodesList.add(node);
            treeNodeVerticalLevelMap.put(width, treeNodesList);
        } else {
            List<TreeNode> treeNodesList = new ArrayList<>();
            treeNodesList.add(node);
            treeNodeVerticalLevelMap.put(width, treeNodesList);
        }
        if (node.left != null) {
            verticalOrderTraversal(node.left, width - 1);
        }
        if (node.right != null) {
            verticalOrderTraversal(node.right, width + 1);
        }
    }
}

Sample Output:
4,
2,
1,5,6,
3,8,
7,
9,