Skip to content

Commit 1e70358

Browse files
rlishtabarlishtaba
committed
Adding intermidiate chages
1 parent a17c5d7 commit 1e70358

44 files changed

Lines changed: 2753 additions & 95 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎algorithmable.gemspec‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,4 +29,5 @@ Gem::Specification.new do |spec|
2929
spec.add_development_dependency 'cucumber', '~> 1.3'
3030
spec.add_development_dependency 'rspec_junit_formatter', '~> 0'
3131
spec.add_development_dependency 'yard', '~> 0.8'
32+
spec.add_development_dependency 'rbench'
3233
end

‎lib/algorithmable.rb‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@ module Algorithmable
1414
autoload :LevenshteinDistance, 'algorithmable/levenshtein_distance'
1515
autoload :Cups, 'algorithmable/cups'
1616
autoload :Cache, 'algorithmable/cache'
17+
autoload :UnionFind, 'algorithmable/union_find'
1718

1819
class << self
1920
def logger

‎lib/algorithmable/cache/primitive_max_heap.rb‎

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -10,11 +10,6 @@ def initialize(index = [])
1010
@index = index
1111
end
1212

13-
def pop
14-
key = @index.delete @index.last
15-
@storage.delete key
16-
end
17-
1813
def []=(key, value)
1914
swim key
2015
@storage[key] = value
@@ -26,6 +21,13 @@ def [](key)
2621
end
2722
end
2823

24+
def pop
25+
key = @index.delete @index.last
26+
@storage.delete key
27+
end
28+
29+
private
30+
2931
def swim(key)
3032
@index.delete(key)
3133
@index.unshift(key)

‎lib/algorithmable/cache/primitive_min_heap.rb‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -10,11 +10,6 @@ def initialize(index = [])
1010
@index = index
1111
end
1212

13-
def pop
14-
key = @index.delete @index.last
15-
@storage.delete key
16-
end
17-
1813
def []=(key, value)
1914
sink key
2015
@storage[key] = value
@@ -26,6 +21,11 @@ def [](key)
2621
end
2722
end
2823

24+
def pop
25+
key = @index.delete @index.last
26+
@storage.delete key
27+
end
28+
2929
private
3030

3131
def sink(key)

‎lib/algorithmable/cups.rb‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,5 +5,8 @@ module Cups
55
autoload :StacksAndQueues, 'algorithmable/cups/stacks_and_queues'
66
autoload :NestedListsProblem, 'algorithmable/cups/nested_lists_problem'
77
autoload :TwoSum, 'algorithmable/cups/two_sum'
8+
autoload :NumberOfOccurrencesInArray, 'algorithmable/cups/stacks_and_queues/number_of_occurrences_in_array'
9+
autoload :LongestCommonSubSequence, 'algorithmable/cups/longest_common_subsequence'
10+
autoload :RootCubeIssue, 'algorithmable/cups/root_cube_issue'
811
end
912
end

‎lib/algorithmable/cups/circular_dependencies.rb‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
module Algorithmable
2+
module Cups
3+
module CircularDependencies
4+
def lib_dependencies(item, dependencies)
5+
visited = []
6+
dfs(item, dependencies, visited) do |entry, dep|
7+
puts "circular dependency: #{entry} <=> #{dep}"
8+
end
9+
visited
10+
end
11+
12+
def dfs(item, dependencies, visited, &block)
13+
next_items = dependencies[item]
14+
return [] unless next_items
15+
visited << item
16+
17+
next_items.each do |dep|
18+
if visited.include? dep
19+
yield item, dep if block_given?
20+
next
21+
end
22+
dfs(dep, dependencies, visited, &block)
23+
end
24+
end
25+
end
26+
end
27+
end

‎lib/algorithmable/cups/longest_common_subsequence.rb‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
module Algorithmable
2+
module Cups
3+
class LongestCommonSubSequence
4+
#
5+
# @see https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
6+
#
7+
# >> a = "aaaaabbbb34354354345"
8+
# >> b = "abbb34aaabbbb"
9+
# >> find(a, b)
10+
# => "aaaabbbb"
11+
#
12+
def find(a, b)
13+
max_len = Array.new(a.size + 1, 0)
14+
max_len.map! { Array.new(b.size + 1, 0) }
15+
16+
(a.size - 1).downto(0) do |i|
17+
(b.size - 1).downto(0) do |j|
18+
if a[i] == b[j]
19+
max_len[i][j] = 1 + max_len[i + 1][j + 1]
20+
else
21+
max_len[i][j] = [max_len[i + 1][j], max_len[i][j + 1]].max
22+
end
23+
end
24+
end
25+
26+
res = ''
27+
i = 0
28+
j = 0
29+
while max_len[i][j] != 0 && i < a.size && j < b.size
30+
if a[i] == b[j]
31+
res << a[i]
32+
i += 1
33+
j += 1
34+
else
35+
if max_len[i][j] == max_len[i + 1][j]
36+
i += 1
37+
else
38+
j += 1
39+
end
40+
end
41+
end
42+
res
43+
end
44+
end
45+
end
46+
end

‎lib/algorithmable/cups/merge_two_arrays.rb‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
module Algorithmable
2+
module Cups
3+
# Given two lists of numbers in descending order, write a function that returns a single list sorted in the same order.
4+
# E.g.
5+
# list1: 4, 2, 1
6+
# list2: 7, 6, 5, 3
7+
# Result list should be: 7,6,5,4,3,2,1
8+
9+
# right = [4, 2, 1]
10+
# left = [7, 6, 5, 3]
11+
#
12+
# l1 = [1]
13+
# l2 = []
14+
15+
def merge_arrays(left, right)
16+
sorted = []
17+
18+
while !left.empty? && !right.empty?
19+
if left[0] >= right[0]
20+
sorted.push(left.shift)
21+
else
22+
sorted.push(right.shift)
23+
end
24+
end
25+
26+
sorted += left if right.empty?
27+
sorted += right if left.empty?
28+
sorted # [1]
29+
end
30+
end
31+
end

‎lib/algorithmable/cups/number_of_occurrences_in_array.rb‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
module Algorithmable
2+
module Cups
3+
module NumberOfOccurrencesInArray
4+
include Algorithmable::Searches
5+
6+
def linear_solve(collection, target)
7+
result = Hash.new 0
8+
collection.each do |item|
9+
result[item] += 1
10+
end
11+
result[target]
12+
end
13+
14+
def logarithmic(collection, target)
15+
i = find_first_one collection, 0, collection.size - 1, target
16+
j = find_last_one collection, i, collection.size - 1, target
17+
j - i + 1
18+
end
19+
20+
def find_first_one(collection, low, high, target)
21+
# if(high >= low)
22+
# {
23+
# int mid = (low + high)/2; /*low + (high - low)/2;*/
24+
# if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
25+
# return mid;
26+
# else if(x > arr[mid])
27+
# return first(arr, (mid + 1), high, x, n);
28+
# else
29+
# return first(arr, low, (mid -1), x, n);
30+
# }
31+
# return -1
32+
end
33+
34+
def find_last_one(collection, low, high, target)
35+
# if(high >= low)
36+
# {
37+
# int mid = (low + high)/2; /*low + (high - low)/2;*/
38+
# if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
39+
# return mid;
40+
# else if(x < arr[mid])
41+
# return last(arr, low, (mid -1), x, n);
42+
# else
43+
# return last(arr, (mid + 1), high, x, n);
44+
# }
45+
# return -1;
46+
end
47+
end
48+
end
49+
end

‎lib/algorithmable/cups/primitives.rb‎

Lines changed: 19 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -139,15 +139,15 @@ def parse_string_with_escapes(string)
139139
def parse_char(char, state)
140140
chunk_id = state[:chunk_id]
141141
case char
142-
when /[\(\{\[\)\}\]]/
143-
state[:escaping] = char != state[:prev_char]
144-
state[:chunks][chunk_id] << char unless state[:escaping]
145-
else
146-
if state[:escaping]
147-
chunk_id = state[:chunk_id] += 1
148-
state[:escaping] = false
149-
end
150-
state[:chunks][chunk_id] << char
142+
when /[\(\{\[\)\}\]]/
143+
state[:escaping] = char != state[:prev_char]
144+
state[:chunks][chunk_id] << char unless state[:escaping]
145+
else
146+
if state[:escaping]
147+
chunk_id = state[:chunk_id] += 1
148+
state[:escaping] = false
149+
end
150+
state[:chunks][chunk_id] << char
151151
end
152152
state[:prev_char] = char
153153
end
@@ -261,7 +261,7 @@ def find_common_chars_in_words(collection)
261261
end
262262

263263
map.select do |key, value|
264-
{key => value} if value == collection.size
264+
{ key => value } if value == collection.size
265265
end
266266
end
267267

@@ -282,17 +282,16 @@ def find_distance_between_words(dictionary, from, to)
282282
distance = -1
283283

284284
dictionary.each_with_index do |word, index|
285-
if [from, to].include? word
286-
temp = word == from
287-
to = temp ? to : from
285+
next unless [from, to].include? word
286+
temp = word == from
287+
to = temp ? to : from
288+
distance += 1
289+
290+
i = index
291+
while i < dict_size - 1 && dictionary[i] != to
292+
i += 1
288293
distance += 1
289-
290-
i = index
291-
while i < dict_size - 1 && dictionary[i] != to
292-
i += 1
293-
distance += 1
294-
return distance if dictionary[i] == to
295-
end
294+
return distance if dictionary[i] == to
296295
end
297296
end
298297
distance

0 commit comments

Comments
 (0)