Skip to content

Commit 698ea30

Browse files
MTrajKMTrajK
committed
Updated one old, added 2 new coding problems and added new training site
1 parent 79cb8f0 commit 698ea30

File tree

4 files changed

+304
-3
lines changed

4 files changed

+304
-3
lines changed

‎Other/fancy_sequence.py‎

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
'''
2+
Fancy Sequence
3+
4+
Write an API that generates fancy sequences using the append, addAll, and multAll operations.
5+
6+
Implement the Fancy class:
7+
- Fancy() Initializes the object with an empty sequence.
8+
- void append(val) Appends an integer val to the end of the sequence.
9+
- void addAll(inc) Increments all existing values in the sequence by an integer inc.
10+
- void multAll(m) Multiplies all existing values in the sequence by an integer m.
11+
- int getIndex(idx) Gets the current value at index idx (0-indexed) of the sequence modulo 109 + 7. If the index is greater or equal than the length of the sequence, return -1.
12+
13+
Input: ["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
14+
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
15+
Output: [null, null, null, null, null, 10, null, null, null, 26, 34, 20]
16+
Output explanation:
17+
Fancy fancy = new Fancy();
18+
fancy.append(2); // fancy sequence: [2]
19+
fancy.addAll(3); // fancy sequence: [2+3] -> [5]
20+
fancy.append(7); // fancy sequence: [5, 7]
21+
fancy.multAll(2); // fancy sequence: [5*2, 7*2] -> [10, 14]
22+
fancy.getIndex(0); // return 10
23+
fancy.addAll(3); // fancy sequence: [10+3, 14+3] -> [13, 17]
24+
fancy.append(10); // fancy sequence: [13, 17, 10]
25+
fancy.multAll(2); // fancy sequence: [13*2, 17*2, 10*2] -> [26, 34, 20]
26+
fancy.getIndex(0); // return 26
27+
fancy.getIndex(1); // return 34
28+
fancy.getIndex(2); // return 20
29+
30+
=========================================
31+
The program is meant to be called many times (more than a million), and because of that, each operation should be constant time.
32+
When getIndex is called all we need to do is to take the first (getIndex index) adding+multiplying values and the last adding+multiplying values
33+
and using these 2 values do math and determine the real adding+multlplying values.
34+
When there is a new adding value, just increase the adding value with that one.
35+
When there is a new multiplying value, multiply the both adding and multiplying values.
36+
Example x=append(8): (((x + 5) + 6) + 7) * 2 = (x + 17) * 2 = x * 2 + 34
37+
So total multiplayer is 2.
38+
And total adder is 18 (from 36/2).
39+
The result is (8+18)*2 = 52.
40+
Example y=append(9) after addAll(6) operation:
41+
(y + 7) * 2 = y * 2 + 14
42+
The total multiplayer is the same, 2 (the previous is 1, the last is 2 that's equal to 2/1=2).
43+
But the total adder is 7, the total last adder is 18 (from 36/2) minus the previous 11 (from 5+6 with no multiplyers till that moment).
44+
The result is (9+7)*2 = 32.
45+
Time Complexity (The whole program, N operations): O(N)
46+
Time Complexity (Only one operation): O(1)
47+
Space Complexity: O(N)
48+
'''
49+
50+
############
51+
# Solution #
52+
############
53+
54+
class Fancy:
55+
def __init__(self):
56+
self.appending = []
57+
self.adding = []
58+
self.multiplying = []
59+
60+
61+
def append(self, val: int) -> None:
62+
self.appending.append(val)
63+
64+
if len(self.appending) > 1:
65+
self.adding.append(self.adding[-1])
66+
self.multiplying.append(self.multiplying[-1])
67+
else:
68+
self.adding.append(0)
69+
self.multiplying.append(1)
70+
71+
def addAll(self, inc: int) -> None:
72+
if len(self.appending) == 0:
73+
return
74+
75+
self.adding[-1] += inc
76+
77+
78+
def multAll(self, m: int) -> None:
79+
if len(self.appending) == 0:
80+
return
81+
82+
self.adding[-1] *= m
83+
self.multiplying[-1] *= m
84+
85+
86+
def getIndex(self, idx: int) -> int:
87+
length = len(self.appending)
88+
if idx >= length:
89+
return -1
90+
91+
prevAdding = 0
92+
prevMultiplying = 1
93+
if idx > 0:
94+
prevMultiplying = self.multiplying[idx-1]
95+
prevAdding = self.adding[idx-1]
96+
97+
currMultiplying = self.multiplying[-1] // prevMultiplying
98+
currAdding = self.adding[-1] - (prevAdding * currMultiplying)
99+
100+
return (self.appending[idx] * currMultiplying + currAdding) % 1000000007
101+
102+
103+
###########
104+
# Testing #
105+
###########
106+
107+
# Test 1
108+
fancy = Fancy()
109+
fancy.append(2) # fancy sequence: [2]
110+
fancy.addAll(3) # fancy sequence: [2+3] -> [5]
111+
fancy.append(7) # fancy sequence: [5, 7]
112+
fancy.multAll(2) # fancy sequence: [5*2, 7*2] -> [10, 14]
113+
print(fancy.getIndex(0)) # return 10
114+
fancy.addAll(3) # fancy sequence: [10+3, 14+3] -> [13, 17]
115+
fancy.append(10) # fancy sequence: [13, 17, 10]
116+
fancy.multAll(2) # fancy sequence: [13*2, 17*2, 10*2] -> [26, 34, 20]
117+
print(fancy.getIndex(0)) # return 26
118+
print(fancy.getIndex(1)) # return 34
119+
print(fancy.getIndex(2)) # return 20

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -196,6 +196,7 @@ If the problems from [LeetCode](https://leetcode.com/) are not enough and you ne
196196
- [Codewars](http://www.codewars.com/)
197197
- [Wolfram Challenges](https://challenges.wolfram.com/)
198198
- [Google's Coding Competitions](https://codingcompetitions.withgoogle.com/)
199+
- [Google Foobar](https://foobar.withgoogle.com/)
199200
- [Cyber-dojo](https://cyber-dojo.org/)
200201
- [CodingBat](http://codingbat.com/)
201202
- [CodeKata](http://codekata.com/)

‎Strings/strong_password_checker.py‎

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
'''
2+
Strong Password Checker
3+
4+
A password is considered strong if the below conditions are all met:
5+
- It has at least 6 characters and at most 20 characters.
6+
- It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
7+
- It does not contain three repeating characters in a row (i.e., "...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).
8+
- Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.
9+
10+
In one step, you can:
11+
- Insert one character to password,
12+
- Delete one character from password, or
13+
- Replace one character of password with another character.
14+
15+
Input: password = "a"
16+
Output: 5
17+
18+
Input: password = "aA1"
19+
Output: 3
20+
21+
Input: password = "1337C0d3"
22+
Output: 0
23+
24+
=========================================
25+
Explanation in some kind of pseudo code:
26+
if length < 6
27+
(3 different types characters, if all 5 are same, than 2 new separators should be added or 1 new added and 1 changed; or if all are the same type, 2 new types should be added, or 1 new and 1 changed)
28+
if length == 5 && (5 repeating or 1 char type)
29+
return 2
30+
return 6-length
31+
32+
if length > 20
33+
delete all till 20
34+
35+
*now you're in legnth > 5 && length <=20
36+
separate groups by changing a character (dividing all groups >=3 with 3)
37+
if char type 1 and changeChar here are <2
38+
changeChar += 2 - changeChar
39+
40+
return deletingChar + changeChar
41+
42+
first, make the string between 6 and 20 characters (when making this, separate/lower the groups bigger than 3)
43+
- when less than 6 characters Array.add((group+1)/2, 1, group/2) - ADDING CHARACTERS - or just use the upper logic when length < 3;
44+
- when more than 6 characters Array.add(group-1) - DELETING CHARACTERS, start from the one with groups bigger than 3, after that delete any)!!! Deleting priority 1. mod with 3 = 0 -> 2. mod with 3 = 1 -> 3. mod with 3 = 2
45+
46+
second, when the string is between 6 and 20 characters, change character in groups with same characters
47+
3 -> 1 operation (*** -> *|*) => 3/3 = 1
48+
4 -> 1 operation (**** -> **|*) => 4/3 = 1
49+
5 -> 1 operations (***** -> **|**) => 5/3 = 1
50+
6 -> 2 operations (****** -> **|*** -> **|**|) => 6/3 = 2
51+
7 -> 2 operations (******* -> **|**** -> **|**|*) => 7/3 = 2
52+
8 -> 2 operations (******** -> **|***** -> **|**|**) => 8/3 = 2
53+
9 -> 3 operations (********* -> **|****** -> **|**|**|) => 9/3 = 3
54+
Time Complexity: O(N)
55+
Space Complexity: O(N)
56+
'''
57+
58+
59+
############
60+
# Solution #
61+
############
62+
63+
def strongPasswordChecker(password):
64+
groups = []
65+
length = len(password)
66+
last = 0
67+
lower = upper = digit = 0
68+
69+
for curr in range(length):
70+
if password[curr].islower():
71+
lower = 1
72+
elif password[curr].isupper():
73+
upper = 1
74+
elif password[curr].isdigit():
75+
digit = 1
76+
77+
if password[last] != password[curr]:
78+
groups.append(curr - last);
79+
last = curr
80+
81+
groups.append(curr + 1 - last);
82+
lud = lower + upper + digit
83+
addSteps = 0
84+
85+
# adding: under 6 chars
86+
if length < 6:
87+
if length == 5 and groups[0] == 5:
88+
addSteps = 2 # add + change, or add + add - it's same
89+
else:
90+
addSteps = 6 - length
91+
92+
ludLeft = 3 - lud
93+
if addSteps < ludLeft:
94+
addSteps = ludLeft
95+
96+
return addSteps
97+
98+
# deleting: over 20 chars
99+
deleteSteps = 0
100+
groupsLength = len(groups)
101+
while length > 20:
102+
found = False
103+
104+
for priority in range(3):
105+
for gidx in range(groupsLength):
106+
if groups[gidx] > 2 and groups[gidx] % 3 == priority:
107+
groups[gidx] -= 1
108+
found = True
109+
break
110+
if found:
111+
break
112+
113+
if not found:
114+
lastGroupIdx = groupsLength - 1
115+
groups[lastGroupIdx] -= 1
116+
if groups[lastGroupIdx] == 0:
117+
groups.pop(lastGroupIdx)
118+
groupsLength -= 1
119+
120+
length -= 1
121+
deleteSteps += 1
122+
123+
# changing: between 6 and 20 chars
124+
changeSteps = 0
125+
126+
for gidx in range(groupsLength):
127+
changeSteps += groups[gidx] // 3
128+
129+
ludLeft = 3 - lud
130+
if changeSteps < ludLeft:
131+
changeSteps = ludLeft
132+
133+
return deleteSteps + changeSteps
134+
135+
136+
###########
137+
# Testing #
138+
###########
139+
140+
# Test 1
141+
# Correct result => 5
142+
print(strongPasswordChecker('a'))
143+
144+
# Test 2
145+
# Correct result => 3
146+
print(strongPasswordChecker('aA1'))
147+
148+
# Test 3
149+
# Correct result => 0
150+
print(strongPasswordChecker('1337C0d3'))

‎Strings/zigzag_conversion.py‎

Lines changed: 34 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -16,12 +16,15 @@
1616
Middle rows have 2 times more elements than the first and last row.
1717
Time Complexity: O(N)
1818
Space Complexity: O(N)
19+
Collect all parts in separate bucket, in the end merge these buckets.
20+
Time Complexity: O(N)
21+
Space Complexity: O(N)
1922
'''
2023

2124

22-
############
23-
# Solution #
24-
############
25+
##############
26+
# Solution 1 #
27+
##############
2528

2629
def convert(s, num_rows):
2730
if num_rows == 1:
@@ -48,14 +51,42 @@ def convert(s, num_rows):
4851
return res
4952

5053

54+
##############
55+
# Solution 2 #
56+
##############
57+
58+
def convert_2(word, numRows):
59+
numLetters = len(word)
60+
bucket = [""] * numRows
61+
fullCycle = 2 * (numRows - 1)
62+
if numRows == 1:
63+
fullCycle = 1
64+
65+
for pos in range(0, numLetters):
66+
posCycle = pos % fullCycle
67+
68+
if posCycle >= numRows:
69+
posCycle = fullCycle - posCycle
70+
71+
bucket[posCycle] += word[pos]
72+
73+
result = ""
74+
for part in bucket:
75+
result += part
76+
77+
return result
78+
79+
5180
###########
5281
# Testing #
5382
###########
5483

5584
# Test 1
5685
# Correct result => 'PAHNAPLSIIGYIR'
5786
print(convert('PAYPALISHIRING', 3))
87+
print(convert_2('PAYPALISHIRING', 3))
5888

5989
# Test 2
6090
# Correct result => 'PINALSIGYAHRPI'
6191
print(convert('PAYPALISHIRING', 4))
92+
print(convert_2('PAYPALISHIRING', 4))

0 commit comments

Comments
 (0)