Skip to content

Instantly share code, notes, and snippets.

View woodRock's full-sized avatar
🫖
Activate zen mode (CTRL + K, Z)

Jesse Wood woodRock

🫖
Activate zen mode (CTRL + K, Z)
30 followers · 61 following
View GitHub Profile
@woodRock
woodRock / daily-coding-problem-06.c
Created August 28, 2018 08:44
An XOR linked list is a more memory efficient doubly linked list. Instead of each node holding next and prev fields, it holds a field named both, which is an XOR of the next node and the previous node. Implement an XOR linked list; it has an add(element) which adds the element to the end, and a get(index) which returns the node at index. f using…
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
struct Node
{
int data;
struct Node* npx; /* XOR of next and previous node */
};
@woodRock
woodRock / daily-coding-problem-07.py
Created August 28, 2018 09:09
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded. For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'. You can assume that the messages are decodable. For example, '001' is not allowed.
mapping=["1", "2", "3", "4", "5", "6", "7" "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26"]
encodedCases = ["918", "739", "1142", "56", "82", "118", "1219", "6", "862", "1111"]
def decodeNumber(decoded, mapping):
count=0
checkFirstLast=0
for i in range(9, len(mapping)):
if mapping[i] in decoded:
@woodRock
woodRock / daily-coding-problem-11.rb
Last active August 28, 2018 09:38
Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix. For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal]. Hint: Try preprocessing the dictionary into a more efficient data structure to spe…
#!/usr/bin/env ruby
dictionary = ["Dog", "Deer", "Deal"]
def autocomplete(search, dict)
result = Array.new
if dict.respond_to?("each")
dict.each do |d|
if search.eql? d[0..search.length-1]
result << d
@woodRock
woodRock / daily-coding-problem-12.py
Created August 28, 2018 09:45
There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters. For example, if N is 4, then there are 5 unique ways: 1, 1, 1, 1 2, 1, 1 1, 2, 1 1, 1, 2 2, 2 What if, instead of being able to cl…
#!/usr/bin/env python
def staircase(n, X):
cache = [0 for _ in range(n + 1)]
cache[0] = 1
for i in range(n + 1):
cache[i] += sum(cache[i - x] for x in X if i - x > 0)
cache[i] += 1 if i in X else 0
return cache[-1]
@woodRock
woodRock / daily-coding-problem-13.rb
Created August 28, 2018 11:26
Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters. For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb".
#!/usr/bin/env ruby
require 'set'
def distinct_char(s,k)
#assert(len(s) >= k)
start_idx, end_idx, max_length = 0, k, k
while end_idx < s.length do
end_idx += 1
while true do
@woodRock
woodRock / daily-coding-problem-14.rb
Created August 28, 2018 12:18
The area of a circle is defined as πr^2. Estimate π to 3 decimal places using a Monte Carlo method. Hint: The basic equation of a circle is x2 + y2 = r2.
#!/usr/bin/env ruby
def pi_estimation(r=5)
inside =0.0
outside = 0.0
total = 0.0
rnd = Random.new
for i in 1 ... 10000
x = rnd.rand(-1*inside..inside)
@woodRock
woodRock / daily-coding-problem-15.rb
Last active August 28, 2018 12:32
Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.
#!/usr/bin/env ruby
def random_element(stream)
size = stream.length
rnd = Random.rand(size)
return stream[rnd]
end
stream = [22,44,33,55]
for i in 0..1000
@woodRock
woodRock / daily-coding-problem-16.rb
Last active April 19, 2023 20:02
You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API: record(order_id): adds the order_id to the log get_last(i): gets the ith last element from the log. i is guaranteed to be smaller than or equal to N. You should be as efficient with time and space…
#!/usr/bin/env ruby
class Log
def initialize(log=["1","2","3","4"])
@log = log
end
def size
return @log.length
end
def record(order_id)
@woodRock
woodRock / daily-coding-problem-17.rb
Created August 28, 2018 13:05
The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext. We are interested in finding the longest (number of characters) absolute path to a file within our file sys…
#!/usr/bin/env ruby
def longest_absolute_path(paths, skips)
size = 0;
paths.each do |p|
skips.each do |skip|
p.sub(skip, '')
end
end
return paths.max.length
@woodRock
woodRock / daily-coding-problem-18.rb
Created August 28, 2018 13:27
Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k. For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get: [10, 7, 8, 8], since: 10 = max(10, 5, 2) 7 = max(5, 2, 7) 8 = max(2, 7, 8) 8 = max(7, 8, 7) Do this in O(n) time and O(k) space. You can …
#!/usr/bin/env ruby
def maximum_subarray_values(k, arr)
max_vals = Array.new
arr.each do |i|
if max_vals.length == 0 || max_vals.length < k
max_vals << i
else
if i > max_vals.min