daifu

=begin
  Implement dijkstra's algorithm

  reference
  https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

  V is the number of vertices
  N is the maximum number of edges attached to a single node.

  Time complexity: O( V * N * log V)

daifu

=begin
  Merge sort in ruby

  Referrence
  https://en.wikipedia.org/wiki/Merge_sort

  Big O complexity
  Time complexity (Average, Best, Worest cases): O(n log(n))
  Space complexity: O(n)
=end

daifu

=begin
implement heapsort in rails

https://en.wikipedia.org/wiki/Heapsort

Big(O) complexity
Time complexity (Average, Best, Worest cases): O(n log(n))
Space complexity: O(1)

test example

daifu

def flatten(ary)
  ret = []
  ary.each do |sub_ary|
    if sub_ary.is_a?(Array)
      ret += flatten(sub_ary)
    else
      ret << sub_ary
    end
  end
  ret

daifu

Flippin' Countdown

A Pen by Doug Avery on CodePen.

License.

daifu

/*
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

daifu

/*
Given n non-negative integers representing an elevation map where 
the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Algorithm: 
1. construct 2 arrays that store the max from left to right and max from right to left
2. At position i, we now know the max from its left and right, then find the max trapped water.

daifu

/*
Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.
*/

daifu

/*
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C 
where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, ..., ak) must be in non-descending order. (ie, a1 ? a2 ? ... ? ak).

daifu

/*
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Algorithm time complexity is O(n), and space complexity is O(n)
Basic algrithm is to keep track of the longest matched paramthesis.
But we need to separate the valid substring, which have 2 special cases: ())()() and ()()(((), and others(whole string