SHARE
TWEET

Untitled

a guest Jun 25th, 2019 45 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """
  2. Google phone interview - Remove repeating numbers
  3. Given a 1-d array candy crush, return the shortest array after removing all the continuous same numbers (the repeating number >= 3)
  4. input: 1-d array [1, 3, 3, 3, 2, 2, 2, 3, 1]
  5. return: [1, 1]
  6. Time complexity should be better than O(n^2)
  7. Mod edit: To slow down the posting of O(n^2) and O(n) "correct" solutions, here is another testcase:
  8. [3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] should
  9. return [3,1,3,2,3]
  10. """
  11.  
  12.  
  13. # BFS
  14. def RemoveRepeatingNumbers(array):
  15.     stack_runs = []
  16.     stack_arrays = [array]
  17.     res = array
  18.  
  19.     while len(stack_arrays) > 0:
  20.         # reseting info from last loop
  21.         i = 0
  22.         repeat_nums = None
  23.         # current_array
  24.         array = stack_arrays[0]
  25.  
  26.         for j in range(1, len(array)):
  27.             # checking list[i] == list[j]
  28.             if array[j] != array[i]:
  29.                 # reseting j to one less than i for the next run through the loop
  30.                 i = j
  31.                 # checking for old stored repeating digits
  32.                 if repeat_nums != None:
  33.                     # adding repeat nums to stack
  34.                     stack_runs.append(repeat_nums)
  35.                     repeat_nums = None
  36.             # checking for repeating digits
  37.             elif (j - i) >= 2:
  38.                 repeat_nums = (i, j)
  39.  
  40.         # check for runs at the end of array [2,1,1,1] --- > finds the [1,1,1]
  41.         if repeat_nums != None and array[-1] == array[-2] == array[-3]:
  42.             # adding repeat nums to stack
  43.             stack_runs.append(repeat_nums)
  44.  
  45.         # remove consecutive digit runs
  46.         for i, j in stack_runs:
  47.             new_array = array[:i] + array[j + 1:]
  48.             stack_arrays.append(new_array)
  49.  
  50.         # empty stacks & delete current array & check for new answer
  51.         stack_runs = []
  52.         if len(res) > len(array):
  53.             res = array
  54.         del stack_arrays[0]
  55.  
  56.     return res
  57.  
  58.  
  59. print(RemoveRepeatingNumbers([1, 3, 3, 3, 2, 2, 2, 3, 1]))
  60. print(RemoveRepeatingNumbers([3, 1, 2, 2, 2, 1, 1, 1, 2, 2, 3, 1, 1, 2, 2, 2, 1, 1, 1, 2, 3]))
  61. print(RemoveRepeatingNumbers([2, 1, 1, 1, 2, 2, 2, 1, 3, 3, 3, 1, 2, 2, 2, 1, 1, 1, 2]))
  62. print(RemoveRepeatingNumbers([2, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 2, 3]))
  63. print(RemoveRepeatingNumbers([1, 1, 2, 2, 3, 1, 3, 2, 2, 1, 1]))
  64. print(RemoveRepeatingNumbers([1, 3, 3, 3, 2, 2, 2, 3, 1]))
  65. print(RemoveRepeatingNumbers([1, 4, 4, 4, 3, 3, 3, 2, 2, 2, 4, 3, 3, 3, 4, 1, 1]))
  66. print(RemoveRepeatingNumbers([1, 1, 1]))
  67. print(RemoveRepeatingNumbers([1, 2, 3]))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top