Some programming questions revisited:

1. Longest Common Subsequence: 

1. For two sequences X and Y, we determine Z as the LCS by iterating over each element in X as i and Y as j. The length of LCS is  

1. 0 if i = 0 or j = 0 

2. C[i-1, j-1] + 1 if i,j > 0 and xi = yj 

3. Max(c[I, j-1], c[i-1,j) if i,j > 0 and xi <> yj

2. Find longest increasing subsequence 

1. For element I from 0 to length of the sequence 

2.      For element j from 0 to I 
1. If criteria and best[j] + 1 > best[I] 
2. Update best[I] with best[j]+1

4. Merge Intervals 
   

   1. Sort the intervals based on start time 

   2. Using a stack initialized with the first interval 

   1. If the top of the stack is not overlapping with the next interval, push it on the stack 

   2. Update the end time of the top of the stack 

    
5. Given a string and a dictionary of words, determine if the string can be segmented into one or more dictionary words  

1. Assuming limited dictionary, maintain an array T of one more than string length such that 

1. T[i] = true implies 0 - i - 1 can be treated as a word boundary and segmented using dictionary, t[0] = true 

2. For each position in the string 

1. We evaluate only if there is a match 

2. Foreach word in the dictionary 

1. If the length + position is already a known word boundary or exceeds the string length, we continue 

2. We set this position as a word boundary 

2. We can simplify the code with 

1. Test both the presence of the substring before the position in the dictionary 

2. And recurse for the position beyond the substring 

5. Find the minimum number of one letter transformations from  

1. Each word could be associated with a number of steps. This will help during BFS 

2. Starting with a  word 

1. If this is the destination word, return its step number 

2. For each of its positions 

1. Switch the character with one from a to z skipping itself 

1. If the dictionary contains this word 

1. add it to the queue with incremented step number 

2. remove the word from the dictionary 

6. Median of two sorted arrays 

1. Sequentially merge from both arrays by taking the minimum from either 

2. If one gets over, take from the other 

3. Stop after the desired number of elements in merged
Find the maximum rectangle under a histogram
1.       Initialize the return value
2.       For each histogram top as the top left of the rectangle,
a.       Find the span it has across the histogram
b.      If this area is greater than max, update max
3.       Return max