We were discussing maximum sum rectangle in a 2d array. There is a technique called Kadane's algorithm that we can use to find this sum. The algorithm returns the maximum sum  and stores the starting and ending indexes
int kadane(List<int>num, ref int start, ref int end, int n)
{
int sum = 0;
int max = INT_MIN;
end = -1;
int cur = 0,
for (int i = 0; i < n; i++)
{
  sum += num[i];
  if sum < 0){
     sum = 0;
     cur =  i + 1;
}else if (sum > max ){
   max = sum;
   start  = cur;
   end  = i;
}
}
if (end != -1)
    return max;
max = num[0];
start = 0;
end = 0;
// find the max element
for (int i = 1; i < n; i++)
  if (num[i] > max){
      max = num[i];
      start = i;
      end = i;
   }
return max;
}
This can also be written as
def max_subarray(A):
      max_ending_here = max_so_far = 0;
      for x in A:
           max_ending_here = max(0, max_ending_here+x)
           max_so_far = max(max_so_far, max_ending_here)
      return max_so_far
#courtesy online resources

2) Check if two strings are anagrams of each other

bool AreAnagrams(String first, String second)
{
var h1 = new HashTable()
var h2 = new HashTable()
for (int i =0;i < first.length; i++)
      h1[first[i]] +=1;
for (int i =0;i < second.length; i++)
      h2[second[i]] +=1;

return h1.IsEqual(h2);

}

Bool getRepeatedChars(string A)
{
var h1 = new HashTable()
for (int i =0;i < first.length; i++)
      h1[first[i]] +=1;
Var ret = new List<int>();
For (int i =0;i < h1.keys.length; i++)
{
If h1.vals[i] > 1
     Ret.add(keys[i]);
}
Return ret.sort();
}

We were discussing maximum sum rectangle in a 2d array. There is a technique called Kadane's algorithm that we can use to find this sum. The algorithm returns the maximum sum  and stores the starting and ending indexes
int kadane(List<int>num, ref int start, ref int end, int n)
{
int sum = 0;
int max = INT_MIN;
end = -1;
int cur = 0,
for (int i = 0; i < n; i++)
{
  sum += num[i];
  if sum < 0){
     sum = 0;
     cur =  i + 1;
}else if (sum > max ){
   max = sum;
   start  = cur;
   end  = i;
}
}
if (end != -1)
    return max;
max = num[0];
start = 0;
end = 0;
// find the max element
for (int i = 1; i < n; i++)
  if (num[i] > max){
      max = num[i];
      start = i;
      end = i;
   }
return max;
}
This can also be written as
def max_subarray(A):
      max_ending_here = max_so_far = 0;
      for x in A:
           max_ending_here = max(0, max_ending_here+x)
           max_so_far = max(max_so_far, max_ending_here)
      return max_so_far
#courtesy online resources

#codingexercises 

Write  a method to delete all the nodes from a binary tree that lie on a path whose sum from root to leaf is less than a given value K.  

Void delPathSums(Node root, int K, ref int cur) 

{ 

If (Root == null) return; 

Cur+= root.data; 

Int left = cur; 

Int right = cur; 

Root.left = delPathSums(root.left , K, ref int left); 

Root.right = delPathSums(root.right, K, ref int right); 

Cur += max(left, right); 

If (cur <k){ 

Tree_delete(root); 

Root = null; 

} 

Return root; 

}

Merge k sorted arrays

List<int> mergeSorted(List<List<int>> sorted, int k, int m)

{

Var result = new List<int>();

Var cur = new List<int> (); // local index

For(int k =0; k <  m×k ; k++)

{

Var min = getMin(sorted, ref cur);

Result.add(min.first);

Cur[min.second]++;

}

Return result;

}

Tuple<int,int> GetMin(List<List<int>> sorted, ref List<int>cur)

{

var min = new List<int>();

for (int I = 0; I < cur.Count; i++)

{

if (cur[i] < sorted[i].Count)

min.Add(sorted[i][cur[i]]);

else{

min.Add(INT_MAX);

}

}

int val = min.min();

int index = min.index(x = > x == val);

return new Tuple<int, int>(val, index);

}

This could also be solved with a heap

List<int> mergeSortedWithHeap(List<List<int>> sorted, int k)

{

var ret = new List<int>();

var h = new Heap();

for (int i =0; i  < n*k; i++)

{

var root = h.getMin();

ret[i] = root.data;

if (root.localindex < n)

{

root.data = sorted[root.globalindex][root.localindex];

root.localindex += 1;

}

else root.element = INT_MAX;

h.replaceMin(root);

}

return ret;

}

Given a 2d array find the maximum sum rectangle
int FindMaxSum(int[,] nums, int row, int col)
{
int max = 0;
for (int i =0; i < row; i++)
  for (int j = 0; j < col; j++)
  {
     int cur = 0;
     var start = new Tuple<int, int> (i,j);
     // choose end to be one of the remaining points to the right and bottom of start
      for (int x = i; x < row; x++)
        for (int y = j; y < col; y++)
            if (x !==i && y !== j) 
                cur = GetSum(nums, i, j, x,y); 
                 if (cur > max) max = cur;
  }
}
return max;

Given a chess board of finite length, start a position of a knight, an end position 

• Find whether the end position is reachable by the knight 
• Number of minimum hops required to reach that position 

One solution is to use backtracking: 

void GetMinMoves(Point start, Point end, int count, ref int min) 

{ 

 if ( start == end) { if (count < min), {min = count;} } 

 var x = new List<int>() { 2, 1, -1, -2, -2, -1,  1,  2}; 

 var y = new List<int>() { 1, 2,  2,  1, -1, -2, -2, -1}; 

for (int k =0 ; k < 8; k ++) 

{ 

   start.x += x[k]; 

   start.y += y[k]; 

   if (isValid(start)) 

       GetMinMoves(start, end, count + 1, ref min); 

   start.x -= x[k]; 

   start.y -= y[k]; 

} 

} 

// isValid checks for both whether the position is on the board and if it has been visited. 

Another is to use breadth first traversal: 

Define the edges in such a graph and the ways when you can travel from vertex I to vertex j. Once we have the graph, it reduces to finding the shortest path in an unweighted graph.  

Int knightMoves (point[,] board, int N, point x, point y) 

{ 

Add the starting point to a queue 

While queue is not empty 

     Extract a point 

     If point == destination return 

     If point already visited continue 

     For each of eight moves the knight can make 

        Enqueue the point 

Return -1; 

} 

In a binary search tree two nodes are out of order. Find them

Here the inorder traversal will find elements tgat are not in the sorted order. However there may be rwo of tgose tgat are lesser than their previous value or there may just be one. In the latter case, tge two nodes that are out of order are adjacent in tge inorder traversal.

Void findBSTHelper(node root, ref node prev, ref node cur, ref node next, ref node last)

{

If root == null return;

FindBSTHelper( root.left, ref prev, ref cur, ref next, ref last);

If (prev && prev.data < root.data){

If(!first){

First = prev;

Cur = root:

}else{

last = root;

}

}

Prev = root;

}

FindBSTHelper( root.right, ref prev, ref cur, ref next, ref last);

}
Swap first and last or swap first and middle