Skip to content

Instantly share code, notes, and snippets.

Avatar
💭
Quality is remembered long after the price is forgotten (Sir Frederick Royce)

Maksim Sokolnikov Bablzz

💭
Quality is remembered long after the price is forgotten (Sir Frederick Royce)
View GitHub Profile
View merge_sort.go
/*
best time O(n log2 n)
worst time O(n log2 n)
*/
package main
import (
"fmt"
)
View bubble_sort.go
package main
// worst n^2
// best n
import (
"fmt"
)
func main() {
arr := []int{2,5,4,-8,9,1}
@Bablzz
Bablzz / countsort.rb
Last active Oct 21, 2019
Counting sort
View countsort.rb
=begin
O(n + k)
=end
def countSort arr
countArr = []
resultArr = Array.new(arr.length)
max = arr.max
@Bablzz
Bablzz / Fib.rb
Created Jul 10, 2019
Fibonacci recursion and non recursion
View Fib.rb
def fib_rec (number)
if number == 0
return number
elsif (number == 1) || (number == 2)
return 1
end
fib_rec(number - 1) + fib_rec(number - 2)
end
def fib_non_rec (number)
@Bablzz
Bablzz / greedy.rb
Last active Jul 9, 2019
Greedy algorithm
View greedy.rb
# Set cover problem
states = ['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az'].uniq
station = {}
station["kone"] = ['id', 'nv', 'ut'].uniq
station["ktwo"] = ['mt', 'wa', 'id'].uniq
station["kthree"] = ['or', 'nv', 'ca'].uniq
station["kfour"] = ['nv', 'ut'].uniq
station["kfive"] = ['ca', 'az'].uniq
@Bablzz
Bablzz / Luhn.rb
Last active Jul 3, 2019
Luhn algorithm
View Luhn.rb
def sum_digits digit
if digit < 10
digit
else
(digit % 10) + (digit / 10).to_f
end
end
def validate number
number = number.to_s.reverse.to_i
@Bablzz
Bablzz / fibonacci.rb
Last active Sep 18, 2019
Fibonacci Binet
View fibonacci.rb
fib = 9
def BinetFib number
phi = ((1 + Math.sqrt(5)) / 2) #or 1.6180339887
divid = phi**number
divider = Math.sqrt(5)
(divid / divider).round
end
puts BinetFib(fib);
@Bablzz
Bablzz / dijkstra.rb
Created Jul 1, 2019
dijkstra's_algorithm
View dijkstra.rb
graph = {}
graph['start'] = Hash.new
graph['start']['a'] = 6
graph['start']['b'] = 2
graph['a'] = Hash.new
graph['a']['fin'] = 1
graph['b'] = Hash.new
graph['b']['a'] = 3
graph['b']['fin'] = 5
@Bablzz
Bablzz / Queue_bfs.rb
Last active Oct 13, 2020
breadth-first search, BFS
View Queue_bfs.rb
# O(|V|+|E|)
graph = Hash.new
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
@Bablzz
Bablzz / quicksort.rb
Last active Oct 21, 2019
quicksort in ruby
View quicksort.rb
=begin
Worst time: O(n2) if choose bad pivot element
Approximate time: O(n log n)
=end
def quicksort array
if array.length < 2
array
else
pivot = array[rand(array.length)]