Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- Google phone interview - Remove repeating numbers
- Given a 1-d array candy crush, return the shortest array after removing all the continuous same numbers (the repeating number >= 3)
- input: 1-d array [1, 3, 3, 3, 2, 2, 2, 3, 1]
- return: [1, 1]
- Time complexity should be better than O(n^2)
- Mod edit: To slow down the posting of O(n^2) and O(n) "correct" solutions, here is another testcase:
- [3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] should
- return [3,1,3,2,3]
- """
- # BFS
- def RemoveRepeatingNumbers(array):
- stack_runs = []
- stack_arrays = [array]
- res = array
- while len(stack_arrays) > 0:
- # reseting info from last loop
- i = 0
- repeat_nums = None
- # current_array
- array = stack_arrays[0]
- for j in range(1, len(array)):
- # checking list[i] == list[j]
- if array[j] != array[i]:
- # reseting j to one less than i for the next run through the loop
- i = j
- # checking for old stored repeating digits
- if repeat_nums != None:
- # adding repeat nums to stack
- stack_runs.append(repeat_nums)
- repeat_nums = None
- # checking for repeating digits
- elif (j - i) >= 2:
- repeat_nums = (i, j)
- # check for runs at the end of array [2,1,1,1] --- > finds the [1,1,1]
- if repeat_nums != None and array[-1] == array[-2] == array[-3]:
- # adding repeat nums to stack
- stack_runs.append(repeat_nums)
- # remove consecutive digit runs
- for i, j in stack_runs:
- new_array = array[:i] + array[j + 1:]
- stack_arrays.append(new_array)
- # empty stacks & delete current array & check for new answer
- stack_runs = []
- if len(res) > len(array):
- res = array
- del stack_arrays[0]
- return res
- print(RemoveRepeatingNumbers([1, 3, 3, 3, 2, 2, 2, 3, 1]))
- print(RemoveRepeatingNumbers([3, 1, 2, 2, 2, 1, 1, 1, 2, 2, 3, 1, 1, 2, 2, 2, 1, 1, 1, 2, 3]))
- print(RemoveRepeatingNumbers([2, 1, 1, 1, 2, 2, 2, 1, 3, 3, 3, 1, 2, 2, 2, 1, 1, 1, 2]))
- print(RemoveRepeatingNumbers([2, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 2, 3]))
- print(RemoveRepeatingNumbers([1, 1, 2, 2, 3, 1, 3, 2, 2, 1, 1]))
- print(RemoveRepeatingNumbers([1, 3, 3, 3, 2, 2, 2, 3, 1]))
- print(RemoveRepeatingNumbers([1, 4, 4, 4, 3, 3, 3, 2, 2, 2, 4, 3, 3, 3, 4, 1, 1]))
- print(RemoveRepeatingNumbers([1, 1, 1]))
- print(RemoveRepeatingNumbers([1, 2, 3]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement