sdpatil

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

/*
  Problem: Perform in order traversal of binary tree without using recursion or stack (No space)
*/
public class InOrderTraversalWithConstantSpace {

    public void inOrderTraversal(BinaryTree<Integer> tree) {
        BinaryTree<Integer> prev = null;

sdpatil

/**
 * Problem: Write a program that efficiently computes the kth node appearing in an inorder traversal. Assume that each 
 * node stores the number of nodes in the subtree rooted at that node
 */
public class ComputeKThNode {

    /*
    Basic idea is if k is less than number of nodes in the left subtree then k is in the left subtree if not then k 
    is in the right subtree. Also if the left node has L nodes then k is the K-L th node in the right subtree
     */

sdpatil

/**
 * Problem : FInd successor of a node in inorder traversal
 */
public class FindSuccessor {

    public BinaryTree<Integer> findSuccessor(BinaryTree<Integer> node) {
        BinaryTree<Integer> next = node;
        //If the node has a right child then go to right child and find the first node by following left children

        if (next.right != null) {

sdpatil

/**
 * Problem: Create a API that allows you to lock nodes in a binary tree
 */
public class LockedBinaryTree {
    private Integer data;
    public LockedBinaryTree parent, left, right;
    private boolean locked;
    private int numLockedDescendant = 0;

    public LockedBinaryTree(Integer data, LockedBinaryTree parent) {

sdpatil

/**
 * Problem: Design an algorithm to compute the sum of the binary numbers represented by the the
 * root-to-leaf path
 */
public class SumRootToLeafPaths {


    public int sumRootToLeaf(BinaryTreeNode<Integer> tree) {
        return sumRootToLeafHelper(tree, 0);
    }

sdpatil

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

/*
   Problem: Write a program that takes an array and returns the length of the longest
   subarray with the
   property that that all its elements are distinct
   Ex. {f,s,f,e,t,w,e,n,w,e} then longest subarray without duplicate is {s,f,e,t,w}
   Solution:- Maintain a map of character to when that character was last appeared

sdpatil

import java.util.*;

/*
Problem: Given a string of strings and set of keywords, find the smallest section of iter that contains all the
keywords.
Basic idea: First create dictonary of keywords with values equals to zero.
 Then start iterating through the paragraph, once we find one of the keyword, put it in map along with the
 index where the word was seen. Once we have all the keywords with values set to index, then that means we saw
 all the keywordsNow calculate index of the farthest seen keyword thats the start and current index is end of subarray.
 Then keep checking if the distance between first and last index of keyword is smaller than current distance if

sdpatil

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

/**
 * Problem: Write a program that takes two arrays of strings and returns the indices of the starting and ending index of
 * a shortest subarray of the first array that sequentially covers all the values in second array
 */
public class FindSmallestSubarraySequential {

sdpatil

import java.util.Arrays;

/**
 * Created by sunilpatil on 2/25/17.
 */
public class NumberOfScoreCombinations {

    /**
     * Basic question is if you have three plays {1,2,3} how many ways you can combine them to make total score of 5.
     * create a dp table with rows equal to number of individual score and columns equal to total score,

sdpatil

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

/**
 * Problem: Calculate fibonacci sequence number for given number n
 * Ex. Fibonacci series generates numbers in the form n-1 + n-2
 * 0 1 1 2 3 5 8 13 21 34 
 */
public class Fibonacci {
    private Map<Integer, Integer> cache = new HashMap<Integer, Integer>();