IC
BAN USERC# with Test method
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public static List<TreeNode> GetDuplicateSubTrees(TreeNode tree)
{
List<TreeNode> matches = new List<TreeNode>();
FindDuplicateSubTree(tree, tree.left, matches);
FindDuplicateSubTree(tree, tree.right, matches);
return matches;
}
//Find if there is at least one duplicate of the subtree in tree
private static Boolean FindDuplicateSubTree(TreeNode tree, TreeNode subTree, List<TreeNode> matches)
{
if (tree == null || subTree == null) return false;
Boolean subTreeMatched = ((tree.val == subTree.val) && tree != subTree); //values match and not the same tree
if (subTreeMatched)
{
if (tree.left != null && subTree.left != null)
{
subTreeMatched = subTreeMatched & FindDuplicateSubTree(tree.left, subTree.left, matches);
}
if (subTreeMatched)
{
if (tree.right != null && subTree.right != null)
{
subTreeMatched = subTreeMatched & FindDuplicateSubTree(tree.right, subTree.right, matches);
}
}
}
if (!subTreeMatched)
{
FindDuplicateSubTree(tree.left, subTree, matches);
FindDuplicateSubTree(tree.right, subTree, matches);
}
else
{
if (matches != null)
{
AddNewSubTree(matches, subTree);
}
}
return subTreeMatched;
}
//Add if not found
private static void AddNewSubTree(List<TreeNode> subTrees, TreeNode tree)
{
foreach (TreeNode n in subTrees)
{
if (FindDuplicateSubTree(n, tree, null))
{
return;
}
}
subTrees.Add(tree);
}
public static void Test()
{
TreeNode n = new TreeNode(1);
n.left = new TreeNode(2);
n.left.left = new TreeNode(4);
n.right = new TreeNode(3);
n.right.left = new TreeNode(2);
n.right.left.left = new TreeNode(4);
n.right.right = new TreeNode(4);
Dump(n);
Console.WriteLine();
List<TreeNode> dups = GetDuplicateSubTrees(n);
foreach(TreeNode t in dups)
{
Dump(t);
Console.WriteLine();
}
}
private static void Dump(TreeNode t)
{
if (t == null) return;
Console.Write(t.val + ", ");
Dump(t.left);
Dump(t.right);
}
public static int TrueRegionCount(Boolean[][] regions)
{
int newRegions = 0;
for (int i = 0; i < regions.Length; i++)
{
for (int j = 0; j < regions[i].Length; j++)
{
if (isNewRegion(regions, i, j))
{
newRegions++;
}
}
}
return newRegions;
}
private static Boolean isNewRegion(Boolean[][] regions, int i, int j)
{
return (regions[i][j] &&
!(((i > 0) &&
((j > 0) && (regions[i - 1][j - 1]) ||
regions[i - 1][j] ||
((j < regions.Length - 1) && regions[i - 1][j + 1]))
) ||
((j > 1) && regions[i][j - 1])
//Following are not visited yet
//||((j < regions.Length - 1) && regions[i][j+1]) ||
//((i < regions.Length -1) &&
//((j > 1) && regions[i+1][j-1] ||
//regions[i+1][j] ||
//regions[i+1][j+1] )
));
}
Boils down to solving arithmetic series and bit manipulation... but tricky
//C#
public static int GetTwoBitSequenceValue(int sequenceNumber)
{
int bit2Position = (int) Math.Round(Math.Sqrt(sequenceNumber * 2), 0) - 1;
int bit1Position = sequenceNumber - ((int)((bit2Position * (bit2Position + 1)) / 2) + 1);
return (2 << bit2Position) | (1 << bit1Position);
}
public static void Test()
{
for (int i = 1; i < 20; i++)
{
int y = GetTwoBitSequenceValue(i);
Console.WriteLine("x {0} => y {1}",i, y);
}
}
A bit different approach.
1. get sum
1. if (sum % 3) = 0; return number
2. if (sum % 3) = 1; remove 1 or 4 or 7 return number
3. if (sum % 3) = 2; remove 2 or 5 or 8 return number
return 0
//C#
public static int GetMax3Divisible(int[] arr)
{
int[] digitCounts = GetDigitCounts(arr);
int sum = GetSum(arr);//get sum of digits
int rem = sum % 3;
if (rem == 1)
{//we have to remove 1 or 4 or 7 to get the number divisible by 3
if (!(RemoveNumber(digitCounts, 1) || RemoveNumber(digitCounts, 4)
|| RemoveNumber(digitCounts, 7)))//Note. Language should support Shortcircuit
{
return 0;
}
}
else if (rem == 2)
{//we have to remove 2 or 5 or 8 to get the number divisible by 3
if (!(RemoveNumber(digitCounts, 2) || RemoveNumber(digitCounts, 5)
|| RemoveNumber(digitCounts, 8)))//Note. Language should support Shortcircuit
{
return 0;
}
}
return GetNumber(digitCounts);
}
private static int[] GetDigitCounts(int[] arr)
{
//transfer the values to an array of digit counts
int[] digitCounts = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] >= 0 && (arr[i] < 10))
{
digitCounts[arr[i]]++;
}
else
{
throw new ArgumentOutOfRangeException();
}
}
return digitCounts;
}
private static Boolean RemoveNumber(int[] digitCounts, int number)
{
if (digitCounts[number] > 0)
{
digitCounts[number]--;
return true;
}
else if (number % 2 == 0)
{
number = number / 2;
if (digitCounts[number] > 1)
{ //remove 2 elements
digitCounts[number] = digitCounts[number] - 2;
}
return true;
}
return false;
}
private static int GetNumber(int[] digitCounts)
{
int number = 0;
for (int i = digitCounts.Length - 1; i >= 0; i--)
{
while (digitCounts[i]-- > 0 )
{
number = number * 10 + i;
}
}
return number;
}
private static int GetSum(int[] arr)
{
int sum = 0;
for (int i = 0; i < arr.Length; i++)
{
sum = sum + arr[i];
}
return sum;
}
public static void Test()
{
int[] a = { 2, 2, 4, 1,1};
Console.WriteLine("Number = {0}", GetMax3Divisible(a));
}
1. Start x from min in Arr1
2. Start z from max in Arr3
3. Find y values in Arr2 between x and z
To improve perf exclude values in Arr3 which are < x or > z from subsequent iterations
//C#
public static int ThreeArrayPatterns(int[] ar1, int[] ar2, int[] ar3)
{
int ar3LeftLimit = 0;
int ar2LeftLimit = 0;
int ar2RightLimit = ar2.Length - 1;
int count = 0;
for (int i = 0; i < ar1.Length; i++) //go from smallest to largest in ar1
{
for (int j = ar3.Length - 1; j >= ar3LeftLimit; j--) //go from largest to smallest in ar3
{
if (ar1[i] + 1 < ar3[j]) // there is room for x<y<z
{
//1. Find ar2[k] such that x<y
for (int k = ar2LeftLimit; k < ar2RightLimit; k++)
{
if (ar2[k] > ar1[i]) //x<y
{
if (ar2[k] < ar3[j])
{//x<y<z found
count++;
Console.WriteLine("{0},{1},{2}", ar1[i], ar2[k], ar3[j]);
}
else
{
ar2RightLimit = k;
break; //No matches further right
}
}
else
{ //x>=y
ar2LeftLimit = k;
}
}
}
if (ar2LeftLimit >= ar2RightLimit)
{
break;
}
}
if (ar2LeftLimit >= ar2RightLimit)
{
break;
}
}
return count;
}
public static void Test()
{
int[] arr1 = { 5, 3, 15, 19, 6 };
int[] arr2 = { 24, 34, 11, 13, 16 };
int[] arr3 = { 91, 45, 57, 72, 100 };
Array.Sort(arr1);
Array.Sort(arr2);
Array.Sort(arr3);
int count = ThreeArrayPatterns(arr1, arr2, arr3);
Console.WriteLine("Match Count = {0}", count.ToString());
}
Dynamic Programming C#
private class BuySell
{
public Int32 buy;
public Int32 sell;
public Int64 profit;
public BuySell()
{
buy = Int32.MaxValue;
sell = Int32.MinValue;
profit = Int64.MinValue;
}
}
public static void Test()
{
int[] a = { 5, 6, 7, 11 };
FindBuySell(a);
}
public static void FindBuySell(int[] weelkyPrice)
{
BuySell bestResult = new BuySell();
bestResult = FindBuySell(weelkyPrice, 0, bestResult);
if (bestResult.profit > 0)
{
Console.WriteLine("Buy on {0} and Sell on {1} to make ${2} profit per share"
, bestResult.buy + 1, bestResult.sell + 1, bestResult.profit);
}
else
{
Console.WriteLine("Can't make profit!");
}
}
private static BuySell FindBuySell(int[] weeklyPrice, int start, BuySell bestResult)
{
if (start == weeklyPrice.Length - 3) // last 3 elements
{
if (weeklyPrice[start] < weeklyPrice[weeklyPrice.Length - 1])
{
bestResult.buy = start;
bestResult.sell = weeklyPrice.Length - 1;
bestResult.profit = weeklyPrice[bestResult.sell] - weeklyPrice[bestResult.buy];
}
}
else
{
bestResult = FindBuySell(weeklyPrice, start + 1, bestResult);
Int32 buyPrice = weeklyPrice[start];
Int32 sellPrice = Int32.MinValue;
Int64 profit = bestResult.profit;
int newSellIndex = Int32.MinValue;
for (int i = start + 2; i < weeklyPrice.Length; i++)
{
sellPrice = weeklyPrice[i];
if (sellPrice - buyPrice > profit)
{
profit = sellPrice - buyPrice;
newSellIndex = i;
}
}
if (profit > bestResult.profit)
{
bestResult.buy = start;
bestResult.sell = newSellIndex;
bestResult.profit = profit;
}
}
return bestResult;
}
Create a tree structure for O(Log(n))
//C#
class blackList
{
public static void Test()
{
blackList bl = new blackList();
bl.AddFilter("abc");
bl.AddFilter("aa*b");
String str = "aadbcb";
Console.WriteLine(str + ": blackListed? " + bl.IsInBlackList(str).ToString());
}
private class Node
{
public char data;
public Node next;
public Node child;
}
private Node filters = null;
public void AddFilter(string filter)
{
if (filter != null)
{
char[] filterChars = filter.ToCharArray();
AddFilter(ref this.filters, this.filters, filterChars, 0);
}
}
private void AddFilter(ref Node parent, Node filters, char[] filterChars, int index)
{
Boolean matched = false;
for (Node current = filters; current != null; current = current.next)
{
if (current.data == filterChars[index])
{
AddFilter(ref current, current.child, filterChars, index+1);
matched = true;
}
}
if (!matched)
{
Node node = CreateFilterNodes(filterChars, index);
if (parent != null)
{
node.next = filters;
parent.child = node;
}
parent = node;
}
}
private Node CreateFilterNodes(char[] filterChars, int index)
{
if (index < filterChars.Length)
{
Node node = new Node();
node.data = filterChars[index];
node.child = CreateFilterNodes(filterChars, index + 1);
return node;
}
else
{
return null;
}
}
public Boolean IsInBlackList(string str)
{
if (this.filters == null)
{
return true;
}
if (str != null)
{
char[] searchStr = str.ToCharArray();
return IsInBlackList(this.filters, searchStr, 0);
}
return false;
}
private Boolean IsInBlackList(Node filters, char[] searchStr, int index)
{
for (Node current = filters; current != null; current = current.next)
{
if (current.data == searchStr[index])
{
if (index == searchStr.Length - 1)
{
return true; //matched
}
return IsInBlackList(current.child, searchStr, index + 1);
}
else if (current.data == '*')
{
for (int i = index + 1; i < searchStr.Length; i++)
{
if (IsInBlackList(current.child, searchStr, i))
{
return true;
}
}
}
}
return false;
}
}
public static int CountSequences(string input)
{
char[] chars = input.ToCharArray();
int count = 0;
CountSequences(chars, 0, 'a', ref count);
return count;
}
//abcabc
private static void CountSequences(char[] chars, int startIndex, char lookupChar, ref int count)
{
if (lookupChar > 'c') return;
for (int currentIndex = startIndex; currentIndex < chars.Length; currentIndex++)
{
if (chars[currentIndex] == lookupChar) //found a match
{
if (lookupChar == 'c')
{
count++;
}
else
{
CountSequences(chars, currentIndex + 1, (char)(lookupChar + 1), ref count);
}
CountSequences(chars, currentIndex + 1, lookupChar, ref count);
}
}
}
Two implementations in C#
public static Boolean Validate(String ipAddress)
{
String[] parts = ipAddress.Split('.');
if (parts.Length != 4) return false;
foreach(String s in parts)
{
Byte part;
Boolean valid = Byte.TryParse(s, out part);
if (valid == false) return false;
}
return true;
}
public static Boolean Validate2(String ipAddress)
{
if (ipAddress == null) return false;
Int32 partInt = 0;
Int32 partCount = 0;
for (int i = 0; i < ipAddress.Length; i++)
{
byte b = (Byte) (ipAddress[i] - '0');
if ( b >= 0 && b <= 9)
{
partInt = partInt * 10 + b;
if (partInt > 255)
{
return false;
}
}
else if (ipAddress[i] == '.')
{
if ((partCount > 3) //only three allowed
|| (i == 0)) //cannot be the first character
{
return false;
}
partCount++;
partInt = 0;
}
else //any other character
{
return false;
}
}
return true;
}
C#
complete class with Test() method testing '+' operator
class ThousandDigitNumber
{
const int MaxSize = 1000; //Some max number of digits
const int Base = 10;
List<byte> value = new List<byte>();
Boolean positive = true;//sign
public static ThousandDigitNumber operator+ (ThousandDigitNumber num1, ThousandDigitNumber num2)
{
ThousandDigitNumber result = new ThousandDigitNumber();
if (! num1.positive)
{
if (num2.positive) //same as num2 - num1
{
return num2 - num1;
}
else //two negative numbers
{
result.positive = false;
}
}
else if (!num2.positive) //same as num1 - num2
{
return num1 - num2;
}
ThousandDigitNumber min, max;
int minSize = num1.value.Count();
if (minSize > num2.value.Count())
{
min = num2;
max = num1;
minSize = num2.value.Count();
}
else
{
min = num1;
max = num2;
}
int maxSize = max.value.Count();
int carry = 0;
int sum;
for (int i = 0; i < minSize; i++)
{
sum = min.value[i] + max.value[i] + carry;
carry = sum/Base;
result.value.Add((Byte) (sum % Base));
}
for (int j = minSize; j < maxSize; j++)
{
sum = max.value[j] + carry;
carry = sum / Base;
result.value.Add((Byte)(sum % Base));
}
if (carry == 1)
{
if (result.value.Count() < MaxSize)
{
result.value.Add((Byte) carry);
}
else
{
throw new OverflowException();
}
}
return result;
}
public static ThousandDigitNumber operator-(ThousandDigitNumber num1, ThousandDigitNumber num2)
{
ThousandDigitNumber result = new ThousandDigitNumber();
if (!num1.positive)
{
if (num2.positive) //(-a) - b -> -(a+b)
{
ThousandDigitNumber num3 = new ThousandDigitNumber(num1);
num3.positive = true;//change the sign
result = num3 + num1;
result.positive = false;
return result;
}
else //(-a) - (-b) = -(b - a)
{
//swap
ThousandDigitNumber tmp = num1;
num2 = num1;
num1 = num2;
result.positive = false;
}
}
else if (! num2.positive) // a - (-b) -> a + b
{
return num1 + num2;
}
//now do num1 - num2
// if num2 > num1, then result = - (num2 - num1)
ThousandDigitNumber min, max;
int minSize = num2.value.Count();
if (minSize > num1.value.Count())
{//num1 < num2
min = num1;
max = num2;
minSize = num1.value.Count();
result.positive = !result.positive;
}
else if (minSize < num1.value.Count())
{//num1 > num2
min = num2;
max = num1;
}
else //minsize = maxsize
{
min = num2;
max = num1;
//find which one is really larger and which one is smaller
//starting from msd to lsd
for(int i = minSize - 1; i >=0; i--)
{
if (num1.value[i] < num2.value[i]) //num1 < num2
{
min = num1;
max = num2;
result.positive = !result.positive;
break;
}
}
}
int maxSize = max.value.Count();
int sub;
int carry = 0;
//Now, finally we can do max - min
for (int i = 0; i < minSize; i++ )
{
sub = max.value[i] - min.value[i] - carry;
if (sub < 0)
{
sub = Base + sub; //get complement
carry = 1;
}
else
{
carry = 0;
}
result.value.Add((Byte) sub);
}
for (int j = minSize; j < maxSize; j++)
{
sub = max.value[j] - carry; //this cannot overflow so no testing
if (sub < 0)
{
sub = Base + sub; //get complement
carry = 1;
}
else
{
carry = 0;
}
result.value.Add((Byte) sub);
}
result.RemoveLeadingZeros();
return result;
}
private void RemoveLeadingZeros()
{
for (int i = value.Count() - 1; i >= 0; i--)
{
if (value[i] != 0)
{
break;
}
else
{
value.RemoveAt(i);
}
}
}
public ThousandDigitNumber()
{ }
//copy constructor
public ThousandDigitNumber(ThousandDigitNumber num)
{
this.value.AddRange(num.value);
this.positive = num.positive;
}
public ThousandDigitNumber(String num)
{
Parse(num);
}
private void Print()
{
if (!positive)
Console.Write("-");
if (value.Count == 0)
{
Console.Write("0");
}
for (int i = value.Count() - 1; i >= 0; i--)
{
Console.Write(value[i]);
}
}
private void Parse(String num)
{
if (num != null && num.Length > 0)
{
int i = 0;
if (num[0] == '-')
{
this.positive = false;
i++;
}
else if (num[0] == '+')
{
i++;
}
if (num.Length > MaxSize)
{
throw new OverflowException();
}
for (int j = num.Length - 1; j >= i; j--)
{
value.Add(Byte.Parse(num[j].ToString()));
}
}
}
public void Test()
{
ThousandDigitNumber t1 = new ThousandDigitNumber("89");
ThousandDigitNumber t2 = new ThousandDigitNumber("999911");
t1.Print();
Console.Write(" + ");
t2.Print();
Console.Write(" = ");
ThousandDigitNumber t3 = t2 + t1;
t3.Print();
Console.WriteLine();
}
}
Use some elimination rules to avoid traversing all producers
1. Sort consumers
2. Sort producers on X and then on Y for the ones that has the same X
for each consumer
3. Stop search when a producer is further on X axis than the distance to the closest producer found thus far
when moving to the next consumer,
4. start from the producer closest to the previous consumer
certainly not O(n) but some improvements here.. very curious to see the O(n) solution if one exists.
C#
public static List<Producer> GetNearestProducer(List<int> consumers, List<Producer> producers)
{
List<Producer> result = new List<Producer>();
if ((consumers != null) && (producers != null))
{
consumers.Sort();
producers.Sort();
int nearestProducerIndex = 0;
Producer nearest = null;
foreach(int c in consumers)
{
Double minDistance = Double.MaxValue;
int lastX = int.MaxValue;
//Start from the closest
for (int i = nearestProducerIndex; i < producers.Count(); i++)
{
Producer p = producers[i];
if (lastX != p.X) //skip all but smallest Y value for a given X
{
lastX = p.X;
if (Math.Abs(p.X - c) > minDistance)
{
/* distance along x axis alone is greater than minDistance
* for any point further down the producers list*/
break;
}
Double distance = p.GetDistance(c);
if (distance < minDistance)
{
minDistance = distance;
nearest = p;
nearestProducerIndex = i;
}
}
}
//this is the closest Pruducer
result.Add(nearest);
}
}
return result;
}
class Producer : IComparable
{
public int X;
public int Y;
public Producer (int x, int y)
{
this.X = x; this.Y = y;
}
public int CompareTo(Object o)
{
Producer p = o as Producer;
if (p == null)
{
throw new ArgumentException();
}
else
{
//first sort by X, then by Y
return this.X == p.X ?
Y.CompareTo(p.Y) : X.CompareTo(p.X);
}
}
public Double GetDistance(int x)
{
return Math.Sqrt(Math.Pow((X - x), 2) + Math.Pow(Y, 2));
}
}
Non Recursive
C#
public static void WriteCombinationsNonRec(char[] arr)
{
if (arr == null) return;
List<String> combinations = new List<String>();
for (int i = 0; i < arr.Count(); i++ )
{
String current = arr[i].ToString();
for (int j = combinations.Count() - 1; j >= 0; j--)
{
combinations.Add(combinations[j] + current);
}
combinations.Add(current);
}
PrintStrings(combinations);
}
private static void PrintStrings(List<String> combinations)
{
foreach (String s in combinations)
{
Console.Write("{0},", s);
}
Console.WriteLine();
}
without using a new array (in place)
O(n), where n=N*N
C#
static public void PrintSurroundingSumInPlace()
{
String input = "3 0 1 0 0 0 0 1 0 0";//Console.ReadLine();
int ind = 0;
//find the first white space to identify N
for (; ind < input.Length; ind++)
{
if (input[ind] == ' ') break;
}
//get N
int N = int.Parse(input.Substring(0, ind));
int matrixStart = ++ind;
for (int row = 0; row < N; row++)
{
for (int col = 0; col < N; col++)
{
int sum = 0;
for (int pRow = row - 1; pRow <= row + 1; pRow++)
{
if ((pRow < N) && (pRow >= 0))
{
for (int pCol = col - 1; pCol <= col + 1; pCol++)
{
if ((pCol < N) && (pCol >= 0))
{
sum += input[matrixStart + 2 * (pRow * N + pCol)] - '0'; ;
}
}
}
}
//Substract self
sum -= input[matrixStart + 2 * (row * N + col)] - '0';
Console.Write("{0}", sum);
if (col != N - 1)
Console.Write(" ");
}
if (row != N - 1)
Console.WriteLine();
}
}
Here is a solution satisfying your conditions
1. No array length (or size) use
2. Single parse
This is C#, this question seems to expect C++
public void Sort(int[] arr)
{
try
{
int i = 0;
int firstOne = int.MaxValue, firstTwo = int.MaxValue;
while (true)
{
switch (arr[i]) {
case 0:
if (i > firstOne)
{
Swap(arr, i, firstOne);
firstOne++;
}
if (i > firstTwo)
{
Swap(arr, i, firstTwo);
firstTwo++;
}
break;
case 1:
if (i < firstOne)
{
firstOne = i;
}
if (i > firstTwo)
{
Swap(arr, i, firstTwo);
firstTwo++;
}
break;
case 2:
if (i < firstTwo)
{
firstTwo = i;
}
break;
}
i++;
}
}
catch (IndexOutOfRangeException)
{
//Means we have run through the array
}
}
private void Swap(int[] arr, int i, int j)
{
int tmp;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
Curious about some performance considerations here
1. If arr2 is significantly larger than arr1, then is it worth sorting arr2?
for example if arr1 size is 5 and arr2 size is 1000. We will need only the largest 5 from arr2. To get the 5 largest is it worth sorting 1000 entries in the array?
2. What would be a good formula to determine 'significantly larger'?
Is it arr2.length > 10* arr1.length
or something like
log arr2.length > arr1.length
If this performance question is valid then maybe we can have a 2 part hybrid solution where we sort arr2 if arr2 is not significantly larger than arr1 and some other solution for significantly larger scenario. Well... depends on the use cases.
The trick here is how to remember which cells had zeros in the original matrix vs which cells were set by the function/method as
we traverse along the metrix row by row.
We would violate the space O(1) constraint if we use a new data structure for this purpose.
So solution for this is a combination of the following actions
1. Replace zeros in cells not traversed yet with -1 when we set row or column to zero.
2. When we encounter a -1 later as we traverse, we will check whether the row or column was set to zero previously to confirm whether the -1 was a zero we memorized or whether it is a -1 in the originzl matrix.
3. Use the first row to keep track whether a column was set to zero or not.
4. Since we use the first row to keep track zero columns, we first check whether the first row has any zeros to begin with
5. after processing and setting all rows, set the first row to zero if there were any zeros at the begining
pseudocode
1. traverse first row
2. if there is a zero in a column
3. set firstRowHasZero = true
4. set non zero values in column to zero and zero values to -1
5. traverse each remaining row
6. set rowAlreadyReset = false
7. if a zero is in a column
8 or if (-1 is in a column and firstrow[column] has zero) //the column was set to zero and the current cell has a original zero
9 or if (-1 is in a column and rowAlreadyReset) //the row was set to zero and the current cell has a original zero
10. set rowAlreadyReset = true
11. set non zero values in column to zero and non visited zero values to -1
12. set non zero values in row to zero and non visited zero values to -1
13. if firstRowHasZero
14. set first row to zero
C# implementation
public int[,] ProcessMatrix(int[,] matrix)
{
const int firstRow = 0; //used for code readability
const int firstColumn = 0; //used for code readability
int lookupValue = 0; //Value to find
int altLookupValue = -1; //Value used to memorize original zeros not parsed yet
int row = firstRow;
int column;
int rowCount = matrix.GetLength(0);
int columnCount = matrix.GetLength(1);
bool rowAlreadyReset = false; //used to avoid repeated rewrite of zero
bool firstRowHasZero = false;
if (rowCount > 0)
{
//Check whether first row has zero and also set columns to zero if zero encountered
for (column = firstColumn; column < columnCount; column++)
{
if (matrix[row, column] == lookupValue) //original zero encountered
{
firstRowHasZero = true;
//Set down cells to 0 if non zero and -1 if zero
AltResetCellsInColumn(matrix, column, row + 1, rowCount, altLookupValue);
}
}
//Process second row onwards
for (row++; row < rowCount; row++)
{
rowAlreadyReset = false;
for (column = firstColumn; column < columnCount; column++)
{
//check whether the column was previously identified to have zero
bool columnAlreadyReset = (matrix[firstRow, column] == lookupValue);
//Is the cell an Original Zero
if (((matrix[row, column] == lookupValue) //found a 0
&& (!(rowAlreadyReset //this zero is not due to a row reset
|| columnAlreadyReset) //or column reset
)
)
|| ((matrix[row, column] == altLookupValue) //found a -1
&& (columnAlreadyReset //is this -1 due to a column reset
||(rowAlreadyReset)) //or a row reset
))
{//found a original 0
if (!rowAlreadyReset)
{
//set all left cells to zero
ResetCellsInRow(matrix, row, firstColumn, column);
//Set right cells to 0 if non zero and -1 if zero
AltResetCellsInRow(matrix, row, column + 1, columnCount, altLookupValue);
rowAlreadyReset = true;
}
else if (!columnAlreadyReset)
{
//Set all cells above to zero, this will flag column reset because it update row 1
ResetCellsInColumn(matrix, column, firstRow, row);
//Set down cells to 0 if non zero and -1 if zero
AltResetCellsInColumn(matrix, column, row + 1, rowCount, altLookupValue);
}
//make sure we overwrite temporary -1 values
matrix[row, column] = 0;
}
}
}
if (firstRowHasZero)
{
//set all records in the first row to zero if first row had zeros orignially
for (column = firstColumn; column < columnCount; column++)
{
matrix[firstRow, column] = lookupValue;
}
}
}
return matrix;
}
//Set the value of all cells between start index and end index in the row to zero
private void ResetCellsInRow(int[,] matrix, int row, int start, int end)
{
for (; start < end; start++)
{
matrix[row, start] = 0;
}
}
//Set the non zero value of all cells between start index and end index in the row
//to zero. Set zero values to -1 to memorize it for latter processing
private void AltResetCellsInRow(int[,] matrix, int row, int start, int end, int altValue)
{
for (; start < end; start++)
{
//If the cell is zero then set it to -1 to memorize it for latter processing
if (matrix[row,start] == 0)
{
matrix[row, start] = altValue;
}
else
{
matrix[row, start] = 0;
}
}
}
//Set the value of all cells between start index and end index in the column to zero
private void ResetCellsInColumn(int[,] matrix, int column, int start, int end)
{
for (; start < end; start++)
{
matrix[start, column] = 0;
}
}
//Set the non zero value of all cells between start index and end index in the column
//to zero. Set zero values to -1 to memorize it for latter processing
private void AltResetCellsInColumn(int[,] matrix, int column, int start, int end, int altValue)
{
for (; start < end; start++)
{
//If the cell is zero then set it to -1 to memorize it for latter processing
if (matrix[start, column] == 0)
{
matrix[start, column] = altValue;
}
else
{
matrix[start, column] = 0;
}
}
}
1 Find the left most node (this will be the root of the flattened tree)
2. rotate right
3. flattern right sub tree
4. return to parent node and repeat from step 2
Optimization : Keep a pointer to the leafNode of the flatterned subtree
Here is the C# implementation
public static TreeNode Flattern(TreeNode bst)
{
//The Flatterned Tree
TreeNode flattenedBST = null;
//The leaf node of the flatterned tree. For Optimization
TreeNode flatternedLeafNode = null;
return Flattern(bst, ref flattenedBST, ref flatternedLeafNode);
}
private static TreeNode Flattern(TreeNode bst, ref TreeNode flattenedBST, ref TreeNode flatternedLeafNode)
{
if (bst == null)
{
return bst;
}
if (bst.left != null)
{
flattenedBST = Flattern(bst.left, ref flattenedBST, ref flatternedLeafNode);
flatternedLeafNode.right = bst;
}
else if (bst.left == null)
{
if (flattenedBST == null)
//This is the smallest in the whole tree, which is the root of the flattened tree
{
flattenedBST = bst;
}
else
//this is the next smallest node
{
flatternedLeafNode.right = bst;
}
}
//Set the last element in the partially flattned tree
flatternedLeafNode = bst;
//We have processed the left sub tree now
bst.left = null;
Flattern(bst.right, ref flattenedBST, ref flatternedLeafNode);
return flattenedBST;
}
1. Take the next Tree Node from the list
2. if the Tree Node is not visited before
2.1 flag it as visited (use a Hashtable for this)
2.2 root = Tree Node
2.3 flag all child nodes in the Tree Node sub tree as visited
3. if there are more nodes in the list then go to 1
4. If list has less elements than the Hashtable //Some nodes from the tree were not given in the list
4.1 root = null //if all nodes are not given, return null
5. return root
//C#
static TreeNode GetRoot(List<TreeNode> nodes)
{
if (nodes == null)
{
return null;
}
Hashtable visitedNodes = new Hashtable();
TreeNode root = null;
foreach(TreeNode currentNode in nodes)
{
if (!visitedNodes.Contains(currentNode))
{
//traverse subtree and flag nodes as visited
Traverse(visitedNodes, currentNode);
root = currentNode;
}
}
if (visitedNodes.Keys.Count > nodes.Count)
{
root = null; //some nodes are not given
}
return root;
}
//Traverse tree
static void Traverse(Hashtable visitedNodes, TreeNode currentNode)
{
if (currentNode != null)
{
if (!visitedNodes.Contains(currentNode))//Avoid retraversal of subtrees already traversed
{
visitedNodes.Add(currentNode, null); //used just for searching so value is NULL
Traverse(visitedNodes, currentNode.left);
Traverse(visitedNodes, currentNode.right);
}
}
}
C#
following sample returns 1, 2, 3, 4 for "BANANA" and "BA"
public void Main1()
{
String str1 = "BANANA";
String str2 = "AN";
//get indices of all permutations to a list
List<int> perms = GetPerms(str1, str2);
foreach(int i in perms)
{
Console.WriteLine(i);
}
Console.ReadLine();
}
private List<int> GetPerms(String s1, String s2)
{
List<int> matchIndices = new List<int>();
String small, large;
int smallLen, largeLen;
if ((s1 != null) && (s2 != null))
{
//1. Identify which string is small and which is large
smallLen = s1.Length;
largeLen = s2.Length;
if (smallLen > largeLen)
{
//swap
int tmp = smallLen;
smallLen = largeLen;
largeLen = tmp;
small = s2;
large = s1;
}
else
{
small = s1;
large = s2;
}
Int16[] smallFreq = new Int16[Int16.MaxValue];
Int16[] largeFreq = new Int16[Int16.MaxValue];
//get char frequency of small String
for(int i = 0; i < smallLen; i++)
{
smallFreq[small[i]] = (Int16) (smallFreq[small[i]] + 1);
}
int charCount = 0;// Count of chars in small
int matchStartIndex = -1; // The index where a match was found
//get char frequency of large String
for (int i = 0; i < largeLen; i++)
{
if (smallFreq[large[i]] > largeFreq[large[i]]) //a character match found
{
if (matchStartIndex == -1)
{
matchStartIndex = i; //remember the start index of possible permutation
}
largeFreq[large[i]] = (Int16)(largeFreq[large[i]] + 1);
charCount++;
if (charCount == smallLen) //permutation found
{
matchIndices.Add(matchStartIndex);
i = matchStartIndex; //start from the next location
matchStartIndex = -1; //flag that we are not within a match
charCount = 0;
Array.Clear(largeFreq, 0, largeFreq.Length);
}
}
else if ((smallFreq[large[i]] > 0) && (smallFreq[large[i]] == largeFreq[large[i]])) //too many instances of a character found within a possible permutation
{
//skip one index and try again
i = matchStartIndex; //start from the next location
matchStartIndex = -1; //flag that we are not within a match
charCount = 0;
Array.Clear(largeFreq, 0, largeFreq.Length);
}
else if (matchStartIndex != -1)
{
//mismatch found while in the middle of a possible permutation
matchStartIndex = -1;
charCount = 0;
Array.Clear(largeFreq, 0, largeFreq.Length);
}
}
}
return matchIndices;
}
//C# with a little improvement (taking primes out and reusing in IsPrime) to Dave's C++ code
// find all pairs of p,q prime numbers such that p * q <= n
// find all prime numbers < = n / 2
// find pairs of prime numbers that satisfy the condition from earlier collected numbers
private static ArrayList primes;
static bool isPrime(int n)
{
if (n <= 1)
return false;
if (n == 2)
return true;
foreach (int i in primes)
{
if (n % i == 0)
return false;
}
return true;
}
static void printPairs(int n)
{
primes = new ArrayList();
primes.Clear(); //Remove all elements from the ArrayList. This could be improved to remove elements larger than n/2 if needed
int max = n / 2; //for performance
for (int i = 1; i <= max; i++)
{
if (isPrime(i))
primes.Add(i);
}
foreach (int i in primes)
{
foreach (int j in primes)
{
if (i * j <= n)
{
Console.WriteLine(String.Format("({0}, {1})", i, j));
}
}
}
}
This pseudocode is for the case of a board of -infinity to + infinity
it also works for n>2 except for the corner cases (which need additional conditions)
Requirement - board origin = 0,0
int hops;
int quotient = (abs(p-x) + abs(q-y))/3;
int remainder = (abs(p-x) + abs(q-y))%3;
int adjustment = 0
if (remainder == 1) then adjustment = 3;
else if (remainder ==2) then adjustment = 2;
hops = quotient + adjustment;
-- validated the above with http :// tacticstime . com/wp-content/uploads/2011/09/chess_knight_all.png
-- There seems to be some cases when x=p or y=q that this does not give the least hops (eg. (x,y)=(0,0) and (p,q) = (4,0), so some additional conditions needed there as well.
/* //Call as
* int n = 3;
* PrintValidWords("", 'a', n);
*/
const char EndChar = 'z';
// Append charCount number of valid charaters to prefix
static private void PrintValidWords(String prefix, char start, int charCount)
{
String newPrefix;
if ((0 == charCount) || (null == prefix) || (start > EndChar))
{
return;
}
for (char c = start; c <= EndChar; c++)
{
newPrefix = prefix + c.ToString();
if (1 == charCount)
{
Console.WriteLine(newPrefix);
}
else
{
PrintValidWords(newPrefix, c, charCount - 1);
}
}
}
//An O(log(n)) Non Recursive C# for unsigned ints.
//get the b th power of a
public static ulong Power(uint a, uint b)
{
ulong power = 1;
if (b > 0)
{
power = power * a;
if (b > 1)
{
uint largestBit = GetLargestBit(b);
uint position = 2;
uint rem = largestBit >> 1;
do
{
power = power * power;
if ((b & rem) > 0)
{
power = power * a;
}
rem = rem >> 1;
position = position << 1;
} while (b >= position);
}
}
return power;
}
//Get the max bit of a number
public static uint GetLargestBit(uint b)
{
uint largestBit = 1;
while (largestBit <= b)
{
largestBit = largestBit << 1;
}
largestBit = largestBit >> 1;
return largestBit;
}
//a C# implementation.
const int MaxChars = 26;
const int MinChar = 'a';
public String FindMaxSubString(String inputStr)
{
if (null == inputStr)
{
return inputStr;
}
int[] chars = new int[MaxChars]; //Temporary helper array
int start = 0, maxStart = 0, maxLen = 0;
int len, charIndex;
for (charIndex = 0; charIndex < MaxChars; charIndex++)
{
//Initialize to a value outside valid array Indexes
chars[charIndex] = -1;
}
for (int current = 0; current < inputStr.Length; current++)
{
charIndex = inputStr[current] - MinChar;
//check for IndexOutOf range
if (chars[charIndex] >= start)
{
len = current - start;
if (maxLen < len)
{
maxLen = len;
maxStart = start;
}
start = chars[charIndex] + 1;
}
chars[charIndex] = current;
}
//check the last streatch of characters in the string
len = inputStr.Length - start;
if (maxLen < len)
{
maxLen = len;
maxStart = start;
}
return inputStr.Substring(maxStart, maxLen);
}
--C#--
private bool IsShuffled(String s1, String s2)
{
if ((null == s1) || (null == s2)
|| s1.Length == 0 || s2.Length == 0
|| s1.Length != s2.Length
)
{
return false;
}
//Identify characters in s1
char[] chars = new Char[26];
for (int i = 0; i < s1.Length; i++)
{
chars[(int)(s1[i] - 'a')]++;
}
//Identify characters in s2
for (int i = 0; i < s2.Length; i++)
{
chars[(int)(s2[i] - 'a')]--;
}
//If both strings have the same characters, then chars[] should have 0 for all
for (int i = 0; i < chars.Length; i++)
{
if (chars[i] != 0)
{
return false;
}
}
return true;
}
O(n) with no extra memory and no need to reverse list
have two pointers pointing at the head
using recursion locate the last element and point one pointer to it
then move the two pointers in opposite direction (with the help of recursion return) checking for equality
Forward pointer has to be a ref pointer for this to work
- IC March 05, 2017