An Algorithm a Day Keeps the Brain Fuzz Away
Check out these perfectly imperfect solutions I developed for some LeetCode problems.
Solving algorithmic challenges gives my brain a burst of dopamine. If you're like me, you'll find these fun. I developed these solutions in node.js using vanilla javascript. Have you solved one of these before? I would love to hear your feedback, ideas, and see your solution!
The Hobby Decider
I was presented with this one in an interview, but wasn't able to fully complete it in the alloted time (dang!). Afterward, I couldn't stop thinking about it, so I had to solved it on my own. Yes, I could've tried using the experimental array.group() javascript method, but I wanted to create a more real-world ready-to-use-now version, so I stuck with the classic array methods that can run in most browsers today.
HOBBY DECIDER You are trying to choose a new hobby, and part of your decision is based on how much each hobby would cost to get started. So, you've brainstormed a list of the things you would need to buy for each one, and the cost of each item. But, they're all mixed together, and what you really need is the total cost added up for each hobby. Write a function that accepts a nested array containing hobby name, item name, and item cost, and returns an object containing the total cost for each hobby. Here's some sample input and output.
Here is the sample input and output (these are a few of my own fun activities!)
const hobbyArray = [
["coding", "computer", 2056],
["silicone pouring", "silicone", 450],
["coding", "classes", 250],
["cooking", "ingredients", 50],
["cooking", "knives", 75],
["silicone pouring", "PPE", 27]
]
//Sample Output:
{
coding: 2306,
'silicone pouring': 477,
cooking: 125
}```
Ok, so we know we want to get an object back, with numbers indicating total dollar values.
I created some empty values to serve as containers, which will hold each value as the accumulator adds it during the loop.
```let newArr = [];
let acc = 0;
let obj = {};
let newObj = {};```
The hobbyReducer() function determines how many different hobbies are present in the hobbyArray. In this example, reducedArr.length will equal 3.
Each time the nested loop runs (indicated by j), the integer amount will be added up for each specific hobby.
By the time the loop finishes, it should return __obj__, which should contain the sample output we defined above.
```function hobbyDecider(array) {
const reducedArr = hobbyReducer(array);
for(i=0; i <reducedArr.length; i++) {
if(acc>0){
obj[reducedArr[i]] = acc;
}
acc = 0;
for(j=0; j<array.length; j++){
if(array[j].indexOf(reducedArr[i]) >= 0) {
acc += array[j][2]
}
}
obj[reducedArr[i]] = acc;
}
return obj;
}
function hobbyReducer(array, index) {
array.forEach(item=>newArr.push(item[0]))
return [...new Set(newArr)]
}
console.log(hobbyDecider(hobbyArray))```
Here is the full solution:
```let newArr = [];
let acc = 0;
let obj = {};
let newObj = {};
function hobbyDecider(array) {
const reducedArr = hobbyReducer(array);
for(i=0; i <reducedArr.length; i++) {
if(acc>0){
obj[reducedArr[i]] = acc;
}
acc = 0;
for(j=0; j<array.length; j++){
if(array[j].indexOf(reducedArr[i]) >= 0) {
acc += array[j][2]
}
}
obj[reducedArr[i]] = acc;
}
return obj;
}
function hobbyReducer(array, index) {
array.forEach(item=>newArr.push(item[0]))
return [...new Set(newArr)]
}
console.log(hobbyDecider(hobbyArray))```
__Letter Combinations of a Phone Number__
I thought this one was intruiging, especially since I've spent so much time talking with business owners who are picking out business numbers that spell catchy words such as 'RENOVATENOW', 'GETMYFREEQUOTE', and 'DOMYTAXES'.
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Sample Input and Output:
```// Input: digits = "23"
// Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
// Example 2:
// Input: digits = ""
// Output: []
// Example 3:
// Input: digits = "2"
// Output: ["a","b","c"]
//Input: "56"
//Output: ['jm', 'jn', 'jo', 'km', 'kn', 'ko', 'lm','ln','lo']```
Constraints:
0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].
Got it! Let's pseudocode this!
1. Take in string containing only numbers 2-9
2. Parse numbers into integers
3. For each integer, loop through it's array of letters
4. For each letter loop in first number's array, loop through the other number's letter array
5. View all possible letter combos (not nessecarily in order)
I've become one of those developers who really likes regular expressions; they're so handy for parsing out values. I created a regex to use to validate the contraint.
```const regex = /[2-9]/g;```
Then, I put the number values into arrays for each number on the phone keypad (just look at any phone keypad to see these!)
```const num2Arr = ['a','b','c'];
const num3Arr = ['d', 'e', 'f'];
const num4Arr = ['g', 'h', 'i'];
const num5Arr = ['j','k', 'l'];
const num6Arr = ['m','n','o'];
const num7Arr = ['p','q','r','s'];
const num8Arr = ['t','u','v'];
const num9Arr = ['w','x','y','z'];```
Put them in an array so we can pull them out based on index.
```const allNumsArr = [["","",""],["","",""],num2Arr, num3Arr, num4Arr, num5Arr, num6Arr, num7Arr, num8Arr, num9Arr];```
Then, I created empty arrays to hold our values as we loop through:
```let finalArr = [];
let firstArr = [];
let secondArr = [];```
The function getCombos first validates the constraints, then - assuming it passes - the string gets parsed from a string to an array. If the user only entered 1 number in the original string, the section of code under if (numArr.length === 1) gets run. If they entered 2 numbers, the 'else' block of code runs. (Note that if they enter more than 2 numbers in the original string, only the first two will run - just sticking with the original sample inputs here)!
```function getCombos(string) {
if (0 <= string.length <= 4 && string.match(regex)){
const numArr = string.match(regex);
if (numArr.length === 1) {
firstArr = allNumsArr[numArr[0]]
for (let i=0; i < firstArr.length; i++) {
finalArr.push(`${firstArr[i]}`)
}
} else {
firstArr = allNumsArr[numArr[0]]
secondArr = allNumsArr[numArr[1]]
for (let i=0; i < firstArr.length; i++) {
for(let j=0; j < secondArr.length; j++) {
finalArr.push(`${firstArr[i]} ${secondArr[j]}`)
}
}
}
return finalArr
} else {
console.log("plz only enter numbers 2-9.")
}
}
getCombos("89")```
Here is the full solution:
```const regex = /[2-9]/g;
const num2Arr = ['a','b','c'];
const num3Arr = ['d', 'e', 'f'];
const num4Arr = ['g', 'h', 'i'];
const num5Arr = ['j','k', 'l'];
const num6Arr = ['m','n','o'];
const num7Arr = ['p','q','r','s'];
const num8Arr = ['t','u','v'];
const num9Arr = ['w','x','y','z'];
const allNumsArr = [["","",""],["","",""],num2Arr, num3Arr, num4Arr, num5Arr, num6Arr, num7Arr, num8Arr, num9Arr];
let finalArr = [];
let firstArr = [];
let secondArr = [];
function getCombos(string) {
if (0 <= string.length <= 4 && string.match(regex)){
const numArr = string.match(regex);
if (numArr.length === 1) {
firstArr = allNumsArr[numArr[0]]
for (let i=0; i < firstArr.length; i++) {
finalArr.push(`${firstArr[i]}`)
}
} else {
firstArr = allNumsArr[numArr[0]]
secondArr = allNumsArr[numArr[1]]
for (let i=0; i < firstArr.length; i++) {
for(let j=0; j < secondArr.length; j++) {
finalArr.push(`${firstArr[i]} ${secondArr[j]}`)
}
}
}
return finalArr
} else {
console.log("plz only enter numbers 2-9.")
}
}
console.log(getCombos("89"))```
__ROMAN TO INTEGER__
This one was by far the most challenging - mostly because I'm not super familiar with roman numerals (I had to copy and paste accurate roman numerals from a Google search)!
I originally wrote it using multiple functions, and later changed it to run methods on an object just to try that approach out.
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII.
Instead, the number four is written as IV.
Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX.
There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Sample Inputs and Outputs:
```// Input: s = "III"
// Output: 3
// Explanation: III = 3.
// Example 2:
// Input: s = "LVIII"
// Output: 58
// Explanation: L = 50, V= 5, III = 3.
// Example 3:
// Input: s = "MCMXCIV"
// Output: 1994
// Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.```
Constraints:
1 <= s.length <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
It is guaranteed that s is a valid roman numeral in the range [1, 3999].
Let's pseudocode this!
1. Take in a string that meets the constraints.
2. Parse out the pieces of that string that make up the building blocks of the roman numeral. For each regex, check the string again and replace accordingly.
3. Translate to integers.
4. Math.
First, you see the objects containing both the regular expressions (which we'll use to parse out the integer values) and the parser methods. The parser methods are designed to call each other in order. We'll need the accumulator for addition at the very end.
```const regexObj = {
regexI: /I/g,
regexV: /V/g,
regexX: /X/g,
regexL: /L/g,
regexC: /C/g,
regexD: /D/g,
regexM: /M/g,
regex4: /IV/g,
regex9: /IX/g,
regex40: /XL/g,
regex90: /XC/g,
regex400: /CD/g,
regex900: /CM/g
}
let accumulator = 0;
const toRomanParserMethods = {
toRoman1000: function(string, array, regex) {
const num1000 = string.replace(regex,1000);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(1000)
}
}
const finalValue = array.reduce((previousValue, currentValue) => previousValue + currentValue, accumulator)
return finalValue
},
toRoman500: function(string, array, regex) {
const num500 = string.replace(regex,500);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(500)
}
}
return this.toRoman1000(num500, array, regexObj.regexM)
},
toRoman100: function(string, array, regex) {
const num100 = string.replace(regex,100);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(100)
}
}
return this.toRoman500(num100, array, regexObj.regexD)
},
toRoman50: function(string, array, regex) {
const num50 = string.replace(regex,50);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(50)
}
}
return this.toRoman100(num50, array, regexObj.regexC)
},
toRoman10: function(string, array, regex) {
const num10 = string.replace(regex,10);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(10)
}
}
return this.toRoman50(num10, array, regexObj.regexL)
},
toRoman5: function(string, array, regex) {
const num5 = string.replace(regex,5);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(5)
}
}
return this.toRoman10(num5, array, regexObj.regexX)
},
toRoman1: function(string, array, regex) {
const num1 = string.replace(regex,1);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(1)
}
}
return this.toRoman5(num1, array, regexObj.regexV)
},
toRoman900: function(string, array, regex) {
const num900 = string.replace(regex,900);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(900)
}
}
return this.toRoman1(num900, array, regexObj.regexI)
},
toRoman400: function(string, array, regex) {
const num400 = string.replace(regex,400);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(400)
}
}
return this.toRoman900(num400, array, regexObj.regex900)
},
toRoman90: function(string, array, regex) {
const num90 = string.replace(regex,90);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(90)
}
}
return this.toRoman400(num90, array, regexObj.regex400)
},
toRoman40: function(string, array, regex) {
const num40 = string.replace(regex,40);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(40)
}
}
return this.toRoman90(num40, array, regexObj.regex90)
},
toRoman9: function(string, array, regex) {
const num9 = string.replace(regex,9);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(9)
}
}
return this.toRoman40(num9, array, regexObj.regex40)
},
toRoman4: function(string, array, regex){
const num4 = string.replace(regex, 4);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(4)
}
}
return this.toRoman9(num4, array, regexObj.regex9)
}
}
function toRoman(string) {
if (0 <= string.length <= 15 && string.includes('I' || 'V' || 'X' || 'L' || 'C'|| 'D'|| 'M')) {
console.log('translating from Roman to integer!')
} else {
console.log('please try again using a correct Roman numeral between 1 and 15 characters long, entering only capital letters!')
}
const integerValue = toRomanParserMethods.toRoman4(string, [], regexObj.regex4)
return integerValue
}
console.log('toroman', toRoman("MMMCMLXXXVIII"))```
Here is the full solution:
```const regexObj = {
regexI: /I/g,
regexV: /V/g,
regexX: /X/g,
regexL: /L/g,
regexC: /C/g,
regexD: /D/g,
regexM: /M/g,
regex4: /IV/g,
regex9: /IX/g,
regex40: /XL/g,
regex90: /XC/g,
regex400: /CD/g,
regex900: /CM/g
}
let accumulator = 0;
const toRomanParserMethods = {
toRoman1000: function(string, array, regex) {
const num1000 = string.replace(regex,1000);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(1000)
}
}
const finalValue = array.reduce((previousValue, currentValue) => previousValue + currentValue, accumulator)
return finalValue
},
toRoman500: function(string, array, regex) {
const num500 = string.replace(regex,500);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(500)
}
}
return this.toRoman1000(num500, array, regexObj.regexM)
},
toRoman100: function(string, array, regex) {
const num100 = string.replace(regex,100);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(100)
}
}
return this.toRoman500(num100, array, regexObj.regexD)
},
toRoman50: function(string, array, regex) {
const num50 = string.replace(regex,50);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(50)
}
}
return this.toRoman100(num50, array, regexObj.regexC)
},
toRoman10: function(string, array, regex) {
const num10 = string.replace(regex,10);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(10)
}
}
return this.toRoman50(num10, array, regexObj.regexL)
},
toRoman5: function(string, array, regex) {
const num5 = string.replace(regex,5);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(5)
}
}
return this.toRoman10(num5, array, regexObj.regexX)
},
toRoman1: function(string, array, regex) {
const num1 = string.replace(regex,1);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(1)
}
}
return this.toRoman5(num1, array, regexObj.regexV)
},
toRoman900: function(string, array, regex) {
const num900 = string.replace(regex,900);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(900)
}
}
return this.toRoman1(num900, array, regexObj.regexI)
},
toRoman400: function(string, array, regex) {
const num400 = string.replace(regex,400);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(400)
}
}
return this.toRoman900(num400, array, regexObj.regex900)
},
toRoman90: function(string, array, regex) {
const num90 = string.replace(regex,90);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(90)
}
}
return this.toRoman400(num90, array, regexObj.regex400)
},
toRoman40: function(string, array, regex) {
const num40 = string.replace(regex,40);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(40)
}
}
return this.toRoman90(num40, array, regexObj.regex90)
},
toRoman9: function(string, array, regex) {
const num9 = string.replace(regex,9);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(9)
}
}
return this.toRoman40(num9, array, regexObj.regex40)
},
toRoman4: function(string, array, regex){
const num4 = string.replace(regex, 4);
const arr = [...string.matchAll(regex)];
if(arr.length > 0){
for(let i=0; i< arr.length; i++){
array.push(4)
}
}
return this.toRoman9(num4, array, regexObj.regex9)
}
}
function toRoman(string) {
if (0 <= string.length <= 15 && string.includes('I' || 'V' || 'X' || 'L' || 'C'|| 'D'|| 'M')) {
console.log('translating from Roman to integer!')
} else {
console.log('please try again using a correct Roman numeral between 1 and 15 characters long, entering only capital letters!')
}
const integerValue = toRomanParserMethods.toRoman4(string, [], regexObj.regex4)
return integerValue
}
console.log('toroman', toRoman("MMMCMLXXXVIII"))```
I hope you enjoyed these solutions and find them helpful!