• API
• FAQ
• Tools
• Archive
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.

Top