interview_prep/smallest_difference_in_stream.py at main · rishsanyal/interview_prep · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

from queue import Queue

# class NumObj(object):
#     def __init__(self, curr_num, curr_index, first_num, first_num_index, second_num, second_num_index, smallest_diff):
#         self.curr_num = curr_num
#         self.curr_index = curr_index
#         self.first_num = first_num
#         self.first_num_index = first_num_index
#         self.second_num = second_num
#         self.second_num_index = second_num_index
#         self.smallest_diff = smallest_diff

class Node(object):
    def __init__(self, val, index, diff, next_node = None):
        self.val = val
        self.index = index
        self.curr_smallest_diff = diff
        self.next = next_node

class Solution():
    def __init__(self):
        self.node = None

    # def insert_node(self, i, val):
    #     curr_node = self.node
    #     tempNode = Node(val, i, 0)

    #     next_node = None

    #     while curr_node:
    #         if val < curr_node.val:
    #             next_node = curr_node
    #             curr_node = tempNode
    #             curr_node.next = next_node
    #             self.node = curr_node
    #         else:
    #             next_node = curr_node
    #             curr_node = curr_node.next

    #     if not curr_node:
    #         next_node.next = tempNode


    #     return None

    def count(self, nums, k):

        if len(nums) == 0:
            return

        q = Queue(k)
        res = []

        first_num, first_num_index = None, None
        second_num, second_num_index = None, None
        third_num, third_num_index = None, None

        for i, val in enumerate(nums):
            if q.full():
                pop_val, pop_index = q.get()
                q.put((val, i))

            if (not first_num or not second_num or not third_num):
                if not first_num:
                    first_num, first_num_index = val, i
                    res.append(val)
                elif not second_num:
                    if val > first_num:
                        second_num, second_num_index = val, i
                    else:
                        second_num, second_num_index = first_num, first_num_index
                        first_num, first_num_index = val, i

                    res.append((second_num - first_num))
                elif not third_num:
                    ## Compare with first_num
                    ## Compare with second_num
                    ## else: assign to third num
                    if val < first_num:
                        third_num, third_num_index = second_num, second_num_index
                        second_num, second_num_index = first_num, first_num_index
                        first_num, first_num_index = val, i
                    elif val < second_num:
                        third_num, third_num_index = second_num, second_num_index
                        second_num, second_num_index = val, i
                    else:
                        third_num, third_num_index = val, i

                    if not third_num:
                        res.append((second_num - first_num))
                    else:
                        res.append(min((second_num - first_num), (third_num - second_num)))

                q.put((val, i))
            else:
                ## pop from queue

                ## Assign None to relevant number
                ## Move number up
                    ## If it's first num that's popped then 2nd becomes first, 3rd becomes second, etc
                    ## If it's second that's popped then third becomes 2nd
                    ## if it's third then we're good

                if pop_index == first_num_index:
                    first_num, first_num_index = second_num, second_num_index
                    second_num, second_num_index = third_num, third_num_index
                    third_num, third_num_index = None, None
                elif pop_index == second_num_index:
                    second_num, second_num_index = third_num, third_num_index
                    third_num, third_num_index = None, None
                else:
                    third_num, third_num_index = None, None

                if val < first_num:
                    third_num, third_num_index = second_num, second_num_index
                    second_num, second_num_index = first_num, first_num_index
                    first_num, first_num_index = val, i
                elif val < second_num:
                    third_num, third_num_index = second_num, second_num_index
                    second_num, second_num_index = val, i
                else:
                    third_num, third_num_index = val, i
                ## Then we compare against all three
                ## if val < first_num
                ## elif val < second_num
                ## else: third_num, thid_num_index = val, i (Third num is free at this point anyway)
                res.append(min((second_num - first_num), (third_num - second_num)))

                print(second_num)
                print(first_num)
            #     ## Then we append the min diff to res

        print(res)


if __name__ == '__main__':
    # Find the minimum absolute difference possible between 2 in a queue of size N
    # if curr_num < smallest_num:

    nums = [1, 2, 8, 4, 7]
    k = 3

    s = Solution()

    print(s.count(nums, k))