coder
BAN USERI think this should work. For example for the signature IID, and the graph 1<-2<-3->4, the reverse topological sort (ordering by end times in DFS) returns 1243 which is correct. Also this will try to give the smallest lex sequence since DFS starts at node 1, etc.
- coder October 27, 2012This question is answered in the Amazon questions
a[i]<a[j]<a[k] s.t i<j<k
From the original array build two arrays.
i) LMin[i] contains index of the min element seen so far from the left including a[i].
ii) RMax[i] contains index of the max element seen so far from the right including a[i].
consider the following array:
a =4,7,5,1,3,8,9,6,2
LMin=0,0,0,3,3,3,3,3,3
RMax=6,6,6,6,6,6,6,7,8
Now for i=1 to n if a[LMin[i]] < a[i] < a[RMax[i] print LMin[i],a[i],RMax[i]
Time complexity: O(n)
Space Complexity: O(n)
using System;
- coder October 27, 2012using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SignatureSequence
{
class Program
{
static void Main(string[] args)
{
char[] signature = "DIIDI".ToCharArray();
int[] permutation = GeneratePermutation(signature);
Console.WriteLine("signature : {0}", string.Join(", ", signature));
Console.WriteLine("permutation : {0}", string.Join(", ", permutation));
Console.ReadKey();
}
private static int[] GeneratePermutation(char[] signature)
{
int[] permutation = new int[signature.Length + 1];
int[] startTime = new int[permutation.Length];
int[] endTime = new int[permutation.Length];
int i;
for (i = 0; i < startTime.Length; i++)
{
startTime[i] = -1;
endTime[i] = -1;
}
Stack<int> stack = new Stack<int>();
int startCounter, endCounter;
startCounter = endCounter = 0;
for (i = 0; i < permutation.Length; i++)
{
Console.WriteLine("Adj({0}) = {1}", i, string.Join(", ", GetAdjacents(i, signature).ToArray()));
}
for (i = 0; i < permutation.Length; i++)
{
Visit(i, startTime, endTime, signature, ref startCounter, ref endCounter);
}
Console.WriteLine("starttime : {0}", string.Join(", ", startTime));
Console.WriteLine("endtimes : {0}", string.Join(", ", endTime));
permutation = endTime.Select((t, j) => new Tuple<int, int>(t, j)).OrderBy(t => t.Item2).Select(t => t.Item1).ToArray();
return permutation;
}
private static void Visit(
int root,
int[] startTime,
int[] endTime,
char[] signature,
ref int startCounter,
ref int endCounter)
{
if (endTime[root] != -1) return;
Stack<Tuple<int,bool>> stack = new Stack<Tuple<int,bool>>();
stack.Push(new Tuple<int,bool>(root,false));
while (stack.Count > 0)
{
var current = stack.Pop();
if (!current.Item2)
{
stack.Push(new Tuple<int, bool>(current.Item1, true));
if (startTime[current.Item1] == -1)
{
startTime[current.Item1] = startCounter++;
var adjacents = GetAdjacents(current.Item1, signature);
foreach (var adj in adjacents)
{
if (startTime[adj] == -1)
{
stack.Push(new Tuple<int, bool>(adj, false));
}
}
}
else if (endTime[current.Item1] == -1)
{
throw new InvalidOperationException("cyclic graph exception");
}
}
else
{
endTime[current.Item1] = endCounter++;
}
}
}
private static List<int> GetAdjacents(int i, char[] signature)
{
List<int> adjacents = new List<int>();
if (i < signature.Length && signature[i] == 'D')
{
adjacents.Add(i + 1);
}
if (i > 0 && signature[i - 1] == 'I')
{
adjacents.Add(i - 1);
}
return adjacents;
}
}
}