scoldboy
BAN USER
Comments (5)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Ruby, Memoized, I think nlog(n) worst case time....
If anyone can figure out the time complexity would be great.
dict = {}
%w(hello to the world).each do word
i = 0
res = 0
while i < word.length
res ^= word[i].ord
i += 1
end
dict[res] = dict[res] ? [word] + dict[res] : [word]
end
def is_word str, dict
i = 0
res = 0
while i < str.length
res ^= str[i].ord
i += 1
end
return nil unless dict[res]
dict[res].each do word
return word if word.split('').sort == str.split('').sort
end
nil
end
def unscramble str, dict, hash = {}
return '' if str.length == 0
str.length.times do idx
value = is_word(str[0..idx], dict)
next unless value
rest = hash[str[idx+1...str.length]] ? hash[str[idx+1...str.length]] : unscramble(str[idx+1...str.length], dict)
next unless rest
return hash[str] = rest == '' ? value : value + " " + rest
end
return nil
end

scoldboy
December 30, 2016 Comment hidden because of low score. Click to expand.
0
of 0 vote
I did it with and without dynamic programming in Ruby
def sums coins, quants, pos = 0, count = 0
res = [0]
res += sums(coins, quants, pos, count+1).map{ el el += coins[pos]} if count < quants[pos]
res += sums(coins, quants, pos+1, 0) if pos < coins.length  1
res.uniq.sort.reverse
end
def sums_dp coins, quants, hash = {}, pos = 0, count = 0
res = [0]
if count < quants[pos]
value = hash[[pos, count+1]]  sums(coins, quants, hash, pos, count+1).map{ el el += coins[pos]}
res += value
end
if pos < coins.length  1
value = hash[[pos+1, 0]]  sums(coins, quants, hash, pos+1, 0)
res += value
end
hash[[pos, count]] = res.uniq.sort.reverse
end

scoldboy
December 29, 2016 Comment hidden because of low score. Click to expand.
0
of 0 vote
class Node
attr_accessor :value, :left, :right
def initialize value
@value = value
@left = nil
@right = nil
end
end
class Tree
attr_accessor :root
def initialize
@root = nil
end
def paths node = @root
return [[node.value]] unless node.right  node.left
res = []
res += [[node.value]]
res += paths(node.left).map{el el += [node.value]} if node.left
res += paths(node.right).map{el el += [node.value]} if node.right
res
end
end

scoldboy
December 29, 2016 Comment hidden because of low score. Click to expand.
0
of 0 vote
I used BFS.
def move arr, idx
loc = arr.index(1)
return false if idx == loc
arr = arr.dup
arr[loc], arr[idx] = arr[idx], arr[loc]
arr
end
def moves arr
res = []
arr.length.times do idx
if move(arr, idx)
res << move(arr, idx)
end
end
res
end
def solved_arr arr
i = 1
solved = [1]
while i < arr.length
solved << i
i += 1
end
solved
end
def bfs arr
hash = {}
hash[arr] = [0, arr]
solved = solved_arr(arr)
break_loop = false
queue = [arr]
until break_loop
past = queue.shift
moves = moves(past)
moves.each do el
queue << el unless hash[el]
hash[el] = past unless hash[el]
break_loop = true if el == solved
end
end
res = []
while hash[solved] != arr
res << solved
solved = hash[solved]
end
res << solved
res << arr
res.reverse
end

scoldboy
December 29, 2016 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
Ruby
 scoldboy December 30, 2016