Google Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
Little bit modification
int lasti=1
For i = 0...siglen-1
If signature[i] == 'I'
print reverse(lasti, i+1)
lasti=i+2
print reverse(lasti, siglen+1)
I think it'll work now perfectly
Here's a working Python code:
from sys import stdin
def solve(sign):
result = []
last = 1
for i in range(1, len(sign) + 1):
if sign[i - 1] == 'I':
result += range(i, last - 1, -1)
last = i + 1
return result += range (len(sign) + 1, last - 1, -1)
for line in stdin.readlines():
print solve(line[:-1])
The greedy strategy only works when n<10. For example, when n=10, for a signature like IDDDDDDDDD, the greedy algorithm like above will generate a permutation "1, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2", however, the lexicographically minimum one should be "10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1" because lexicographically 10 is smaller than 1.
@nybon: I guess that really depends on how you interpret the term "lexicographically minimum permutation". My interpretation was that each number would be interpreted as coming "lexicographically before" if it is less than the other number. So 2 comes before 11. It's true that "lexicographically" would suggest that things should be in dictionary order, not numeric order, but the interpretation I used makes sense in the context of this question, as evidenced by how everyone else assumed exactly the same thing. Also, since the integers seem to be given as an array of ints, you might think of each int as being 32 0s and 1s, in which case lexicographic ordering would be identical to numeric ordering for nonnegative integers.
I think you're the first person here to interpret the question in the way that you did, so it's not so much that these solutions are wrong, but just a different interpretation of the question. Your interpretation isn't any less valid though.
Fundamentally, the solution is the same either way: the algorithm here tells you the rank of the element that should be placed at each position. If your sequence is 3, 2, 1, 4, that just means you should place the 3rd lowest element first, followed by the 2nd lowest, followed by the lowest, followed by the greatest. You can use whatever metric you want for how you decide the order of elements (numeric value or alphabetic order or something else entirely). Of course whether or not this paragraph is true depends on the exact specifics of how we define "lexicographic" ordering between permutations.
@eugene.yarovol, thanks for the reply. Correct, after some further thought, I think both the interpretations are valid, by "lexicographically", the above solution consider the alphabet contains all the numbers possible (this is an infinite alphabet, for example, 10 is consider as single character in the alphabet instead two characters), while if you consider the alphabet contains only single digits (0~9), the "lexicographically minimum" will lead to very different result and algorithm. I posted a solution for the different interpretation below because both interpretations are interesting problems to solve, but I think the problem should give some more explanation on the definition of "lexicographically minimum" to make it more clearly defined.
Thanks for DuckBoy, I think your idea is good and simple to implement.
Also thanks for Biswajit Sinha to fix the bug in DuckBoy's original pseudo code.
The following is the working Java code with a simple test:
class G211
{
public static void main(String[] args)
{
System.out.println(findPermutation("DDIIDDI"));
}
private static String reverse(int begin, int end)
{
StringBuffer sb = new StringBuffer();
for (int i = end; i >= begin; i--) {sb.append(i + " ");}
return sb.toString();
}
public static String findPermutation(String signature)
{
StringBuffer sb = new StringBuffer();
int lasti = 1;
for (int i = 0; i < signature.length(); i++)
{
if ('I' == signature.charAt(i))
{
sb.append(reverse(lasti, i + 1));
lasti = i + 2;
}
}
sb.append(reverse(lasti, signature.length() + 1));
return sb.toString();
}
}
Represent D and I as directed edges between successive indices i.e. DDIIDI = 0 <-- 1 <-- 2 --> 3 --> 4 <-- 5 --> 6. Perform topological sort with the constraint that left edges should be visited before right edges. Assign values to the topologically sorted output. So, the resulting permutation would 3, 2, 1, 4, 6, 5, 7.
Topological sort returns 2, 1, 0, 3, 5, 4, 6 as the order of the indices. Assigning values starting from 1 to N to these indices gives 3, 2, 1, 4, 6, 5, 7.
I 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.
using System;
using 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;
}
}
}
@johnny...........could you please explain the data structure you will use for it....or explain thru some pseudo code or code.......because using conventional topological sorting it's difficult to implement
A simple DFS should suffice if you reverse the direction of the edges (DDIIDI = 0 --> 1 --> 2 <-- 3 <-- 4 --> 5 <-- 6) and assign a label to the node when the node reaches finished state (when all its descendants have been visited).
void DFS_visit(Graph G, int v, int& count){
G.setVisited(v, true);
for i in G.AdjList[v]
if (!G.isVisited(i))
DFS_visit(G, i, count);
}
G.assignLabel(v, count++);
}
void DFS(Graph G){
int count = 1;
for (int i = 0; i < V; ++i)
if (!G.isVisited(i))
DFS_visit(G, i, count);
}
@johny, can you explain why we need to reverse the direction of the edge? What you said did work, but I wanna know why. Thanks for the explanation.
I think we can use some rules to do the talk in O(n) time complexity:
Lets say ch='I'/‘D' is the variable we use to tranverse the input sequence,
when ch is not the last character from the input sequence
1) if 'D' is found, then push the corresponding digit in a stack;
2) if 'I' is found, then print the corresponding digit; then pop out all the digits in the stack and print them;
when ch is the last character from the input sequence
1) if 'D' is found, push the corresponding and next digit in the stack, and then print and pop all;
2) if 'I' is found, then print the corresponding digit, and print and pop all in the stack and then print the next digit;
If there is any problem, please point it out. Thanks.
Why did you all recommend a topological sort? The following algorithm has O(N) complexity:
static vector<int> solve(const string input) {
vector<int> result(input.size() + 1);
int indexOfSequence = 0;
int elementNumber = 1;
for (int i = 0; i < input.size(); i++) {
if (input[i] == 'I') {
for (int j = i; j >= indexOfSequence; j--) {
result[j] = elementNumber;
elementNumber++;
}
indexOfSequence = i + 1;
}
}
for (int j = input.size(); j >= indexOfSequence; j--) {
result[j] = elementNumber;
elementNumber++;
}
return result;
}
You can use backtracking to construct solution.
Suppose you have signature "DID"
1. Generate sorted sequence [1, 2, 3, 4]
2. Use backtracking to constuct solution.
Start with.
[1] -> [2,3,4]
[2] -> [1,3,4]
[3] -> [1,2,4]
[4] -> [1,2,3]
Get first char from signature 'D'.
[1] -> [2,3,4] 'D' => No solution
[2] -> [1,3,4] 'D' => [2,1]->[3,4]
etc..
This is a simple recursive algorithm that iterates through candidate solutions and terminates fairly quickly when a dead end is reached.
def min_solution(s):
nums = range(1, len(s) + 2)
def _min_solution(legal, nums, s):
if s == '':
if legal(nums[0]):
return nums
else:
return None
start = 0
for c in s:
if c == 'D':
start += 1
else:
break
for i in range(start, len(nums)):
if legal(nums[i]):
new_nums = nums[:]
val = new_nums.pop(i)
if s[0] == 'D':
new_legal = lambda n: n < val
else:
new_legal = lambda n: n > val
rest = _min_solution(new_legal, new_nums, s[1:])
if rest:
return [val] + rest
return None
always = lambda n: True
solution = _min_solution(always, nums, s)
return solution
tests = [
"",
"D",
"I",
"DD",
"II",
"DI",
"ID",
"DID",
"IDI",
"DDD",
"IDIDIDI",
"IIIIIIIIIII",
"DDDDDDDDDDI",
"IDDDDDDDDDD",
"DIDDDDDDDDD",
]
for s in tests:
print repr(s), min_solution(s)
I think this code will add repeated number.........see for a signature DDIIDI, it will create a list efficiently upto 3,2,1 and after that it will add again 2 for 'I' and so on..........i think you need to keep some check to exclude those number which already included....because every time the start variable starts from 0 may cause some problem here
Biswajit, I don't think you're reasoning about my code correctly.
I added the the test case for "DDIIDI", and it produced the answer [3, 2, 1, 4, 6, 5, 7]. Is there a better solution?
Do you understand what pop() does in Python? It removes an item from the list, preventing the exact non-problem problem that you describe.
Showell ....you are right........I skipped that one...anyways I loved your code....that's why I want to be sure that it's perfect....anyways thanks to clarify...
No worries. pop() is somewhat idiomatic in Python, but for folks coming from other languages, I don't think I express my intent in the code very well. As far as I can tell, my algorithm works correctly and efficiently, but I bet the expressiveness of the code could be much improved. Gotta run...
Agree with Johnny's topological sort solution. Construct a graph whose nodes each represent one number slot. If the nodes of the graph ar a1, a2... an, ai -> ai+i (edge from i to i+1) if signature(i) = I and ai <- ai+1 (edge from i+1 to i) if signature(i)=D
Run the topological sort on all the nodes starting from the last node since you wish to have the last one be assigned the biggest value
Code:
public static int[] findLexicographicallyLowestPermutation(String signature) {
if (signature == null) return null;
int[] result = new int[signature.length() + 1];
int graph[][] = new int[signature.length() + 1][signature.length() + 1];
for(int i=0; i<graph.length; i++) for(int j=0; j<graph[i].length; j++) graph[i][j] = 0;
for(int i=0; i<signature.length(); i++) {
if (signature.charAt(i) == 'D') {
graph[i+1][i] = 1;
} else {
graph[i][i+1] = 1;
}
}
boolean visited[] = new boolean[signature.length() + 1];
int topValue = result.length;
for (int i=result.length-1; i>=0; i--) {
topValue = topSort(graph, visited, result, i, topValue);
}
return result;
}
public static int topSort(int[][] graph, boolean[]visited, int[] result, int n, int topValue) {
if (visited[n]) return topValue;
visited[n] = true;
for(int i=0; i<graph.length; i++) {
if (graph[n][i] != 0) {
topValue = topSort(graph, visited, result, i, topValue);
}
}
result[n] = topValue;
return topValue - 1;
}
Follow this algorithm:
1. Start from the left
2. Count the largest consecutive decrease in the remaining sequence = n_D
eg, "ID", n_D = 0
eg, "DI", n_D = 1
eg, "DD", n_D = 2
eg, "II", n_D = 0
3. Pick the n_Dth smallest of the available numbers
4. Repeat
The idea of this algorithm is that you always pick the smallest number that will be able to 'survive' the longest incoming decrease.
For example, "IDIDI":
IDIDI, n_D = 0 , pick 1
DIDI, n_D = 1, pick 3
IDI, n_D =0, pick 2
DI, n_D = 1, pick 5
I, N_D = 0, pick 4
add in the remaining, 6
This can be done in time O(n) and space O(n)
public static List<Integer> findPermute( String signature ){
List<Integer> numbers = generateSortedSequence( signature.length() );
BitSet usedNumbers = new BitSet( numbers.size() + 1 );
for( int i =0; i < numbers.size(); i++ ){
int curNum = numbers.get(i);
List<Integer> seq = new ArrayList<Integer>();
seq.add( curNum );
usedNumbers.set(curNum);
List<Integer> available = new ArrayList<Integer>( numbers );
available.remove(i);
List<Integer> genSeq = generatePermutation(seq, available, signature, 0);
// sequence fully generated
if( genSeq.size() == numbers.size() ){
return genSeq;
}
}
return null;
}
private static List<Integer> generatePermutation( List<Integer> constuctedSeq, List<Integer> availableNumbers, String signature, int sigIndex ){
if( sigIndex >= signature.length() ){
return constuctedSeq;
}
char di = signature.charAt( sigIndex );
for( int i = 0; i < availableNumbers.size(); i++ ){
int lastElem = constuctedSeq.get( constuctedSeq.size()-1);
int curElem = availableNumbers.get(i);
if( (di == 'D' && lastElem > curElem) || (di == 'I' && lastElem < curElem) ){
List<Integer> newSeq = new ArrayList<Integer>( constuctedSeq );
newSeq.add( curElem );
List<Integer> newAvailNumbers = new ArrayList<Integer>( availableNumbers );
newAvailNumbers.remove(i);
List<Integer> partPerm = generatePermutation( newSeq, newAvailNumbers, signature, sigIndex+1 );
if( partPerm.size() > 0 ){
return partPerm;
}
}
}
return new ArrayList<Integer>();
}
public class DI {
static int n;
static int[] q ;
public static void main(String[] args) {
String str = "IIIIDI";
n = str.length()+1;
q = new int[n];
getNumber(str);
}
public static void getNumber(String str){
int index =0;
while (index!=str.length()){
if (str.charAt(index)=='D'){
if (q[index]==0){
q[index]=2;
q[index+1]=1;
index++;
continue;
} else {
int temp = q[index];
q[index]=q[index]+1;
q[index+1]=temp;
for (int i=index-1;i>=0;i--){
for (int j=i+1;j<=index;j++){
if (q[i]==q[j]){
q[i]+=1;
break;
}
}
}
index++;
}
} else if (str.charAt(index)=='I'){
if (q[index]==0){
q[index]=1;
q[index+1]=2;
index++;
continue;
} else {
int l = getLargestNumberInQ(q);
q[index+1]=l+1;
index++;
}
}
}
for (int i =0;i<q.length;i++){
System.out.print(q[i]);
}
}
static int getLargestNumberInQ(int[] q){
int large=q[0];
for (int i=1;i<q.length;i++){
if (q[i]>large){
large =q[i];
}
}
return large;
}
}
public class DI {
static int n;
static int[] q ;
public static void main(String[] args) {
String str = "IIIIDI";
n = str.length()+1;
q = new int[n];
getNumber(str);
}
public static void getNumber(String str){
int index =0;
while (index!=str.length()){
if (str.charAt(index)=='D'){
if (q[index]==0){
q[index]=2;
q[index+1]=1;
index++;
continue;
} else {
int temp = q[index];
q[index]=q[index]+1;
q[index+1]=temp;
for (int i=index-1;i>=0;i--){
for (int j=i+1;j<=index;j++){
if (q[i]==q[j]){
q[i]+=1;
break;
}
}
}
index++;
}
} else if (str.charAt(index)=='I'){
if (q[index]==0){
q[index]=1;
q[index+1]=2;
index++;
continue;
} else {
int l = getLargestNumberInQ(q);
q[index+1]=l+1;
index++;
}
}
}
for (int i =0;i<q.length;i++){
System.out.print(q[i]);
}
}
static int getLargestNumberInQ(int[] q){
int large=q[0];
for (int i=1;i<q.length;i++){
if (q[i]>large){
large =q[i];
}
}
return large;
}
}
my solution,
starting from the first lexographically ordered - [1,2,3,....,N]
basically, running left to right, once a swap is needed, as long as it's all 'D' / 'I',
the swap will be between the current, and last once to switch to 'I'/'D'
example run
D, D, I, I, D, I, D, I, I,
2, 1, 0, 3, 5, 4, 7, 6, 8, 9
public void minLexographicallPermutation(string v)
{
int j, i;
int N = v.Length + 1;
List<int> L = new List<int>(N);
int swap;
bool bSwap = false;
// populate list
for (i = 0; i < N; i++)
L.Add(i);
for (i = 0; i < v.Length; i++ )
Console.Write(v[i] + ", ");
Console.WriteLine("");
// validate input
for (i = 0; i < N - 1; i++)
{
if (v[i].Equals("D") || v[i].Equals("I"))
{
Console.WriteLine("v is not legal");
return;
}
}
for (i = 0; i < N-1; i++)
{
bSwap = false;
j = 0;
if (v[i].Equals('D') )
{
j = i + 1;
if (L[i] < L[j])
bSwap = true;
while (L[i] < L[j] && v[j].Equals('D'))
j++;
}
else if (v[i].Equals('I'))
{
j = i + 1;
if (L[i] > L[j])
bSwap = true;
while (L[i] > L[j] && v[j].Equals('I'))
j++;
}
if (bSwap)
{
swap = L[j];
L[j] = L[i];
L[i] = swap;
}
Console.Write(L[i] + ", ");
}
Console.WriteLine(L[N-1]);
}
doesn't matter.
I've just built the List of integers from 0 to N-1
it's the same result if I build it from 1 to N
other than that, found any flaws?
it does work on it, say DDD - 123
i=0, j=1:1 < 2
while (D), j++
1 <--> 3
array = 321
least leicographical for all Descening.............................
show me an output where this doesnt work?
Java solution:
//You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}.
//Now we create a signature of this array by comparing every consecutive pair of elements.
//If they increase, write I else write D. For example for the above array, the signature would be "DDIIDI".
//The signature thus has a length of N-1. Now the question is given a signature,
//compute the lexicographically smallest permutation of [1,2,....n].
import java.util.*;
public class SignatureBacktrack {
/**
* @param args
*/
static Vector<Vector<Integer>> ansList;
static Boolean finished;
public static void main(String[] args) {
// TODO Auto-generated method stub
int test[] = {1,2,3,4,5};
Arrays.sort(test);
finished = false;
HashSet<Integer> set = new HashSet<Integer>();
for(int i=0;i<test.length;i++) {
set.add(test[i]);
}
ansList = new Vector<Vector<Integer>>();
String signature = "DDDD";
if(!(test == null || signature.length() != test.length-1))
{
for(int i=0;i<test.length;i++) {
Vector<Integer> x = new Vector<Integer>();
HashSet<Integer> setClone = (HashSet<Integer>) set.clone();
setClone.remove(test[i]);
x.add(test[i]);
signMatch(x,1,setClone,signature);
}
for(Vector<Integer> a : ansList) {
System.out.println(a);
}
//System.out.println(ansList.get(0));
}
}
static void signMatch(Vector<Integer> vec, int pos, HashSet<Integer> s,String sign) {
if(!finished) {
if(s.isEmpty()) {
ansList.add(vec);
finished = true;
} else {
if((""+sign.charAt(pos-1)).compareToIgnoreCase("D") == 0) {
for(Integer a : s) {
Vector<Integer> vecClone = (Vector<Integer>) vec.clone();
HashSet<Integer> setClone = (HashSet<Integer>) s.clone();
if(vec.get(pos-1) > a) {
vecClone.add(a);
setClone.remove(a);
signMatch(vecClone,pos+1,setClone,sign);
}
}
}else if((""+sign.charAt(pos-1)).compareToIgnoreCase("I") == 0) {
for(Integer a : s) {
Vector<Integer> vecClone = (Vector<Integer>) vec.clone();
HashSet<Integer> setClone = (HashSet<Integer>) s.clone();
if(vec.get(pos-1) < a) {
vecClone.add(a);
setClone.remove(a);
signMatch(vecClone,pos+1,setClone,sign);
}
}
}
}
}
}
}
My algorithm, run in O(n), space O(1).
def smallest_permuation(signature):
imin = 1 # value for next i
perm = []
left = 0
while left < len(signature):
try:
right = left + signature[left:].index('I')
except:
right = len(signature)
perm.extend(range(right - left + imin, imin - 1, - 1))
imin += right - left + 1
left = right + 1
if signature[-1] == 'I': # increase the last time
perm.append(imin)
return perm
import java.util.*;
public class PermutationFromSignature {
static ArrayList<Integer> res;
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
String input = sc.next();
res = new ArrayList<Integer>();
permGenSig(input);
for(int i = 0; i<res.size();i++){
System.out.print(res.get(i)+" ");
}
System.out.println();
}
static void permGenSig(String input){
if(input.length()==0) return ;
int i = input.lastIndexOf('I');
int n = input.length()+1;
if(i==-1){
for(int j = 0; j<=input.length(); j++){
res.add(n-j);
}
}
else{
if(i==0) {
res.add(1);
for(int l = 0; l<input.length();l++) res.add(n-l);
return;
}
permGenSig(input.substring(0, i));
int count = 0;
for(int j = i+1;j<=input.length();j++){
res.add(n-count);
count++;
}
}
}
}
C# solution:
public static List<int> FindPermute(string signature)
{
List<int> result = new List<int>();
int d_count = 0;
for (int i = 1; i <= signature.Length + 1; i++)
{
result.Add(i);
}
for (int i = 0; i < signature.Length; i++)
{
if (signature[i] == 'd')
{
d_count++;
}
else
{
int begin = i - d_count;
int end = i;
d_count = 0;
for (; begin < end; begin++, end--)
{
int tmp = result[begin];
result[begin] = result[end];
result[end] = tmp;
}
}
}
return result;
}
Agree with DuckBoy that this is a typical greedy algo.
std::vector<int> FindPermute (const std::string & signature)
{
std::vector<int> permu;
if (signature.empty ())
{
permu.push_back (1);
}
else
{
if (signature.at (0) == 'I')
{
permu.push_back (1);
permu.push_back (2);
}
else
{
permu.push_back (2);
permu.push_back (1);
}
for (int i = 1; i < signature.size (); ++i)
{
if (signature.at (i) == 'I')
{
permu.push_back (i + 2);
}
else
{
permu.push_back (permu.at (permu.size () - 1));
int j = permu.size () - 1;
while (j > 0)
{
if (signature.at (j - 1) == 'D')
{
permu.at (j) = permu.at (j - 1);
-- j;
}
else
{
break;
}
}
permu.at (j) = i + 2;
}
}
}
return permu;
}
Here's a solution in O(n) space and O(n) time complexity:
The Algo relies on the fact the in the output string, there can be( and should be) only one instance of zero.
Input String in A.
Step: 1. Create a separate array of size N - called B.
Step 2. Set the first element of B as 0. Check the first element in A. If its 'D', set B[i] = -1 else set B[i] = 1.
Step 3.. Do this for all elements of A. Keep noting the lowest -ve number seen (=min_negative).
Step4: The output in B after Step 3 is not perfect as it contains -ve numbers. So add min_negative to all elements in B. Now B is our final result.
If I understand this question correctly, "lexicographically minimum" means a number like "10" comes before "1", and both the topological sort solution and the greedy solution above doesn't consider the case when n >= 10. For example, when n=11, for a signature like IDDDDDDDDD, the greedy algorithm like above will generate a permutation "1, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2", however, the lexicographically minimum one should be "10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1" because lexicographically 10 is smaller than 1.
Here is an O(n^2) solution to this problem (according to my understanding of "lexicographically minimum"), and it is like this:
* 1) sort all the numbers lexicograhically, for example, [1..12] is sorted to [10, 11, 1, 12, 2, 3, 4, 5, 6, 7, 8, 9]
* 2) put all numbers [1..n] into a sorted set, this can be done by using a tree set
* 3) iterate each element in the signature, find the numbers with highest indexes and lowest indexes, for example, DDID, the highest number index is 3, and the lowest number index is 2, 4
* 4) for each signature element
* 4.1) if this is an I signature element:
* the current output number should not be greater than (next possible highest number - distance to next highest number)
* the next possible highest number is the max one from sorted set
* and the distance to next highest number can be calculated from (next highest index - current index)
* for each number in the lexicographically sorted array, find the first number that is less or equal to the (max - distance), and add it to the permutation
* 4.2) if this is an D signature element:
* the current output number should not be less than (next possible lowest number + distance to next lowest number)
* the next possible lowest number is the min one from sorted set
* and the distance to next lowest number can be calculated from (next lowest index - current index)
* for each number in the lexicographically sorted array, find the first number that is greater or equal to the (min + distance), and add it to the permutation
Here is the working code to solve this problem like I described above:
public class SignaturePermutation {
public List<Integer> smallestPermutation(String signatureString) {
List<Direction> signature = parse(signatureString);
int n = signature.size() + 1;
List<Integer> numbers = allNumbers(n);
SortedSet<Integer> sortedNumbers = new TreeSet<Integer>(numbers);
List<Integer> lexicographicallySortedNumbers = sortLexicographically(numbers);
List<Integer> highestIndexes = extremeNumberIndexes(signature, Direction.I);
List<Integer> lowestIndexes = extremeNumberIndexes(signature, Direction.D);
List<Integer> permutation = new ArrayList<Integer>(n);
int hi = 0;
int li = 0;
for(int si=0;si<signature.size();si++) {
Direction direction = signature.get(si);
int nextElement = 0;
if(direction == Direction.I) {
int nextHighestIndex = highestIndexes.get(hi);
int distanceToHighest = nextHighestIndex - si;
if(distanceToHighest == 1) { // climb over the highest
hi++;
}
int max = sortedNumbers.last();
int maxAllowed = max - distanceToHighest;
nextElement = findLexicographicallyMax(lexicographicallySortedNumbers, maxAllowed);
} else {
int nextLowestIndex = lowestIndexes.get(li);
int distanceToLowest = nextLowestIndex - si;
if(distanceToLowest == 1) { // move to the lowest
li++;
}
int min = sortedNumbers.first();
int minAllowed = min + distanceToLowest;
nextElement = findLexicographicallyMin(lexicographicallySortedNumbers, minAllowed);
}
sortedNumbers.remove(nextElement);
permutation.add(nextElement);
}
permutation.add(sortedNumbers.first());
return permutation;
}
int findLexicographicallyMax(List<Integer> lexicographicallySortedNumbers, int maxAllowed) {
int result = 0;
for(int i=0;i<lexicographicallySortedNumbers.size();i++) {
if(lexicographicallySortedNumbers.get(i) <= maxAllowed) {
result = lexicographicallySortedNumbers.get(i);
lexicographicallySortedNumbers.remove(i);
break;
}
}
return result;
}
int findLexicographicallyMin(List<Integer> lexicographicallySortedNumbers, int minAllowed) {
int result = 0;
for(int i=0;i<lexicographicallySortedNumbers.size();i++) {
if(lexicographicallySortedNumbers.get(i) >= minAllowed) {
result = lexicographicallySortedNumbers.get(i);
lexicographicallySortedNumbers.remove(i);
break;
}
}
return result;
}
List<Integer> extremeNumberIndexes(List<Direction> signature, Direction extreme) {
List<Integer> indexes = new ArrayList<Integer>();
for(int si=0;si<signature.size();si++) {
Direction direction = signature.get(si);
if(direction == extreme) {
Direction nextDirection = si == signature.size() - 1 ? null : signature.get(si + 1);
if(nextDirection == null || (nextDirection != null && nextDirection != direction)) {
indexes.add(si + 1);
}
}
}
return indexes;
}
List<Integer> allNumbers(int n) {
List<Integer> allNumbers = new ArrayList<Integer>(n);
for(int i = 0; i < n;i++) {
allNumbers.add(i+1);
}
return allNumbers;
}
List<Direction> parse(String signature) {
List<Direction> parsedSignature = new ArrayList<Direction>();
for(int i = 0; i < signature.length(); i++) {
parsedSignature.add(Direction.valueOf(signature.charAt(i)));
}
return parsedSignature;
}
List<Integer> sortLexicographically(List<Integer> numbers) {
List<Integer> lexicographicallySortedNumbers = new ArrayList<Integer>(numbers);
Collections.sort(lexicographicallySortedNumbers, new LexicographicalComparator());
return lexicographicallySortedNumbers;
}
private static class LexicographicalComparator implements Comparator<Integer> {
@Override
public int compare(Integer one, Integer two) {
String s1 = one.toString();
String s2 = two.toString();
int result = s1.compareTo(s2);
if(s1.length() != s2.length()) {
if(s1.length() > s2.length()) {
if(s1.startsWith(s2)) {
result = compare(s1, s2);
}
} else {
if(s2.startsWith(s1)) {
result = -1 * compare(s2, s1);
}
}
}
return result;
}
private int compare(String longString, String shortString) {
int result = longString.charAt(longString.length()-1) - shortString.charAt(0); // 123 is considered larger than 12
result = result == 0 ? -1 : result; // 11 is smaller than 1
return result;
}
}
static enum Direction {
I, D;
public static Direction valueOf(char c) {
return c == 'I' ? I : D;
}
};
}
"1" is lexicographically less than "10". Please also refer to compareTo doc of String that should make things more clear.
So the lexicographically sorted output for the example you have specified should be = 1, 10, 11, 9 , 8 ....
>> "1" is lexicographically less than "10". Please also refer to compareTo doc of String that should make things more clear.
Maybe I don't make it clear enough. But in order to make the concatenated string lexicographically smaller, "1" should be larger than "10" during comparison. For example", when you try to concatenate "1" and "10", "1,10" is larger than "10,1"
Start with regular sequence - this is the smallest one possible for IIIIII, when encounter sequence of D, just reverse them
1234567
DDIIDI find consecutive sequence of D - reverse these numbers (123 -> 321)
3214567
D
3215657 find consecutive sequence of D - reverse these numbers (56 -> 65)
DDIIDI
O(n) in-place algorithm
A[i] = i 1<=i<=n
dStart = dEnd = 0
for each S[j], 1<=j<=N
switch S[j]:
case 'D':
if (dStart==0)
{
dStart = j;
}
break;
case 'I':
if (dStart > 0)
{
dEnd = j-1; // S[dStart] .. S[dEnd] has D 1<=dStart<=dEnd<=N-1
Reverse(A, dStart, dEnd+1); // reverse A[dStart]..A[dEnd+1]
dStart = dEnd = 0;
}
break;
Reverse(A, s, e)
{
while (s < e)
{
t = A[s];
A[s] = A[e];
A[e] = t;
s++;
e--;
}
}
A[] 1 2 3 4 5 6 7
S[] D D I I D I
dStart = 1, dEnd = 2
Reverse(A, 1, 3)
A[] 3 2 1 4 5 6 7
S[] D D I I D I
dStart = 5, dEnd = 5
Reverse(A, 5, 6)
A[] 3 2 1 4 6 5 7
Validate: 3214657
DDIIDI
reverse(1,1) is 1, and reverse(4,6) is 654.
- DuckBoy October 31, 2012The pseudocode works in linear time and constant space, and uses 1 based indexing, which is why the indexing looks kind of strange. It is equivalent to starting with a list 1234567...n, finding all groups of Ds, and reversing sections of the initial list that the Ds overlap.
This greedy algorithm stems from the idea that if the list starts with an I, the output must start with a 1, if it starts with a single D, it must start 21, DD, 321 and so forth. Whenever it sees an I, it picks the minimum element that can be placed, and is therefore lexicographically minimal.