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.