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

Comment hidden because of low score. Click to expand.
2

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

Comment hidden because of low score. Click to expand.
0

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)

print solve(line[:-1])``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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)

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

}

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++)
{
}

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

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

if (i < signature.Length && signature[i] == 'D')
{
}

if (i > 0 && signature[i - 1] == 'I')
{
}

}
}
}

Comment hidden because of low score. Click to expand.
0

This should definitely work!

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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.

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.

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

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

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

This can be done in time O(n) and space O(n)

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

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

Comment hidden because of low score. Click to expand.
0

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

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

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

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

Comment hidden because of low score. Click to expand.
0

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

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.

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

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

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

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

}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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

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++) {
}

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

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()) {
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) {
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) {
setClone.remove(a);
signMatch(vecClone,pos+1,setClone,sign);
}
}
}
}
}
}
}``````

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

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++){
}
}
else{
if(i==0) {
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++){
count++;
}
}

}
}

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

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

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.

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

Comment hidden because of low score. Click to expand.
0

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> 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);
}
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)) {
}
}
}
return indexes;
}

List<Integer> allNumbers(int n) {
List<Integer> allNumbers = new ArrayList<Integer>(n);
for(int i = 0; i < n;i++) {
}
return allNumbers;
}

List<Direction> parse(String signature) {
List<Direction> parsedSignature = new ArrayList<Direction>();
for(int i = 0; i < signature.length(); 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;
}
};
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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.

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

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?

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.

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