impala
BAN USERBelow recursive solution in C# should work. Let me know if I am missing something.
public static void Test()
{
HashSet<string> combinations = new HashSet<string>();
Paranthesize(2, 2, 2, "", combinations);
foreach (string s in combinations)
{
Console.WriteLine(s);
}
}
private static void Paranthesize(int n1, int n2, int n3,
string part, HashSet<string> combinations)
{
if (n1 <= 0 && n2 <= 0 && n3 <= 0)
{
if (!combinations.Contains(part))
{
combinations.Add(part);
}
return;
}
if (n1 > 0)
{
Paranthesize(n1 - 1, n2, n3, "{}" + part, combinations);
Paranthesize(n1 - 1, n2, n3, part + "{}", combinations);
Paranthesize(n1 - 1, n2, n3, "{" + part + "}", combinations);
}
if (n2 > 0)
{
Paranthesize(n1, n2 - 1, n3, "[]" + part, combinations);
Paranthesize(n1, n2 - 1, n3, part + "[]", combinations);
Paranthesize(n1, n2 - 1, n3, "[" + part + "]", combinations);
}
if (n3 > 0)
{
Paranthesize(n1, n2, n3 - 1, "()" + part, combinations);
Paranthesize(n1, n2, n3 - 1, part + "()", combinations);
Paranthesize(n1, n2, n3 - 1, "(" + part + ")", combinations);
}
}
Here is a DP solution in C#.
Time complexity is O(N). Each index is evaluated only once. You can see it by looking at the print traces.
private static Hashtable cachedResults = new Hashtable();
private static int CacheAndReturn(int index, int jump)
{
cachedResults.Add(index, jump);
return jump;
}
private static int MinJump(int[] array, int index)
{
if(cachedResults.ContainsKey(index))
return (int)cachedResults[index];
Console.WriteLine("Evaluating index: " + index);
if (index >= array.Length - 1)
return CacheAndReturn(index, 0);
if (array[index] >= array.Length - index - 1)
return CacheAndReturn(index, 1);
int min = Int32.MaxValue;
for (int x = 1; x <= array[index]; x++)
{
int temp = MinJump(array, index + x);
if (temp < min)
{
min = temp;
}
}
if (min != Int32.MaxValue)
{
return CacheAndReturn(index, 1 + min);
}
else
{
return CacheAndReturn(index, Int32.MaxValue); // no jump
}
}
My C# implementation is here. Java should be almost same. Notice that HasNext() and Next() methods are very similar. They can be combined, too.
public class NestedList
{
private int row;
private int col;
private List<List<int>> items;
public NestedList(List<List<int>> items)
{
this.items = items;
}
public bool HasNext()
{
if (this.items == null)
{
return false;
}
// while not end of first level items
while (row < this.items.Count)
{
if (items[row] == null || items[row].Count == 0)
{
col = 0;
row++;
}
else if (col == items[row].Count)
{
col = 0;
row++;
}
else
{
return true;
}
}
return false;
}
public int Next()
{
if (this.items == null)
{
throw new IndexOutOfRangeException();
}
// while not end of first level items
while (row < this.items.Count)
{
if (items[row] == null || items[row].Count == 0)
{
col = 0;
row++;
}
else if (col == items[row].Count)
{
col = 0;
row++;
}
else
{
return items[row][col++];
}
}
throw new IndexOutOfRangeException();
}
public static void Test()
{
List<List<int>> items = new List<List<int>>()
{
new List<int>(){3, 4, 5},
new List<int>(){},
new List<int>(){6},
new List<int>(){7, 8},
null,
new List<int>(){9, 10},
};
NestedList list = new NestedList(items);
while (list.HasNext())
{
Console.WriteLine(list.Next());
}
}
}
A C# implementation of the recursive solution described in above posts.
public static int DifferentWays(int diceFace, int diceCount, int sum)
{
if (diceCount == 0)
return 0;
if (sum < diceCount) // * 1
return 0;
if (sum > diceCount * diceFace)
return 0;
if (diceCount == 1)
return 1;
int count = 0;
for (int x = 1; x <= diceFace; x++)
{
count += DifferentWays(diceFace, diceCount - 1, sum - x);
}
return count;
}
Here is my non-recursive solution. Note: It assumes that we are asked to return the successor even if the given key is in the tree.
int GetSuccessor (CNode* root, int key)
{
int lastBig = Int32.Max;
CNode* current = root;
while ( current != null )
{
if (key < current->data)
{
lastBig = current->data;
current = current->left;
}
else
{
current = current->right;
}
}
return lastBig;
}
A non-recursive solution is here:
public static void WildCardPrint(string wildcard)
{
int count = 0;
foreach (char c in wildcard)
{
if (c == '?')
{
count++;
}
}
int permutation = (int)Math.Pow(2, count);
for (int perm = 0; perm < permutation; perm++)
{
int current = perm;
int qmarkSoFar = 0;
for (int index = 0; index < wildcard.Length; index++)
{
if (wildcard[index] != '?')
{
Console.Write(wildcard[index]);
}
else
{
qmarkSoFar++;
int digit = count-qmarkSoFar;
if (current < Math.Pow(2, digit))
{
Console.Write('0');
}
else
{
Console.Write('1');
current -= (int)Math.Pow(2, digit);
}
}
}
Console.WriteLine();
}
}
Here is a C# implementation.
public class Vertex
{
public string Id { get; set; }
public List<Edge> Neighbours { get { return this.neighbours; } }
private List<Edge> neighbours = new List<Edge>();
}
public class Edge
{
public Vertex Target { get; set; }
public int Cost { get; set; }
}
public class Graph
{
public List<Vertex> Vertices { get { return this.vertices; } }
private List<Vertex> vertices = new List<Vertex>();
public int ShortestPath(Vertex start, Vertex end, ref List<Vertex> path)
{
// set initial distances
Hashtable<Vertex, int> distances = this.InitializeDistances(start);
// keep track of previous path
Hashtable<Vertex, Vertex> previous = new Hashtable<Vertex, Vertex>();
// process each vertex after adding them into a queue
List<Vertex> queue = new List<Vertex> (this.Vertices);
while (queue.Count > 0)
{
// get the vertex, which has the smallest distance, from the queue
Vertex v = PopWithSmallestDistance (queue, distances);
int distanceV = distances [v];
if ( distanceV == Int32.Max)
break; // no edge or no need to continue
if ( v == end)
break; // we are done
foreach ( Vertex n in v.Neighbours)
{
int altN = distanceV + n.Cost;
if ( altN < distances [n.Target] ) // relax
{
distances [n.Target] = altN; // improve the result
previous [n.Target] = v; // add or override
}
}
}
// build up the path
Vertex temp = end;
while (temp != start)
{
path.Add (temp);
temp = previous [temp];
}
// add the initial vertex, too
path.Add (start);
// reverse the path
path.Reverse();
// return the shortest distance from start to end
return distances [end];
}
private static Vertex PopWithSmallestDistance (
List<Vertex> queue, Hashtable<Vertex, int> distances)
{
Vertex v = null;
int min = Int32.Max;
foreach ( Vertex t in queue)
{
int cost = distances [ t ];
if ( cost < min )
{
v = t;
min = cost;
}
}
queue.Remove (v);
return v;
}
private Hashtable<Vertex, int> InitializeDistances (Vertex start)
{
Hashtable<Vertex, int> distances = new Hashtable<Vertex, int>();
foreach (Vertex v in this.Vertices)
{
if (v != start)
{
// initial distance is inifite
distances.Add(v, Int32.Max);
}
else
{
distances.Add (v, 0);
}
}
return distances;
}
}
Here is my solution written in C#
public class Range
{
public int Min { get; set; }
public int Max { get; set; }
public int Cost { get { return this.Max - this.Min; } }
public Range(int min, int max)
{
this.Min = min;
this.Max = max;
}
public int CompareTo(Range range)
{
return this.Cost.CompareTo(range.Cost);
}
public override string ToString()
{
return String.Format("[{0}, {1}]", this.Min, this.Max);
}
}
public class Ranger
{
private List<List<int>> lists;
private int[] indices;
public Ranger(List<List<int>> lists)
{
this.lists = lists;
// create an array to keep track of the indices during iterations
// initially all are 0's.
indices = new int[lists.Count];
}
private int IndexOfNextMin()
{
int index = -1;
int min = Int32.MaxValue;
for (int x = 0; x < lists.Count; x++)
{
if (indices[x] < lists[x].Count - 1)
{
int val = lists[x][indices[x] + 1];
if (val < min)
{
min = val;
index = x;
}
}
}
return index;
}
private Range CalculateCurrentRange()
{
int min = Int32.MaxValue;
int max = Int32.MinValue;
for (int x = 0; x < lists.Count; x++)
{
int val = lists[x][indices[x]];
if (val < min)
{
min = val;
}
if (val > max)
{
max = val;
}
}
return new Range(min, max);
}
public Range GetMinimumRange()
{
// initial range
Range range = this.CalculateCurrentRange();
// walk through to find a better range
while (true)
{
// iterate
int index = IndexOfNextMin();
if (index >= 0)
{
indices[index]++;
Range temp = CalculateCurrentRange();
if (range.CompareTo(temp) > 0)
{
// we have a better range
range = temp;
}
}
else
{
break;
}
}
return range;
}
}
public static void Main(string[] args)
{
// data
List<List<int>> lists = new List<List<int>>()
{
new List<int>(){4, 10, 15, 24, 26},
new List<int>(){0, 9, 12, 20},
new List<int>(){5, 18, 22, 30},
};
Ranger ranger = new Ranger(lists);
Range range = ranger.GetMinimumRange();
Console.WriteLine(range);
}
what if the lists are as following?
List 1: [1, 2, 3, 80]
List 2: [1, 2, 3, 90, 200]
List 2: [1, 2, 3, 99, 300]
In that case, your algorithm chooses [80, 99]. the range is 99-80 = 19.
However the answer is [1, 2] where range is 1 ; i.e. 2-1.
that is why your algorithm won't work.
I'd keep the PATH infomation for each node.
Table Node
- Id
- Value (or Cost)
- Path
Assume that the graph is like below.
(i.e. a complete binary tree which is a special form of a graph)
. 1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
Example Rows for the graph above:
Id Path
-------------------------
1.......... NULL
2.......... 1
3.......... 1
4.......... 1,2
5.......... 1,2
6.......... 1,3
7.......... 1,3
8.......... 1,2,4
9.......... 1,2,4
10..........1,2,5
11..........1,2,5
12..........1,3,6
13..........1,3,6
14..........1,3,7
15..........1,3,7
Selecting all parents of Node X:
. SELECT [Path] FROM [PathTable] WHERE [Id] = X;
Selecting all children of Node X:
. declare @path varchar(max);
set @path = (SELECT [Path] FROM [PathTable] WHERE [Id] = X);
set @path = @path + ',%';
SELECT [Id] FROM [PathTable] WHERE [Path] LIKE @path;
However, this is only an optimization for the given conditions. There are many disadvantages of this solution. For example insert and delete operations are too costly since you need to update all impacted paths in the table..
- impala May 10, 2013Here is a solution in C#. Simply convert it to Java.
It doesn't implement IEnumerable<int> but this can be added very easily.
public class FlatIntList
{
private List<List<int>> allLists;
private int rowIndex;
private int cellIndex;
public FlatIntList(List<List<int>> data)
{
this.allLists = data;
this.BeginIteration();
}
public void BeginIteration()
{
this.rowIndex = 0;
this.cellIndex = 0;
// omit the empty lists
this.SkipEmptyLists();
}
public bool HasNext()
{
if (this.rowIndex < this.allLists.Count &&
this.cellIndex < this.allLists[this.rowIndex].Count)
{
return true;
}
return false;
}
public int Next()
{
int result = this.allLists[this.rowIndex][this.cellIndex];
this.Iterate();
return result;
}
private void Iterate()
{
if (this.cellIndex < this.allLists[this.rowIndex].Count - 1)
{
// iterate on current row
this.cellIndex++;
}
else
{
// go to the next row
this.cellIndex = 0;
this.rowIndex++;
// omit the empty lists
this.SkipEmptyLists();
}
}
private void SkipEmptyLists()
{
while (this.rowIndex < this.allLists.Count &&
this.allLists[this.rowIndex].Count == 0)
{
this.rowIndex++;
}
}
}
// test the solution
public class Program
{
public static void Main(string[] args)
{
// data
List<List<int>> data = new List<List<int>>()
{
new List<int>(){},
new List<int>(){1},
new List<int>(){2, 3},
new List<int>(){},
new List<int>(){},
new List<int>(){4, 5, 6, 7, 8},
new List<int>(){9},
new List<int>(){},
};
FlatIntList flat = new FlatIntList(data);
// print twice to test it in a better way
for (int x = 0; x < 2; x++)
{
flat.BeginIteration();
while (flat.HasNext())
{
int number = flat.Next();
Console.Write(number);
Console.Write(", ");
}
Console.WriteLine();
}
}
}
Here is a C# code that refers to a solution mentioned above. Its worst case time complexity is O(n^2) though. I am wondering if there is an O(n) solution.
- impala August 08, 2013