Monday, August 17, 2015

Today we start the review of a book called Thirteeners. This book is written by Daniel Prosser.  The book is about why only thirteen percent of the companies execute their strategies. The author states that the key to this success is the real nature of human interaction and the key to success which is connectedness. He says that when the workplace environment is such that every team member supports the vision, then breakthrough results happen. Everything is a function of the types of conversation that you engage in and the conversations that create every dimension of your life are the conversations that let your business succeed. The author also provides some examples of such conversations
The conversations in which you say how : the author provides an example of two snow boarders who declared well in advance of a competition that they will win the monetary prize and they did. If you change the way you are looking at business, the business will change.
Such conversations happen when there is connectedness in the workplace.
He quotes a psychiatrist as saying that connectedness is the feeling of being part of something that is bigger than oneself. But its really the authors jargon for the force that urges us to ally, to affiliate, to enter into mutual relationships, to take strength and to grow through co-operative behavior.
There are a multitude of hidden, disconnecting conversations that are detrimental to our performance and only a handful that take strength to grow through co-operative behavior The author lists ten conversations that will help you tremendously. These 10 conversations are for and not about their topics. These topics are Contribution, Acknowledgement and appreciation, alignment, accountability, communication, relatedness, responsibility, Integrity, possibility and Fun, Rewards, Gratitude.
The author introduces us to the seeds of the conversations as memes. A meme is a unit of transmission of cultural ideas, symbols or practice. It facilitates the spread of such things from person to person through writing, speech, gestures, rituals and so on. Some people look at it as a culture's genes.In a workplace, the genetic code determines the success and failure of the organization. Sometimes there are limiting memes Such a conversation that becomes a viral meme is called an Execution Virus.
#codingexercise
int getDuplicate(int[] numbers) // max val less than length
{
for(int i =0; i < numbers.length; i++)
{
if (A[Math.Abs(A[i])] > 0 )
{
   A[Math.Abs(A[i])]=-A[Math.Abs(A[i])];
}
else
  return A[i];
}
}

Continuing with the book review above:
The author provides few different examples of converstations that obstruct. These include “It’s not our strategy”, “They treat us like shit”, “We’ve always done it this way”, “It’s the same old story” etc. He says this is further exaberated when the manager feels he or she is above the employees. This kind of disconnected company is termed ‘looking glass’ for two reasons. – the leader would see the company problems if they looked in the mirror and the employees reflect the thinking and behavior of their leaders.
To isolate such execution virus and to apply the vaccine of truth, the author says you have to take initiatives to find the memes. Though a negative meme cannot be removed, it can be replaced with a  positive meme through the following four step process.
-       tell the truth about your past – good and bad
-       identify the limiting and negative viral conversation
-       declare a positive future
-       adopt a system to keep the positive meme  active and replicating throughout your organization
In order to effect such a positive meme, you have to act as a leader.  You can do so by not providing all the answers but by leading the inquiry into the solutions.
The author urges us to take risks and step out of our comfort zone. He says business strategies fall into two categories.
The rower strategy  - this is where you are fighting alone to row upstream and avoid the turbulent downstream
The grower strategy – is about inventing something from nothing.  This strategy investigates all available possibilities at most times.
He says try not to get stuck in rower strategy and instead use the grower strategy.

The author also mentions that chaos is actually a great transformer so long as we are ready to tolerate the disequilibrium that comes with it.  The biggest mistake that organizations make is to quickly make sense of the situation and jump to judgements and only to regret it when the crisis has tided. Instead if we allow creativity and innovation to take over in such space.

Sunday, August 16, 2015

#codingexercise
A very common coding question is to find the duplicate in an array of n+1 numbers with values ranging from 0 to n. This problem has many variations and different solutions depending on the requirements. We will list some of these here.
The problems can vary in the following ways:
1) exactly one number appears in duplicate
2) more than one number appears in duplicate
3) number of elements in the array may be large
4) any number can appear any number of times

The solutions can vary depending on whether the
1) elements can be sorted
2) auxiliary storage is available
3) optimize for both storage and computation
4) solutions based on indices

Let us discuss a few approaches:
1) The O(n^2) approach
List<int> duplicates = new List<int>();
for (int i = 0; i < n; i ++)
    for (int j = i + 1; j < n; j ++)
        if A[i] == A[j] && duplicates.Contains(A[I]) == false
            duplicates.Add(i);
return duplicates;

2) The HashTable approach that uses a frequency count
    for (int i = 0; i < n; i++)
         H[i] += 1;

    foreach (var item in H)
        if H[i] > 1
              print H[i];

3) The linear scan approach when the elements are sorted:
      sort (A);
      curSum = 0;
      for (int i = 0; i< N; i ++)
           curSum += A[i];
      return sumofduplicates = n(n+1)/2 - CurSum;

4) If we are able to modify the array, one innovative example that appears in internet is to flip the sign of an element. And the next time we see a flipped sign we know it is a duplicate.
This works like this:
Traverse the array. Do following for every index i of A[].
{
check for sign of A[abs(A[i])] ;
if positive then
   make it negative by   A[abs(A[i])]=-A[abs(A[i])];
else  
   this   element (ith element of list) is a repetition

}



Saturday, August 15, 2015

Write a function to find the 2nd largest element in a binary search tree

This should be the predecessor of the largest item. In a binary search tree, the largest item is the rightmost  node.
Int GetMax(Node root)
{
  if (root == null) return root;
  while (root.right != null)
         root = root.right;
  return root;
}
Node GetPredecessor(Node root)
{
if (root == null) return null;
if (root.left)
{
Node current = root.left;
while(current && current.right)
   current = current.right;
return current;
}
Node parent = root.parent;
while(parent && parent.left == root)
{
   root = parent;
   parent =parent.parent;
}
return parent;

}

Find the duplicate element in an array of n+1 integers in the range 1 to n.


One of the common approaches is to sort the numbers then use binary chop
Or use the property that the sun of consecutive n numbers is n (n+1)/2

Thursday, August 13, 2015

#codingexercise
Write a function condense_meeting_times() that takes an array of meeting time ranges and returns an array of condensed ranges.
For example, given [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]
return [(0, 1), (3, 8), (9, 12)]
void condense_meeting_time(List<Tuple<int, int>> meetings)
{

Sort(ref meetings, compararer); //comparer sorts meetings by start time, end time

var merged = new Stack<Tuple<int. int>>();

merged.add(meetings[0]);

for (int i = 1; i < meetings.length; i++)
{
   var top = merged.Peek();
   if (top.Item2 == meetings[i].Item1)
   {
top.Item2 = meetings[i].Item2;
        merged.Pop();
        merged.push(top);
   }
   else if (top.Item2 < meetings[i].Item1)
   {
       merged.Push(meetings[i]);
   }
   else if (top.Item2 < meetings[i].Item2)
   {
top.Item2 = meetings[i].Item2;
        merged.Pop();
        merged.push(top);
    }

}

while (merged.empty() == False)
{
var top = merged.Peek();
Console.WriteLine("[{0},{1}]", top.Item1, top.Item2);
merged.pop();
}

}
Today we start the  review of a book titled the four disciplines of execution 4DX for short. This is not a strategy or theory book claims the authors - McChesney, Covey and Huling who are themselves Leaders in FranklinCovey - a company that consults on this practice in over 130 countries.
To begin with 4DX talks about the challenges in execution - major initiatives crash with a thud, important initiatives are quietly scuttled, and the overall distraction of the whirlwind - a term used to describe the chores that take a disproportionate amount of time from your goal or cause a randomization of your tasks. This book says the author is not about managing the whirlwind but to effectively meet your wildly important goals (WIG)  even in the face of a whirlwind and can help you reclaim as much as 20 percent of your time for your WIG. A WIG is one that can make all the difference. By such a definition, a WIG has to be narrow and focused.   A WIG not only gives you direct benefits but also gives you new levels of performance.  You can choose it from within the whirlwind or outside. But the following practice will help:
1) no team focuses on more than one or two WIGs
2) the battles you choose must win the war
3) senior leaders can veto but not dictate the goal.
4) All WIGs must have a finish line and a duration.

The above rules help you narrow and find your WIG. 
The next set of rules is to act on the lead measures. 
A lag measure tells you if you have achieved the goals, a lead measure tells you how likely you are to achieve it. 
To define and track a lead measure, the authors cited an example of how the managers of a baseball team determined that the number of runs was the criteria to find the most productive player. Defining such a lead measure makes everyone feel empowered to achieve it.

Then the third discipline is to keep a compelling scorecard. Everyone should know the scorecard at all times. This will let them know whether they are winning or losing. When the scorecard is easy to visualize and updated regularly, the whirlwind will not take it away from you. Great teams must know whether they are winning or losing otherwise they will not know what works and doesn't to win. Everyone gets to see the scorecard and everyone knows what to do to win.
A scorecard should be
1) simple just like a scoreboard in a game
2) it should be prominent just like the scoreboard
3) It should show lead and lag measures
4) and it should tell at  a glance whether you are winning or losing

Finally the fourth discipline is creating a cadence of accountability - a frequently recurring cycle of accounting for past performance and planning to move the score forward. Discipline 4 is where execution happens because the team meets at least weekly in a WIG session. The meeting lasts no longer than 20 to 30 minutes, has a set agenda and goes quickly In this meeting, you should hear account reports from everyone, you should review the scorecard to learn from successes and failures, and to clear the path and make new commitments. Blockers for any person must be discovered and removed. Each fresh commitment must meet two standards - it must represent a specific deliverable and it must influence the lead measure.

The authors say that the accountability here is different from the usual organizational one. It's more personal. Instead of saying it is to an outcome, it is something to yourself When this resonates with the peers, it improves the performance of the team dramatically. The WIG session encourages experimentation with fresh ideas. It engages everyone in problem solving and promotes shared learning.

Having discussed what the 4DX is, the authors outline the different stages of behavior change.
Stage 1) Getting clear  - this is when the team knows what WIG and 4DX are , 2) Launch stage - this is when the leader and the team get together to focus, 3) adoption This is probably the stage that takes most time  When the WIG sessions begin to go smoothly, you know that this stage is being met. 4) Stage 4 - optimization - this is to brainstorm and follow through on efficiencies and Stage 5) Habit stage. This is when you have to make the habits of what has been working for you

Now each of the items in a bit more actionable mention so that you can install them:
Step 1 : Consider the possibilities:
Brainstorm with peer leaders
Brainstorm with your team members
Brainstorm alone
Step 2: Rank by impact
When you are satisfied with your list of candidate Team WIGs, start prioritizing
Step 3: test top ideas -
Is the team aligned to the overall WIG
Is it measurable
who owns the results
who owns the game
Step 4 : Define the WIG
Once you have selected and tested the ideas for high impact team WIGs, define it as follows:
1) begin with a verb
2) define the lag measure
3) keep it simple
4) focus on what, not how

Installing discipline 2) act on the lead measures and this is usually the most difficult
There are three reasons :
Lead measures can be counterintuitive
Lead measures are hard to keep track of
Lead measures often look too simple

To  follow through on this discipline, here are the steps again :
1) Consider the possibilities
2) Rank by impact
3) Test top ideas
  - Is it predictive
  - Is it influencable
  - Is it ongoing process
  - Is it a leaders game or a team game
  - Can it be measured
  - Is it worth measuring
4) Define the lead measures
  - Are we tracking them  or individual performance
  - Are we tracking the lead measure daily or weekly
  - what is the quantitative standard
  - what is the qualitative standard
  - does it start with a verb
  - is it simple ?

 Installing discipline 3
1) Choose a theme
2) design the scoreboard
3) Build the scoreboard
4) Keep it updated

Installing discipline 4
1) demonstrate respect in your language and in your actions
2) reinforce accountability by making it transparent how important the task may be
3) encourage performance by empowering and reinforcement

The final section of the book is about installing 4DX across the organization and not just your team.
1) clarify the overall WIG
2) design the team WIGs and lead measures
3) leader certification by training the leaders separately
4) Team launch - when leaders conduct a launch
5) execution with coaching - leaders typically need experienced coaching
6) Quarterly summits

As we practice this more and more, we will realize that execution is ubiquitous and therefore so is 4DX and you can draw to it to your closer circles and personal life as well.

#codingexercise
Int height ( node root )
{
If (root == null) return 0;
Return max ( height(root.left) , height(root.right)) +1;
}

While Queen Elizabeth has a limited number of types of cake, she has an unlimited supply of each type.
Each type of cake has a weight and a value, stored in tuples with two positions:
1 An integer representing the weight of the cake in kilograms
2 An integer representing the monetary value of the cake in British pounds For example: # weighs 7 kilograms and has a value of 160 pounds (7, 160) # weighs 3 kilograms and has a value of 90 pounds (3, 90) You brought a duffel bag that can hold limited weight, and you want to make off with the most valuable haul possible. Write a function max_duffel_bag_value() that takes an array of cake tuples and a weight capacity, and returns the maximum monetary value the duffel bag can hold.
int fill_knapsack(int Capacity, int [] weights, int[] value, int number)
{
if (number == 0 || Capacity == 0) return 0;
if (weight[n-1] > Capacity) return fill_knapsack(Capacity, weight, value, n-1);
return max(val[n-1] + fill_knapsack(Capacity-weights[n-1], weights, value, n-1), fill_knapsack(Capacity, weights, value, n-1);
}


  

Wednesday, August 12, 2015

#codingexercise
A turning number is the maximum number in a unimodal array that increases and then decreases. Please write a function (or a method) that finds the index of the turning number in a unimodal array.
For example, the turning number in the array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 10, so its index 5 is the expected output.
Int getTurningIndex(int[] numbers)
{
If (numbers.length < 2)
      Return -1;
Int left = 0;
Int right = numbers.length -1;
While (right >= left+1) {
                Int mid = (left+right)/2;
               If (mid == left ) {
                     If (numbers[left] > numbers[right])        
                      Return left;
                     Return -1;
              }
        
                If (numbers[mid] > numbers[mid -1] && numbers[mid] > numbers[mid+1])
                       Return mid;
               Else if (numbers[mid] > numbers[mid-1] &&
                                Numbers[mid] < numbers[mid+1])
                                Left = mid;
               Else
                                Right = mid;
                               
}
Return  -1;
}
The above function assumes a decreasing order means the turning number is the first number and a strictly increasing order has no turning number.
This could be modified to detect the presence of an increasing sequence  or return -1.
Also we use a binary search because the numbers are mostly ordered.
#codingexercise
here is a stair with n levels. A frog can jump up one level or two levels at one time on the stair. How many ways are there for the frog to jump from the bottom of the stairs to the top?

For example, there are three choices for the frog to jump up a stair with three levels: (1) it jumps in three steps, one level for each jump; (2) it jumps in two steps, one level for the first jump and two levels for the second jump or (3) it jumps with two steps, two levels for the first step and one level for the last jump.
Can we do tail recursion here ?
If the last set was a single step, then we have a subproblem of n-1
If the last set was a two step, then we have a subproblem of n-2
we define the recursion as :
f(n) = f(n-1)+ f(n-2);
f(0) = 1
f(1) = 1
f(2) = 2
f(3) = 3
and this is a Fibonacci series

Another one:

Rectangles with size 2 x 1 are utilized to cover other rectangles, horizontally or vertically. How many approaches are available to cover a 2 x 8 rectangle with eight 2 x1 rectangles ?

Again using a similar argument as above, if we keep the 2 x 1 vertically to cover the leftmost vertical then we have sub-problem of 2 x 7
If we keep two horizontal 2 x 1 one on top of the other over the leftmost, we have a subproblem of 2 x 6 rectangle.
Let f(n) denote the number of choices to lay the smaller rectangle over a 2 x n rectangle.
Then the recursion is f(n) = f(n-1) + f(n-2) which is again a Fibonacci series.

Tuesday, August 11, 2015

We briefly discuss SUMMONS which is the first example of a multi document summarization system and illustrates one of the stages of text summarization  - topic fusion. It tackles news events about a single topic and produces a briefing that merges relevant information about each event and how reports by different newsagencies have evolved over time. Rather than working with raw text SUMMONS reads a database previously built by a template-based message understanding system. Therefore there are two stages: one that takes fulltext as input and fills template slots and then synthesizes a summary and the other that takes summary opertors and a set of rules and with connective phrases smoothens out a summary. While SUMMONS works great with narrow domain texts, it does not scale to internet documents like the ones from a web search query. This was later improved with systems by McKeown 1999 and Barzilay 1999 that identifies the topics first by clustering and then applying decision rules. These systems start by identifying themes in the form of text units or paragraphs which is then clustered based on similarity measures. To compute thesimilarity measures between text units, these are mapped to vectors of features, that include single words weighted by their TF-IDF scores, noun phrases, proper nouns, synsets from the WordNet database and a database of semantic classes of verbs. For each pair of paragraphs, a vector is computed that represents matches ondifferent features. Decision rules that were learned from data are then used to classify each pair of text units either as similar ordissimilar; this in turn feeds a subsequent algorithm that places the most related paragraphs in the same theme. Once themes are identified SUMMONS enters into an information fusion stage where sentences about a theme that should be included in the summary are decided. But instead of picking these sentences, analgorithm is proposed which compares and intersects predicate argument structures of the phrases within each theme to determine which are repeated often to include in a summary. The comparisonalgorithm then traverses these dependency trees recursively adding identical nodes to output tree. Once the summary content is decided, a grammatical text is generated by translating those structures into arguments expected by the FUF/SURGE languagegeneration system. 
Courtesy: Survey on Automatic Text Summarization by Das and Martins