hnatsu
BAN USERRefactor from my previous post I don't need the array Time O(n) Space O(1)
public int GetNumberCombinations(string s)
{
// Skyp invalid chars, example: 00001 or 00000
int k = 0;
while (k < s.Length && !IsValid(s[k]))
k++;
if (k >= s.Length)
return 0;
int curr = 0;
int prev = 1;
for (int i = k + 1; i < s.Length; i++)
{
curr = prev;
if (IsValid(s[i-1], s[i]))
curr++;
prev = curr;
}
return curr;
}
private bool IsValid(char c)
{
int n = (int)(c - '0');
return IsValid(n);
}
private bool IsValid(char c1, char c2)
{
if (c1 == '0')
return false;
int n1 = (int)(c1 - '0');
int n2 = (int)(c2 - '0');
int n = n1 * 10 + n2;
return IsValid(n);
}
private bool IsValid(int n)
{
return (n >= 1 && n <= 26);
}
Is a dynamic programig problem
public int GetNumberCombinations(string s)
{
// Skyp invalid chars, example: 00001 or 00000
int k = 0;
while (k < s.Length && !IsValid(s[k]))
k++;
if (k >= s.Length)
return 0;
int[] dp = new int[s.Length];
dp[k] = 1;
for (int i = k + 1; i < s.Length; i++)
{
dp[i] = dp[i - 1];
if (IsValid(s[i-1], s[i]))
dp[i]++;
}
return dp[s.Length - 1];
}
private bool IsValid(char c)
{
int n = (int)(c - '0');
return IsValid(n);
}
private bool IsValid(char c1, char c2)
{
if (c1 == '0')
return false;
int n1 = (int)(c1 - '0');
int n2 = (int)(c2 - '0');
int n = n1 * 10 + n2;
return IsValid(n);
}
private bool IsValid(int n)
{
return (n >= 1 && n <= 26);
}
My idea is to use recursion, in every recursion I split the number of cells in two equals halves or the most proportional/equal that can be split, in this implementation I chose the prisoner that gives me the the smaller difference between the number of left-right cells;
public int GetMinimumBribe(int numCells, int[] pricioners)
{
bool[] used = new bool[pricioners.Length];
return GetMinimumBribe(1, numCells, pricioners, used);
}
private int GetMinimumBribe(int start, int end, int[] pricioners, bool[] used)
{
if (end < start)
return 0;
int minDiff = int.MaxValue;
int index = -1;
for (int i = 0; i < pricioners.Length; i++)
{
int p = pricioners[i];
if (used[i] || p < start && p > end)
continue;
int left = p - start;
int rigth = end - p;
int diff = Math.Abs(rigth - left);
if (diff < minDiff)
{
minDiff = diff;
index = i;
}
}
if (index == -1)
return 0;
used[index] = true;
int total = end - start;;
int n = pricioners[index];
total += GetMinimumBribe(start, n-1, pricioners, used);
total += GetMinimumBribe(n + 1, end, pricioners, used);
return total;
}
// Using string.Split method this requires O(N) space where N = number of words;
public string ReverseWords(string s)
{
if (string.IsNullOrEmpty(s))
return string.Empty;
var arr = s.Split(' ');
var sb = new StringBuilder();
for (int i = arr.Length - 1; i > 0; i--)
sb.Append(arr[i]).Append(" ");
sb.Append(arr[0]);
return sb.ToString();
}
// Implementing my own code to split the words
public string ReverseWords(string s)
{
if (string.IsNullOrEmpty(s))
return string.Empty;
var sb = new StringBuilder();
int i = s.Length - 1;
int end = i;
string word;
while (i > 0)
{
if (s[i] == ' ')
{
word = s.Substring(i + 1, end - i);
sb.Append(word);
sb.Append(" ");
end = i - 1;
}
i--;
}
word = s.Substring(0, end + 1);
sb.Append(word);
return sb.ToString();
}
Quick Select I found this implementation
public int findKthLargest(int[] nums, int k)
{
if (k < 1 || nums == null)
return 0;
return getKth(nums.length - k +1, nums, 0, nums.length - 1);
}
public int getKth(int k, int[] nums, int start, int end)
{
int pivot = nums[end];
int left = start;
int right = end;
while (true)
{
while (nums[left] < pivot && left < right)
left++;
while (nums[right] >= pivot && right > left)
right--;
if (left == right)
break;
swap(nums, left, right);
}
swap(nums, left, end);
if (k == left + 1)
return pivot;
else if (k < left + 1)
return getKth(k, nums, start, left - 1);
else
return getKth(k, nums, left + 1, end);
}
public void swap(int[] nums, int n1, int n2)
{
int tmp = nums[n1];
nums[n1] = nums[n2];
nums[n2] = tmp;
}
input value Board where TRUE means there is a coin.
Like dx > 0 and dy > 0 the least we can move is dx = 1 and dy = 1 so the minimum position we came from is [i-1, j-1]
We skyp the coins from first row and firs col because is not posible to get them.
O(MxN)
public int GetMaxCoins(bool[,] board)
{
int[,] dp = new int[board.GetLength(0), board.GetLength(1)];
dp[0, 0] = board[0,0] ? 1 : 0;
int max = dp[0, 0];
for (int i=1; i < board.GetLength(0); i++)
{
for (int j= 1; j < board.GetLength(1); j++)
{
int n = board[i, j] ? 1 : 0;
dp[i, j] = n + dp[i - 1, j - 1];
max = Math.Max(max, dp[i, j]);
}
}
return max;
}
public bool ContainsSameValues(TreeNode root1, TreeNode root2)
{
var values = GetValues(root1);
return HasSameValues(root2, values);
}
private HashSet<int> GetValues(TreeNode root)
{
var values = new HashSet<int>();
GetValues(root, values);
return values;
}
private void GetValues(TreeNode node, HashSet<int> values)
{
if (node == null)
return;
if (!values.Contains(node.Value))
values.Add(node.Value);
GetValues(node.Left, values);
GetValues(node.Right, values);
}
private bool HasSameValues(TreeNode root, HashSet<int> values)
{
var matched = new HashSet<int>();
return HasSameValues(root, values, matched) && values.Count == 0;
}
private bool HasSameValues(TreeNode node, HashSet<int> values, HashSet<int> matched)
{
if (node == null)
return true;
if (!matched.Contains(node.Value))
{
if (!values.Contains(node.Value))
return false;
values.Remove(node.Value);
matched.Add(node.Value);
}
return HasSameValues(node.Left, values, matched) && HasSameValues(node.Right, values, matched);
}
Breadth traversal, uses two list one to hold the nodes in the current level and another to add the nodes in the next level.
public List<int> GetFirstLastOnLevel(TreeNode root)
{
var result = new List<int>();
if (root == null)
return result;
var list = new List<TreeNode>();
list.Add(root);
while(list.Count > 0)
{
result.Add(list[0].Value);
if (list.Count > 1)
result.Add(list[list.Count - 1].Value);
var next = new List<TreeNode>();
foreach(var node in list)
{
if (node.Left != null)
next.Add(node.Left);
if (node.Right != null)
next.Add(node.Right);
}
list = next;
}
return result;
}
public int FindRow(int[,] a)
{
int[] rows = new int[a.GetLength(0)];
int pow = 1;
int maxIndex = -1;
for (int j = a.GetLength(1) - 1; j >= 0; j--)
{
maxIndex = 0;
for (int i = 0; i < a.GetLength(0); i++)
{
rows[i] += a[i, j] * pow;
if (rows[i] > rows[maxIndex])
maxIndex = i;
}
pow *= 2;
}
return maxIndex + 1;
}
The idea I got to solve this problem was to use the previous comparation, if they are opposite I continue generating the sub-sequence. Ones I get a subsequence I can skyp lenght-1, I need to start lenght -1 because that can be the starting of the next valid subsequence.
public int[] FindLongestAlternatingSequence(int[] a)
{
int maxStart = -1;
int maxEnd = -1;
if (a == null || a.Length < 2)
return new int[0];
int i = 0;
int length = a.Length - 1;
while (i < length)
{
bool equals = a[i] == a[i + 1];
bool curr = a[i] > a[i + 1];
bool prev = !curr;
int start = i;
int j = i;
while (j < length && !equals && curr == !prev)
{
j += 2;
if (j >= length)
break;
prev = curr;
equals = a[j] == a[j + 1];
curr = a[j] > a[j + 1];
}
int end = (j <= a.Length) ? j - 1 : j - 3;
int l = end - start;
if (l > maxEnd - maxStart)
{
maxStart = start;
maxEnd = end;
}
if (l <= 0)
i++;
else
i = end;
}
if (maxStart == -1)
return new int[0];
int n = maxEnd - maxStart + 1;
int[] result = new int[n];
for (int j = 0; j < n; j++)
result[j] = a[j + maxStart];
return result;
}
private void test_Click(object sender, EventArgs e)
{
var a = new int[] { 2, 4, 5, 7, 3, 1, 5, 8, 8, 8, 5, 4, 3, 4, 5, 2, 1, 5, 4, 7, 7 };
var result = FindLongestAlternatingSequence(a);
for (int i = 0; i < result.Length; i+=2)
Console.Write("[" + result[i] + ", " + result[i + 1] + "] - ");
Console.WriteLine();
}
c# implementation, NO recursion, keep a reference of the previous in order node to set up its Random property.
public class RandomTreeNode
{
public int Value;
public RandomTreeNode Left;
public RandomTreeNode Right;
public RandomTreeNode Random;
}
public RandomTreeNode SetInorderTraversal(RandomTreeNode root)
{
if (root == null)
return null;
var prev = new RandomTreeNode();
var first = prev;
var stack = new Stack<RandomTreeNode>();
var node = root;
while (node != null && stack.Count > 0)
{
if (node == null)
{
node = stack.Pop();
prev.Random = node;
prev = node;
node = node.Right;
break;
}
stack.Push(node);
node = node.Left;
}
return first.Random;
}
There are four possibilities:
1- M and S are in the same position, o moves.
2- M and S are in the same diagonal, 1 move.
3- The diagonals projected by M and S intersect, 2 moves.
4- The diagonals projected by M and S do not intersect, 3 moves.
The idea is to see if the projected diagonals intersect, is to sum (x1 + x2) and (y1 + y2) if both numbers are even or odd the projected diagonals intersect and 2 moves are needed, other case a jump is needed given a total of 3 moves.
public int MinNumMoves(int x1, int y1, int x2, int y2)
{
//
if (x1 == x2 && y1 == y2)
return 0;
if (x1 + x2 == y1 + y2)
return 1;
bool evenx = ((x1 + x2) % 2) == 0;
bool eveny = ((y1 + y2) % 2) == 0;
return (evenx == eveny) ? 2 : 3;
}
If we need to return all the strings we can use recursion and a string builder but is really inefficient, This is based on a DP solution you just check the current and last chars according to that update the lists; I used list of integers instead of string builders is more easy to do the operations/comparations.
public List<string> GetCombinations(string s)
{
var result = new List<string>();
if (string.IsNullOrEmpty(s))
return result;
int i = 0;
var list = new List<List<int>>();
// Add the first valid element to the first list
while (!IsValid(s[i]))
i++;
if (i < s.Length)
{
var newList = new List<int>();
newList.Add(ToInt(s[i]));
list.Add(newList);
i++;
}
while (i < s.Length)
{
// If is valid update the existing list.
if (IsValid(s[i]))
{
int n1 = ToInt(s[i]);
foreach (var item in list)
item.Add(n1);
}
// If the current and previus numbers form a valid letter add new lists.
if (IsValid(s[i - 1], s[i]))
{
int n1 = ToInt(s[i - 1]);
int n2 = ToInt(s[i]);
int n = (n1 * 10) + n2;
var list2 = new List<List<int>>();
foreach (var item in list)
{
int m = -1;
// Special case when n2 == 0, the 0 is not in the item list and there is only one eleent
if (n2 == 0 && item.Count > 0 && item[item.Count - 1] == n1)
m = item.Count - 1;
else if (item.Count > 1 && item[item.Count - 2] == n1 && (n2 == 0 || item[item.Count - 1] == n2))
m = item.Count - 2;
if (m == -1)
continue;
var newList = new List<int>();
for (int j = 0; j < m; j++)
newList.Add(item[j]);
newList.Add(n);
list2.Add(newList);
}
list.AddRange(list2);
}
i++;
}
// Parse int values to char
foreach (var item in list)
result.Add(ToString(item));
return result;
}
private bool IsValid(char c)
{
return IsValid(c, null);
}
private bool IsValid(char c1, char? c2)
{
int n1 = ToInt(c1);
if (n1 == 0 || n1 > 9)
return false;
if (c2.HasValue)
{
int n2 = ToInt(c2.Value);
if (n1 > 2)
return false;
if (n1 == 2 && n2 > 26)
return false;
}
return true;
}
private int ToInt(char c)
{
return (int)(c - '0');
}
private char ToChar(int n)
{
return (char)((int)'A' + n - 1);
}
private string ToString(List<int> list)
{
var sb = new StringBuilder();
foreach (var item in list)
sb.Append(ToChar(item));
return sb.ToString();
}
public void Test(object sender, EventArgs e)
{
var s = "1123";
//var s = "134524";
//var s = "1203";
var list = GetCombinations(s);
foreach (var item in list)
Console.WriteLine(item);
}
This is a Dinamic Propramming question, if we just want to know the number of combinations:
public int GetNumCombinations(string s)
{
int[] dp = new int[s.Length];
dp[0] = IsValid(ToInt(s[0])) ? 1 : 0;
for (int i=1; i < s.Length; i++)
{
dp[i] = dp[i - 1];
if (IsValid(ToInt(s[i-1]), ToInt(s[i])))
{
int j = i > 2 ? i - 2 : 0;
dp[i] += dp[j];
}
}
return dp[s.Length -1];
}
private bool IsValid(int first)
{
return IsValid(first, null);
}
private bool IsValid(int first, int? second)
{
if (first == 0)
return false;
if (second.HasValue)
{
if (first > 2)
return false;
if (first == 2 && second.Value > 6)
return false;
}
return true;
}
private int ToInt(char c)
{
return (int)(c - '0');
}
The confusing part is Math.min(a, b) I think the intention for this is to ask to the interviewer, and could be Math.min(aIndex, bIndex); But assuming is correct in the way it is this is my solution.
static int func(String s, char a, char b)
{
if (string.IsNullOrEmpty(s)) return -1;
char[] strArray = s.ToCharArray();
if (a == b) return a;
for (int i=0; i < strArray.Length; i++)
if (strArray[i] == a || strArray[i] == b)
return i;
return -1;
}
C# has the operator "yield" that we can use in method to combines the enumerators and returns the values as a single enumerator.
public IEnumerator<int> CombineIterators(IEnumerator<int>[] iterators)
{
bool[] used = new bool[iterators.Length];
int count = iterators.Length;
int index = 0;
while (count > 0)
{
if (!used[index])
{
used[index] = !iterators[index].MoveNext();
if (used[index])
count--;
else
yield return iterators[index].Current;
}
index = (index + 1) % iterators.Length;
}
}
Post Order Traversal and calculate the min Weight
public int? GetMinWeight(TreeNode root)
{
if (root == null)
return null;
int minWeight = int.MaxValue;
GetMinWeight(root, 1, ref minWeight);
return minWeight;
}
private int GetMinWeight(TreeNode node, int deep, ref int minWeight)
{
if (node.Left == null)
return 0;
int leftWeight = GetMinWeight(node.Left, deep + 1, ref minWeight);
int rightWeight = GetMinWeight(node.Right, deep + 1, ref minWeight);
int weight = node.Value * deep + leftWeight + rightWeight;
minWeight = Math.Min(minWeight, weight);
if (node.Left != null)
minWeight = Math.Min(minWeight, leftWeight);
if (node.Right != null)
minWeight = Math.Min(minWeight, rightWeight);
return weight;
}
}
Breath Search Traversal, without recursion. C# implementation
public bool Find(TreeNode root, int x, int y)
{
if (root == null)
return false;
var current = new List<TreeNode>();
current.Add(root);
while (current.Count > 0)
{
bool foundX = false;
bool foundY = false;
var next = new List<TreeNode>();
foreach(var node in current)
{
foundX |= (node.X == x);
foundY |= (node.Y == y);
if (foundX && foundY)
return true;
foreach (var child in node.Child)
next.Add(child);
}
current = next;
}
return false;
}
public List<Tuple<int, int, int, int>> FindCubics(int n)
{
List<int> cubics = new List<int>();
int i = 0;
int m = 0;
while (m < n)
{
cubics.Add(m);
i++;
m = i * i * i;
}
var result = new List<Tuple<int, int, int, int>>();
for (i = 0; i < cubics.Count; i++)
{
for (int j = cubics.Count - 1; j > i; j--)
{
int target = cubics[i] + cubics[j];
int start = i + 1;
int end = j - 1;
while (start < end)
{
int value = cubics[start] + cubics[end];
if (value == target)
{
result.Add(Tuple.Create(cubics[i], cubics[j], cubics[start], cubics[end]));
break;
}
else if (value < target)
start++;
else
end--;
}
}
}
return result;
}
Only considere cases when m >= 1 and n >= 1
public ListNode RemoveRetain(ListNode head, int m, int n)
{
if (head == null)
return head;
if (m == 0 && n == 0)
return head;
// If don't skip elements and delete N is an empty list
if (m == 0)
return null;
// If skyp M and don't delete elements is the list is not modified
if (n == 0)
return head;
var fakeHead = new ListNode();
fakeHead.Next = head;
var current = fakeHead;
int count;
while (current != null)
{
count = 0;
while (current != null && count < m)
{
current = current.Next;
count++;
}
if (current == null)
break;
var last = current;
count = 0;
while (current != null && count < n)
{
current = current.Next;
count++;
}
last.Next = (current != null) ? current.Next : null;
}
return fakeHead.Next;
}
public TreeNode FindCloset(TreeNode root, int value)
{
TreeNode current = root;
TreeNode minNode = null;
int minValue = int.MaxValue;
while (current != null)
{
int diff = Math.Abs(current.Value - value);
if (diff < minValue)
{
minValue = diff;
minNode = current;
if (diff == 0)
break;
}
current = (value < current.Value) ? current.Left : current.Right;
}
return minNode;
}
My solution in C# Time complexity O(N) Space (N) the idea is to use a column ID to identify each column the root is column 0 if we move left column decrease by one if we move right column increase. The algorithm uses a bucket sort to store the items in the corresponding column; We use a first past O(N) to get the min and max values of columns and a second pass to store each value in the corresponding bucket position; another pass to generate the final result;
public List<int> GetByColumns(TreeNode root)
{
var t = GetColumnLimits(root);
int min = Math.Abs(t.Item1);
int max = t.Item2;
List<int>[] bucket = new List<int>[min + max + 1];
for (int i = 0; i < bucket.Length; i++)
bucket[i] = new List<int>();
var stack = new Stack<TreeNode>();
var columns = new Stack<int>();
stack.Push(root);
columns.Push(0);
// Traversal the tree and add the column in the corrsponding bucket;
while (stack.Count > 0)
{
var node = stack.Pop();
var value = columns.Pop();
int index = min + value;
bucket[index].Add(node.Value);
if (node.Left != null)
{
stack.Push(node.Left);
columns.Push(value - 1);
}
if (node.Right != null)
{
stack.Push(node.Right);
columns.Push(value + 1);
}
}
var result = new List<int>();
foreach (var list in bucket)
result.AddRange(list);
return result;
}
private Tuple<int, int> GetColumnLimits(TreeNode root)
{
var stack = new Stack<TreeNode>();
var columns = new Stack<int>();
int min = int.MaxValue;
int max = int.MinValue;
stack.Push(root);
columns.Push(0);
while (stack.Count > 0)
{
var node = stack.Pop();
var column = columns.Pop();
min = Math.Min(min, column);
max = Math.Max(max, column);
if (node.Left != null)
{
stack.Push(node.Left);
columns.Push(column - 1);
}
if (node.Right != null)
{
stack.Push(node.Right);
columns.Push(column + 1);
}
}
return Tuple.Create(min, max);
}
Based on the first publish I did a refactor
public string PrintNumber(string s)
{
int numDec = 0;
foreach (var c in s)
if (c == 'D')
numDec++;
var sb = new StringBuilder();
numDec = numDec + 1;
sb.Append(numDec);
int numInc = numDec + 1;
numDec--;
foreach (var c in s)
{
if (c == 'I')
{
sb.Append(numInc);
numInc++;
}
else
{
sb.Append(numDec);
numDec--;
}
}
return sb.ToString();
}
The idea is to use a queue to keep track of the maximum values/idexes in the window. Every time a new posible maximum value is added all the smaller elements are removed from the queue. Also all the indexes outside the window
public List<int> GetMaxValues(int[] values, int k)
{
var result = new List<int>();
var queue = new Queue<int>(); // Stores the indexes
queue.Enqueue(0);
for (int i = 1; i < values.Length; i++)
{
int value = values[i];
queue.Enqueue(i);
// Remove index outside the window
if (queue.Peek() <= i - k)
queue.Dequeue();
// Remove elements smaller that the new max value
int index = queue.Peek();
while (values[index] < value)
{
queue.Dequeue();
index = queue.Peek();
}
if (i >= k-1)
result.Add(values[index]);
}
return result;
}
I'm not familiar with DAG instead I use an array representation, but the same idea can be used with a Tree or DAG.
private class PathHelper
{
public int Value = 0;
public List<int> Path = new List<int>();
}
public List<int> FindMaxPath(int[][] values)
{
int n = values.Length;
PathHelper[] prev = new PathHelper[n];
PathHelper[] curr = null;
for (int i = 0; i < n; i++)
{
prev[i] = new PathHelper();
prev[i].Value = values[n - 1][i];
prev[i].Path.Add(values[n - 1][i]);
}
for (int i = n - 2; i >= 0; i--)
{
int m = values[i].Length;
curr = new PathHelper[m];
for (int j = 0; j < m; j++)
{
curr[j] = new PathHelper();
var max = (prev[j].Value > prev[j + 1].Value) ? prev[j] : prev[j + 1];
curr[j].Value = values[i][j] + max.Value;
curr[j].Path.Add(values[i][j]);
curr[j].Path.AddRange(max.Path);
}
prev = curr;
}
return curr[0].Path;
}
public int GetMinDiff(TreeNode root)
{
if (root == null)
return 0;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
int minValue = int.MaxValue;
// Using Breath Search/Traversal
while (queue.Count > 0)
{
var node = queue.Dequeue();
if (node.Left != null)
{
queue.Enqueue(node.Left);
int value = GetMaxValue(node.Left);
minValue = Math.Min(minValue, node.Value - value);
}
if (node.Right != null)
{
queue.Enqueue(node.Right);
int value = GetMinValue(node.Right);
minValue = Math.Min(minValue, value - node.Value);
}
}
return minValue;
}
private int GetMinValue(TreeNode root)
{
var node = root;
while (node.Left != null)
node = node.Left;
return node.Value;
}
private int GetMaxValue(TreeNode root)
{
var node = root;
while (node.Right != null)
node = node.Right;
return node.Value;
}
We can shuffle if there are (maximum existente character minus one) available characters is S; s.Length - maxRepeated >= maxRepeated - 1;
Exe. aaaabbc Maxrepeated = 4 so we need 3 available characters in S in order to shuffle: ababaca
public bool CanShuffle(string s)
{
var dict = new Dictionary<char, int>();
int maxRepeated = int.MinValue;
foreach (char c in s)
{
int n = 0;
if (!dict.TryGetValue(c, out n))
dict.Add(c, 1);
else
dict[c] = n + 1;
maxRepeated = Math.Max(maxRepeated, dict[c]);
}
return s.Length - maxRepeated >= maxRepeated - 1;
}
public int MaxConsecutive(int[] values, int k)
{
int numOnes = 0;
int max = int.MinValue;
int tmpK = k;
int begin = 0;
int end = 0;
while(begin < values.Length)
{
Debug.Assert(values[begin] == 0 || values[begin] == 1);
if (values[begin] == 0)
{
//Release the last kth 0 converted to 1
if (tmpK == 0)
{
// Skip the ones
while (values[end] == 1)
{
end++;
numOnes--;
}
numOnes--;
end++;
}
else
tmpK--;
}
numOnes++;
begin++;
max = Math.Max(numOnes, max);
}
return max;
}
public List<Tuple<int, int>> Merge(List<Tuple<int, int>> l1, List<Tuple<int, int>> l2)
{
if (l1 == null && l2 == null)
return null;
if (l1 == null && l2.Count > 0)
return l2;
if (l2 == null && l1.Count > 0)
return l1;
var result = new List<Tuple<int, int>>();
int i = l1[0].Item1 < l2[0].Item1 ? 1 : 0;
int j = l2[0].Item1 < l1[0].Item1 ? 1 : 0; ;
Tuple<int, int> p = i == 1 ? l1[0] : l2[0];
Tuple<int, int> curr;
while (i < l1.Count || j < l2.Count)
{
if (i < l1.Count && j < l2.Count)
curr = (l1[i].Item1 < l2[j].Item1) ? l1[i++] : l2[j++];
else
curr = (i < l1.Count) ? l1[i++] : l2[j++];
if (curr.Item1 < p.Item2)
p = Tuple.Create(p.Item1, Math.Max(p.Item2, curr.Item2));
else
{
result.Add(p);
p = curr;
}
}
result.Add(p);
return result;
}
This code returns a list of the elements that gives the max sum, the code uses dynamic programming
public List<int> FindMaxSum(int[] values)
{
int sum = values[0];
int index = 0;
int maxSum = values[0];
int maxIndex = 0;
int minIndex = 0;
for (int i = 1; i < values.Length; i++)
{
if (sum + values[i] > values[i])
{
sum += values[i];
}
else
{
sum = values[i];
index = i;
}
if (sum > maxSum)
{
maxSum = sum;
maxIndex = i;
minIndex = index;
}
}
var result = new List<int>();
for (int i = minIndex; i <= maxIndex; i++)
result.Add(values[i]);
return result;
}
Using a HashSet we can do it in O(n) time
public bool IsArithmeticSecuence(int[] a)
{
if (a == null || a.Length < 2)
return false;
var hash = new HashSet<int>();
foreach (var item in a)
hash.Add(item);
var inc = Math.Abs(a[0] - a[1]);
var right = a[0];
var left = a[0] - inc;
while (hash.Remove(right))
right += inc;
while (hash.Remove(left))
left -= inc;
return hash.Count == 0;
}
public bool PatterExist(int[,] matrix, int[,] pattern)
{
if (matrix == null || matrix.Length == 0)
return false;
if (pattern == null || pattern.Length == 0)
return false;
int n = matrix.GetLength(0) - pattern.GetLength(0);
int m = matrix.GetLength(1) - pattern.GetLength(1);
for (int i=0; i < n; i++)
for (int j=0; j < m; j++)
if (CheckPattern(matrix, pattern, i, j))
return true;
return false;
}
private bool CheckPattern(int[,] matrix, int[,] pattern, int row, int col)
{
for (int i = 0; i < pattern.GetLength(0); i++)
for (int j = 0; j < pattern.GetLength(1); j++)
if (matrix[row + i, col + j] != pattern[i, j])
return false;
return true;
}
//string s = "test";
string s = "abccdcc";
Console.WriteLine(string.Format("Palindrome of {0} is {1}", s, CompletePalindrome(s)));
public string CompletePalindrome(string s)
{
int minIndex = s.Length - 1;
for (int i = s.Length - 1; i > 0; i--)
{
int index = GetPalindrome(s, i, i);
if (index != -1 && index < minIndex)
minIndex = index;
index = GetPalindrome(s, i-1, i);
if (index != -1 && index < minIndex)
minIndex = index;
}
var sb = new StringBuilder();
sb.Append(s);
for (int i = minIndex - 1; i >= 0; i--)
sb.Append(s[i]);
return sb.ToString();
}
private int GetPalindrome(string s, int left, int right)
{
int n = 0;
while (left - n > 0 && right + n < s.Length && s[left - n] == s[right + n])
n++;
return (right + n == s.Length) ? left - n + 1 : -1;
}
An improvement from my previous post, dynamic programming, just use two rows for previous and current row. space O(n) C# implementation
public int GetNumPaths(int numRows, int numCols)
{
int[] prevRow = new int[numCols];
int[] currRow = new int[numCols];
currRow[0] = prevRow[0] = 1;
for (int i = 0; i < numRows; i++)
{
for (int j = 1; j < numCols; j++)
currRow[j] = currRow[j - 1] + prevRow[j];
int[] temp = currRow;
currRow = prevRow;
prevRow = temp;
}
return prevRow[numCols - 1];
}
Dynamic programming solution for a NxM matrix in C#
public int GetNumbPaths(int numRows, int numCols)
{
int[,] matrix = new int[numRows, numCols];
for (int i = 0; i < numRows; i++)
matrix[i, 0] = 1;
for (int j = 0; j < numCols; j++)
matrix[0, j] = 1;
for (int i = 1; i < numRows; i++)
for (int j = 1; j < numCols; j++)
matrix[i, j] = matrix[i - 1, j] + matrix[i, j - 1];
return matrix[numRows - 1, numCols - 1];
}
public int? FindFirstNorepeating(int[] values)
{
Dictionary<int, int> dic = new Dictionary<int, int>();
Queue<int> queue = new Queue<int>();
foreach (var item in values)
{
if (!dic.ContainsKey(item))
{
dic.Add(item, 1);
queue.Enqueue(item);
continue;
}
dic[item] = dic[item] + 1;
if (queue.Count > 0 && item == queue.Peek())
{
while (queue.Count > 0)
{
var first = queue.Peek();
if (dic[first] == 1)
break;
queue.Dequeue();
}
}
}
return queue.Count > 0 ? (int?)queue.Peek() : null;
}
public bool FindConsequitve(int[] values, int target)
{
int sum = values[0];
int begin = 0;
int end = 0;
while (end < values.Length)
{
if (sum == target)
return true;
if (begin == end && values[begin] > target)
{
begin++;
end++;
sum = values[begin];
}
else if (sum < target)
{
end++;
if (end < values.Length)
sum += values[end];
}
else
{
sum -= values[begin];
begin++;
}
}
return false;
}
C# implementation
public int MultiplyTwoWords(string[] words)
{
var arr = new HashSet<char>[words.Length];
for (int i = 0; i < words.Length; i++)
arr[i] = new HashSet<char>(words[i]);
int max = 0;
for (int i=0; i < arr.Length - 1; i++)
for (int j=i+1; j < arr.Length; j++)
if (!arr[i].Overlaps(arr[j]))
{
int value = arr[i].Count * arr[j].Count;
if (value > max)
max = value;
}
return max;
}
C#,
void PrintInwardSpiralTree(TreeNode root)
{
if (root == null)
return;
var list = new List<List<TreeNode>>();
var currentList = new List<TreeNode>();
var nextList = new List<TreeNode>();
currentList.Add(root);
while (currentList.Count > 0)
{
list.Add(currentList);
nextList = new List<TreeNode>();
foreach (var node in currentList)
{
if (node.Left != null)
nextList.Add(node.Left);
if (node.Right != null)
nextList.Add(node.Right);
}
currentList = nextList;
}
int n = list.Count;
int first = 0;
int last = n - 1;
int i = 1;
while (i <= n)
{
if (i % 2 == 1)
{
currentList = list[first];
for (int j = 0; j < currentList.Count; j++)
Console.Write(currentList[j].Value + ", ");
first++;
}
else
{
currentList = list[last];
for (int j = currentList.Count - 1; j >= 0; j--)
Console.Write(currentList[j].Value + ", ");
last--;
}
i++;
}
Console.WriteLine();
}
I think the tricky part is that you need to iterate for the small number, also take care of the sign. C# code
public int Multiply(int a, int b)
{
int sign = a > 0 ^ b > 0 ? -1 : 1;
a = Math.Abs(a);
b = Math.Abs(b);
int n = Math.Min(a, b);
int number = Math.Max(a, b);
int total = 0;
for (int i = 0; i < n; i++)
total += number;
return sign * total;
}
What I understood is to reverse the first K nodes in the case of alternative we need to navigate ti the staring node.
Note. I dont have a compiler but is the idea.
public class ListNode
{
int Data;
ListNode Next;
}
public ReverseFirstKNodes(ListNode list, int k)
{
if (list == null)
return null;
ListNode root = new ListNode();
ListNode p = list;
ListNode last = list;
int i = 0;
while (i < k && p != null)
{
ListNode q = p.Next;
p.Next = root.Next;
root.Next = p;
p = q;
i++;
}
last.Next = p;
return root.Next;
}
public Tuple<int, int> GetMinInterval(int[] values, int[] keys)
{
Tuple<int, int> result = Tuple.Create(-1, -1);
int total = 0;
var dic = new Dictionary<int, int>();
foreach (var key in keys)
{
total += key;
dic.Add(key, -1);
}
int min = int.MaxValue;
bool completed = false;
Tuple<int, int> = Tuple.Create(-1, -1);
for (var i = 0; i < values.Lenght; i++)
{
int value = values[i];
int lastIndex = -1;
if (!dict.TryGetValue(value, out lastIndex))
continue;
if (lastIndex == -1)
{
total -= value;
completed = total == 0;
if (i < min)
min = i;
if (completed)
result = Tuple.Create(min, i);
}
dict[value] = i;
if (!completed)
continue;
int lastValue = values[min];
// Trim the lower side
if (lastValue == value)
{
for (var j = min; j < i; j++)
{
if (!dict.TryGetValue(values[j], out lastIndex))
continue;
if (j >= lastIndex)
{
min = j;
break;
}
}
if (i - min < result.Item2 - result.Item1)
result = Tuple.Create(min, i);
}
}
return result;
}
Based on previous submitted answers I code this, the sort of the elements is O(n)
Create an array of ten elements, count the numbers in A, the array gives us a natural sort then create the new number based on the array-count
- hnatsu May 17, 2016