Непонятное техническое интервью

Question

Вопрос был задан в недавнем интервью по программированию.

Учитывая строку «str» и пару индексов обмена «N», сгенерируйте лексикографически большую строку. Индексы обмена можно повторно использовать сколько угодно раз.

Например:

String = "abdc" 
Indices: 
(1,4) 
(3,4) 

Ответ:

cdba, cbad, dbac,dbca 

Вы должны напечатать только "DBCA", который является лексикографически по величине.

Это может показаться наивным, но я полностью не в состоянии ответить на этот вопрос. Может кто-то, пожалуйста, помогите мне понять, что означает этот вопрос?

Answer 1

Я думаю, что это говорит, что, учитывая строку mystring = "abdc", вы проинструктированы для переключения символов в указанных парах индексов такой, что вы производите лексикографически «большую» строки (то есть такой, что если вы lex-sorted все возможные строки, это закончишься вверх по последнему индексу). Таким образом, у вас есть две действительные операции: (1) переключатель mystring[1] с mystring[4] ("abdc" ->"cbda"), и (2) переключатель mystring[3] с mystring[4] ("abdc" ->"abcd"). Кроме того, вы можете размножать цепные операции: либо операцию (1), за которой следует (2) ("abdc" ->"cbda" ->"cbad"), либо наоборот ("abdc" ->"abcd" ->"dbca") и так далее ("abdc" ->"cbda" ->"cbad" ->"dbac").

Тогда вы (реверс) Лекс сортировка эти и палить верхний индекс:

>>> allPermutations = ['abcd', 'cbad', 'abdc', 'cbda', 'dbca', 'dbac'] 
>>> lexSorted = sorted(allPermutations, reverse=True) # ['dbca', 'dbac', 'cbda', 'cbad', 'abdc', 'abcd'] 
>>> lexSorted.pop(0) 
'dbca' 

Answer 2

На основе выяснено @ncemami я пришел с этим решением.

public static String swap(String str, Pair<Integer, Integer> p1, Pair<Integer, Integer> p2){ 

     TreeSet<String> set = new TreeSet<>(); 
     String s1 = swap(str, p1.getKey(), p1.getValue()); 
     set.add(s1); 
     String s2 = swap(s1, p2.getKey(), p2.getValue()); 
     set.add(s2); 
     String s3 = swap(str, p2.getKey(), p2.getValue()); 
     set.add(s3); 
     String s4 = swap(s3, p1.getKey(), p1.getValue()); 
     set.add(s4); 
     return set.last(); 

    } 
    private static String swap(String str, int a, int b){ 
     StringBuilder sb = new StringBuilder(str); 
     char temp1 = str.charAt(a); 
     char temp2 = str.charAt(b); 
     sb.setCharAt(a, temp2); 
     sb.setCharAt(b, temp1); 
     return sb.toString(); 
    } 

Answer 3

String = "abcd" 

co_ord = [(1,4),(3,4)] 

def find_combinations(co_ord, String): 

    l1 = [] 
    for tup_le in co_ord: 
     l1.extend(tup_le) 
    l1 = [x-1 for x in l1] 
    l1 = list(set(l1)) 
    l2 = set(range(len(String)))-set(l1) 
    return l1,int(''.join(str(i) for i in l2)) 

def perm1(lst): 

    if len(lst) == 0: 
     return [] 
    elif len(lst) == 1: 
     return [lst] 
    else: 
     l = [] 
     for i in range(len(lst)): 
      x = lst[i] 
      xs = lst[:i] + lst[i+1:] 
      for p in perm1(xs): 
       l.append([x]+p) 
     return l 

lx, ly = find_combinations(co_ord, String)  

final = perm1(lx) 

print(final) 

temp = [] 

final_list=[] 

for i in final: 

    for j in i: 

     temp.append(String[j]) 

    final_list.append(''.join(temp)) 

    temp=[] 

final_list = [ i[:ly] + String[ly] + i[ly:] for i in final_list]  

print(sorted(final_list,reverse=True)[0])