Question

Cisco | OA Coding and Solutions | Set - 18 | 2022

Answer 1

Alice and her friends appeared in CISCO hackathon and they are very exicted . In hackathon htey have given a programming question on string in which Alice and her team needs to form a string of length n by using two characters 'A' and 'B' in which two consecutive B's are not allowed .
Alice can generate any string by using permutation and satisfying the above condition . So, Alice and her team can make any number of strings but there is one more condition in which they need to sort all the the possible strings in lexographical order and they provide a string as output which comes at a particular index mentioned in question.

 

Input Format :
T - Test Cases
N - number of characters M - index
1<=t<=10
1<=N<=100
1<=M<=10^9

 

Input -
2
2 3
2 4

 

Output -
BA
Not possible

Answer 2

I used backtracking, kind of like a depth first traversal, I think it works. Since we have 2 characters a and b you can think of it like a binary tree. Left child is always "a" right child is always "b". If the current node is b we don't have a right child. Keeping this order in the tree will keep it sorted lexographically. Maybe there is a better solution, the total number of valid strings appear to be Fibonacci numbers

 

def ab_sort(n,m):
    ans = ""
    index = 0
    def backtrack(str, level, char):
        nonlocal ans
        nonlocal index
        str.append(char)

        if level == n:
            index+=1
            if index == m:
                ans = "".join(str[1:])
            else:
                return
        if not ans:
            backtrack(str,level+1,"a")
            str.pop()
            if str[-1]!="b":
                backtrack(str,level+1,"b")
                str.pop()
    backtrack([], 0, "")
    return ans if ans else None