кодинг интервие

[ystar]

знатоки - вот задача, нигде в интернете не находится (в студию если найдете) -
Параметр - "A B C" нужно посетить все переходы ровно 1 раз, например A->B->C->B->A->C->A, AB, BC, CB, BA,AC, CA <=> AB AC BA BC CA CB - все посетили 1 раз.
Return - linked list or array.

Итак. Понятно что все пары это пермутации, для данного примера их 6. А вот результат должен быть массив из 7. Допустим мы получили все пары, это легко сделать. А вот как получить результат из них.Можно Biderctional graph, пройтись с помощью DFS, посещяя каждый edge один раз. Может можно как то проще. Если кто знает, псевдокод или код в студию плиз

1. купите литкод, у них сейчас новая фича - study plan -> от простого к сложному, и чтобы как можно больше тем обхватить
2. educative или ещё что нибудь, где систем дизайн раздают.

[alex-IT]

знатоки - вот задача, нигде в интернете не находится (в студию если найдете) -
Параметр - "A B C" нужно посетить все переходы ровно 1 раз, например A->B->C->B->A->C->A, AB, BC, CB, BA,AC, CA <=> AB AC BA BC CA CB - все посетили 1 раз.
Return - linked list or array.

Итак. Понятно что все пары это пермутации, для данного примера их 6. А вот результат должен быть массив из 7. Допустим мы получили все пары, это легко сделать. А вот как получить результат из них.Можно Biderctional graph, пройтись с помощью DFS, посещяя каждый edge один раз. Может можно как то проще. Если кто знает, псевдокод или код в студию плиз

1. купите литкод, у них сейчас новая фича - study plan -> от простого к сложному, и чтобы как можно больше тем обхватить
2. educative или ещё что нибудь, где систем дизайн раздают.

да купил давно, не находится на литкоде, и нигде не находится, даже подобная задача

[alex-IT]

немного поясню, обходим элементы таким образом, чтобы все переходы от одного к другому элементу были пройдены 1 раз
Т.е нам надо пройти от А к B, от B к А и т.д.полный список переходов будет AB AC BA BC CA CB. Ясно что это пермутации.

Сложность в том как пройти эти элементы по цепочке, например A->B->C->B->A->C->A
В данной цепочке мы прошли AB, BC, CB, BA,AC, CA . Ясно что цепочка на 1 больше чем количество пар (пермутаций). В данном случае пермутаций 6, а в цепочке 7, понятно почему.
Цель - построить любую валидную цепочку. Пермутации найти задача простая и возожно можно и без пермутаций обойтись
Примеры валидных цепочек, кроме приведенной выше A->C->B->C->A->B->A , другой пример B->A->C->A->B->C->B
Само собой должно работать для любого количества элементов - например ABCD уже дает 24 пермутации.

[mikeG]

Code: Select all

n = 4
for x in range(n):
  for y in range(x+2, n):
    print chr(ord('A') + x)
    print chr(ord('A') + y)
  print chr(ord('A') + x)
for x in range(1, n):
  print chr(ord('A') + n - 1 - x)

[alex-IT]

Code: Select all

r=[]
for i in range(len(s)):
    for j in range(i+1,len(s)):
        r.append(s[i])
        r.append(s[j])
r.append(s[0])

тоже работает. Думаю, а как сделать чтобы ВСЕ верные варианты цепочек выдавались, хотя бы те верные которые начинаются с первого элемента, в нашем случае с А. Начинающиеся с других элементов, можно составить разрезав на 2 подстроки и поменяв их местами.