#codingexercise
find the least common ancestor of two nodes
Node GetLCA (Node root, int n1, int n2)
{
if (root == null) return null;
if (root.data == n1|| root.data == n2) return root;
var left = GetLCA(root.left, n1, n2);
var right = GetLCA(root.right, n1, n2);
if (left && right ) return root;
if (left != null) return left;
return right;
}

Find middle of linked list
void GetMid(Node root)
{
var slow = root;
var fast = root;
while( fast && fast.next && fast.next.next)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

Print Left View of a tree
void LeftView(Node root)
{
int max = 0;
LeftViewHelper(root, 1, ref max);
}

void LeftViewHelper(Node root, int level, ref int max)
{
if (root == null) return;
if (level > max){
print root.data;
max = level;
}
LeftViewHelper(root.left, level+1, max);
LeftViewHelper(root.right, level+1, max);
}


Subjective  question : Are solaris zones good or bad ? Give examples
Solaris zones or containers are easy and lightweight. They are not like running a full OS on VMWare. It is just enough for OS to be separate but lightweight but we can run dozens even hundreds.
Applications that had virtually unrestricted physical resource in the native solaris OS do not nearly have the same on a  solaris zone so they are not able to transition without breaks in many cases.

#sorted array to a balanced binary search tree
Node GetTree(List<int> A, int start, int end)
{
if (start > end) return NULL;
int n = end-start+1;
int median = (start+end)/2;
var root = new Node();
root.data = A[median];
root.left =  GetTree(A, start, median-1);
root.right = GetTree(A, median+1, end);
return root;
}

#codingexercise

Given n non-negative integers in array representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

int GetArea(List<int> height)
{
int result = 0;
int n = height.Count
if (height == null || n <=2)
    return height;
var left = new List<int>();
var right = new List<int>();
// scan left
int max = height[0];
left[0] = height[0];
for (int i = 1; i < n; i++)
{
if (height[i] < max){
left[i] = max;
}else{
left[i] = height[i];
max = height[i];
}
}
// scan right
max = height[n - 1];
right[n-1] = height[n-1];
for (int i = n-2; i>=0; i--)
{
if (height[i] < max){
right[i] = max;
}else{
right[i] = height[i];
max = height[i];
}
}
for (int i =0; i < n ; i++)
{
result += Math.min(left[i],right[i]) - height[i];
}
return result;
}

int match(char* regexp, char* text)
{
if (regexp[0] == '^')
    return matchHere(regexp+1, text);
do {
if (matchHere(regexp, text)
    return 1;
} while( *text++ != '/0');
return 0;
}

int matchHere(char* regexp, char* text)
{
if (regexp[0] == '/0')
   return 1;
if (regexp[0]  == '*')
   return matchStar(regexp[0], regexp+2, text);
if (regexp[0] == '$' || regexp[1] == '/0')
  return *text == '/0';
if ('*text != '/0' && (regexp[0] == '.' && *regexp == *text))
   return matchHere(regexp+1, text+1);
return 0;
}
int matchStar(int c, char* regexp, char* text)
{
do
{
if (matchHere(regexp, text))
    return 1;
}while(*text != '/0' && (c == '.' || *text++ == c);
return 0;
}
Courtesy: kerninghan & poker 

#codingexercise
Rotate a 2D array without using extra space for an array
void Rotate(ref int[,] A, int r, int c)
{
//Choose one square
//    Start with four corners    1   2
                                              4   3
//        swap one diagonal     4 with 2
//            swap horizontally  1 with 2, 4 with 3
//    Repeat for next four elements at the next position in clockwise
//Repeat for inner square
for (int k = 0; k < c / 2; k++){ // to progress to inner square corners
    int 1x = 0+k, 1y=0+k;
    int 2x = 0+k, 2y = c-1-k;
    int 3x = r-1-k, 3y = c-1-k;
    int 4x = r-1-k, 4y = 0+k;
    for (int m = 0; m < c-1; m++) // to progress along each side
   {
         Swap(ref A, 4x-m,4y,2x+m,2y);
         Swap(ref A, 1x,1y+m, 2x+m, 2y);
         Swap(ref A, 4x-m,4y,3x,3y-m);
   }
}
}

Find the minimum number of characters required to form a palindrome
int MakePalindrome(string A, int center)
{
int len = GetPalindromeLength(A, center);
if (len = A.length) return 0;
int min = INT_MAX;
for (int I = center-1; I  > 0; I--)
{
    len = GetPalindromeLength(A, I);
    if (A.length -len < min)
        min = a.length - len;
}
return min;
}

Fast modular exponentiation (Pow(A,B) % C)
{
int n = hcf(A%C, C);
for (int  i = 1; i < INT_MAX; i++)
      if (n *i > A)
           return A - n * i;
return A%C;
}

# better fast modular exponentiation
represent B in Binary and from right for the positions of the 1s, split B as  sum of 2^position
then take modulo of each component and take the product of the results.

Minimum Number following a pattern
DDIDDIID
321654798
//untested
int GetMinNumberFromPattern(string A)
{
int max = 1;
var number = new List<int>();
for (int I =0;i < a.Length; I++)
{
switch(A[I])
{
  case 'I':
      if (I==0) {ret.Add(last_incr);continue;}
           int start = I+1;
           int end = I+1;
           for (int k = start; k < A.Length && A[k] == 'D'; k++)
                 end++;
           ret.Add(max + end - start + 1);
           max = max + end - start + 1;
         break;
  case 'D':
      if (max > 1) {max--; ret.Add(max); continue;}
           int start = I;
           int end = I;
           for (int k = start; k < A.Length && A[k] == 'D'; k++)
                 end++;
           ret.Add(max + end - start);
           max = max + end - start;
  default:
     throw;
}
}
return ret.ToNumber();
}
int gcd(int x, int y)
{
if (y == 0) return x;
return gcd(y, x%y);
}

Count ways to reach the n’th stair
int f(int n)
{
if ( n <=1) return 1;
return f(n-1)  + f(n-2);
}

#autocorrect spelling implementation
First form a dictionary of all known words
Second train a model on the extracted words from a test. The words form the features. This could be a word count table or a radix tree aka trie.
Third, form a set of  modified words with insertions, deletions, substitutions of the given word.
Optionally form a set of known words from the modified words of step 3 and add it to the set generated.
return the max of the words from the set with the dictionary words as lookup keys.

#coding exercise
Find the minimum number of steps to reach the end of array from start. Array values give how much we can move.
Int GetMin( List <int> arr, int start, int end )
{
If (start == end) return 1;
Return min (
1 + GetMin (Arr, start+ arr [start], end),
GetMin (arr, start+1,end));
}

median of a stream of two numbers:
Maintain two heaps max and min
on a new number
       if (total size is odd)
             if max_heap size is >0 && num > median
                       max_heap.push(num)
                        heapify
                        num = max_heap.pop_back()
                        heapify
             min_heap.add(num)
              heapify
        else
             if min_heap size is > 0 && num < median
                          min_heap.push(num)
                          heapify
                          num =  max_heap.pop_back()
                           heapify
              max_heap.add(num)
              heapify
median :
     heap_size is odd
                  min_heap[0]
     else
                  (max_heap[0] + min_heap[0] ) /2

It may be better to rename the heaps as left and right because one will be max heap and the other will be min heap and we merely extract the top and insert. In other words we balance.

Find the maximum difference in the values between a node and an ancestor in a  tree
int GetMin(Node root, ref int max)
{
if (root == null) return INT_MAX;
int min_left = GetMin(root.left);
int min_right = GetMin(root.right);
int min =  min(root.data, min_left, min_right);
if ( root.data - min > max)
   max = (root.data - min);
return min;
}

Given n eggs and k floors where any egg might break when dropped from a certain minimum height, find the minimum number of tries to find the answer
int W(int n, int k)
{
if (k == 1) return 1;
if( n== 1) return k;
int min = INT_MAX;
for (int i = i; i <= k; i++)
     int val = max(W(n-1,i-1), W(n, k-i))
if ( val < min)
    min = val;
return 1 + min;
}
#autocomplete : https://github.com/ravibeta/javascriptexamples/blob/master/Autocompleteextender
Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j]
int GetMax(List<int> A, int start, int end)
{
int max = 0;
for (int k = start; k <= end; k++)
{
 int ret = k;
 int maxindex = k;
for(int I = end; I > k; I--)
     if (A[I] > A[k]){
           maxindex = I;
           break;
   }
if (maxindex-k> max)
   max = maxindex-k;
}
return max;
} 

Applications of Machine Learning for private cloud operations
We continue listing some more scenarios from yesterday's post.

Use case 8) Feature Extraction 

We want to find server request patterns from a set which can help with identifying themes that are independently present in various combinations. Like clustering, we are not interested in making predictions but in finding interesting things about the data. Similarly from server usage patterns, we may be able to find multiple underlying causes that combine to create results.

We find a feature matrix from that has a row for each feature and a column for chosen set of server requests. We also find a weights matrix that maps the features to the requests matrix. Each row is a request and each column is  a feature. From the data converted into a nested dictionary, we factorize to get the features and the weights matrix.
Use case 9) matching customers
Customers may request various resources from the cloud over time. They may be interested in servers, file shares at specific regions. If we help find a buddy for the customer, they may benefit from their common interests. 
We could use an advanced classifier like kernel methods and support vector machines to make predictions whether people with a given set of attributes will match or not.
#codingexercise
Find the minimum number of swaps required for arranging pairs adjacent to each other.
eg:
pairs[] = { 1->3, 2->6, 4->5 }
arr[] = {3, 5, 6, 4, 1, 2}

int GetMinSwaps(List<Tuple<int,int>> pairs, List<int> arr, int start, int end) start and end are  for the pairs
{
if (arr.Count <= 1)return 0;
if ( start >= arr.Count) return 0;
// no-op
if (arr[start] == pairs.find_match(arr[1])) return GetMinSwaps(pairs, arr, start+2, end);

int index = arr.find(pairs.find_match(arr[0));
Swap(arr, start+1, index);
int a = GetMinSwaps(pairs, arr, start+2, end);
Swap(arr,start+1, index);

index = arr.find(pairs.find_match(arr[1]));
Swap(arr, start, index);
int b = GetMinSwaps(pairs, arr, start+2, end);
Swap(arr, start, index);
return 1 + min(a,b);
}

int RemoveExtraSpaces(stringbuilder input)

{ 

var words = input.split(); 

return words.aggregate( (sent, next) => sent + " " + next); 

} 

Find the sum of bit differences between all pairs in an array of n integers 

Int bitdiff(List<int> arr, int n) 

{ 

int total = 0; 

For ( int I =0; I < 32; I ++) 

{ 

int count = 0; 

for (int j = 0; j <n ; j++) 

   if (arr[j] & (1 << i)) 

       count++; 

total += (count * (n-count) * 2); 

} 

return total; 

} 

Find next greater element for every element of an array to its right in O(n)
List<int> GetNextLargest(List<int> arr)
{
var greater = new List<int>(); // stores index
for (int i = 0; i < arr.Count; i++)
{
   int next = -1;
   for (int j = i+1; j <arr.Count; j++)
   {
     if (arr[j] > arr[i])
     {
         next = j;
         break;
     }   
   }
   greater[i] = next;
}
return greater;
}
Arrange balls in a line so that no two of the same type are together
Void arrange (ref List <ball> candidate, List <int> colornum, int start, int level)
{


For (int I = start, I < colornum.sum (); i++)
Candidate [level] = 0;
for ( int color = 0; color < colornum.count; color++)
If (level > 0 && candidate [level-1] != color && candidate( x => x == color) != colornum [color])
Candidate [level]  = color;
If (candidate.length == colornum.sum ())
   Print candidate.toString ();
If (I < colornum.sum ())
{
Arrange( ref candidate, colornum, start+1, level+1);
}

Candidate [level] = -1;
}

}

Applications of Machine Learning for private cloud operations
We continue listing some more scenarios from yesterday's post.

Use case 4) Optimization 

Users may want the portal to search for the lowest cost set of resources when there are many choices for their solution when there are many different solutions. Optimization finds the best solution to a problem by trying many different solutions and scoring them to determine their quality. 

First we propose a cost function to determine the costs for different sets of resources. Then we use hill climbing or simulated annealing to reduce the cost 

Use case 5) Document Filtering 

This is about training a classifier to classify documents that are published as resource usages and logs. The classifiers start off very uncertain and increase in certainty as it learns which features are important for making a distinction.  By classifying the documents, we expect to find resources that require attention either immediate or in the near future. 

This will require a training set as well as a test set. The training set will be used to tune the classifier and the classifier will then be run on the test sample. If the features are independent of each other they can be used in a naiive Bayes classifier. 

Use Case 6) Find which customers will likely pay for premium access. 

In order to predict the likelihood that a user will become a paying customer, we collect information and put it in say a table with the attributes that we pick from server logs, such as location, read FAQ, pages viewed, and whether a premium service was chosen. 

Then we use decision trees to construct a tree from real data that is easy to understand where each node tells how important it is and how it will impact the outcome. 

Use case 7) Building price models for premium customers. 

We can build models that predict prices. We can price something manually and then by finding the items that are similar to the item that interests the customer, the algorithm can average their prices and make a guess at what the price should be for this item.

#codingexercise

Write your own pow(x,n) 

int pow(int x, int n)

{

if (n == 0) return 1;

if (n%2 == 0)

   return pow(x,n/2) * pow(x,n/2);

else

   return x*pow(x,n/2) * pow(x,n/2);

}
Find the median of two sorted arrays
int median (List<int> first)
{
int n = first.count;
assert(n> 0);
if (n %2 == 0)
    return (first[n/2-1] + first[n/2])/2
else
    return first[n/2];
}
int GetMedian(List<int> first, List<int> second)
{
int p = first.count;
int q = second.count;
if ( p == 0) return median(second);
if (q == 0) return median(first);
if (p == 1 && q == 1) return (first[0]+second[0])/2;
int m1 = median(first);
int m2 = median(second);
if ( m1 == m2) return m1;
if (m1 < m2)
{
    if (p%2==0) 
        return GetMedian(first.Range(p/2-1, p/2+1), second);
    return GetMedian(first.Range(p/2, p/2), second);
}
if (q%2==0)
     return GetMedian(first, second.Range(q/2-1,q/2+1));
return GetMedian(first, second.Range(q/2,q/2));
}

Applications of Machine Learning for private cloud operations 

The following are some use cases for building smart web applications for a private cloud provider.  

Use case 1) Making recommendations 

Customers often have a variety of choices when they come to request resources from a private cloud. One way to help them would be to tell them what others like them have been leasing from the cloud provider. If we search a large group of people and smaller set with tastes similar to a customer in terms of what they have been liking or borrowing, then we can make a ranked list of suggestions by finding the people who are similar and combining their choices to make a list. 

Different people and their preferences can be represented as a nested dictionary. To find similarity among people, we could use some sort of similarity measures based on Euclidean distance or Pearson correlation. We can then score the items by producing a weighted score that ranks the participants. 

Use case 2) Discovering groups 

Customers can be pigeonholed by clustering and categorizing them based on their requests.  By determining the frequency of a certain type of resource in the requests made by the customers, we may be able to find customers who are similar in their needs or have similar planning. Such a result could be very useful in searching, cataloging and discovering the themes in the vast number of adhoc requests made over time. 

We can employ hierarchical clustering or K-means clustering to categorize the requests and relate personas to this shopping pattern. 

Use case 3) Searching and Ranking 

Searching and Ranking form the core of analytics for a customer when she wants to filter through support documents and literature. Very often customers will get a buzzword to search for and help themselves but they might not know the site layout or the categories to walk down to filter it. 

They can be helped with a page ranking that gives a weighted score based on the fraction of in-references to out references. Other ways of arranging them or finding results based on clustering can also help. 

#codingexercise 

Determine if three points are on a line

bool onSegment(Point p, Point q, Point r)

{

// q is on p r

if (q.x <= max(p.x,r.x)  && q.x >= min(p.x, r.x) &&

     q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))

{

 return true;

}

return false;

}

Determine if three points are oriented clock wise (1) or anti clockwise(2)

int orientation(Point p, Point q, Point r)

{

int val = (q.y-p.y)*(r.x-q.x) -

                (q.x-p.x)*(r.y-p.y);

if (val == 0) return 0;

return (val > 0) ? 1: 2;

}

Determine if two line segments intersect

bool intersect(Point p1, Point q1, Point p2, Point q2)

{

//  (p1,q1,p2) and (p1,q1,q2) have different orientations
and (p2,q2,p1) and (p2,q2,p1) have different orientations
// and they are all collienar and one point lies on the segment of the other two

}

Find the squares of the sides using distances (x2-x1)^2+ (y2-y1)^2

Lets call them a-sq, b-sq and c-sq, 

then if two of the squares add up to the third - it is right triangle

if two of the squares are greater than the third no matter which two are picked it is acute

else obtuse.