denis-mironov

# An in memory cache implementation that expires the least recently used items, and limits cache size by a maximum number of items.

class Cache
  attr_reader :store, :max_size

  def initialize(max_size)
    @max_size = max_size
    @store = {}
  end

denis-mironov

http://www.geekinterview.com/Interview-Questions/J2EE/Ruby

http://www.toptal.com/ruby/interview-questions  --10 Great Ruby Interview Questions

http://srikantmahapatra.wordpress.com/2013/11/07/ruby-on-rails-interview-questions-and-answers/  --ruby on rails 

What Ruby and Rails Developers Ought To Know?:

##Senior:

denis-mironov

Majority Element

Problem Introduction

Majority rule is a decision rule that selects the alternative which has a majority, that is, more than half the votes. Given a sequence of elements 𝑎1, 𝑎2, . . . , 𝑎𝑛, you would like to check whether it contains an element that appears more than 𝑛/2 times. A naive way to do this is the following.

MajorityElement(𝑎1, 𝑎2, . . . , 𝑎𝑛):
for 𝑖 from 1 to 𝑛:
currentElement ← 𝑎𝑖
count ← 0

denis-mironov

Binary Search

Problem Introduction

In this problem, you will implement the binary search algorithm that allows searching very efficiently (even huge) lists, provided that the list is sorted.

Problem Description

Task.

The goal in this code problem is to implement the binary search algorithm.

Input Format.

The first line of the input contains an integer 𝑛 and a sequence 𝑎0 < 𝑎1 < . . . < 𝑎𝑛−1 of 𝑛 pairwise distinct positive integers in increasing order. The next line contains an integer 𝑘 and 𝑘

denis-mironov

Partitioning Souvenirs

You and two of your friends have just returned back home after visiting various countries. Now you would like to evenly split all the souvenirs that all three of you bought.

Problem Description

Input Format.

The first line contains an integer 𝑛. The second line contains integers 𝑣1, 𝑣2, . . . , 𝑣𝑛 separated by spaces.

Constraints.

1 ≤ 𝑛 ≤ 20, 1 ≤ 𝑣𝑖 ≤ 30 for all 𝑖.

Output Format.

denis-mironov

Maximum Amount of Gold

Problem Introduction

You are given a set of bars of gold and your goal is to take as much gold as possible into your bag. There is just one copy of each bar and for each bar you can either take it or not (hence you cannot take a fraction of a bar).

Problem Description

Task.

Given 𝑛 gold bars, find the maximum weight of gold that fits into a bag of capacity 𝑊.

Input Format.

The first line of the input contains the capacity 𝑊 of a knapsack and the number 𝑛 of bars

denis-mironov

Problem Introduction

The edit distance between two strings is the minimum number of operations (insertions, deletions, and substitutions of symbols) to transform one string into another. It is a measure of similarity of two strings. Edit distance has applications, for example, in computational biology, natural language processing, and spell checking. Your goal in this problem is to compute the edit distance between two strings.

Problem Description

Task.

The goal of this problem is to implement the algorithm for computing the edit distance between two strings.

Input Format.

denis-mironov

As we already know, a natural greedy strategy for the change problem does not work correctly for any set of denominations. For example, if the available denominations are 1, 3, and 4, the greedy algorithm will change 6 cents using three coins (4 + 1 + 1) while it can be changed using just two coins (3 + 3). Your goal now is to apply dynamic programming for solving the Money Change Problem for denominations 1, 3, and 4.

Input Format.

Integer money.

Output Format.

The minimum number of coins with denominations 1, 3, 4 that changes money.

result = gets.chomp.to_i
coins = [1,3,4]

denis-mironov

Visualisation: https://www.toptal.com/developers/sorting-algorithms

The main idea of this method is to create a sorted sequence by attaching one element after another in the correct order. The selection sorting algorithm consists of several successive steps. At each sorting step, the current array element is interchanged with the element with the smallest value. Thus, an array of values is obtained, sorted in ascending order.

Основная мысль этого метода заключается в том, чтобы создать отсортированную последовательность, присоединяя к ней один элемент за другим в правильном порядке. Алгоритм сортировки выбором состоит из нескольких последовательных шагов. На каждом шаге сортировки текущий элемент массива меняется местами с элементом с наименьшим значением. Таким образом, получается массив значений, отсортированный по возрастанию.

puts 'Please, enter array size'
arr_size = gets.chomp.to_i
array = Array.new(arr_size) { rand(1..100) }

denis-mironov

Visualisation: https://www.toptal.com/developers/sorting-algorithms

def quicksort(array, beg_index, end_index)
  if beg_index < end_index
    p_index = partition(array, beg_index, end_index)
    quicksort(array, beg_index, p_index - 1)
    quicksort(array, p_index + 1, end_index)
  end