1 Install
2 Links
3 Just enough ruby
4 Example code
5 Complexity
6 Counting of elements
7 Prefix sums
8 Counting sort O(n+m)
9 Merge sort O(n*log(n))
10 Prime Numbers
11 Euclidean algorithm
12 Geometry
13 Math
14 Tutorial
15 Constrains

Install

Install vim plugin seeing-is-believing and write Gemfile

# Gemfile
source 'https://rubygems.org'

ruby '2.2.3'

# for instant output of commands
gem 'seeing_is_believing'

# irbtools includes interactive_editor (vim inside irb)
# just create ~/.irbrc with
# require 'rubygems'
# require 'irbtools'
gem 'irbtools'

# debugging
gem 'byebug'

# simple test assertions
gem 'minitest'

Just enough ruby

read from STDIN or from a file if you run with ruby script.rb my_data
```
n = gets.to_i
array = gets.strip.split(' ').map(&:to_i)
```

write to a file

File.open "my_file_name", 'w' do |file|
  file.puts "first line (no need for new line char \ n)"
  file << "second line \n"
  file.write "third line \n"
end

or in single line File.write '/path/to/file', 'My Text', mode: 'a'

To read one liner

file_content = File.read("/path/to/file")

division is integer division, so that 1/2 == 0 in ruby. You need to convert to float x = x.to_f
iterate range (1..10).each or 1.upto(10).each
exponent is 2**2 == 4

Example code

We can use pp standard library to print arrays just require 'pp'. But if you need to print matrix, than you can use ppp require './ppp'

# ppp.rb
def ppp(x)
  if x.class == Array
    puts_array(x)
  else
    puts x
  end
end

def puts_array(x)
  need_new_line = false
  x.each do |e|
    if e.class == Array
      puts e.join(', ')
    else
      print e.to_s + ', '
      need_new_line = true
    end
  end
  puts if need_new_line
end

Here is example for one solution that is submitted on site (it can not require byebug) so it use constant PRODUCTION. Test are in the same file. If the task is to read from file and to submit generated file, than use second template.

# 0_short_palindrome.rb
# https://www.hackerrank.com/challenges/short-palindrome
# string s of n lowecase letters s_i 0<=i<n
# (a, b, c, d)
# s_a = s_b chars at a and d are the same
# s_b = s_c
# constrains:
# 0<=a<b<c<d<n
# input: string s
# 1<= |s| < 10^6
# output: number of (a, b, c, d) tuples, use moduo 10^9 + 7
PRODUCTION = false
if PRODUCTION
  def ppp(_arg = nil); end

  def pp(_arg = nil); end
else
  require 'pp'
  require './ppp'
  require 'byebug'
end

# rubocop:disable Metrics/MethodLength
# rubocop:disable Metrics/AbcSize
def solution(a)
  r = a.length
  ppp "r=#{r}"
  r
end

if PRODUCTION
  n = gets.to_i
  a = []
  n.times do
    # strip is needed since on hackerrank, new line is at the end of gets
    r = gets.strip.split('').map { |c| c == '*' ? 0 : 1 }
    a << r
  end
  puts solution(a)
end # if PRODUCTION

require 'minitest/autorun'
class Test < Minitest::Test
  def test_sample
    s = 'kkkkkkz'
    expected = 12
    actual = solution(prepare(s))
    assert_equal expected, actual
  end

  def test_long
    s = %(***.*
**..*
***.*
*****
*****)
    assert_equal 12, solution(prepare(s))
  end

  def test_float
    asert_in_delta 0.5, solution(1,2) # default delta=0.001
  end

  def test_that_is_skipped
    skip "later"
  end

  private

  def prepare(s)
    s
  end
end

This template has separate test and actual code

# my_script.rb
# description of a problem
require 'pp'
require './ppp'
require 'byebug'

def solution(aa:, l:, h:)
end

# when we run: ruby my_script.rb data/example.in
# output is saved in data/example.out
if ARGV.length == 1
  file_name = ARGV.last.split('.').first
  r, _c, l, h = gets.split(' ').map(&:to_i)
  aa = []
  r.times do
    # strip is needed since on hackerrank, new line is at the end of gets
    aa << gets.strip.split('').map { |c| c == 'M' ? 1 : 0 }
  end
  results = solution(aa: aa, l: l, h: h)
  File.open "#{file_name}.out", 'w' do |file|
    # puts results.length
    file.puts results.length
    results.each do |row|
      # puts row.join(' ')
      file.puts row.join(' ')
    end
  end
end

# test_my_script.rb
require 'minitest/autorun'
require './pizza'
class Test < Minitest::Test
  def test_solution
    a =
    [
      1,
    ]
    res = 1
    assert_equal res, solution(a)
  end
end

If you want to run only one specific test, than run

ruby 0_short_palindrome.rb --name test_sample

If you want to print all local variables, you can use

local_variables.map { |vn| { vn => eval(vn.to_s) } }

Run with colors ruby my_class_test.rb -p, or ruby -r minitest/pride my_class_test.rb or put require 'pride' in test file.

For minitests you can use describe and it blocks.

TIPS:

if you need to perform big number of tests, and you can not calculate solution but you need to iterate something, than use table of solutions. First call create_table of results and query that @table[n] (if you can, fill just what it needs)
two dimensional 2d array @table = Array.new(n) { Array.new(n) }
if stack level too deep then try to use @table class variables instead of passing them as arguments (not much help since arguments are passed by reference, but there are less number of arguments link)

Complexity

Ruby Array#find method has O(n) complexity. If array is big, you should use bsearch O(log(n)). Array needs to be sorted. Binary search works in two modes:

find minimum: block must return true or false and there must be an index i so that: block returns false elements whose index is less than i, block returns true for any element whose index is greater than or equal to i. This method returns i-th element.
find any: block returns number and there are must be two indices i and j (0<=i<=j<=ary.size) so that: block returns positive number for 0<=k<i, returns zero for i<=k<j and negative for j<=k<ary.size. This method returns any element whose index is within i..j.

a = [1, 4, 7, 10]
# find minimum that satisfy block
a.bsearch { |x| x >= 6 } #=> 7

# find any
ary = [0, 4, 7, 10, 12]
# try to find v such that 4 <= v < 8
ary.bsearch {|x| 1 - x / 4 } #=> 4 or 7
# try to find v such that 8 <= v < 10
ary.bsearch {|x| 4 - x / 2 } #=> nil

Array a.include? is O(n) but hash a.key? (or a.include?) is O(1). So instead of big time, you can use big space by using Hashtables.

Counting of elements

tutorial if we need to check if some elements exists, we can create counting array in O(N) time and query in constant time

a = [0, 3, 1, 3]
counting = [0]*(a.max+1)
a.each { |e| counting[e]+=1 }
counting # =>  [1, 1, 0, 2]
counting[2] == 0 # true in constant time

Prefix sums

tutorial In O(N) time we can calculate p_1, …p_n, where p_k= a_0+a_1+…+a_(k-1). Note that p_k does not use a_k, and p_0 == 0 Than we can calculate sum of any slice (x,y) in constant time instead of O(y-x) (that is usually needed for query several results). Slice could be defined on 1..n (index starts from 1 and include bounds), slice(x,y) = prefix_sum[y] - prefix_sum[x-1] for example

slice(a_0,a_0) = slice(1,1) = prefix_sum[1]-prefix_sum[0]
slice(a_1,a_3) = slice(2,4) = prefix_sum[4]-prefix_sum[1]

a = [1, 4, 0, 4, 2]
prefix_sum = [0] * (a.length+1)
a.each_with_index do |e,i|
  prefix_sum[i+1] = prefix_sum[i] + e
end
# slice a_1 + a_2 + a_3
prefix_sum[3+1]-prefix_sum[1] # => 8

Counting sort O(n+m)

a=[4,2,0,2,3]
c=[0] * (a.max+1)
a.each_with_index do |e,i|
  c[e] += 1
end
s=[]
i=0
c.each_with_index do |n,v| # => [1, 0, 2, 1, 1]
  n.times do
    s[i] = v
    i+=1
  end
end
s # => [0, 2, 2, 3, 4]

Merge sort O(n*log(n))

a=[4,2,0,2,3]

def sort(a)

  if a.length == 1
    return a # => [4], [2], [0], [2], [3]
  else
    middle = a.length/2
    a[0..middle-1] # => [4, 2], [4], [0], [2]
    a[middle..-1] # => [0, 2, 3], [2], [2, 3], [3]
    left = sort(a[0..middle-1]) # => [4], [2, 4], [0], [2]
    right = sort(a[middle..-1]) # => [2], [3], [2, 3], [0, 2, 3]
    i = 0
    j = 0
    r = []
    while ! left[i].nil? || ! right[j].nil?
      if ! left[i].nil? && (right[j].nil? || left[i] <= right[j])
        r << left[i] # => [2, 4], [2], [0], [0, 2], [0, 2, 2, 3, 4]
        i += 1
      else
        r << right[j] # => [2], [2, 3], [0, 2], [0, 2, 3], [0], [0, 2, 2], [0, 2, 2, 3]
        j += 1
      end
    end
    return r # => [2, 4], [2, 3], [0, 2, 3], [0, 2, 2, 3, 4]
  end
end
sort(a) # => [0, 2, 2, 3, 4]

leader (value on more than half elements) is the same when we remove pair of different items

maximum slice is a slice (a_p..a_q) with max sum, can be computed in O(n^2)

# max_slice O(n^2)
a=[5,-7,3,5,-2,4,-1]
res = 0
a.each_with_index do |p,i|
  sum = 0
  a[i..-1].each do |q|
    sum += q
    res = [res,sum].max
  end
end
res # => 10

positive ending sum slice is wrapped with negative elements (or bounds first/last) because we can always choose empty slice (sum is 0) we can deduce that positive_ending_sum = max(0, positive_ending_sum_prev + a)

# max_slice O(n)
a=[5,-7,3,5,-2,4,-1]

res = 0
positive_ending_sum = 0
a.each do |p| # => [5, -7, 3, 5, -2, 4, -1]
  positive_ending_sum = [0, positive_ending_sum+ p].max # => 5, 0, 3, 8, 6, 10, 9
  res = [res,positive_ending_sum].max # => 5, 5, 5, 8, 8, 10, 10
end
res # => 10

Prime Numbers

count number of divisors of N is O(sqrt(N)) since every divisor a has symetric divisor b, n = a * b

n = 30
i = 1
result = 0
while i * i < n
  result += 2 if n % i == 0
  i += 1
end
result += 1 if i * i == n

finding all primes less than N is in O(Nlog(log(N))) Sieve of Eratosthenes. Find first prime (until sqrt(N) since we do not need to mark greater than N) and mark all multiplies of prime, starting from primeprime (since iprime will be marked with prime divisor of i) untill N, that is n/2 + n/3+ n/5 … = nlog(log(n) Rembember that largest prime factor of N can not be greated than Math.sqrt(N). 0, 1 are not prime numbers.
```
m = 10
definitely_non_prime = Array.new m + 1, false
definitely_non_prime[0] = definitely_non_prime[1] = true
2.upto(Math.sqrt(m)) do |i|
  next if definitely_non_prime[i]
  prime = i
  non_prime = prime * prime
  while non_prime <= m
    definitely_non_prime[non_prime] = true
    non_prime += prime
  end
end
definitely_non_prime.each_with_index { |e,i| puts i if e == false }
```

factorization is to find prime numbers and its order. We can create fixed F where F[i] is smallest prime that divides i, ie F[12] = 2, F[6] = 2, F[2] = 0. If we already have that F, than we can factorize in O(log(n)) time

n = 12
f = [0]*(n+1)
i=2
while i*i <= n
  if f[i] == 0
    prime = i
    temp = prime * prime
    while temp <= n
      f[temp] = prime if f[temp] == 0
      temp += prime
    end
  end
  i += 1
end
f # => [0, 0, 0, 0, 2, 0, 2, 0, 2, 3, 2, 0, 2]

def factorization(n, f)
  res = []
  while f[n] > 0
    res << f[n] # => [2], [2, 2]
    n /= f[n] # => 6, 3
  end
  res << n # => [2, 2, 3]
end

factorization(n,f) # => [2, 2, 3]

we can find all divisors, for example 12 has [1,2,3,4,6,12] divisor list, with simply iterate to all numbers and add number (for example 2) to set for product (divisors[4].add(2), divisors[6].add(2) …). Better perfomance is when we stop at number * number <= n and we add divisors[product].add(product/number) (note that we still iterate to n in inner loop).

n = 12
divisors = [] * (n+1)
[*1..n].each do |i| # => [1, 2, 3, 4, 5, 6]
  divisors[i] = Set.new([1,i]) # => #<Set: {1}>, #<Set: {1, 2}>, #<Set: {1, 3}>, #<Set: {1, 4}>, #<Set: {1, 5}>, #<Set: {1, 6}>
end
number = 2
while number <= n  # number * number <= n
  product = number # => 2, 3, 4, 5, 6
  while product <= n
    if ! divisors[product].include? number
      divisors[product].add number # => #<Set: {1, 4, 2}>, #<Set: {1, 6, 2}>, #<Set: {1, 6, 2, 3}>
      # divisors[product].add(product/number)
    end
    product += number
  end
  number += 1
end

Euclidean algorithm

Theory:

The: for a, b nonzero integer, their gcd(a,b) is linear combination of a and b ie: exists s and t such that sa+tb=gcd(a,b) Proof: let d be least positive linear combination d = sa+tb . We can show that d|a. We can write a = d*q+r (0 <= r < d ) so `r = a - dq = a - (sa + tb)q = (1

qs)a + (-qt)b. Since d is least positive and r<d that means r = 0`. Similarly d|b. We can show it is the greatest common divisor because if d1=gcd(a,b) < d it will be that d1|a d1|b and from d=sa+t*b that d1|d which is contradiction so d1==d

gcd(k, 1) = 1 if a|b*c and gcd(a,b)==1 than a|c

Lem: if a = bq + r than gcd(a,b) == gcd(b,r) Proof: gcd(a,b)=gcd(bq+r,b)=gcd(r,b) GCD will not change if you can add multiple of b, ie gcd(a,b)=gcd(a+k*b,b)

Def: The integers a and b are relatively prime if and only if there exist integers α and β such that aα + bβ = 1

Def: Lcm(a,b) least common multiple is =

a*b

/gcd(a,b)

The: ax+by=d has integer solution iff gcd(a,b)

If (x0,y0) is solution, we can add +- ab/d ie ax+by + ab/d - ba/d = a(x+b/d) +b(y-a/d) so (x+ b/d, y-a/d) is solution. General solutions are { (x0+kb/d, y0-ka/d) for k in Z}

Found gcd(a,b) with Euclidean algorithm by subtraction in O(a+b) steps, or by division in O(log(a+b))
```
def gcd(a,b)
  if a % b == 0
    return b
  else
    gcd(b, a % b)
  end
end
```
lcm(a,b) = a*b/gcd(a,b) and lcm(a,b,c) = lcm(a, lcm(b,c))
Fibonacci numbers F[n] = F[n-1] + F[n-2] and F[0] = 0 and F[1] = 1 and can be generated in O(N)
faster could be with matrix calculation

binary search for sorted array could be in O(log(N)) time. We found middle element and test condition. Array should be sorted (ascending) so we can test (mid<=target) and pick next item. Result is last middle when condition was true (max element <= target). If it is true go with (bigger) elements, othervise go with lower elements. We do not stop when we found solution since usual we have optimization problem (min or max). When we pass solution and set first = middle +1 (could be equal last) next iteration will be false (or last = new_middle -1 until last < first). If we search for min, then if condition is true we took lower elements (last = mid - 1). That is easy to replace in check function but result should be taken from that as well. So general check function store result if test is true with max, or test is false with min. Another nice non general solution is to return last for max, or first for min.

a=[1,2,3,4,5] #[12,15,15,19,24,31,53,59,60,61]
target = 3 # 13 
def check(a, middle, target, result)
  if a[middle] <= target
    result.value = middle
    true
  else
    false
  end
end
#a = [0,1,1,0,1,1,0,1,1]
#target = 3 # k boards 3 boards
#def check(a, middle, target, result)
#  last_board = -1
#  boards = 0
#  middle # => 4, 1, 2
#  for i in 1..a.length
#    if a[i] == 1 && last_board < i
#      boards += 1 # => 1, 2, 1, 2, 3, 4, 5, 6, 1, 2, 3
#      last_board = i + middle - 1 # => 4, 8, 1, 2, 4, 5, 7, 8, 2, 5, 8
#    end
#  end
#  boards # => 2, 6, 3
#  if boards <= target # => true, false, true
#    # since we search to min, we invert return value
#    result.value = middle
#    false
#  else
#    true
#  end
#end
class Result
  attr_accessor :value
end
def binary_search(a, target)
  first = 0
  last = a.length - 1
  result = Result.new
  result.value = -1
  while first <= last
    first     # => 0, 3
    last    # => 4, 4
    middle = (first+last)/2 # => 2, 3
    if check(a, middle, target, result) # => true, false
      first = middle + 1 # => 3
    else
      last = middle - 1 # => 2
    end
  end
  return result.value
end
binary_search(a, target) # => 2

caterpillar method. found subseqence which total sum equals s

a = [6,2,7,4,1,3,6]
target_sum = 12

back = 0
front = 0
sum = 0
a.each_with_index do |e, back|
  while front < a.length && sum + a[front] <= target_suM
    sum += a[front]
    front += 1
  end
  if sum == target_sum
    puts "je"
  end
  sum -= e
end

greedy algorithm is simplest possible algorithm

dinamic programming

def dynamic_coin_changing(c, k)
  n = c.length
  dp = [0] + [1/0.0]* k # => [0, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]
  for i in 1..n # => 1..3
    for j in c[i-1] .. k # => 1..6, 3..6, 4..6
       # => 1..6, 3..6, 4..6
      dp[j-c[i-1]]+1 # => 1, 2, 3, 4, 5, 6, 1, 2, 3, 2, 1, 2, 3
dp[j] # => Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 3, 4, 5, 6, 2, 3, 2
      dp[j] = [dp[j-c[i-1]]+1, dp[j]].min # => 1, 2, 3, 4, 5, 6, 1, 2, 3, 2, 1, 2, 2
    end
    dp # => [0, 1, 2, 3, 4, 5, 6], [0, 1, 2, 1, 2, 3, 2], [0, 1, 2, 1, 1, 2, 2]
  end
  dp
end
dynamic_coin_changing([1,3,4],6) # => [0, 1, 2, 1, 1, 2, 2]

Geometry

Find line that is perpendicular to line y = 2*x + 11 and contains (6, -7) video Perpendicular means slope is negative inverse ie -1/2. Note that in ruby you need to use x = x.to_f since 1/2==0 for integer division
maximum area for fixed length sides (edges) polygon has edges on circle (descripted circuit) and orders does not matter link
triangle area s = (a+b+c)/2; P = Math.sqrt(s*(s-a)*(s-b)*(s-c));

Math

radius = Math.sqrt((l1/2)**2 + (l2/2)**2)

Tutorial

https://www.toptal.com/algorithms/interview-questions

Constrains

memory: usually if you need to loop more than 10**6 (1MB) that could be a problem

Ruby Math Hackerrank

Contents