forked from thatguyintech/100-day-coding-challenge
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathrandomnode.py
127 lines (97 loc) · 2.36 KB
/
randomnode.py
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
import random
class Node:
def __init__(self, val):
self.val = val
self.next = None
# This approach saves space - O(1) space complexity
# but is slower - O(n) runtime
class Solution(object):
def __init__(self, head):
"""
@param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node.
:type head: ListNode
"""
self.head = head
self.numNodes = 0
p = self.head
while p != None:
self.numNodes += 1
p = p.next
def getRandom(self):
"""
Returns a random node's value.
:rtype: int
"""
p = self.head
for i in xrange(random.randint(0, self.numNodes-1)):
p = p.next
return p.val
## Helpers ##
# this is my noob way of checking randomness...
def is_random(f, possibilities):
d = {i: 0 for i in xrange(1, possibilities+1)}
for i in xrange(10000):
d[f()] += 1
for key in d:
if not (d[key] > 900 and d[key] < 1100):
return False
return True
## Tests ##
# A linked list for testing
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n6 = Node(6)
n7 = Node(7)
n8 = Node(8)
n9 = Node(9)
n10 = Node(10)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6
n6.next = n7
n7.next = n8
n8.next = n9
n9.next = n10
def test_new_node():
check = False
n = Node(2)
check = (n.val == 2)
check = (n.next == None)
return check
def test_linked_list_pointer_connection():
check = False
head = Node(1)
middle = Node(2)
tail = Node(3)
head.next = middle
middle.next = tail
check = (head.next.next == tail)
return check
def test_init_solution_sizing():
check = False
solution = Solution(n1)
check = (solution.numNodes == 10)
return check
def test_get_random_returns_int():
check = False
solution = Solution(n1)
check = (type(solution.getRandom()) == int)
return check
def test_solution_randomness():
check = False
solution = Solution(n1)
check = (is_random(solution.getRandom, 10))
return check
def tests():
print(test_new_node())
print(test_linked_list_pointer_connection())
print(test_init_solution_sizing())
print(test_get_random_returns_int())
print(test_solution_randomness())
tests()