'Broken Record' Coding Challenge

Question

I was asked to complete a coding challenge for an interview. The challenge being to write a test function to check whether or not a string was a broken record. A broken record is defined as a string that contains a sequential repeated substrings. For example:

# These are broken records
"This is is a broken record"
"This is a is a broken record"
"This is a broken record. This is a broken record."

# These are not broken records
"This is not is a broken record"
"This is a is This"
"This is a broken record. This is not a broken record."

This is the code that I was able to come up with (Python 2.7). Any criticisms, improvements, or suggestions are greatly appreciated.

# Author: Jeremiah Zucker
# brokenRecord.py
# A small module to test whether a substring is repeated 
# immediately, like a broken record

def brokenRecord(sent):
   if sent == "": # Use defualt string if empty
      sent = "This is a a is This"
   print("Determining if broken record: %s" % sent)

   arr = sent.split(" ")

   # Create count array for the sentence
   carr = [0] * len(arr)
   for i in range(0,len(arr)):
      carr[i] = arr.count(arr[i])

   # For each element in the array, try to find the
   # repeat if one is possible
   for i in range(0,len(arr)):
      if carr[i] > 1 and findRepeat(arr, i):
         print("Is a broken record at %d!" % i)
         return
   print("Not a broken record.")

def findRepeat(arr, i):
   beg = arr[i]
   j = i

   # Find all other indices of 'beg'
   others = []
   while beg in arr[j+1:]:
      j = arr[j+1:].index(beg) + j + 1
      others.append(j)

   # For all other indices of 'beg'
   for j in others:
      # Get both substrings
      lenRep = j - i
      try:
         rep = arr[i:j]
         rep2 = arr[j:j+lenRep]
      except IndexError:
         continue

      # Are they equal?
      if rep == rep2:
         # print(rep)
         # print(rep2)
         return True

   # Nope
   return False


if __name__ == '__main__':
   # print usage
   print("brokenRecord.py")
   print("To use, type a string and hit ENTER.")
   print("If no string is provided, the default string will be used.")

   # do until ctrl+c
   while True:
      try:
         brokenRecord(raw_input("\nString: "))
      except KeyboardInterrupt:
         print("\nThanks for testing!")
         break

Answer 1

First impressions matter in interview coding situations. My first thought is: There's a lot of code. And interviewers usually don't like to wade through a lot of code. For you, as a candidate, that may be a sign that you are taking the wrong approach.

Function names should be lower_case_with_underscores as specified in PEP 8 coding conventions.

There should be a function that accepts a string and returns either True or False. Your brokenRecord() function…

def brokenRecord(sent):
   if sent == "": # Use defualt string if empty
      sent = "This is a a is This"
   print("Determining if broken record: %s" % sent)
   …
   print("Not a broken record.")

… incorporates all kinds of junk that make it not reusable:

• A weird if sent == "": sent = "This is a a is This" special case. Such a special case should be moved out into your testing mechanism — the caller, or, better yet, a doctest.
• Printing diagnostics. Again, such code should be done by the caller.
• Not returning any useful value, making it hard for the caller to know what happened.

Catching IndexError to recover from out-of-bounds array access is poor style.

In your main loop, you could eliminate the break by swapping the try and while.

# do until ctrl+c
try:
   while True:
      brokenRecord(raw_input("\nString: "))
except KeyboardInterrupt:
   print("\nThanks for testing!")

Suggested solution

If I, as an interviewer, had asked this question, I would be hoping for a completely different kind of answer. String analysis is much more easily done using regular expressions. In particular, you need this feature:

Backreferences in a pattern allow you to specify that the contents of an earlier capturing group must also be found at the current location in the string. For example, \1 will succeed if the exact contents of group 1 can be found at the current position, and fails otherwise. Remember that Python’s string literals also use a backslash followed by numbers to allow including arbitrary characters in a string, so be sure to use a raw string when incorporating backreferences in a RE.

For example, the following RE detects doubled words in a string.

>>>
>>> p = re.compile(r'(\b\w+)\s+\1')
>>> p.search('Paris in the the spring').group()
'the the'

import re

def is_broken_record(s):
    """
    Check whether a string contains sequential repeated substrings.

    >>> is_broken_record("This is is a broken record")
    True
    >>> is_broken_record("This is a is a broken record")
    True
    >>> is_broken_record("This is a broken record. This is a broken record.")
    True

    >>> is_broken_record("This is not is a broken record")
    False
    >>> is_broken_record("This is a is This")
    False
    >>> is_broken_record("This is a broken record. This is not a broken record.")
    False
    """
    return bool(re.search(r'\b(.+)\s+\1', s))

Answer 2

@200_success solution is great. In case you still want to make the comparison in nested loops I think it is cleaner to have it all in one simple function. The following is just such nested loops function. The hardest part is formulating the indices correctly.

def brokenrecord(sentence):
    words = sentence.split(' ')
    n = len(words)
    for i in range(n):
        for j in range(int((n-i)/2)):
            if words[i:i+j+1] == words[i+j+1:i+2*j+2]:
                return True
    return False