Skip to content

Commit 6d2f350

Browse files
author
Мето Трајковски
committed
Added 3 new geometry solutions and 1 DP
1 parent 3d3e728 commit 6d2f350

5 files changed

Lines changed: 248 additions & 9 deletions

File tree

‎Dynamic Programming/create_palindrom.py‎

Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
'''
2+
Create Palindrome (Minimum Insertions to Form a Palindrome)
3+
4+
Given a string, find the palindrome that can be made by inserting the fewest number of characters as possible anywhere in the word.
5+
If there is more than one palindrome of minimum length that can be made, return the lexicographically earliest one (the first one alphabetically).
6+
7+
Input: 'race'
8+
Output: 'ecarace'
9+
Output explanation: Since we can add three letters to it (which is the smallest amount to make a palindrome).
10+
There are seven other palindromes that can be made from "race" by adding three letters, but "ecarace" comes first alphabetically.
11+
12+
Input: 'google'
13+
Output: 'elgoogle'
14+
15+
Input: 'abcda'
16+
Output: 'adcbcda'
17+
Output explanation: Number of insertions required is 2 - aDCbcda (between the first and second character).
18+
19+
Input: 'adefgfdcba'
20+
Output: 'abcdefgfedcba'
21+
Output explanation: Number of insertions required is 3 i.e. aBCdefgfEdcba.
22+
23+
=========================================
24+
Recursive count how many insertions are needed, very slow and inefficient.
25+
Time Complexity: O(2^N)
26+
Space Complexity: O(N^2) , for each function call a new string is created (and the recursion can have depth of max N calls)
27+
Dynamic programming. Count intersections looking in 3 direction in the dp table (diagonally left-up or min(left, up)).
28+
Time Complexity: O(N^2)
29+
Space Complexity: O(N^2)
30+
'''
31+
32+
33+
##############
34+
# Solution 1 #
35+
##############
36+
37+
def create_palindrome_1(word):
38+
n = len(word)
39+
40+
# base cases
41+
if n == 1:
42+
return word
43+
if n == 2:
44+
if word[0] != word[1]:
45+
word += word[0] # make a palindrom
46+
return word
47+
48+
# check if the first and last chars are same
49+
if word[0] == word[-1]:
50+
# add first and last chars
51+
return word[0] + create_palindrome_1(word[1:-1]) + word[-1]
52+
53+
# if not remove the first and after that the last char
54+
# and find which result has less chars
55+
first = create_palindrome_1(word[1:])
56+
first = word[0] + first + word[0] # add first char twice
57+
58+
last = create_palindrome_1(word[:-1])
59+
last = word[-1] + last + word[-1] # add last char twice
60+
61+
if len(first) < len(last):
62+
return first
63+
return last
64+
65+
66+
##############
67+
# Solution 2 #
68+
##############
69+
70+
import math
71+
72+
def create_palindrome_2(word):
73+
n = len(word)
74+
dp = [[0 for j in range(n)] for i in range(n)]
75+
76+
# run dp
77+
for gap in range(1, n):
78+
left = 0
79+
for right in range(gap, n):
80+
if word[left] == word[right]:
81+
dp[left][right] = dp[left + 1][right - 1]
82+
else:
83+
dp[left][right] = min(dp[left][right - 1], dp[left + 1][right]) + 1
84+
left += 1
85+
86+
# build the palindrome using the dp table
87+
return build_palindrome(word, dp, 0, n-1)
88+
89+
def build_palindrome(word, dp, left, right):
90+
# similar like the first solution, but without exponentialy branching
91+
# this is linear time, we already know the inserting values
92+
if left > right:
93+
return ''
94+
if left == right:
95+
return word[left]
96+
97+
if word[left] == word[right]:
98+
return word[left] + build_palindrome(word, dp, left + 1, right - 1) + word[left]
99+
100+
if dp[left + 1][right] < dp[left][right - 1]:
101+
return word[left] + build_palindrome(word, dp, left + 1, right) + word[left]
102+
103+
return word[right] + build_palindrome(word, dp, left, right - 1) + word[right]
104+
105+
106+
###########
107+
# Testing #
108+
###########
109+
110+
# Test 1
111+
# Correct result => 'ecarace'
112+
word = 'race'
113+
print(create_palindrome_1(word))
114+
print(create_palindrome_2(word))
115+
116+
# Test 2
117+
# Correct result => 'elgoogle'
118+
word = 'google'
119+
print(create_palindrome_1(word))
120+
print(create_palindrome_2(word))
121+
122+
# Test 3
123+
# Correct result => 'adcbcda'
124+
word = 'abcda'
125+
print(create_palindrome_1(word))
126+
print(create_palindrome_2(word))
127+
128+
# Test 4
129+
# Correct result => 'abcdefgfedcba'
130+
word = 'adefgfdcba'
131+
print(create_palindrome_1(word))
132+
print(create_palindrome_2(word))

‎Math/calculate_area_of_polygon.py‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
'''
2+
Calculate Area of Polygon
3+
4+
Given ordered coordinates of a polygon with n vertices. Find area of the polygon.
5+
Here ordered mean that the coordinates are given either in clockwise manner or anticlockwise from first vertex to last.
6+
7+
Input: [(0, 0), (3, 0), (3, 2), (0, 2)]
8+
Output: 6.0
9+
Output explanation: The polygon is a 3x2 rectangle parallel with the X axis. The area is 6 (3*2).
10+
11+
=========================================
12+
Use Shoelace formula (https://en.wikipedia.org/wiki/Shoelace_formula).
13+
abs( 1/2 ((X1Y2 + X2Y3 + ... + Xn-1Yn + XnY1) - (X2Y1 + X3Y2 + ... + XnYn-1 + X1Yn)) )
14+
Time Complexity: O(N)
15+
Space Complexity: O(1)
16+
'''
17+
18+
19+
############
20+
# Solution #
21+
############
22+
23+
def calculate_area_of_polygon(polygon):
24+
n = len(polygon)
25+
prev = polygon[-1]
26+
area = 0
27+
28+
for curr in polygon:
29+
area += (prev[0] + curr[0]) * (prev[1] - curr[1])
30+
prev = curr
31+
32+
return abs(area / 2) # return absolute value
33+
34+
35+
###########
36+
# Testing #
37+
###########
38+
39+
# Test 1
40+
# Correct result => 6.0
41+
print(calculate_area_of_polygon([(0, 0), (3, 0), (3, 2), (0, 2)]))

‎Math/check_if_point_inside_polygon.py‎

Lines changed: 12 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,12 @@
11
'''
22
Check if Point is Inside Polygon
33
4-
Given a polygon (created by counterclockwise ordered points, more than 2 points) and a point "p", find if "p" lies inside the polygon or not.
4+
Given a polygon (created by counterclockwise ordered points, more than 2 points) and a point "p", find if "p" lies inside the polygon or not.
55
The points lying on the border are considered inside.
66
77
Input: [(0, 0), (3, 0), (3, 2), (0, 2)], (1, 1)
88
Output: True
9-
Output explanation: In this example the polygon is a rectangle parallel with the X axis.
9+
Output explanation: The polygon is a 3x2 rectangle parallel with the X axis.
1010
1111
=========================================
1212
To check if a point is inside a polygon you'll need to draw a straight line (in any of the 4 directions: up, right, down, left),
@@ -23,22 +23,22 @@
2323

2424
def check_if_point_inside_polygon(polygon, p):
2525
n = len(polygon)
26-
# add the first point as last to avoid checking, using modulo (polygon[(i + 1) % n]) or duplicate code for the last point
27-
polygon.append(polygon[0])
26+
prev = polygon[-1]
2827
is_inside = False # or you can use counter and return (counter % 2) == 1
2928

30-
for i in range(n):
31-
if intersect(polygon[i], polygon[i + 1], p):
29+
for curr in polygon:
30+
if intersect(prev, curr, p):
3231
is_inside = not is_inside
32+
prev = curr
3333

3434
return is_inside
3535

3636
def intersect(a, b, p):
3737
# Y coordinate of p should be between Y coordinates
3838
# this can be written like (a[1] > p[1]) != (b[1] > p[1])
3939
if p[1] < max(a[1], b[1]) and p[1] >= min(a[1], b[1]):
40-
'''
41-
Equation of line:
40+
'''
41+
Equation of line:
4242
y = (x - x0) * ((y1 - y0) / (x1 - x0)) + y0
4343
This formula is computed using the gradients (slopes, changes in the coordinates)
4444
Modify this formula to find X instead Y (because you already have Y)
@@ -65,6 +65,10 @@ def intersect(a, b, p):
6565
# Correct result => True
6666
print(check_if_point_inside_polygon([(0, 0), (3, 0), (3, 2), (0, 2)], (3, 1)))
6767

68+
# Test 3
69+
# Correct result => True
70+
print(check_if_point_inside_polygon([(0, 0), (3, 0), (3, 2), (0, 2)], (3, 0)))
71+
6872
# Test 3
6973
# Correct result => False
7074
print(check_if_point_inside_polygon([(0, 0), (3, 0), (3, 2), (0, 2)], (3, 3)))

‎Math/check_if_two_rectangles_overlap.py‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
'''
2+
Check if Two Rectangles Overlap
3+
4+
Given two rectangles, find if the given two rectangles overlap or not.
5+
Note that a rectangle can be represented by two coordinates, top left and bottom right.
6+
So mainly we are given following four coordinates (min X and Y and max X and Y).
7+
- l1: Bottom Left coordinate of first rectangle. (mins)
8+
- r1: Top Right coordinate of first rectangle. (maxs)
9+
- l2: Bottom Left coordinate of second rectangle. (mins)
10+
- r2: Top Right coordinate of second rectangle. (maxs)
11+
It may be assumed that the rectangles are PARALLEL to the coordinate axis.
12+
13+
Input: (0, 0), (3, 2), (1, 1), (5, 4)
14+
Output: True
15+
16+
=========================================
17+
First check if rectangles are overlapping on X axis and
18+
after that if they are overlapping on Y axis.
19+
Time Complexity: O(1)
20+
Space Complexity: O(1)
21+
'''
22+
23+
24+
############
25+
# Solution #
26+
############
27+
28+
def check_if_two_rectangles_overlap(l1, r1, l2, r2):
29+
# first check by X coordinates, if rectangles can overlap on X axis
30+
# longer form (l1[0] < l2[0] and r1[0] < l2[0]) or (l1[0] > r2[0] and r1[0] > r2[0])
31+
# but we know that l1[0] is always smaller than r1[0]
32+
if (r1[0] < l2[0]) or (l1[0] > r2[0]):
33+
return False
34+
35+
# now we know that the rectangles are overlapping on X axis
36+
# check if they are overlapping on Y axis
37+
# (use the same logic from previous)
38+
if (r1[1] < l2[1]) or (l1[1] > r2[1]):
39+
return False
40+
41+
return True
42+
43+
44+
###########
45+
# Testing #
46+
###########
47+
48+
# Test 1
49+
# Correct result => True
50+
print(check_if_two_rectangles_overlap((0, 0), (3, 2), (1, 1), (5, 4)))
51+
52+
# Test 2
53+
# Correct result => True
54+
print(check_if_two_rectangles_overlap((0, 0), (3, 2), (3, 2), (5, 4)))
55+
56+
# Test 3
57+
# Correct result => True
58+
print(check_if_two_rectangles_overlap((0, 0), (3, 2), (1, -1), (5, 4)))
59+
60+
# Test 4
61+
# Correct result => False
62+
print(check_if_two_rectangles_overlap((0, 0), (3, 2), (2, 3), (5, 4)))

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -89,7 +89,7 @@ Each solution/problem in this repo belongs to one of these categories:
8989
3. [Trees](https://github.com/MTrajK/coding-problems/tree/master/Trees) - Binary Search Trees, Tree Traversals: Breadth-First (Level Order) Traversal, Depth-First Traversal (Inorder, Preorder, Postorder), etc.
9090
4. [Dynamic Programming](https://github.com/MTrajK/coding-problems/tree/master/Dynamic%20Programming) - 2D and 1D Dynamic Programming, LCS, LIS, Knapsack, etc.
9191
5. [Strings](https://github.com/MTrajK/coding-problems/tree/master/Strings) - String Manipulations, Reversing, Encodings/Decodings, etc.
92-
6. [Math](https://github.com/MTrajK/coding-problems/tree/master/Math) - GCD, LCM, Prime Factors, Math Formulas, etc.
92+
6. [Math](https://github.com/MTrajK/coding-problems/tree/master/Math) - GCD, LCM, Factorization, Geometry, Math Formulas, etc.
9393
7. [Other](https://github.com/MTrajK/coding-problems/tree/master/Other) - Backtracking, BFS, DFS, Queues, Stacks, Matrices, etc.
9494

9595

0 commit comments

Comments
 (0)