1
$\begingroup$

Today, in an interview, I was asked this programming question:

Given a string, w, following two operations are performed alternatively per day.

  1. Remove last m characters from w and prepend them to w. m is less than length of w.
  2. Remove last n characters from w and prepend them to w. n is less than length of w.

Find how many days would it take to get back w if we start to perform the above operations.

For example, if w is abcde and m is 2 and n is 3, then

original w: abcde after m op, w: deabc after n op, w: abcde

stop since new string abcde is same as the original string w = abcde

My approach was the brute force one where I had a loop and was performing both of the above operation and was continuously checking if the new w is same as the original w. However, this approach is definitely not scalable.

Improve this question
$\endgroup$
  • $\begingroup$ You have to find the smallest $k$ such that $km+kn$ or $km+(k-1)n$ is a multiple of the length $N$ of $w$. Those are Diophantine equations you can solve. Problem is, some manipulations of $w$ could be equal to $w$, (for example, if $w=aaaaa$, one day gets you back to the original string !) so your "Brute force" approach, if correctly implemented, is, IMO, as good as a tricky math exploration... $\endgroup$ – Nicolas FRANCOIS Jul 8 '19 at 4:27
  • $\begingroup$ For the test case, w = abcde, m =2 and n = 3, k = 1 satisfies (km +kn) to be multiple of length N. However, the correct answer is 2 not 1. $\endgroup$ – user3243499 Jul 8 '19 at 4:40
  • $\begingroup$ It should be $2k$ if $m$ and $n$ characters are removed the same amount of times and $2k-1$ if $m$ is removed one more time. $\endgroup$ – Varun Vejalla Jul 8 '19 at 5:05
  • $\begingroup$ Are all characters of the string distinct? $\endgroup$ – Varun Vejalla Jul 8 '19 at 5:05
  • $\begingroup$ @automaticallyGenerated: Are all characters of the string distinct? Not necessarily. $\endgroup$ – user3243499 Jul 8 '19 at 5:14
0
$\begingroup$

The following method should be a great improvement over brute force in the case where the characters of the string are distinct. In the case where the characters are not distinct, it at least provides an upper bound.

Assume the string consists of the integers $1$ through $N$ in sequence, so $N$ is the length of the string. Apply the operations 1 and 2 to the string. Interpret the resulting string of integers as a permutation of the original string. Write this permutation as a product of disjoint cycles. The period of the permutation is the least common multiple of the lengths of the cycles.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.