Skip to content

Commit 6f33534

Browse files
keonkeon
committed
update
1 parent eb09d25 commit 6f33534

16 files changed

Lines changed: 324 additions & 109 deletions

‎algorithms/sorting.py‎

Lines changed: 0 additions & 88 deletions
This file was deleted.

‎linkedlist/firstCyclicNode.py‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
# find the first node of a cycle in the linked list.
2+
3+
# 1 -> 2 -> 3 -> 4 -> 5 -> 1 => 1
4+
# A -> B -> C -> D -> E -> C => C
5+
6+
def firstCyclicNode():
7+
pass
8+

‎linkedlist/linkedlist.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,14 +11,14 @@
1111
# In contrast, arrays have constant time operations to access
1212
# elements in an array.
1313

14-
class DoublyLinkedList(object):
14+
class DoublyLinkedListNode(object):
1515
def __init__(self, value):
1616
self.value = value
1717
self.next = None
1818
self.prev = None
1919

2020

21-
class SinglyLinkedList(object):
21+
class SinglyLinkedListNode(object):
2222
def __init__(self, value):
2323
self.value = value
2424
self.next = None

‎linkedlist/printKthToLast.py‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
class Node():
2+
def __init__(self, val = None):
3+
self.val = val
4+
self.next = None
5+
6+
def printKthToLast(head):
7+
"""
8+
Time Complexity: O()
9+
Space Complexity: O()
10+
"""
11+
pass
12+
13+
def printLinkedList(head):
14+
string = ""
15+
while head.next:
16+
string += head.val + " -> "
17+
head = head.next
18+
string += head.val
19+
print(string)
20+
21+
# A A B C D C F G
22+
23+
a1 = Node("A")
24+
a2 = Node("A")
25+
b = Node("B")
26+
c1 = Node("C")
27+
d = Node("D")
28+
c2 = Node("C")
29+
f = Node("F")
30+
g = Node("G")
31+
32+
a1.next = a2
33+
a2.next = b
34+
b.next = c1
35+
c1.next = d
36+
d.next = c2
37+
c2.next = f
38+
f.next = g
39+
40+
# removeDups(a1)
41+
# printLinkedList(a1)
42+
# removeDupsWithoutSet(a1)
43+
# printLinkedList(a1)
44+

‎linkedlist/removeDups.py‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
class Node():
2+
def __init__(self, val = None):
3+
self.val = val
4+
self.next = None
5+
6+
def removeDups(head):
7+
"""
8+
Time Complexity: O(N)
9+
Space Complexity: O(N)
10+
"""
11+
hashset = set()
12+
prev = Node()
13+
while head:
14+
if head.val in hashset:
15+
prev.next = head.next
16+
else:
17+
hashset.add(head.val)
18+
prev = head
19+
head = head.next
20+
21+
def removeDupsWithoutSet(head):
22+
"""
23+
Time Complexity: O(N^2)
24+
Space Complexity: O(1)
25+
"""
26+
current = head
27+
while current:
28+
runner = current
29+
while runner.next:
30+
if runner.next.val == current.val:
31+
runner.next = runner.next.next
32+
else:
33+
runner = runner.next
34+
current = current.next
35+
36+
def printLinkedList(head):
37+
string = ""
38+
while head.next:
39+
string += head.val + " -> "
40+
head = head.next
41+
string += head.val
42+
print(string)
43+
44+
# A A B C D C F G
45+
46+
a1 = Node("A")
47+
a2 = Node("A")
48+
b = Node("B")
49+
c1 = Node("C")
50+
d = Node("D")
51+
c2 = Node("C")
52+
f = Node("F")
53+
g = Node("G")
54+
55+
a1.next = a2
56+
a2.next = b
57+
b.next = c1
58+
c1.next = d
59+
d.next = c2
60+
c2.next = f
61+
f.next = g
62+
63+
removeDups(a1)
64+
printLinkedList(a1)
65+
removeDupsWithoutSet(a1)
66+
printLinkedList(a1)
67+

‎queue/queue.py‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -57,10 +57,10 @@ def expand(self):
5757
expands size of the array.
5858
Time Complexity: O(n)
5959
"""
60-
newArray = [None] * len(self.array) * 2 # double the size of the array
60+
new_array = [None] * len(self.array) * 2 # double the size of the array
6161
for i, element in enumerate(self.array):
62-
newArray[i] = element
63-
self.array = newArray
62+
new_array[i] = element
63+
self.array = new_array
6464

6565
def __iter__(self):
6666
probe = self.top - 1

‎search/binarySearch.py‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
def binarySearch(array, query):
1+
def binary_search(array, query):
22
lo, hi = 0, len(array) - 1
33
while lo <= hi:
44
print("--------")
@@ -18,11 +18,11 @@ def binarySearch(array, query):
1818
array = [1,2,3,3,3,3,4,4,4,4,5,6]
1919
print(array)
2020
print("-----SEARCH-----")
21-
print("found: ", 5, " in index:" , binarySearch(array, 5))
21+
print("found: ", 5, " in index:" , binary_search(array, 5))
2222
print("-----SEARCH-----")
23-
print("found: ", 6, " in index:" , binarySearch(array, 6))
23+
print("found: ", 6, " in index:" , binary_search(array, 6))
2424
print("-----SEARCH-----")
25-
print("found: ", 7, " in index:" , binarySearch(array, 7))
25+
print("found: ", 7, " in index:" , binary_search(array, 7))
2626
print("-----SEARCH-----")
27-
print("found: ", -1, " in index:" , binarySearch(array, -1))
27+
print("found: ", -1, " in index:" , binary_search(array, -1))
2828
print("-----SEARCH-----")

‎search/countElem.py‎

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
1-
def countElem(array, query):
2-
def firstOccurance(array, query):
1+
def count_elem(array, query):
2+
def first_occurance(array, query):
33
lo, hi = 0, len(array) -1
44
while lo <= hi:
55
mid = lo + (hi - lo) // 2
@@ -10,7 +10,7 @@ def firstOccurance(array, query):
1010
lo = mid + 1
1111
else:
1212
hi = mid - 1
13-
def lastOccurance(array, query):
13+
def last_occurance(array, query):
1414
lo, hi = 0, len(array) -1
1515
while lo <= hi:
1616
mid = lo + (hi - lo) // 2
@@ -22,8 +22,8 @@ def lastOccurance(array, query):
2222
else:
2323
hi = mid - 1
2424

25-
first = firstOccurance(array, query)
26-
last = lastOccurance(array, query)
25+
first = first_occurance(array, query)
26+
last = last_occurance(array, query)
2727
if first is None or last is None:
2828
return None
2929
return last - first + 1
@@ -34,19 +34,19 @@ def lastOccurance(array, query):
3434
print(array)
3535
print("-----COUNT-----")
3636
query = 3
37-
print("count: ", query, " :" , countElem(array, query))
37+
print("count: ", query, " :" , count_elem(array, query))
3838
print("-----COUNT-----")
3939
query = 5
40-
print("count: ", query, " :" , countElem(array, query))
40+
print("count: ", query, " :" , count_elem(array, query))
4141
print("-----COUNT-----")
4242
query = 7
43-
print("count: ", query, " :" , countElem(array, query))
43+
print("count: ", query, " :" , count_elem(array, query))
4444
print("-----COUNT-----")
4545
query = 1
46-
print("count: ", query, " :" , countElem(array, query))
46+
print("count: ", query, " :" , count_elem(array, query))
4747
print("-----COUNT-----")
4848
query = -1
49-
print("count: ", query, " :" , countElem(array, query))
49+
print("count: ", query, " :" , count_elem(array, query))
5050
print("-----COUNT-----")
5151
query = 9
52-
print("count: ", query, " :" , countElem(array, query))
52+
print("count: ", query, " :" , count_elem(array, query))

‎sorting/insertion_sort.py‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
def insertion_sort(arr):
2+
""" Insertion Sort
3+
Complexity: O(n^2)
4+
"""
5+
for i in xrange(len(arr)):
6+
cursor = arr[i]
7+
pos = i
8+
while pos > 0 and arr[pos-1] > cursor:
9+
# Swap the number down the list
10+
arr[pos] = arr[pos-1]
11+
pos = pos-1
12+
# Break and do the final swap
13+
arr[pos] = cursor
14+
return arr

‎sorting/merge_sort.py‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2+
3+
def merge_sort(arr):
4+
""" Merge Sort
5+
Complexity: O(n log(n))
6+
"""
7+
size = len(arr)
8+
half = size/2
9+
# Our recursive base case
10+
if size <= 1:
11+
return arr
12+
# Perform merge_sort recursively on both halves
13+
left, right = merge_sort(arr[half:]), merge_sort(arr[:half])
14+
15+
# Merge each side together
16+
return merge(left, right)
17+
18+
def merge(left, right):
19+
""" Merge helper
20+
Complexity: O(n)
21+
"""
22+
arr = []
23+
left_cursor, right_cursor = 0,0
24+
while left_cursor < len(left) and right_cursor < len(right):
25+
# Sort each one and place into the result
26+
if left[left_cursor] <= right[right_cursor]:
27+
arr.append(left[left_cursor])
28+
left_cursor+=1
29+
else:
30+
arr.append(right[right_cursor])
31+
right_cursor+=1
32+
# Add the left overs if there's any left to the result
33+
if left:
34+
arr.extend(left[left_cursor:])
35+
if right:
36+
arr.extend(right[right_cursor:])
37+
return arr
38+

0 commit comments

Comments
 (0)