Skip to content

Commit 0b7b7ed

Browse files
author
Мето Трајковски
committed
Added 5 new solutions
1 parent 98c9338 commit 0b7b7ed

5 files changed

Lines changed: 348 additions & 0 deletions

File tree

‎Linked Lists/max_difference_subll.py‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
'''
2+
Maximum Difference Sub-Linked List
3+
4+
Given a linked list of integers, find and return the sub-linked list of ​k consecutive elements where
5+
the difference between the smallest element and the largest element is the largest possible.
6+
If there are several sub-linked lists of ​k elements in ​items so that all these sub-linked list have
7+
the same largest possible difference, return the sub-linked list that occurs first.
8+
9+
Input: 42 -> 17 -> 99 -> 12 -> 65 -> 77 -> 11 -> 26, 5
10+
Output: 99 -> 12 -> 65 -> 77 -> 11
11+
12+
=========================================
13+
Using 2 pointers (start and end), traverse the linked list and compare the results.
14+
But first, move the end pointer for k places.
15+
Time Complexity: O(N)
16+
Space Complexity: O(1)
17+
'''
18+
19+
20+
############
21+
# Solution #
22+
############
23+
24+
class ListNode:
25+
def __init__(self, x, n = None):
26+
self.val = x
27+
self.next = n
28+
29+
def max_diference_subll(ll, k):
30+
if ll is None:
31+
return None
32+
33+
start, end = ll, ll
34+
35+
# move the end pointer for k-1 places
36+
for i in range(1, k):
37+
end = end.next
38+
if end is None:
39+
return None
40+
41+
result_start, result_end = start, end
42+
43+
while end is not None:
44+
# compare the result with the current sub-linked list
45+
if abs(result_start.val - result_end.val) < abs(start.val - end.val):
46+
result_start, result_end = start, end
47+
48+
# move the both pointers
49+
start = start.next
50+
end = end.next
51+
52+
# cut the original linked list
53+
result_end.next = None
54+
return result_start
55+
56+
57+
###########
58+
# Testing #
59+
###########
60+
61+
# Test 1
62+
# Correct result => 99 -> 12 -> 65 -> 77 -> 11
63+
result = max_diference_subll(ListNode(42, ListNode(17, ListNode(99, ListNode(12, ListNode(65, ListNode(77, ListNode(11, ListNode(26)))))))), 5)
64+
while result != None:
65+
print(result.val)
66+
result = result.next
67+
68+
# Test 2
69+
# Correct result => 14 -> 58 -> 11 -> 63 -> 77
70+
result = max_diference_subll(ListNode(36, ListNode(14, ListNode(58, ListNode(11, ListNode(63, ListNode(77, ListNode(46, ListNode(32, ListNode(87))))))))), 5)
71+
while result != None:
72+
print(result.val)
73+
result = result.next

‎Lists/find_el_smaller_left_bigger_right.py‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
'''
2+
Find the element before which all the elements are smaller than it, and after which all are greater
3+
4+
Given an array, find an element before which all elements are smaller than it, and after which all are greater than it.
5+
Return the index of the element if there is such an element, otherwise, return -1.
6+
7+
Input: [5, 1, 4, 3, 6, 8, 10, 7, 9]
8+
Output: 4
9+
10+
=========================================
11+
Traverse the array starting from left and find all max elements till that element.
12+
Also traverse the array starting from right and find all min elements till that element.
13+
In the end only compare mins and maxs with the curent element.
14+
Time Complexity: O(N)
15+
Space Complexity: O(N)
16+
'''
17+
18+
19+
############
20+
# Solution #
21+
############
22+
23+
import math
24+
25+
def find_element_smaller_left_bigger_right(arr):
26+
n = len(arr)
27+
left_maxs = [-math.inf]
28+
right_min = math.inf
29+
30+
# find all mins from the front
31+
for i in range(n - 1):
32+
left_maxs.append(max(left_maxs[-1], arr[i]))
33+
34+
for i in range(n - 1, -1, -1):
35+
# check if all left are smaller
36+
# and all right are bigger
37+
if (left_maxs[i] < arr[i]) and (right_min > arr[i]):
38+
return i
39+
40+
# don't need a separate for loop for this as mins
41+
right_min = min(right_min, arr[i])
42+
43+
return -1
44+
45+
46+
###########
47+
# Testing #
48+
###########
49+
50+
# Test 1
51+
# Correct result => 4
52+
print(find_element_smaller_left_bigger_right([5, 1, 4, 3, 6, 8, 10, 7, 9]))
53+
54+
# Test 2
55+
# Correct result => -1
56+
print(find_element_smaller_left_bigger_right([5, 1, 4, 4]))

‎Other/postfix_evaluate.py‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
'''
2+
Postfix Evaluate
3+
4+
When arithmetic expressions are given in the familiar infix notation 2 + 3 * 4, we need to use
5+
parentheses to force a different evaluation order than the usual ​PEMDAS order determined by
6+
precedence and ​associativity ​. Writing arithmetic expressions in ​postfix notation (also known as
7+
Reverse Polish Notation ​) may look strange to us humans accustomed to the conventional ​infix
8+
notation, but is computationally much easier to handle, since postfix notation allows any evaluation
9+
order to be expressed without using any parentheses at all! A postfix expression is given as a list of
10+
items that can be either individual integers or one of the strings ​'+' ​, ​'-' ​, ​'*' and ​'/' for the four
11+
possible arithmetic operators. Calculate the result of the postfix expression.
12+
13+
Input: [2, 3, '+', 4, '*']
14+
Output: 20
15+
Output explanation: (2+3) * 4
16+
17+
Input: [1, 2, 3, 4, 5, 6, '*', '*', '*', '*', '*']
18+
Output: 720
19+
Output explanation: 1 * 2 * 3 * 4 * 5 * 6
20+
21+
=========================================
22+
Use stack, save all numbers into the stack.
23+
When a sign comes, pop the last 2 numbers from the stack, calculate their result and return the result into the stack.
24+
Time Complexity: O(N)
25+
Space Complexity: O(N)
26+
'''
27+
28+
29+
############
30+
# Solution #
31+
############
32+
33+
from collections import deque
34+
35+
def postfix_evaluate(items):
36+
stack = deque()
37+
# lambda functions for all 4 operations
38+
operations = {
39+
'+': (lambda a, b: a + b),
40+
'-': (lambda a, b: a - b),
41+
'*': (lambda a, b: a * b),
42+
'/': (lambda a, b: 0 if (b == 0) else (a // b))
43+
}
44+
45+
for item in items:
46+
# check if the item is a sign or a number
47+
if item in operations:
48+
b = stack.pop()
49+
a = stack.pop()
50+
51+
result = operations[item](a, b)
52+
53+
stack.append(result)
54+
else:
55+
stack.append(item)
56+
57+
return stack.pop()
58+
59+
60+
###########
61+
# Testing #
62+
###########
63+
64+
# Test 1
65+
# Correct result => 20
66+
print(postfix_evaluate([2, 3, '+', 4, '*']))
67+
68+
# Test 2
69+
# Correct result => 14
70+
print(postfix_evaluate([2, 3, 4, '*', '+']))
71+
72+
# Test 3
73+
# Correct result => 0
74+
print(postfix_evaluate([3, 3, 3, '-', '/']))
75+
76+
# Test 4
77+
# Correct result => 2
78+
print(postfix_evaluate([7, 3, '/']))
79+
80+
# Test 5
81+
# Correct result => 720
82+
print(postfix_evaluate([1, 2, 3, 4, 5, 6, '*', '*', '*', '*', '*']))

‎Other/safe_squares_rooks.py‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
'''
2+
Safe Squares from Rooks
3+
4+
On a generalized ​n-by-​n chessboard, there are some number of ​rooks ​, each rook represented as a
5+
two-tuple ​(row, column) of the row and the column that it is in. (The rows and columns are
6+
numbered from 0 to ​n-1.) A chess rook covers all squares that are in the same row or in the same
7+
column as that rook. Given the board size ​n and the list of ​rooks on that board, count the number of
8+
empty squares that are safe, that is, are not covered by any rook.
9+
10+
Input: [(1, 1), (3, 5), (7, 0), (7, 6)], 8
11+
Output: 20
12+
13+
=========================================
14+
The result is a multiplication between free rows and free columns.
15+
Use hashsets to store the free rows and columns.
16+
Time Complexity: O(N)
17+
Space Complexity: O(N)
18+
'''
19+
20+
21+
############
22+
# Solution #
23+
############
24+
25+
def safe_squares_rooks(rooks, n):
26+
rows = set()
27+
cols = set()
28+
29+
for i in range(n):
30+
rows.add(i)
31+
cols.add(i)
32+
33+
for rook in rooks:
34+
if rook[0] in rows:
35+
rows.remove(rook[0])
36+
if rook[1] in cols:
37+
cols.remove(rook[1])
38+
39+
return len(rows) * len(cols)
40+
41+
42+
###########
43+
# Testsing #
44+
###########
45+
46+
# safe_squares_rooks 1
47+
# Correct result => 1
48+
print(safe_squares_rooks([(1, 1)], 2))
49+
50+
# safe_squares_rooks 2
51+
# Correct result => 4
52+
print(safe_squares_rooks([(2, 3), (0, 1)], 4))
53+
54+
# safe_squares_rooks 3
55+
# Correct result => 20
56+
print(safe_squares_rooks([(1, 1), (3, 5), (7, 0), (7, 6)], 8))
57+
58+
# safe_squares_rooks 4
59+
# Correct result => 0
60+
print(safe_squares_rooks([(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)], 6))

‎Strings/reverse_vowels.py‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
'''
2+
Reverse Vowels
3+
4+
Given a ​text string, create and return a new string constructed by finding all its ​vowels (for
5+
simplicity, in this problem vowels are the letters in the string ​'aeiouAEIOU' ​) and reversing their
6+
order, while keeping all non-vowel characters exactly as they were in their original positions.
7+
8+
Input: 'Hello world'
9+
Output: 'Hollo werld'
10+
11+
=========================================
12+
Simple solution, find a vowel from left and swap it with a vowel from right.
13+
In Python, the string manipulation operations are too slow (string is immutable), because of that we need to convert the string into array.
14+
In C/C++, the Space complexity will be O(1).
15+
Time Complexity: O(N)
16+
Space Complexity: O(N)
17+
'''
18+
19+
20+
############
21+
# Solution #
22+
############
23+
24+
def reverse_vowels(sentence):
25+
arr = [c for c in sentence]
26+
27+
vowels = {
28+
'a': True, 'A': True,
29+
'e': True, 'E': True,
30+
'i': True, 'I': True,
31+
'o': True, 'O': True,
32+
'u': True, 'U': True
33+
}
34+
35+
left = 0
36+
right = len(arr) - 1
37+
38+
while True:
39+
# find a vowel from left
40+
while left < right:
41+
if arr[left] in vowels:
42+
break
43+
left += 1
44+
45+
# find a vowel from right
46+
while left < right:
47+
if arr[right] in vowels:
48+
break
49+
right -= 1
50+
51+
if left >= right:
52+
# in this case, there are only 1 or 0 vowels
53+
# so this is the end of the algorithm, no need from more reversing
54+
break
55+
56+
# swap the vowels
57+
temp = arr[left]
58+
arr[left] = arr[right]
59+
arr[right] = temp
60+
61+
left += 1
62+
right -= 1
63+
64+
return ''.join(arr)
65+
66+
67+
###########
68+
# Testing #
69+
###########
70+
71+
# Test 1
72+
# Correct result => 'ubcdofghijklmnepqrstavwxyz'
73+
print(reverse_vowels('abcdefghijklmnopqrstuvwxyz'))
74+
75+
# Test 2
76+
# Correct result => 'Hollo werld'
77+
print(reverse_vowels('Hello world'))

0 commit comments

Comments
 (0)