Smallest positive number.

You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space.
Eg: 
Input = {2, 3, 7, 6, 8, -1, -10, 15}
Output = 1


Input = { 2, 3, -7, 6, 8, 1, -10, 15 }
Output = 4


Approach:
Put all the numbers from array in the hashmap, and then starting from 1, check all the natural numbers in the map, the first number not there is the answer.

Least natural number.

Given a set of natural numbers N = {1,2,3,4,5 ... infinity}
And another array A with random numbers, now find the least natural number which is not present in array A.


Example:
A = {9, 8, 5, 1, 15}
here least natural number which is not present in A is 2.


Example2:
A = {5, 7, 2, 1, 4}
here least natural number which is not present in A is 3.




Approach:
1. Take a bit vector propertional to the size of array A.
if we consider the first example then our bit vector would be of size 5.
A = {9, 8, 5, 1, 15}
initially bit vector would be like:
0 0 0 0 0 
2. Go through elements in array A and set the corresponding bit vector.
A[0] = 9
since bit vector size is 5, we cant set 9th bit vector so we ignore 9.
A[1] = 8
since 8 > bit_vector_size(5), we ignore it.
A[2] = 5
we set 5th bit vector.
0 0 0 0 1
A[3] = 1
we set the 1st bit vector
1 0 0 0 1
A[4] = 15
15 > bit_vector_size(5), we ignore it.


Now our bit vector looks like:
1 0 0 0 1


And our answer is the first unset bit vector, that is 2.


time complexity: O(n) where is n is the size of array A.
space complexity: O(n) where n is the size of the array A.

Design Pattern: Observer pattern.

Head First - Design Patterns: chapter 02 notes:


The Observer Pattern defines a one-to-many dependency between objects so that when one object changes state, all of its dependents are notified and updated automatically.


Design Principle
Strive for loosely coupled designs between objects that interact.


Loosely coupled designs allow us to build flexible OO systems that can handle change because they minimize the interdependency between objects.

Design Pattern: Strategy pattern.

Head First - Design Patterns: chapter 01 notes:

Design Principle
Identify the aspects of your application that vary and separate them from what stays the same.


Take what varies and “encapsulate” it so it won’t affect the rest of your code.
The result? Fewer unintended consequences from code changes and more flexibility in your systems!


Design Principle
Program to an interface, not an implementation.
“Program to an interface” really means “Program to a supertype.”


Design Principle
Favor composition over inheritance


The Strategy Pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. Strategy lets the algorithm vary independently from clients that use it.

Construct binary tree from inorder and preorder.

In Binary tree .. from the in-order traversal and pre-order travrsal .. construct the tree.


Input:
int [] inorder = {5, 9, 7, 8, 2, 10, 3};
int [] preorder = {8, 9, 5, 7, 10, 2, 3};


output:
printing inorder of the built binary tree: 
5 9 7 8 2 10 3 


Approach:
1. First data of preorder Array is 8, so it would be root of the binary tree.
2. All the elements in inorder array before 8 would be the left subtree and all the elements to the right of 8 in inorder array would be right subtree.
3. develope the recursion based on 1. and 2.

Longest Arithmetic Progression

Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that 
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. 
The sequence S1, S2, …, Sk is called an arithmetic progression if 
Sj+1 – Sj is a constant


{2,3,5,7,8,11}


DP solution with O(n^3). 
Assume, we've optimum solution for array a[0,1,2,....,k]. To get solution for index = k+1, we can put a[k+1] next in a sequence ending with a[j] for 0 <= j <= k. 
So, if diff = a[k+1] - a[j], we need to look up sub-problem solution for index = j to search for diff, and taking the max value to get a maximum sequence.


code input/output:
{2,3,5,7,8,11};
max seq: 2, 5, 8, 11
DP array values:

0 0 0 0 0 0 
1 0 0 0 0 0 
1 1 0 0 0 0 
1 1 2 0 0 0 
1 1 2 1 0 0 
1 1 1 2 3 0 

Valid phrases from text.

You have given a dictionary and a string, you need to separate words that are in dictionary.
ex - catsanddog (here cat and cats both can be in dictionary)
output - cats and dog


Approach:
1. Lets say the length of the string is n and init phrase String as empty.
2. Now for every substring S[i,j] (0<=i<=j<n), check if its a valid word - check against the dictionary.
3. If we get a valid word then append it to the previously calculated and running phrase with a space.


Code input/output:
Input String: catsanddog
valid phrases:
[cats and dog]