City Planning using k-means clustering algorithm

Problem

Given a city with coordinates of n houses, find the most optimal location for k hospitals so that the mean distance required to be traveled by the residents of the city is minimum.

Input

n (0 < n <= 100)

(x, y) coordinates of n houses

k (0 < n <= 5)

Output

k coordinates representing the locations of the hospitals.

Solution

This problem can be solved by using the k-means clustering algorithm which involves finding clusters in a scatter plot based on the condition that the mean distance of the points in a cluster from the cluster centroid is minimum

 

Python Code

import math
import random
import matplotlib.pyplot as plt
import matplotlib.collections as mcoll
import time

def generate_random_points(n):
    points = []
    for _ in range(n):
        x = random.uniform(0, 100)
        y = random.uniform(0, 100)
        points.append((x, y))
    return points

def calculate_mean_distance(points, centroids):
    total_distance = 0
    for x, y in points:
        min_distance = float('inf')
        for cx, cy in centroids:
            distance = math.sqrt((x - cx) ** 2 + (y - cy) ** 2)
            min_distance = min(min_distance, distance)
        total_distance += min_distance
    return total_distance / len(points)

'''
This method starts with k centroids randomly chosen from the given coordinates.
It then 
'''
def k_means(points, k):
    centroids = random.sample(points, k)
    iterations = 0
    while True:
        iterations += 1
        clusters = [[] for _ in range(k)]
        for x, y in points:
            min_distance = float('inf')
            closest_centroid = None
            for i, (cx, cy) in enumerate(centroids):
                distance = math.sqrt((x - cx) ** 2 + (y - cy) ** 2)
                if distance < min_distance:
                    min_distance = distance
                    closest_centroid = i
            clusters[closest_centroid].append((x, y))
        new_centroids = []
        for cluster in clusters:
            x_sum = sum(x for x, y in cluster)
            y_sum = sum(y for x, y in cluster)
            new_centroids.append((x_sum / len(cluster), y_sum / len(cluster)))
        if new_centroids == centroids:
            break
        centroids = new_centroids
        plot_iteration(points, centroids, clusters, iterations)
        time.sleep(1)  # Pause for 1 second
    return centroids, clusters

def plot_iteration(points, centroids, clusters, iteration):
    plt.clf()  # Clear the previous plot
    colors = ['b', 'g', 'r', 'c', 'm']  # Colors for clusters

    # Plot the random points
    x_coords, y_coords = zip(*points)
    plt.scatter(x_coords, y_coords, c='k', marker='o', s=10, alpha=0.5, label='Random Points')

    # Plot the centroids
    centroid_x, centroid_y = zip(*centroids)
    plt.scatter(centroid_x, centroid_y, c='r', marker='*', s=100, label='Centroids')

    # Plot the line segments and clusters
    for i, cluster in enumerate(clusters):
        x_coords, y_coords = zip(*cluster)
        plt.scatter(x_coords, y_coords, c=colors[i], marker='o', label=f'Cluster {i+1}', alpha=0.5)
        line_segments = []
        for x, y in cluster:
            line_segments.append([(x, y), (centroids[i][0], centroids[i][1])])
        line_collection = mcoll.LineCollection(line_segments, colors=colors[i], linewidths=0.5, alpha=0.5)
        plt.gca().add_collection(line_collection)

    plt.xlim(0, 100)
    plt.ylim(0, 100)
    plt.title(f'Iteration {iteration}')
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.grid(True)
    plt.legend()
    plt.pause(0.01)  # Pause for a brief moment to update the plot

# Example usage
n = 100  # Number of random points
k = 5    # Number of centroids to find
points = generate_random_points(n)
centroids, clusters = k_means(points, k)
mean_distance = calculate_mean_distance(points, centroids)
print(f"Mean distance of {k} centroids from {n} points: {mean_distance:.2f}")

# Plot the final points, centroids, and line segments
plt.figure(figsize=(8, 6))
colors = ['b', 'g', 'r', 'c', 'm']  # Colors for clusters

for i, cluster in enumerate(clusters):
    x_coords, y_coords = zip(*cluster)
    plt.scatter(x_coords, y_coords, c=colors[i], marker='o', label=f'Cluster {i+1}', alpha=0.5)
    centroid_x, centroid_y = centroids[i]
    plt.scatter(centroid_x, centroid_y, c='k', marker='*', s=100)
    line_segments = []
    for x, y in cluster:
        line_segments.append([(x, y), (centroid_x, centroid_y)])
    line_collection = mcoll.LineCollection(line_segments, colors=colors[i], linewidths=0.5, alpha=0.5)
    plt.gca().add_collection(line_collection)

plt.xlim(0, 100)
plt.ylim(0, 100)
plt.title('Random Points, Centroids, and Line Segments')
plt.xlabel('X')
plt.ylabel('Y')
plt.grid(True)
plt.legend()
plt.show()
  

 

The above code requires matplotlib library to be installed. 

Scatter Plot

The circles represent the coordinates of the houses, stars represent the cluster centroids (or hospitals) and the line segments represent the nearest centroid.

C++ Program for Tree Iterator

Problem

Given n-ary (n children per node) tree, write a C++ iterator to iterate over all the nodes.

Solution

Iterator Interface

One of the potential interface is as follows:

/**
 * If there are more children to be traversed in the current layer
 * @param index
 * @return True if there are children yet to be traversed, false otherwise
 */
virtual bool hasMoreChildren(int index);

/**
 * Move to child at index in a layer
 * @param index
 */
virtual void moveToChildAt(int index);

/**
 * Print the current node
 * @param index
 */
virtual void printNode();

Implementation

For implementing the iterator, we will use a stack to keep track of the node being traversed in the tree.

private:
    Node* mCurrentNode = nullptr;
    std::stack<Node*> mNodeStack;
};

The mCurrentNode and mNodeStack are used in the implementation as follows:

C++ Code

bool TreeIterator::hasMoreChildren(int index) {
    if (mNodeStack.empty()) return false;
    mCurrentNode = mNodeStack.top();
    // If no children, return false.
    if (mCurrentNode->children().empty()) {
        mNodeStack.pop();
        if (!mNodeStack.empty()) {
            mCurrentNode = mNodeStack.top();
        }
        return false;
    }
    auto it = mCurrentNode->children().begin();
    it += index;
    // If all children in this layer are traversed, return false.
    if (it == mCurrentNode->children().end()) {
        mNodeStack.pop();
        if (!mNodeStack.empty()) {
            mCurrentNode = mNodeStack.top();
        }
        return false;
    }
    // There are more children to be drawn, return true
    return true;
}

void TreeIterator::moveToChildAt(int index) {
    if (mCurrentNode->children().empty()) {
        // No children, nothing to do in current layer
        return;
    }
    auto it = mCurrentNode->children().begin();
    it += index;
    if (it == mCurrentNode->children().end()) {
        // All children visited once, nothing to do in current layer
        return;
    }
    mNodeStack.push(*it);
    mCurrentNode = mNodeStack.top();
}

void TreeIterator::printNode() {
    cout << mCurrentNode->data() << endl;
}

Using the iterator

/**
 * Recursively traverse the tree hierarchy
 */
void traverse() {
    int i = 0;
    while (hasChildren(i)) {
        moveToChildAt(i);
        traverse();
        i++;
    }
}

int main() {
    TreeIterator *it;
    it->traverse();
}

Explanation

The above code is a recursively traverses the children of each node in the tree. The stack maintains the current node at the top and the index passed from the traverse() method determines how many children of a particular node have been visited.

Alternate Solutions

Alternate solutions may use the following approach.

Visitor Pattern

Yet to write a working code, but this approach would mark a node as visited once it has been traversed to keep track of which child of a particular node should be visited next.

Parent Tracking

This requires modifying the tree node to contain a pointer to the parent node so that the mCurrentNode can be moved to the parent when all the children of a particular node are visited.

Automatic Train Controller System Code

TrainController class starts two infinite loops in separate threads:

1. User Override Control Loop
2. Automatic Control Loop

In this post, the Train class contains a few characteristics such as distance travelled from Origin and its speed, which can be abstracted into a separate class and can be handled in a more centralized manner inside TrainController class.

Also a few more features such as directionality of train movement and maximum distance from origin will be introduced.

Code

package com.example.lib;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class TrainController {
    private final List mTrains = new ArrayList<>();
    private final List mManuallyStoppedTrains = new ArrayList<>();
    private final InstructionParser mInstructionParser = new InstructionParser();
    public static void main(String[] args) {
        final TrainController trainController = new TrainController();
        trainController.createAndStartTrains(5);
         // This is the main controller loop.
         // 1. It monitors the distance between the pairs of trains and sends stop and start signals appropriately.
         // 2. This is run in a separate thread so that the user input can be captured in the main thread.
        Runnable controllerRunnable = new Runnable() {
            @Override
            public void run() {
                while (true) {
                    trainController.checkAndControlTrains();
                }
            }
        };
        Thread controllerThread = new Thread(controllerRunnable);
        controllerThread.start();
        trainController.printAllCommands();
        // Accept user input in a loop.
        while (true) {
            Scanner scanner = new Scanner(System.in);
            int option = scanner.nextInt();
            trainController.executeOption(option);
            System.out.println("Waiting for the next input");
        }
    }

    public void printAllCommands() {
        System.out.println("Choose from the below options");
        System.out.println("1. Start 5 trains");
        System.out.println("2. Get status of all trains");
        System.out.println("3. Stop all trains");
        System.out.println("4. Start all trains");
        System.out.println("5. Exit");
        System.out.println("6. Control individual train");
        System.out.println("7. Print all commands");
    }

    public void executeOption(final int option) {
        switch (option) {
            case 1:
                createAndStartTrains(5);
                break;
            case 2:
                printCurrentStateOfAllTrains();
                break;
            case 3:
                stopAllTrains();
                break;
            case 4:
                startAllTrains();
                break;
            case 5:
                stopAllTrains();
                System.exit(0);
            case 6:
                String instruction = System.console().readLine();
                System.out.println("Instruction received: " + instruction);
                if (instruction.toLowerCase().split(" ").length == 2) {
                    try {
                        int index = mInstructionParser.getIndex(instruction);
                        switch (instruction.toLowerCase().split(" ")[0]) {
                            case "start":
                                startTrain(index);
                                break;
                            case "stop":
                                stopTrain(index);
                                break;
                        }
                    } catch (IllegalArgumentException e) {
                        // Do nothing.
                    }
                }
                break;
            case 7:
                printAllCommands();
                break;
        }
    }

    /**
     * Initialize trains with different speeds and start them on different threads.
     * @param count of trains to start
     */
    public void createAndStartTrains(final int count) {
        final String trainName = "Train ";
        for (int i = 0; i < count; i++) {
            Train train = new Train(trainName + i, i * 1000);
            mTrains.add(train);
            train.startTrain();
        }
    }

    /**
     * Checks that the distance between successive trains is more than 1000 units.
     * Whenever the distance between successive trains is less than 1000 units, it calls {@link Train#stopTrain()} on the rear train.
     * Whenever the distance between successive trains is more than 1000 units, it calls {@link Train#startTrain()} on the rear train.
     */
    private void checkAndControlTrains() {
        // Loop to stop a train if it is within 1000 units of the train ahead of it.
        for (int i = 0; i < mTrains.size() - 1; i++) {
            if (mTrains.get(i + 1).getDistance() - mTrains.get(i).getDistance() - 3 * mTrains.get(i).getSpeed() <= 1000) {
                mTrains.get(i).stopTrain();
            }
        }
        // Loop to start a train if it is more than 1000 units away from the train ahead of it and it was not stopped manually.
        for (int i = 0; i < mTrains.size() - 1; i++) {
            if (mTrains.get(i + 1).getDistance() - mTrains.get(i).getDistance() - mTrains.get(i).getSpeed() > 1000) {
                Train train = mTrains.get(i);
                if (!mManuallyStoppedTrains.contains(train) && !train.isRunning()) {
                    train.startTrain();
                }
            }
        }
    }

    private void printCurrentStateOfAllTrains() {
        if (mTrains.size() == 0) {
            System.out.println("No train is in running state");
            return;
        }
        System.out.println("Printing status of all trains");
        for (Train train : mTrains) {
            train.printCurrentState();
        }
    }

    private void stopAllTrains() {
        for (Train train : mTrains) {
            train.stopTrain();
        }
    }

    private void startAllTrains() {
        for (Train train : mTrains) {
            train.startTrain();
        }
    }

    /**
     * Stop the train with the provided index.
     * @param trainIndex the index of the train to stop
     */
    private void stopTrain(int trainIndex) {
        // First add the train to the list of manually stopped trains. Otherwise the checkAndControl loop will start the train again.
        mManuallyStoppedTrains.add(mTrains.get(trainIndex));
        mTrains.get(trainIndex).stopTrain();
    }

    /**
     * Start the train with the provided index safely.
     * This checks if the train ahead is more than 1000 units ahead before starting the train.
     * @param trainIndex the index of the train to start
     */
    private void startTrain(int trainIndex) {
        if (trainIndex < mTrains.size() - 1) {
            if (mTrains.get(trainIndex + 1).getDistance() - mTrains.get(trainIndex).getDistance() <= 1000) {
                System.out.println("Cannot start train " + trainIndex + " since the train ahead is within 1000");
                return;
            }
            System.out.println("Starting train " + trainIndex + " since the train ahead is more than 1000");
        }
        // First remove the train from the list of manually stopped trains. Otherwise the checkAndControl loop will not start the train again.
        mManuallyStoppedTrains.remove(mTrains.get(trainIndex));
        mTrains.get(trainIndex).startTrain();
    }

    private static class InstructionParser {
        public int getIndex(final String instruction) {
            String lowerCaseInstruction = instruction.toLowerCase();
            if (!lowerCaseInstruction.startsWith("start") &&
                    !lowerCaseInstruction.startsWith("stop")) {
                System.out.println("Invalid instruction");
                throw new IllegalArgumentException("Invalid instruction provided. Cannot proceed");
            }
            return Integer.parseInt(lowerCaseInstruction.split(" ")[1]);
        }
    }

    private static class Train extends Thread {
        private final int mSpeed;
        private boolean mIsRunning;
        private int mDistance = 0;
        private int dummyLooper = 0;
        private boolean mIsInitialized;

        public Train(String name, int speed) {
            super(name);
            mSpeed = speed;
        }

        @Override
        public void run() {
            while (true) {
                dummyLooper++; // dummyLooper is just to keep this thread from becoming No-op when mIsRunning is false.
                while (mIsRunning) {
                    dummyLooper = 0;
                    try {
                        // The train runs at mSpeed units per second.
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    mDistance += mSpeed;
                }
                if (dummyLooper > 0) {
                    mIsRunning = false;
                }
            }
        }

        public int getDistance() {
            return mDistance;
        }

        public int getSpeed() {
            return mSpeed;
        }

        public boolean isRunning() {
            return mIsRunning;
        }

        /**
         * Sets the mIsRunning to true starts this thread.
         */
        public void startTrain() {
            mIsRunning = true;
            // Calling start always causes {@link IllegalThreadStateException}. Hence mIsInitialized is used as a check.
            if (!mIsInitialized) {
                mIsInitialized = true;
                start();
            }
        }

        public void stopTrain() {
            mIsRunning = false;
        }

        public void printCurrentState() {
            if (mIsRunning) {
                System.out.println(getName() + " is running and has reached " + mDistance);
            } else {
                System.out.println(getName() + " is stopped and has reached " + mDistance);
            }
        }
    }
}

Simple Automated Train Controller System

Introduction to Template and Function Pointer in C++

#include <iostream>

using namespace std;

template<typename T>
bool ascending(T a, T b) {
    return a > b;
}

template<typename T>
bool descending(T a, T b) {
    return a < b;
}

template<typename T>
void sort(T *p, int size, bool (*f)(T a, T b)) {
    for (int i = 0; i < size; i++) {
        for(int j = i; j < size; j++) {
            if (f(p[i], p[j])) {
                swap(p[i], p[j]);
            }
        }
    }
}

template<typename T>
void swap(T *a, T *b) {
    T temp = *a;
    *a = *b;
    *b = temp;
}

template<typename T>
void print(T* q, int size) {
    for(int i = 0; i < size; i++) {
        cout<<q[i]<<" ";
    }
    cout<<endl;
}

void expSwap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int main()
{
    int i = 10, j = 20;
    expSwap(&i, &j);
    cout<<i<<" "<<j<<endl;
    int a = 0, b = 1;
    swap(a, b);
    cout<<a<<" "<<b<<endl;
    double c = 1.05, d = 2.05;
    swap(c, d);
    cout<<c<<" "<<d<<endl;
    int A[] = {5, 1, 2, 3, 4};
    print(A, 5);
    sort(A, 5, ascending);
    print(A, 5);
    sort(A, 5, descending);
    print(A, 5);
    char C[] = {'e', 'a', 'b', 'c', 'd'};
    print(C, 5);
    sort(C, 5, ascending);
    print(C, 5);
    sort(C, 5, descending);
    print(C, 5);
    double D[] = {5.05, 1.01, 2.02, 3.03, 4.04};
    print(D, 5);
    sort(D, 5, ascending);
    print(D, 5);
    sort(D, 5, descending);
    print(D, 5);
    return 0;
}

Number of ways to have breakfast

Problem:
Find the number of ways you can have breakfast in ‘n’ days, given Bread-butter can be eaten every day, Pizza can be eaten every alternate day and Burger can be eaten every two days. Only one item can be eaten on a given day.

Solution:
Let us call the sequence of breakfast item on the days as timetable. And the condition of whether a particular item can be consumed on a given day as constraint.

Approach 1:
Create the timetable while checking that the constraints are met.

Approach 2:
Generate all possible timetables and eliminate the timetables that do not meet the constraints.

Java Program:

package com.sourabh.practice;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Breakfast {
    public static void main(String[] args) {
        String[] menu = new String[]{"Bread-butter", "Pizza", "Burger"};
        int[] constraint = new int[]{1, 2, 3};
        List<List<String>> timeTableList = new ArrayList<>();
        List<String> timeTable = new ArrayList<>();
        int n = 3;
        Breakfast breakfast = new Breakfast();
        breakfast.countNumberOfWaysEvaluationApproach(menu, constraint, timeTableList, timeTable, n);
        System.out.println(timeTableList.size());
    }
    
    public void countNumberOfWaysEvaluationApproach(String[] menu, int[] constraint, List<List<String>> timeTableList, List<String> timeTable, int n) {
        if(timeTable.size() == n) {
            // For unit-testing purpose
            List<String> output = new ArrayList<>();
            for(String food : timeTable) {
                System.out.print(food + " ");
                output.add(food);
            }
            System.out.println();
            timeTableList.add(output);
        } else {
            List<String> possibilities = new ArrayList<>();
            boolean found = false;
            for(int i=0; i<constraint.length; i++) {
                for(int j=1; j<constraint[i]; j++) {
                    if(timeTable.size() - j >=0 && timeTable.get(timeTable.size() - j).equals(menu[i])) {
                        found = true;
                    }
                }
                if(!found) {
                    possibilities.add(menu[i]);
                } else {
                    found = false;
                }
            }
            for(String possibility : possibilities) {
                timeTable.add(possibility);
                countNumberOfWaysEvaluationApproach(menu, constraint, timeTableList, timeTable, n);
                timeTable.remove(timeTable.size() - 1);
            }
        }
    }
    
    public void countNumberOfWaysExhaustiveApproach(String[] menu, int[] constraint, List<List<String>> timeTableList, List<String> timeTable, int n) {
        generatePermutation(menu, timeTableList, timeTable, n);
        Iterator<List<String>> iterator = timeTableList.iterator();
        while(iterator.hasNext()) {
            List<String> output = iterator.next();
            boolean passed = true;
            for(int i=0; i<menu.length; i++) {
                int occ1 = -1;
                int occ2 = -1;
                for(int j = 0; j < output.size(); j++) {
                    if(output.get(j).equals(menu[i])) {
                        if(occ1 < 0) {
                            occ1 = j;
                        } else {
                            occ2 = occ1;
                            occ1 = j;
                        }
                    }
                    if(occ1 >= 0 && occ2 >= 0 && occ1 > occ2 && occ1 - occ2 < constraint[i]) {
                        passed = false;
                    }
                }
            }
            if(!passed) {
                iterator.remove();
            }
        }
        for(List<String> output : timeTableList) {
            for(String food : output) {
                System.out.print(food + " ");
            }
            System.out.println();
        }
        System.out.println(timeTableList.size());
    }
    
    public void generatePermutation(String[] menu, List<List<String>> timeTableList, List<String> timeTable, int n) {
        if(timeTable.size() == n) {
            // For unit-testing purpose
            List<String> output = new ArrayList<>();
            for(String food : timeTable) {
                output.add(food);
            }
            timeTableList.add(output);
        } else {
            for(int i=0; i<menu.length; i++) {
                timeTable.add(menu[i]);
                generatePermutation(menu, timeTableList, timeTable, n);
                timeTable.remove(timeTable.size() - 1);
            }
        }
    }
} 

Sample Output:

Bread-butter Bread-butter Bread-butter 
Bread-butter Bread-butter Pizza 
Bread-butter Bread-butter Burger 
Bread-butter Pizza Bread-butter 
Bread-butter Pizza Burger 
Bread-butter Burger Bread-butter 
Bread-butter Burger Pizza 
Pizza Bread-butter Bread-butter 
Pizza Bread-butter Pizza 
Pizza Bread-butter Burger 
Pizza Burger Bread-butter 
Pizza Burger Pizza 
Burger Bread-butter Bread-butter 
Burger Bread-butter Pizza 
Burger Pizza Bread-butter 
15

Unit Tests:

package com.sourabh.practice;

import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.List;

import org.junit.Assert;
import org.junit.Test;

public class BreakfastTests {
    Breakfast breakfast = new Breakfast();
    @Test
    public void testCountNumberOfWaysInTermsOfFrequency() {
        String[] menu = new String[]{"Bread-butter", "Pizza", "Burger"};
        int[] constraint = new int[]{1, 2, 3};
        List<List<String>> timeTableList = new ArrayList<>();
        List<String> timeTable = new ArrayList<>();
        int n = 3;
        Breakfast breakfast = new Breakfast();
        breakfast.countNumberOfWaysEvaluationApproach(menu, constraint, timeTableList, timeTable, n);
        boolean passed = true;
        for(List<String> output : timeTableList) {
            for(int i=0; i<menu.length; i++) {
                int occ1 = -1;
                int occ2 = -1;
                for(int j = 0; j < output.size(); j++) {
                    if(output.get(j).equals(menu[i])) {
                        if(occ1 < 0) {
                            occ1 = j;
                        } else {
                            occ2 = occ1;
                            occ1 = j;
                        }
                    }
                    if(occ1 >= 0 && occ2 >= 0 && occ1 > occ2 && occ1 - occ2 < constraint[i]) {
                        passed = false;
                    }
                }
            }
        }
        Assert.assertTrue(passed);
    }
    
    @Test
    public void testCountNumberOfWaysInTermsOfExhaustiveness() {
        String[] menu = new String[]{"Bread-butter", "Pizza", "Burger"};
        int[] constraint = new int[]{1, 2, 3};
        List<List<String>> timeTableList = new ArrayList<>();
        List<String> timeTable = new ArrayList<>();
        int n = 3;
        Breakfast breakfast = new Breakfast();
        breakfast.countNumberOfWaysExhaustiveApproach(menu, constraint, timeTableList, timeTable, n);
        boolean passed = true;
        for(List<String> output : timeTableList) {
            for(int i=0; i<menu.length; i++) {
                int occ1 = -1;
                int occ2 = -1;
                for(int j = 0; j < output.size(); j++) {
                    if(output.get(j).equals(menu[i])) {
                        if(occ1 < 0) {
                            occ1 = j;
                        } else {
                            occ2 = occ1;
                            occ1 = j;
                        }
                    }
                    if(occ1 >= 0 && occ2 >= 0 && occ1 > occ2 && occ1 - occ2 < constraint[i]) {
                        passed = false;
                    }
                }
            }
        }
        Assert.assertTrue(passed);
    }
    
    @Test
    public void testCountNumberOfWaysInTermsOfAccuracy() {
        String[] menu = new String[]{"Bread-butter", "Pizza", "Burger"};
        int[] constraint = new int[]{1, 2, 3};
        List<List<String>> timeTableList = new ArrayList<>();
        List<String> timeTable = new ArrayList<>();
        int n = 3;
        Breakfast breakfast = new Breakfast();
        Long start1 = System.currentTimeMillis();
        breakfast.countNumberOfWaysEvaluationApproach(menu, constraint, timeTableList, timeTable, n);
        Long end1 = System.currentTimeMillis();
        int size1 = timeTableList.size();
        timeTableList = new ArrayList<>();
        timeTable = new ArrayList<>();
        Long start2 = System.currentTimeMillis();
        breakfast.countNumberOfWaysExhaustiveApproach(menu, constraint, timeTableList, timeTable, n);
        Long end2 = System.currentTimeMillis();
        int size2 = timeTableList.size();
        Assert.assertEquals(size1, size2);
        System.out.println(end1 - start1);
        System.out.println(end2 - start2);;
    }
}

Find the common vacant meeting slot

Problem:
Given the meeting slots of several persons, find the common vacant slot in which all the persons can meet.

Input and Output format:
The first line of input contains a single integer n denoting the number of persons. Next n lines of input contain the start and end time of meetings of each person in HH:MM format separated by a space character.

The first line of output should contain the number of distinct vacant slots followed by those many lines containing the start and end time of each vacant slot in HH:MM format separated by a space character.

Sample Input:
4
08:30 09:00
08:45 09:30
09:00 09:30
10:00 11:00

Sample Output:
3
00:00 08:30
09:30 10:00
11:00 23:59

Java Program:
 

package com.sourabh.first;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class CommonMeeting {
    public static void main(String[] args) {
        int A[] = new int[86401];
        Scanner scanner = new Scanner(System.in);
        int persons = Integer.parseInt(scanner.nextLine());
        List<Integer> meetingStartHour = new ArrayList<>();
        List<Integer> meetingStartMinute = new ArrayList<>();
        List<Integer> meetingStartSecond = new ArrayList<>();
        List<Integer> meetingEndHour = new ArrayList<>();
        List<Integer> meetingEndMinute = new ArrayList<>();
        List<Integer> meetingEndSecond = new ArrayList<>();
        
        List<Integer> vacantStartHour = new ArrayList<>();
        List<Integer> vacantStartMinute = new ArrayList<>();
        List<Integer> vacantStartSecond = new ArrayList<>();
        List<Integer> vacantEndHour = new ArrayList<>();
        List<Integer> vacantEndMinute = new ArrayList<>();
        List<Integer> vacantEndSecond = new ArrayList<>();
        
        for(int i=0;i<persons;i++)
        {
            String meeting = scanner.nextLine();
            //System.out.println(meeting);
            String[] parts = meeting.split(" ");
            String[] start = parts[0].split(":");
            String[] end = parts[1].split(":");
            
            meetingStartHour.add(Integer.parseInt(start[0]));
            meetingStartMinute.add(Integer.parseInt(start[1]));
            meetingStartSecond.add(Integer.parseInt(start[2]));
            
            meetingEndHour.add(Integer.parseInt(end[0]));
            meetingEndMinute.add(Integer.parseInt(end[1]));
            meetingEndSecond.add(Integer.parseInt(end[2]));
        }
        
        for(int i=0;i<persons;i++)
        {
            for(int j = 3600 * meetingStartHour.get(i) 
                        + 60 * meetingStartMinute.get(i)
                        + meetingStartSecond.get(i);
                    j <= 3600 * meetingEndHour.get(i) 
                        + 60 * meetingEndMinute.get(i)
                        + meetingEndSecond.get(i);
                    j++) {
                A[j]=1;
            }
        }
        if(A[0] == 0)
        {
            vacantStartHour.add(0);
            vacantStartMinute.add(0);
            vacantStartSecond.add(0);
        }
        for(int i=0;i<86400;i++)
        {
            if(A[i]==1 && A[i+1]==0)
            {
                vacantStartHour.add(i/3600);
                vacantStartMinute.add((i%3600)/60);
                vacantStartSecond.add(i%60);
            }
            else if(A[i]==0 && A[i+1]==1)
            {
                vacantEndHour.add(i/3600);
                vacantEndMinute.add((i%3600)/60);
                vacantEndSecond.add(i%60);
            }
        }
        if(A[86399] == 0)
        {
            vacantEndHour.add(86399/3600);
            vacantEndMinute.add((86399%3600)/60);
            vacantEndSecond.add(59);
        }
        System.out.println(vacantStartHour.size());
        for(int i=0;i<vacantStartHour.size();i++)
        {
            String vacantSlotStart = format(vacantStartHour.get(i)) + ":" +
                                     format(vacantStartMinute.get(i)) + ":" +
                                     format(vacantStartSecond.get(i));
            String vacantSlotEnd = format(vacantEndHour.get(i)) + ":" +
                                   format(vacantEndMinute.get(i)) + ":" +
                                   format(vacantEndSecond.get(i));
            System.out.println(vacantSlotStart + " " + vacantSlotEnd);
        }
    }
    
    private static String format(Integer time) {
        if(time < 10) {
            return "0" + time;
        }
        else {
            return time.toString();
        }
    }
}

Longest subarray containing all values greater than a given value

Problem:
Given the temperature trends over a number of days, find the longest streak of continuous days having temperatures greater than a given temperature k.

Input and Output format:
The first line of input contains two space separated integers n and k. The second line of input contains n space separated integers denoting the temperatures.

The output should contain three integers denoting the length of the longest streak of days having temperatures greater than k, the starting index of the longest streak and the ending index of the longest streak. Index starts from 1.

Sample Input:
5 30
29 31 28 32 33

Sample Output:
2 4 5

Explanation:
The longest streak of days having temperatures greater than 30 are days 4 and 5 with a length of 2.

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,

Streak of Consecutive Numbers

Given a streak of numbers, find k length block of consecutive numbers
Given an array of 0s and 1s, find k length streak of consecutive 0s or 1s.

Optimal Selfies

On your recent trip with your friends (numbered from 1 to n), you have taken multiple selfies with different subsets of firends. Find the minimal set of photos so that each friend is covered at least once.