sdpatil

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

/**
 * Problem: Write a program that takes an array A and index i into A, and rearranges the elements such that all elements
 * less than A[i] pivot appear first, followed by elements equal to pivot, followed by elements equal to pivot
  */
public class DutchNationalFlag {
    public static void main(String[] argv) {

sdpatil

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

/**
 * Problem: Write a program for knapsack problem that selects a subset of items that has maximum value and satisfies
 * the weight constraint. All items have integer weights and value
 */
public class KnapsackProblem {
    public static class Item {

sdpatil

/**
 * Problem: Design an efficient algorithm for computing(n/k) which has the property that it never 
 * overflows if the final result fits in the integer word size
 */
public class BionomialCoefficient {

    /**
     * Bionomial coefficient is nothing but pascal's traingle basic idea is value of cell is sum of
     * value of two cells from previous nodes (n-1) and n
     */

sdpatil

import java.util.List;

/**
 * Problem: Write a program that takes as argument a 2D array and a 1D array and checks whether the
 * 1D array occurs in 2D array
 */
public class SearchSequenceIn2DArray {
    static class Attempt {
        int x;
        int y;

sdpatil

/*
    Problem: Given totalNumber of ways and how many steps you can take in one go calculate how many
    ways you can climb to top
 */
public class NumberOfWaysToClimbStairs {
    public static void main(String[] argv) {
        System.out.println(computeNumberOfWays(4, 3));
    }

    /*

sdpatil

import java.util.Arrays;

/*
    Problem: Given cost of ticket for each station from A to B as 2 dimensional matrix
    what is the minimum cost that you can use to travel
 */
public class MinTicketCost {
    public static void main(String[] argv) {
        int[][] cost = {
                {0, 10, 75, 94},

sdpatil

/**
 * Problem: Compute the right sibling tree
 */
public class ComputeRightSiblingTree {

    public void constructRightSibling(BinaryTreeNode<String> treeNode){
        BinaryTreeNode<String> leftStart = treeNode;

        while(leftStart != null && leftStart.left != null){
            populateLowerLevelNextField(leftStart);

sdpatil

/**
 * Problem: Write a program that computes exterior of binary tree
 */
public class ComputeExteriorOfBinaryTree {

    public List<BinaryTreeNode<String>> exteriorBinaryTree(BinaryTreeNode<String> tree){
        List<BinaryTreeNode<String>> result = new LinkedList<>();
        if(tree!= null){
            result.add(tree);
            result.addAll(leftBoundaryAndLeaves(tree.left, true));

sdpatil

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Problem: Calculate binary tree from preorder and inorder traversal

    Solution: First node in preorder traversal will give us the root node of tree, The root node divides the
 inOrder list into 2 parts, first part is the left sub tree and second part is the right subtree

sdpatil

import java.util.List;

/*
      Problem: Given pre order traversal data of a binary tree where null markers are used when a node is empty
      construct binary tree
      {"H","B","F",null,null,"E","A",null,null,null,"C",null,"D",null,"G","I",null,null,null}
                     H
            / \
           /   \
          /     \