woodRock’s gists

woodRock / daily-coding-problem-45.rb

Last active September 22, 2018 05:02

Using a function rand5() that returns an integer from 1 to 5 (inclusive) with uniform probability, implement a function rand7() that returns an integer from 1 to 7 (inclusive).

	#!/usr/bin/env ruby

	def rand5()
	rand(5) + 1
	end

	def rand7()
	(7 * rand5()) / 5
	end

woodRock / daily-coding-problem-44.rb

Created September 22, 2018 04:59

We can determine how "out of order" an array A is by counting the number of inversions it has. Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element. Given an array, count the number of inversions it has. Do this faster than O(N^2) time. You may assume each element in the…

	#!/usr/bin/env ruby

	def out_of_order set
	n = set.size()
	inv = 0
	n.times do \|i\|
	(i+1...n).each do \|j\|
	inv += 1 if set[i] > set[j]
	end
	end

woodRock / daily-coding-problem-43.rb

Created September 18, 2018 08:12

Each method should run in constant time. Implement a stack that has the following methods:

	#!/usr/bin/env ruby


	class Stack
	def initialize(init=nil)
	@stack = []
	@stack << init if !init.nil?
	end
	def push val
	@stack << val

woodRock / daily-coding-problem-42.rb

Last active September 18, 2018 06:10

Given a list of integers S and a target number k, write a function that returns a subset of S that adds up to k. If such a subset cannot be made, then return null. Integers can appear more than once in the list. You may assume all numbers in the list are positive. For example, given S = [12, 1, 61, 5, 9, 2] and k = 24, return [12, 9, 2, 1] since…

	#!/usr/bin/env ruby

	def isSubsetSum(set,n, sum)
	return true if (sum == 0)
	return false if (n == 0 and sum != 0)
	return isSubsetSum(set, n - 1, sum) if (set[n - 1] > sum)
	return isSubsetSum(set, n-1, sum) \|\| isSubsetSum(set, n-1, sum - set[n-1])
	end

	s = [12, 1, 61, 5, 9, 2]

woodRock / gist:e239594eb0e38530d84346218665641e

Created September 18, 2018 06:00

Given a list of integers S and a target number k, write a function that returns a subset of S that adds up to k. If such a subset cannot be made, then return null. Integers can appear more than once in the list. You may assume all numbers in the list are positive. For example, given S = [12, 1, 61, 5, 9, 2] and k = 24, return [12, 9, 2, 1] since…

	#!/usr/bin/env ruby

	def isSubsetSum(set,n, sum)
	return true if (sum == 0)
	return false if (n == 0 and sum != 0)
	return isSubsetSum(set, n - 1, sum) if (set[n - 1] > sum)
	return isSubsetSum(set, n-1, sum) \|\| isSubsetSum(set, n-1, sum - set[n-1])
	end

	s = [12, 1, 61, 5, 9, 2]

woodRock / daily-coding-problem-40.rb

Created September 18, 2018 05:00

Given an array of integers where every integer occurs three times except for one integer, which only occurs once, find and return the non-duplicated integer. For example, given [6, 1, 3, 3, 3, 6, 6], return 1. Given [13, 19, 13, 13], return 19.

	#!/usr/bin/env ruby

	def non_duplicate_in_set set
	freq = set.inject(Hash.new(0)) {\|hash,word\| hash[word] += 1; hash }
	freq.keys.each { \|k\| return k if freq[k] < 3 }
	end

	set = [6, 1, 3, 3, 3, 6, 6]
	puts non_duplicate_in_set(set)

woodRock / daily-coding-problem-33.rb

Created September 17, 2018 13:09

	def medians(stream)
	smaller, greater = Array.new, Array.new
	med = stream[0]
	smaller << stream[0]
	puts med
	for i in 1...stream.length
	current = stream[i]
	if smaller.size() > greater.size()
	if current < med
	greater << smaller[-1]

woodRock / daily-coding-problem-37.rb

Created September 17, 2018 11:18

The power set of a set is the set of all its subsets. Write a function that, given a set, generates its power set. For example, given the set {1, 2, 3}, it should return {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

	#!/usr/bin/env ruby

	def power_set(set)
	size = set.size() ** 2
	size.times do \|counter\|
	size.times do \|j\|
	if ((counter & (1 << j)) > 0)
	print set[j]
	end
	end

woodRock / daily-coding-problem-36.rb

Created September 17, 2018 10:54

Given the root to a binary search tree, find the second largest node in the tree.

	#!/usr/bin/env ruby

	class Node
	attr_accessor :val, :left, :right
	def initialize(val, left=nil, right=nil)
	@val = val
	@left = left
	@right = right
	end
	end

woodRock / daily-coding-problem-35.rb

Last active September 17, 2018 10:03

Given an array of strictly the characters 'R', 'G', and 'B', segregate the values of the array so that all the Rs come first, the Gs come second, and the Bs come last. You can only swap elements of the array. Do this in linear time and in-place. For example, given the array ['G', 'B', 'R', 'R', 'B', 'R', 'G'], it should become ['R', 'R', 'R', 'G…

	#!/usr/bin/env ruby

	def sort(array)
	order = ["R","G","B"]
	res = Array.new(order.size()) { Array.new }
	array.each { \|c\| res[order.index(c)] << c }
	return res.flatten
	end

	def sort_proper(array)

Jesse Wood woodRock