Saturday, July 11, 2015

Today we discuss a book review summary of the book  "How the World sees you" by Sally Hogshead with the motto - Discover your highest value through the science of fascination
There is power in understanding how the world sees you : you appear confident, authentic and ready to make a positive impression. This book gives a step by step method to describe yourself in one or two words which then becomes your tag. This book helps you with some of the terms. Your slogan helps you  in all walks of life from writing that self-introduction on a new job to pitching your profile on LinkedIn.
This book differs from some self-improvement books in that it does not ask you to change but to be more of who you are. It should help you better relationships and grow your business.
This book focuses on the seven fascination advantages and its discussion.
When we are born, we are automatically fascinating to the world with our gestures but over time we acquire layers of what makes us boring. For example, you don't want to stand out with your ideas or present them as insipid as possible to avoid attracting criticism. We want to become unnoticed when we want to avoid being seen as unworthy. However hiding works temporarily and usually backfires. Sometimes we feel we don't have anything noteworthy but that only dulls our edges.
As conversations become compressed in a more crowded marketplace, you need to know your strength and your differences. We need to know our values and the highest distinct value.
Likability and leadership are improved with fascination advantages. With such an advantage, when you talk, people will listen and remember you and even anticipate your messages.
One example of why this is important is given by the experiment of Joshua Bell. As a famous violinist, he could command a lot of money for his skills. When he agreed to participate in an arranged experiment to play in a subway station, the throng passed by in their rush. This tells us that no matter how good we are, we need to do more to fascinate others in a highly demanding environment.
There are three deadly threats in a competitive environment:
Distraction - that threatens the connection with others. Typically a listener only gives the first nine seconds You have to add value in that golden window
Competition  - which threatens your ability to differentiate and win. Customers want to try out something different. And you are already different.
Commoditization - which threatens your relationships and loyalty. This can seep into your relationships and erode your connections to the point of being replaced.
You can triumph by adding distinct value: This makes yobyu become admired for a noteworthy ability and for being worth more than you are being paid. You deliver more than you would normally be expected. You become preferred even if you are more expensive or less convenient.
Highest Distinct Value has a meaning in each word.You discover it by recollecting what it means to be in fascination. Its the state of being completely engaged mentally, emotionally and physically.
The Art of Fascination comes with the triumph of adding distinct value over the threats of distraction, competition and commoditization.  The key here is to fully recognize your differences rather than just the strengths. When you communicate, you are either adding value or taking up space. That's why those "Touchpoints" are important. Every touch point should highlight why you are different and better. Maximize value and subtract everything else.
The  Seven Fascination Advantages are
1) the power advantage - leading through authority where the power personalities speak the language of confidence. You will take charge of the conversation because you are decisive and self-assured.
2) the passion advantage - you create warm emotional connections. You are approachable and gregarious. Use reassuring terms such as "you bet"
3) the mystique advantage - This is about thinking before speaking. Mystique personalities speak the language of listening. You see nuances and you think things through.
4) the prestige advantage - Achieving success with higher standards You should speak the language of excellence
5) the alert advantage - You use careful precision. You speak details where it matters. They are risk averse.
6) the innovation advantage - You speak the language of creativity. You propose unexpected solutions or come up with a profusion of ideas.
7) the trust advantage - you pay attention to building loyalty over time.
At this point you should list your advantages as primary + secondary to articulate your highest distinct value.

#codingexercise
Given a binary tree implement an iterator that will iterate through its elements.
public interface ITreeEnumerator
{
 bool MoveNext();
 void Reset();
}

public class TreeEnum: ITreeEnumerator
{
   Stack<Node> inorder = new Stack<Node>();
   Node current = null;
   Node root = null;
   public TreeEnum(TreeNode n){
       root = n;
       Leftmost(n);
   }
   private void Traverse() {
      current = inorder.pop();
      Leftmost(current.right);
   }
   public void Leftmost(Node n){
     while (n != null) {
              inorder.Push(n);
              n = n.left;
     }
   }
  public bool MoveNext() {
      if (inorder.IsEmpty() == False) {
          traverse();
          return true;
      }
      return false;
  }
 public void Reset() {
   if (root){
           Leftmost(root);
   }      
 }
}

Implementation of partition method in quicksilver
int partition ( ref int [] A, int start, int end){
Int I = start - 1;
Int r = end - 1;
For ( int j = start; j < r; j++)
{
    If ( A [ j ] < =A [r] ) {
         i = i + 1;
         Swap ( A[i] , A [j] );
    }
 }
   Swap (A [i+1], A [r]);
return i + 1;
}


Friday, July 10, 2015

Today we discuss a coding problem.
Question: Given a series of numbers from 1 to pow (2, n) on a paper, we fold it in the following way  with the help of two commands
L : Fold the paper from left edge to right edge
R : Fold the paper from right edge to left edge
For n = 1 we have numbers 1,2
These can be folded in two ways L & R
L makes the number 1 come on top of 2
R makes the number 2 come on top of 1
And a sequence of alternating L and R.
After n number of commands there will be a number in each layer
We have to print it from top to bottom as
{1,2} in this case.
Solution Note that folding only involves left and right commands
And this is repeated for log N steps
If we maintain a list for each index, folding causes elements to be added onto each index from another index.
In each step these lists on either side of the center come closer until there is only one.
With a data structure as a list of list for current and previous iterations,
We can iterate for log N steps and merge according to whether the command is left or right

// partial code
List<int> Fold(List<int> numbers>)
{
string command = "L";
var curr = new List<List<int>> ();

for (int i = 0; i < numbers.Length; i++)
{
      curr.append (new List<int>(){ numbers[i]});
}

For (int i = 0; i < curr.length/2; i++)
{
       if (command == "L")
       {
            for (k = 0; k < curr.length / 2; k++)
                Merge(ref curr, k, length-1-k);
            LeftShift(curr, curr.length/2);
       }
       else
       {
            for (k=0; k < curr.lenght / 2; k++)
                Merge(ref curr, length-1-k, k)
            RightShift(curr, curr.length/2);
       }
}
return curr[0];
}

void Merge(ref List<List<int>> curr, int src, int dest)
{
// source will have its list reversed and pushed at the front of the list on destination
// source list will be set to null
}
LeftShift and RightShift will trim the left and right null lists.

Another question along similar lines is that there are two arrays given and we can sort all the elements of array A in the order of B. Then the remaining elements of A can be sorted in that order.

Question : Given an array where each element is maximum +-k index away from its sorted position, find an algorithm to sort such array. 
Solution : We will assume n = number of elements in array is greater than k.  
 
One solution is to use InsertionSort. It will benefit from the property of the given array because it won't have to traverse the entire length of the array in the worst case. 
The Insertion sort goes like this :  
for int i = 1 to len(A) -1 
   j = i 
   while( j > 0 and A[j-1] > A[j]) 
       swap(A[j] and A[j-1]) 
       j = j - 1 
 
 
Another algorithm cited online was to use a heap of size 2K. As the elements fill up, we could take the minimum and output it. This does not affect the input array.  
However this will not work because the heapsize has to be all the elements of the array for this kind of sorting to work because the choice of the first 2k elements does not guarantee that the successor of the next element will be found  
 
 
Question: Given a string left rotate it by a given number of times. 
Answer: Let us first write it down as it is described. 
void Rotate(Stringbuilder b, int n) 
while (n) 
  char c = b.removeAt(0) 
  b.append(c) 
  n-- 
return b; 
Next the optimal solution would be to split the string at the index and swap the two partitions 
 
Question: Given a number between 0 to 1000, raise 11 to that number and determine the count of times '1' appears in the result. 
Answer: Generate the Pascal numbers with levels upto and inclusive of that number. Then for each number appearing at that level test and count the number of ones. 
 
Question: given a string of characters x and o where x and o are interspersed, find the cheapest way to group all the x together. Each movement of a letter is expensive. 
Answer: we can find the weighted average of the index by taking a weight of 1 for all x and a weight of 0 for all o. Then we can shift all the x’s closer together to this index. 

Question Write SQL to calculate the number of work days  between two dates
Answer:
SELECT (DATEDIFF(dd, @StartDate, @EndDate)+1) - (DATEDIFF(wk,@StartDate,@EndDate)*2)
-(CASE WHEN DATENAME(dw, @StartDate) = 'Sunday' THEN 1 ELSE 0 END)
-(CASE WHEN DATENAME(dw, @EndDate)='Saturday' THEN 1 ELSE 0 END)
 
Question: Design a file search utility
Answer: A depth first traversal with escape for current and parent folder notations.
 

Thursday, July 9, 2015

Today we discuss MapReduce algorithm in Hadoop with reference to their documentation.
MapReduce processes vast amounts of data in parallel on large clusters(thousands of nodes) in a reliable fault-tolerant manner.
A MapReduce job usually splits the input data set into independent chunks which are then processed in a shared nothing model by map tasks. The outputs of the maps are then input to the reduce tasks. The framework stores the input and output of a job in  a filesystem, schedules the processing, monitors the activity and re-executes failed tasks. The framework employs a master slave model for the execution of the map and reduce.
 While the jobs are monitored and completed by the framework, their configuration including the input or output locations are specified by the applications.
At each stage of the processing - the map, combine, reduce steps take the <key, value> pairs as the input and output.  Both key and value implement the writable interface and the key classes have to implement the writablecomparable interface.

For eg:
public static class Map extends MapReduceBase implements Mapper<LongWritable, Text, Text, IntWritable>{
public void map (LongWritable key, Text Value, OutputCollector<Text, IntWritable> output, Reporter reporter)
:// eg tokenizes a sentence into words
}
}

public static class Reduce MapReduceBase implements Reducer<Text, IntWriteable, Text, IntWriteable> {
public void reduce (Text key, Iterator<IntWriteable> values, OutputCollector<Text, IntWriteable> output, Reporter) {
:// counts the number of words encountered
}
}
The Mapper splits the line into tokens which the tokenizer emits as a keyvalue pair of the words and the counts.
The Reducer sums up the values which represent occurrences for each key.

Together the mapper and the reducer form the payload to the framework and are specified by the applications.
 The Mapper decides on the number of maps based on the input data and blocksize. The Reducer has three primary phases - shuffle, sort and reduce.  Shuffle takes the sorted output of all the mappers as input. Reducer inputs are grouped by keys during sort. Both shuffle and sort occur simultaneously as map outputs are fetched. The output of the reducer is not sorted. A partitioner partitions the key space. It controls the partitioning of the keys of the intermediate map-outputs. By default, a hash function is used to derive the partitions. A reporter reports progress and relevant application-level status messages. An OutputCollector collects data output by the Mapper or the reducer.

Wednesday, July 8, 2015

1)  Given two strings find the longest common substring.  We can use dynamic programming for this. 
We define the optimal substructure as follows: 
Let S be a string of length m and T be a string of length n. Recall that the pattern matching of strings involved computing a prefix. Here too we find all possible prefixes and taking any two prefixes, we choose the one with the longest suffix.  
This can be written as  
The longest common suffix = 
                 LCSuffix(S1p-1, T1..q-1)+1  if S[p] = T[q] 
                 0 otherwise 
Then we can choose the longest common substring as the max of the longest common suffixes for i ranging from 1 to m and j ranging from 1 to n. 
LCSubstr(S,T) = max 1<= i <=m  and  1<= j <=n  LCSuffix(S1..i, T1..j)

We will investigate suffix tree for solving this. A suffix tree helps arrange the strings as a path from the root to the leaves with the strings denoted by numbers and appearing at the leaves of the suffix tree. The problem then can be translated to one which finds out which strings appear below each node. The tree is traversed bottom up ( which means level order traversal with the results reversed level wise) and a bit vector is maintained for all possible strings. Alternatively the lowest common ancestor of two strings can be found out.

Suffix tree reminds us of a trie. A prefix tree is also a trie. Both have special terminators on the nodes to signify the end of a string or word.

Another interview question is as follows:

Given a csv of name and age of persons, sort it by age. For this we could use a list data structure that already has a method sort and can take an IComparer for duplicates. And duplicate elements can also be stored as lists within the overall list. Of course, .Net also provides a tuple collection.

Another interview question is based on levels of friendship:
Given the input as
A: B C D
D: B E F
E: C F G
This produces the output as
Level 1 : B, C, D
Level 2 : E, F
Level 3 : G

The given example has no cycles in the graph. So starting at the root as the chosen node, we can form a tree and then complete a Level wise traversal to find the next levels of friendship.

However, the problem may not be restricted to acyclic graph even if it is directed. Hence we maintain a queue for each level

Monday, July 6, 2015

We review another example of moving on a checkerboard . We are given an n by n checkerboard it's valid to move ftom any of the boxes on the bottom to goto any of the boxes in the top board.  A move can only be made to a square on the top left, directly above and a top right as long as they are within the square checkout  each move results in a positive or negative amount of money . We have to find the optimal set of moves that maximizes profit.
We apply dynamic programming by defining the opt optimal substructure.
The current position i,j can be moved to from one of three positions in the row below. Because we make an opt choice in this move, the previous set of Moves upto and inclusive of the previous position is also optimal.
Hence we define as recurrence relationship as

Next move = p [(i-1,j-1), (i,j)] + d (i-1,j-1)
                     = p [(i-1,j), (i,j)] +d (i-1,j)
                      =p[i-1, j+1 , (i,j)] + d (i-1, j+1)
And repeat for n steps.
The bottom up method would be like this:
let d[1..n, 1..n] and s[1 .. n-1, 2..n] be new tables for cost and index of optimal

for i = 1 to n

    d[i,i] = - infinity

for l = 2 to n // chain length

     for i = 2 to n-l+1

           j = i+l-1

           d[i,j] = - infinity

           q = max ( p [(i-1,j-1), (i,j)] + d (i-1,j-1)

                     , p [(i-1,j), (i,j)] +d (i-1,j)

                      , p[i-1, j+1 , (i,j)] + d (i-1, j+1))

                 if q > d[i,j]

                     d[i,j] = q

                     s[i,j] = k

return d and s


The top down strategy using recursion is as follows:

RecursiveStepping (i, j, d)

   If I == n-1
         Return d(i,j)
   Q = max (p [(i-1,j-1), (i,j)]+ RecursiveStepping (i-1,j-1,d)

                     , p [(i-1,j), (i,j)] +RecursiveStepping(i-1,j,d)

                      , p[i-1, j+1 , (i,j)] + RecursiveStepping (i-1, j+1, d))
    If q > d (i,j)
      D (i,j) = k
   Return d(i,j)

We review a coding question to determine the count of numbers that have 4 as a digit from 1 to n.

int getCount(int n)
{
  int count = 0;
  for (int i = 0; i < n; i++)
           if (has4(i)) count ++;
  return count;
}

bool has4(int n)
{
   while (x != 0)
   {
        if (x%10 == 4)
          return true;
        x = x / 10;
   }
   return false;
}

We review webhooks today. We discussed that they were useful for notifications in REST API implementation.

In addition, Web hooks do the following :
1) keep Data in sync
2) give other applications a chance to do something
3) provide necessary params on certain events

Web hooks take a URL to send the notification to. A "postbin" web service will receive and log the notifications so that it can monitor all POST HTTP requests it receives.  This URL is taken from a registration form hosted by the publisher.  When this notification arrives, the subscriber can choose to respond by making additional API calls based on the information in the notification.

If the registration is to be avoided, APIs can optionally take a callback parameter that takes in a URI. This way during the execution of this specific API, a POST method will be called on the URI provided with a predetermined template of information. This lets the caller subscribe and unsubscribe dynamically.




Saturday, July 4, 2015

#codingexercise
Write an efficient program to reverse the bits of a number.
We do this by looping through the number and testing each bit. If the bit is set at position i then we set the bit at total_number_of_possible_bits -1 - i in the reverse number.
unsigned int reverseBits(unsigned int num)
{
unsigned int number_of_possible_bits = sizeof(num) * 8;
unsigned int reverse_num = 0;
for (int i = 0; i < number_of_possible_bits; i++)
{
int temp = (num & (1 << i );
if (temp)
    reverse_num |= (1 << ((number_of_possible_bits - 1) - i));
}
return reverse_num;
}

Another coding interview question is how to count the number of binary search trees that are within a numerical range?.
This can be found by performing  a  traversal
If the subtrees are in range the root is also in range.

bool getCount(Node root, ref count)
{
if (root == NULL) return true;
Bool l = false;
Bool r = false;
if (root.left) l = getCount(root.left, count);
if (root.right) r = getCount(root.right, count);
if ( l && r && inRange(root.left, root.right))
  count++
return false;
}

Another interview problem is schedule a meeting
Given an employee array of a large number of employees, find a window of time with maximum duration for a meeting that suits all the employees in the input.
Since each employee has different availabilities we can first find the availability ranges for each employee. This may result in a number of time Slots greater than the number of employees. Then taking time as increments of  time slices such as a minute, we can write them down as sequences. After that we can find the longest common subsequence. This approach can scale to any length and number of time range of employees when the time slice increments are more granular. It also finds a maximum number of employees who can make it to a meeting when all cannot.
This problem can be attempted in many ways but we focus on one based on max flow algorithm. The reason we choose maximum flow is because we want to find the window that is maximum.  We consider Ford Fulkerson algorithm.
Before using Ford Fulkerson, we have to transform the problem from multisource multisink to single source single sink by adding a consolidated source and a consolidated sink.  Each flow is considered as a viability for an employee and the max flow is when we can augment this flow for all the employees. We consider granular time slots for augmenting this maximum flow. Then we add increment timeslots for maximum duration of the meeting.