hnatsu
BAN USERc# implementation
public class AverageManager
{
private int k;
private float[] values;
private float total = 0;
private int n = 0;
private int index = 0;
private object obj = new object();
public AverageManager (int k)
{
Debug.Assert(k > 0);
this.k = k;
values = new float[k];
}
public float Average()
{
lock (obj)
{
return total / n;
}
}
public void AddItems(float[] stream)
{
int i=0;
while (i < stream.Length)
{
lock (obj)
{
total += stream[i];
total -= values[index];
values[index] = stream[i];
index++;
if (index >= values.Length)
index = 0;
if (n < k)
n++;
}
}
}
}
My C# solution
public int[] GenerateMaxSecuence(int[] a1, int[] a2, int k)
{
if (a1.Length + a2.Length < k)
return null;
int[] result = new int[k];
int index = 0;
int i1 = 0;
int i2 = 0;
while (index < result.Length)
{
int available = (a1.Length - i1) + (a2.Length - i2);
int maxIndex1 = GetMaxIndex(a1, i1, k, available);
int maxIndex2 = GetMaxIndex(a2, i2, k, available);
if (maxIndex2 >= a2.Length || (maxIndex1 < a1.Length && a1[maxIndex1] >= a2[maxIndex2]))
{
result[index] = a1[maxIndex1];
i1 = maxIndex1 + 1;
}
else
{
result[index] = a2[maxIndex2];
i2 = maxIndex2 + 1;
}
index++;
k--;
}
return result;
}
private int GetMaxIndex(int[] a, int startIndex, int k, int available)
{
int maxIndex = startIndex;
int runner = startIndex;
while (runner < a.Length && (available >= k))
{
if (a[runner] > a[maxIndex])
maxIndex = runner;
runner++;
available--;
}
return maxIndex;
}
public class CIterator
{
int[] items;
int index = 0;
public CIterator(int[] items)
{
this.items = items;
}
public int Next()
{
if (!HasNext())
throw new InvalidOperationException();
return items[index++];
}
public bool HasNext()
{
return index < items.Length;
}
}
public class CPeekIterator
{
private CIterator iterator;
private bool prevAdvanced = false;
private int peek;
private bool hasNext;
public CPeekIterator(CIterator iterator)
{
this.iterator = iterator;
}
public int Next()
{
if (prevAdvanced)
{
prevAdvanced = false;
return this.peek;
}
return iterator.Next();
}
public bool HasNext()
{
if (prevAdvanced)
return this.hasNext;
return iterator.HasNext();
}
public int Peek()
{
if (prevAdvanced)
return this.peek;
this.hasNext = iterator.HasNext();
this.prevAdvanced = true;
this.peek = iterator.Next();
return this.peek;
}
}
My solution in C# without using string.split() and int parse() methods
public int? GetMaxSum(string s)
{
int maxValue = int.MinValue;
int sum = 0;
int count = 0;
int row = 1;
int? value = null;
foreach (var c in s)
{
if (c == '#')
{
if (!value.HasValue)
return null;
if (row == count)
{
count = 0;
row++;
}
if (value > maxValue)
maxValue = value.Value;
value = null;
count++;
if (row == count)
{
sum += maxValue;
maxValue = int.MinValue;
}
}
else if (c >= '0' && c <= '9')
{
if (!value.HasValue)
value = 0;
value = value * 10 + (int)(c - '0');
}
else
return null;
}
if (value > maxValue)
maxValue = value.Value;
count++;
if (row == count)
sum += maxValue;
return (count == row) ? (int?)sum : null;
}
The tricky part is that we need to return an array, and can be a carry in my solution I add the two arrays and put the result in an integer variable so I can know if there is carry and the exact length of the resulting array. The last thing is to put back the variable in the resulting array. This will be more easy if we can return an array with and extra cell for a possible carry.
public int[] AddArrays(int[] a1, int[] a2)
{
if (a1 == null || a1.Length == 0)
return a2;
if (a2 == null || a2.Length == 0)
return a1;
int n = 0;
bool carry = false;
int length = Math.Max(a1.Length, a2.Length);
int index1 = a1.Length - 1;
int index2 = a2.Length - 1;
int i = 1;
while (index1 >= 0 || index2 >= 0)
{
int v1 = (index1 >= 0) ? a1[index1] : 0;
int v2 = (index2 >= 0) ? a2[index2] : 0;
int v = v1 + v2;
if (carry)
v++;
carry = v >= 10;
n += i * (v % 10);
i *= 10;
index1--;
index2--;
}
if (carry)
{
length++;
n += 1 * i;
}
int[] result = new int[length];
int index = length - 1;
while (n > 0)
{
result[index] = n % 10;
index--;
n /= 10;
}
return result;
}
My C# implementation, Uses a Tuple to store the string and testing index, also consider the case that a word can be just a single char
// Test code
char[] stream = { 'a', 'b', 'c', 'o', 'k', 'h', 'd', 'e', 'f', 't', 'r', 'y', 'i', 'n', 'g' };
string[] words = { "ok", "test", "one", "try", "trying", "h"};
var list = new List<string>(words);
FindWords(stream, list);
public void FindWords(char[] stream, List<string> list)
{
// Word to test and index
List<Tuple<string, int>> words = new List<Tuple<string, int>>();
foreach (var current in stream)
{
for (int i=0; i < words.Count; i++)
{
var item = words[i];
var word = item.Item1;
int index = item.Item2 + 1;
if (word[index] == current)
{
if (word.Length == (index + 1))
{
CallAPI(word);
words.RemoveAt(i--);
}
else
{
words[i] = Tuple.Create<string, int>(word, index);
}
}
else
{
words.RemoveAt(i--);
}
}
foreach (var word in list)
if (word[0] == current)
{
if (word.Length == 1)
CallAPI(word);
else
words.Add(Tuple.Create<string, int>(word, 0));
}
}
}
public void CallAPI(string word)
{
Console.WriteLine(word);
}
To solve this problem a merge sort approach must be used, if we use recursion by far the implementation is clean, The idea is to split the list and in the merge process in the second list locate the first occurrence of a greater value and use its current count, a helper array is used to store the counts.
The tricky part is that the original list must be split in a pow of two in order to get a correct result.
public int[] FindValues(int[] values)
{
if (values == null || values.Length == 0)
return new int[0];
int[] result = new int[values.Length];
int n = 1;
while (n < values.Length)
n *= 2;
MergeSort(values, result, 0, n);
return result;
}
private void MergeSort(int[] values, int[] result, int startIndex, int n)
{
if (n == 1)
return;
int middle = n / 2;
MergeSort(values, result, startIndex, middle);
MergeSort(values, result, startIndex + middle, middle);
MergeLists(values, result, startIndex, startIndex + middle);
}
private void MergeLists(int[] values, int[] result, int index1, int index2)
{
int n = index2 - index1;
Debug.Assert(n > 0);
if (index2 + n >= values.Length)
n = values.Length - index2;
while (index1 < index2)
{
for (int i = 0; i < n; i++)
if (values[index1] < values[index2 + i])
{
result[index1] += (result[index2 + i] + 1);
break;
}
index1++;
}
}
public void MoveZeros(int[] values)
{
int start = 0;
int end = values.Length - 1;
while (start < end)
{
while (start < end && values[end] == 0)
end--;
while (start < end && values[start] != 0)
start++;
if (values[start] == 0)
{
values[start] = values[end];
values[end] = 0;
}
}
}
Saw a similar solution but wanted to post, The idea is to use two index and the sum of the values between them, the values are add/subtracted according to the target value, at the same time a list with this values is updated
public List<int> FindSubList(int[] values, int target)
{
List<int> result = new List<int>();
if (values == null || values.Length == 0)
return result;
int start = 0;
int end = 0;
int sum = values[0];
result.Add(sum);
while (end < values.Length)
{
if (sum == target)
return result;
if (sum < target)
{
end++;
if (end < values.Length)
{
sum += values[end];
result.Add(values[end]);
}
}
else
{
sum -= values[start];
start++;
result.RemoveAt(0);
}
}
result.Clear();
return result;
}
My C# Solution, I am asuming the ranges in a sort order, if that is not the case the ranges must be sorted first:
Array.Sort(ranges, IComparer<int>);
The IComparer interface must be implemented comparing the first element of the range.
public int[][] CombineRanges(int[][] ranges)
{
int length = ranges.GetLength(0);
if (length <= 1)
return ranges;
List<int[]> result = new List<int[]>();
int[] p = ranges[0];
for (int i = 1; i < length; i++)
{
int[] current = ranges[i];
Debug.Assert(current.Length == 2);
if (current[0] <= p[1])
{
int[] np = new int[2];
np[0] = p[0];
np[1] = Math.Max(p[1], current[1]);
p = np;
}
else
{
result.Add(p);
p = current;
}
}
result.Add(p);
return result.ToArray();
}
Can be solved without using the ranges array is pretty much the same
private int NumberCombinations(int n, int value)
{
if (n == 1)
return map[value];
int total = 0;
int m = value - 4;
for (int i = 1; i <= m; i++)
total += NumberCombinations(n - 1, i);
m = value + 4;
for (int i = 9; i >= m; i--)
total += NumberCombinations(n - 1, i);
return total;
}
int[] map = {0, 5, 4, 3, 2, 2, 2, 3, 4, 5 };
int[][] ranges = new int[][]
{
new int[] { 5, 6, 7, 8, 9 },
new int[] { 6, 7, 8, 9 },
new int[] { 7, 8, 9 },
new int[] { 8, 9 },
new int[] { 9, 1 },
new int[] { 1, 2 },
new int[] { 1, 2, 3 },
new int[] { 1, 2, 3, 4 },
new int[] { 1, 2, 3, 4, 5 }
};
public int NumberCombinations(int n)
{
if (n == 1)
return 9;
else if (n == 0)
return 0;
else if (n < 0)
return -1;
int total = 0;
for (int i = 1; i <= 4; i++)
{
total += NumberCombinations(n - 1, i);
}
total *= 2;
total += NumberCombinations(n - 1, 5);
return total;
}
private int NumberCombinations(int n, int value)
{
if (n == 1)
return map[value];
int total = 0;
int[] a = ranges[value - 1];
for (int i = 0; i < a.Length; i++)
total += NumberCombinations(n - 1, a[i]);
return total;
}
Observation if you already generate/process the values until M (where M < N) the next required value is sum(values in array) + 1. Eje:
Int[] a = {5, 9};
Int n = 20;
And you already processed until 5 (M = 5) so you array currently is { 1, 2, 4, 5, 9 } the sum of those values is 12 = 1 + 2 + 4 + 5 so the next required value is 13. But you need to take in consideration that can be values between 5 and 13 in this case 9; so adding 1, 2, 4 to the original array [5, 9] you can generate until 21.
public List<int> NeededValues(int[] a, int n)
{
List<int> values = new List<int>();
if (a == null || a.Length == 0)
return values;
int sum = 0;
int index = 0;
int i = 1;
while (i <= n)
{
if (index < a.Length && i == a[index])
{
sum += a[index];
index++;
}
else if (sum < i)
{
sum += i;
values.Add(i);
}
i++;
}
return values;
}
public void Increment(int[] a)
{
int index = a.Length - 1;
bool carry = true;
while (carry && index >=0)
{
a[index]++;
carry = a[index] % 10 == 0;
if (carry)
{
a[index] = 0;
index--;
}
}
// Optional if we want to spin the values
if (carry && index < 0)
a[a.Length - 1] = 1;
}
public class TreeNode
{
public TreeNode() : this(0) { }
public TreeNode(int value)
{
Value = value;
Left = null;
Right = null;
}
public int Value;
public TreeNode Right;
public TreeNode Left;
}
public TreeNode FlattenTree(TreeNode root)
{
if (root == null)
return null;
TreeNode header = new TreeNode();
TreeNode p = header;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0)
{
TreeNode node = stack.Pop();
if (node.Left == null && node.Right == null)
{
p.Right = node;
p = node;
}
else
{
if (node.Right != null)
stack.Push(node.Right);
stack.Push(node);
if (node.Left != null)
stack.Push(node.Left);
node.Left = node.Right = null;
}
}
return header.Right;
}
public int? FindNthElement(int[] a1, int[] a2, int n)
{
if (a1 == null || a2 == null || n < 0 || (a1.Length + a2.Length) <= n)
return null;
int i = 0;
int j = 0;
while (true)
{
if (i + j == n)
break;
if (j >= a2.Length || i < a1.Length && a1[i] < a2[j])
i++;
else
j++;
}
return (j >= a2.Length || i < a1.Length && a1[i] < a2[j]) ? a1[i] : a2[j];
}
I know there are N values and the values are from 1 to N-1 and there is a duplicate
After sorting the array I should expect:
1 is in index 0
2 is in index 1
3 is in index 2
And so on.
if N = 10 with no duplicate
1, 2, 3, 4, 5, 6, 7, 8, 9, _
if N = 10 with duplicate
1, 2, 3, 4, 5, 5, 6, 7, 8, 9
So the duplicate is the one that not correspond/match with the index
Like is a sort O(nlog(n))
public int FindDuplicate(int[] a)
{
Array.Sort(a);
for(int i=0; i < a.Length; i++)
{
if (a[i] != (i + 1))
return a[i];
}
return -1;
}
Count the characters in S1 and check if there are the same in S2 use a Hash Table to store the count, in theory HashTable operations are O(1) so the order is O(n). Another approach is to use a char array of 255 elements to store the count, is the same order O(N) but requires more memory O(M)
public bool IsAnagram(string s1, string s2)
{
if (s1 == null || s2 == null || s1.Length != s2.Length)
return false;
Dictionary<char, int> table = new Dictionary<char, int>();
foreach(var c in s1)
{
if (table.ContainsKey(c))
table[c]++;
else
table.Add(c, 1);
}
foreach (var c in s2)
{
if (!table.ContainsKey(c))
return false;
table[c]--;
if (table[c] == 0)
table.Remove(c);
}
return table.Count == 0;
}
I solve this problem with an odometer approach, the number of '?' determine the length of the odometer, I use an array to manage/store the odometer. A StringBuilder is used to generate the resulting strings. To modify the StringBuilder I use a second array that store the indexes to modify (C# implementation)
public List<string> ParseWildcard(string s)
{
List<string> result = new List<string>();
List<int> indexes = new List<int>();
List<int> odometer = new List<int>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '?')
{
indexes.Add(i);
odometer.Add(0);
sb.Append('0');
}
else
sb.Append(s[i]);
}
if (odometer.Count == 0)
{
result.Add(s);
return result;
}
bool lastChanged = false;
int lastIndex = odometer.Count - 1;
while (!lastChanged)
{
result.Add(sb.ToString());
int i = 0;
int j = i - 1;
while (i != j && i <= lastIndex)
{
j = i;
odometer[i] = (odometer[i] + 1) % 2;
if (odometer[i] == 0)
{
lastChanged = i == lastIndex;
i++;
}
sb[indexes[j]] = (char)(odometer[j] + 48);
}
}
return result;
}
// Test Code
//string s = "010010";
//string s = "01?";
string s = "01?0?";
var result = ParseWildcard(s);
foreach (var item in result)
Console.WriteLine(item);
Considere the sign and just print the needed digits.
public string Division(int numerator, int denominator, int presicion)
{
if (denominator == 0)
throw new DivideByZeroException();
StringBuilder sb = new StringBuilder();
// The division takes care of the sign -
sb.Append(numerator / denominator);
numerator = Math.Abs(numerator);
denominator = Math.Abs(denominator);
numerator = (numerator % denominator) * 10;
if (numerator == 0)
return sb.ToString();
sb.Append('.');
while(presicion > 0 && numerator != 0)
{
sb.Append(numerator / denominator);
numerator = (numerator % denominator) * 10;
presicion--;
}
return sb.ToString();
}
There is a case where all the kids have a weight bigger that 150
public int GetNumCanoes(int[] weights, int maxWeight)
{
Array.Sort(weights);
int start = 0;
int end = weights.Length - 1;
int numCanoes = 0;
while (start <= end)
{
if (weights[start] > maxWeight)
start++;
else if (weights[end] > maxWeight)
end--;
else if (start <= end)
{
numCanoes++;
// If the sum is bigger that maxWeight they can't go an the same canoe, lets try in the next iteration
if (weights[start] + weights[end] <= maxWeight)
start++;
end--;
}
}
return numCanoes;
}
The idea is to use a the binary search
public int GetNumShifts(int[] a)
{
if (a == null || a.Length == 0)
return 0;
int index = GetIndexMaxValue(a);
return (index + 1) % a.Length;
}
private int GetIndexMaxValue(int[] a)
{
int start = 0;
int end = a.Length - 1;
while (a[start] > a[end])
{
int middle = (start + end) / 2;
if (a[middle] > a[middle + 1])
return middle;
if (a[start] > a[middle])
end = middle - 1;
else
start = middle + 1;
}
return end;
}
Hi I like a lot of the solutions already proposed, the idea with this one is to cache the already used strings so no need to reuse the SubString method repeatedly.
public List<string> CreateIstrings(string s)
{
List<string> result = new List<string>();
if (s == null || s.Length <= 2)
return result;
int index = 1;
int n = s.Length - 2;
string[] list1 = new string[n];
string[] list2 = new string[n];
string a = new string(s[0], 1);
string b = new string(s[s.Length - 1], 1);
for (int i = n; i >= 1; i--)
{
list1[index - 1] = a;
list2[n - index] = b;
for (int j = 0, k = n - index; j < index; j++, k++)
result.Add(list1[j] + i + list2[k]);
a += s[index];
b = s[s.Length - 1 - index] + b;
index++;
}
return result;
}
This can be done with brute force multiply the base N-times giving a O(n)
X^N = X*X*X*...X // N-time Brut force O(N)
But can be done in O(logN) if we use a math trick, we can split the pow operation
X^N = X^(N/2) * X^(N/2) //If exponent is even
X^N = X^(N/2) * X^(N/2) * X //If exponent is odd
We just need to compute one call from the recursiĆ³n
public double Pow(double x, int n)
{
if (x == 0 && n == 0)
throw new InvalidOperationException();
if (n == 0)
return 1;
double result = InternalPow(x, Math.Abs(n));
// If exponent is negative
if (n < 0)
result = 1 / result;
return result;
}
private double InternalPow(double x, int n)
{
if (n == 1)
return x;
else if (n == 2)
return x * x;
double pow = InternalPow(x, n / 2);
pow *= pow;
// If N is even extra multiply X^N = X^(N/2) * X^(N/2) * N
if (n % 2 != 0)
pow *= x;
return pow;
}
C# solution using Stream; Stream B could have less digits that stream A
public string SubstractNumber(Stream sa, Stream sb)
{
int carry = 0;
StringBuilder result = new StringBuilder();
int a, b;
while((a = sa.ReadByte()) != -1)
{
b = sb.ReadByte();
if (b == -1)
b = 0;
b += carry;
int diff = a - b;
carry = (diff < 0) ? 1 : 0;
if (carry == 1)
diff = 10 + diff;
result.Insert(0, diff);
}
return result.ToString();
}
My idea is to use binary search to locate the first occurrence of the target value, once we found it we just count the number of occurrences of the target value to the left and right.
public int NumberOccurrences(int[] values, int value)
{
int index = FindValue(values, value);
if (index == -1)
return 0;
int count = 1;
// Count the number of occurrences to the left
int i = index-1;
while (i >= 0 && values[i--] == value)
count++;
// Count the number of occurrences to the right
i = index + 1;
while (i < values.Length && values[i++] == value)
count++;
return count;
}
// Returns the index of the first occurrence found of value; using binary search.
private int FindValue(int[] values, int target)
{
return FindValue(values, target, 0, values.Length-1);
}
private int FindValue(int[] values, int target, int start, int end)
{
if (end < start)
return -1;
int middle = (start + end) / 2;
if (values[middle] == target)
return middle;
if (target < values[middle])
return FindValue(values, target, start, middle-1);
return FindValue(values, target, middle+1, end);
}
This is my implementation in C#, similar to other already post. To find the peak the problem don't specify the rotation orientation (left or right) so we need to handle that case. The re-arrange is in place and has a O(N)
// Returns the index of the peak
public int FindPeak(int[] a, int n)
{
n = n % a.Length;
if (n == 0)
return a.Length - 1;
int length = a.Length;
return (a[n - 1] > a[n]) ? n - 1 : length - n - 1;
}
public void Rearrange(int[] a, int n)
{
int peakIndex = FindPeak(a, n);
if (peakIndex == a.Length - 1)
return;
SwapValues(a, 0, peakIndex);
SwapValues(a, peakIndex + 1, a.Length - 1);
SwapValues(a, 0, a.Length - 1);
}
private void SwapValues(int[] a, int start, int end)
{
while (start < end)
{
int tmp = a[start];
a[start] = a[end];
a[end] = tmp;
start++;
end--;
}
}
The idea is to use a round list so we keek track of the last K numbers, we have a variable with the sum of the last K numbers the last number is subtracted and the new number is added. a locks where added to critical regions. the stream is simulated with an array of floats.
- hnatsu November 28, 2015