Google Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
14
of 14 vote

int lasti=1
For i = 1...siglen
    If signature[i] == 'I'
        print reverse(lasti, i)
        lasti=i+1
print reverse(lasti, siglen)

reverse(1,1) is 1, and reverse(4,6) is 654.
The 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.

- DuckBoy October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- Biswajit Sinha October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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])

- liancheng November 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, in the above example, n=11 instead of 10

- nybon December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.yarovoi December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- nybon December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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();
 }
}

- Alva0930 February 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do I miss something here? Because from my understanding it does not work. For a sequence 4,3,5,2,1,6 it builds 341256, but the "correct" answer is 1,2,3,4,5,6 no? (even though you cannot sort this array just by having D,I information)

- mbriskar May 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
8
of 8 vote

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.

- Johny October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

With 2-->3, how does a topological sort return 3 first and then 2?

- anonymous October 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Johny October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- coder October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}
}
}

- coder October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This should definitely work!

- Epic_coder October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Biswajit Sinha October 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 October 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Jack January 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Johny, It does work correctly. But what's the principal of using topological sort for this problem? I think the output order of ts is the logical order of nodes. What's the relation between the logical order and the final order of this problem? Could you please explain it in detail?

- zilchistDeepblue January 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

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;
}

- A.Y.R. November 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I struggled with understanding the topological sort approach, so was very happy to come across this simpler one. Seems to work for the cases I can think of, so thanks a lot.

Now that I know how to solve this, I can go back and try to understand the topological sort approach again.

- Sunny December 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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..

- m@}{ October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

- showell30@yahoo.com October 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 Sinha October 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- showell30@yahoo.com October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- Biswajit Sinha October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- showell30@yahoo.com October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
	}

- Looper October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice Implementation................best code so far

- Biswajit Sinha October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

- tamasir December 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you please explain the meaning of 'lexicographically smallest permutation'.

- ngupta October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose for DDIIDI there can be so many combination like 5324716,5214763 etc. but lexicographically smallest one is 3214657

- Biswajit Sinha October 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- m@}{ October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();
	}

- m@}{ October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you have used a new List for constructed sequence for each iteration???........and how are you checking the smallest lexicographical combination?

- Biswajit Sinha October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

I think the key here is to fInd the longest increasing subseq of D . And make sure the others numbers are set around this.

- Anonymous October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- preeti October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- preeti October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
            

        }

- shacharm October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You cannot include 0 because it would be in range 1 to N

- Biswajit Sinha October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- shacharm October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But your algorithm doesn't work for DD,DDD,DDDD...........................

- Biswajit Sinha October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- shacharm November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

or form DDDDD
123456
623451
653421
654321
solved for DDDDD
you say this is wrong? why?

- shacharm November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
						}
					}
				}
			}
		}
	}
}

- bleep October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- hieuza October 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
}
}

}
}

- Shane October 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- shahar November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- meanmee November 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Ramesh November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- nybon December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
		}
	};
}

- nybon December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"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 ....

- prashant2361 April 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

>> "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"

- nybon August 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For my example above, "1011987654321" is a string lexicographically smaller than "1111098765432"

- nybon August 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Johnny's idea works. The only key is that every graph can have multiple topological sorts. So it is important to start the topological sort with the largest node - i.e 6.

- seattle_gal December 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sme January 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't the lexicographically minimum permutation of 3,2,1,6,7,4,5 being 3,2,1,6,7,5,4?

- panxin0718 January 27, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More