Michael.Karn.Ivanov
BAN USERWell, if array has even length it can be done in a single run across list - just for each pair of neighbours put max in odd position and min in even. So we just start cycle from beginning and compare each two elements. so, lets say 6, 5, 4, 3, 2, 1 will give us 5, 6, 3, 4, 1, 2
If array has odd length, like 6, 5, 4, 3, 2, 1, 100 then it's slightly trickier - we need to run second, backward cycle again, but starting from the last element
so, 6, 5, 4, 3, 2, 1, 100 after first cycle will be 5, 6, 3, 4, 1, 2, 100 and after second cycle
5, 6, 3, 4, 1, 100, 2
public void rearrange(int[] input) {
for(int i = 0; i < input.Length - 1; i+=2) {
if(input[i] > input[i + 1]) {
swap(input, i, i+1);
}
}
if (input.Length % 2 == 1) {
for(int i = input.Length - 1; i > 0; i -= 2) {
if(input[i] > input[i - 1]) {
swap(input, i, i - 1);
}
}
}
}
public void swap(int[] data, int from, int to) {
int temp = data[from];
data[from] = data[to];
data[to] = temp;
}
the idea is that each depth-path contributes to total ownership, so we run DFS, and each time we reach final destination, we add value which is multiplication of weights of all edges in the path. For example
Start - (0.8) - B - (0.7) - C -(0,5)- Destination
\--(0.4)- E -(0.3)-/
will give us 0.8 * 0.7 * 0.5 + 0.8 * 0.4 * 0.3 of result
public static float getStockAmount(Dictionary<string, Dictionary<string, float>> stocks, string owner, string of)
{
var dej = new Dictionary<string, float>();
foreach (var key in stocks.Keys) dej.Add(key, 0);
dej[owner] = 1;
var stack = new Stack<String>();
// we run all possible DFS here
stack.Push(owner);
while (stack.Count > 0)
{
var current = stack.Pop();
var value = dej[current];
foreach (var child in stocks[current].Keys)
{
if (child == of)
// for destination we sum up values
dej[child] += (stocks[current][child] * value);
else
dej[child] = (stocks[current][child] * value);
stack.Push(child);
}
}
return dej[of];
}
I can look at it as a kind-of directed graph, where each vertex has only one node, to another vertex. So if array is w/o dups, visually, graph will contain only circles - 1 or more.
For example array 2, 1, 3, 0, 4
contains
2 -> 3(which is a[2]) -> 0(which is a[3]) -- 2 again (circle completed)
and 1 (which is primitive circle itself) and 4 (primitive circle as well)
But when array has dups, there will be node which has two or more incoming edges. For example
2 0 3 4 2
has circle 2 -> 3 -> 4 -> 3 again, so 3 has two incoming edges - from a[0] and a[4]
what we have to do, is to run through array like it was graph and track a situation when we visited neither first (node of circle), nor new node.
Here is approx code (i use magic digits <0 not to use additional storage for nodes)
public List<int> getRepeated(int[] input) {
var result = new List<int>();
for(int i = 0; i < input.Length; i++) {
// this node was visited as part of other circle
if(input[i] < 0) continue;
int nextIdx = i;
var nextIdx = input[nextIdx];
// start new circle marking its head with -2
input[nextIdx] = -2;
while (true) {
// we return to head, circle complete, we should start a new circle
if (input[nextIdx] == -2) {
input[nextIdx] = -1;
break;
} else {
// this node was already visited as a part of another circle
if(input[nextIdx] < 0) {
result.Add(input[i]);
break;
} else {
// mark current node as visited
var current = nextIdx;
nextIdx = input[nextIdx];
input[current] = -1;
}
}
}
}
return result;
}
public static bool isMeta(string first, string second)
{
if (first == null || second == null || first.Length != second.Length) return false;
Mode metaMode = Mode.BeforeMeta;
int indexOfMismatch = -1;
for (int i = 0; i < first.Length; i++)
{
if (first[i] != second[i])
{
switch (metaMode)
{
case Mode.BeforeMeta:
indexOfMismatch = i;
metaMode = Mode.Meta;
break;
case Mode.AfterMeta:
return false;
case Mode.Meta:
if (first[i] == second[indexOfMismatch]
&& first[indexOfMismatch] == second[i])
{
metaMode = Mode.AfterMeta;
}
else
{
return false;
}
break;
}
}
}
return metaMode == Mode.AfterMeta;
}
public enum Mode {
BeforeMeta, Meta, AfterMeta
}
- Michael.Karn.Ivanov April 27, 2017
We keep cache of calculated Fib numbers and run through the array. If next elem in array greater then last calculated in cache - we calc all fib numbers till next and check if it's in cache
- Michael.Karn.Ivanov May 20, 2017