/* Contents:
- the instructions
- my Exercise 1 solution
- someone else's Exercise 1 solution
- my Exercise 2 solution
*/
/* Instructions
EXERCISE 1
Enumerate all uppercase/lowercase permutations for any letter specified in $rule_char_set.
Input:
word = "medium-one"
rule_char_set = "dn"
Output:
solutions = ["medium-one", "meDium-one", "medium-oNe", "meDium-oNe"]
If the character in $rule_char_set appears more than once in $word, treat them as independent
variables. For example:
Input:
word = "medium-one"
rule_char_set = "m"
Output:
solutions = ["medium-one", "Medium-one", "mediuM-one", "MediuM-one"]
EXERCISE 2
Find the median number of all values from two very large arrays of sorted integers. Assume
both arrays have the same large length = N.
I'd like to see a solution of runtime faster than O(N).
Input:
array_int1 = 10, 20, 30, 40, 51, 61, 71
array_int2 = 15, 25, 31, 86, 600, 700, 900
Output: median = 45.5
*/
// Exercise 1 (my solution; is recursive and creates duplicates; is not as concise as I'd like)
const listPerms = (wordStr, charSetStr, input) => {
let indexesOfChars = []
wordStr.split('').forEach((wordLett, i) => {
charSetStr.split('').forEach(charSetLett => {
if (wordLett === charSetLett) {
indexesOfChars.push(i)
}
})
})
// console.log(indexesOfChars)
let wordWithMaxCaps = []
wordStr.split('').forEach((lett, i) => {
indexesOfChars.forEach(num => {
if (i === num) {
lett = lett.toUpperCase()
}
})
wordWithMaxCaps.push(lett)
})
// console.log(wordWithMaxCaps)
// console.log(input)
if (input.includes(wordWithMaxCaps.join(''))) {
return []
} else {
if (input.length === 0) {
input.push(wordStr.split(''))
// console.log(input)
} else {
input = input.map(wStr => wStr.split(''))
// console.log(input)
}
let newArr = []
input.forEach(word => {
word.forEach((lett, i) => {
indexesOfChars.forEach(num => {
if (i === num && lett !== lett.toUpperCase()) {
newArr.push(word.slice(0, i).concat(lett.toUpperCase()).concat(word.slice(i + 1)).join(''))
}
})
})
})
// console.log(newArr)
input = newArr.filter((wStr, i) => newArr.indexOf(wStr) === i) // removing newArr's duplicate strings
// console.log(input)
const solution = listPerms(wordStr, charSetStr, input)
solution.unshift(...input) // this occurs after the recursive function call has returned
solution.unshift(wordStr) // wordStr could have been added by returning '[wordStr]' instead of '[]' when the base case was met. However, if this were done, then wordStr wouldn't be at the beginning of the 'solution' array, given that one line above this one is 'solution.unshift(...input)' and not 'solution.push(...input)'. If 'push' were used instead, then returning '[wordStr]' at the base case would put wordStr at the beginning of 'solution', but then the order of all the non-wordStr strings would no longer be correct.
return solution.filter((wStr, i) => solution.indexOf(wStr) === i) // removing solution's duplicate wordStr strings
}
}
console.log(listPerms('medium-one', 'm', []))
console.log(listPerms('medium-one', 'dn', []))
console.log(listPerms('medium-one', 'md', []))
console.log(listPerms('medium-one', 'mdn', []))
console.log(listPerms('medium-one', 'dnm', []))
console.log(listPerms('medium-one', 'edon', []))
console.log(listPerms('medium-one', 'medon', []))
console.log(listPerms('medium-one-man', 'mdn', []))
// Exercise 1 (someone else's solution; isn't recursive and doesn't create duplicates; is very concise)
const getPerms = (word, charSet) => {
let result = ['']
for (let i in word) { // loop over each character in 'word'
let char = word[i]
let temp = []
result.forEach(str => { // loop over each string that is, so far, in 'result'
if (charSet.indexOf(char) !== -1) { // if 'char' is in 'charSet'...
// ...add both cases of 'char'
temp.push(str + char.toUpperCase())
temp.push(str + char.toLowerCase())
} else { // if 'char' is not in 'charSet'...
temp.push(str + char) // ...add the existing case of 'char'
}
})
result = temp
// console.log(result) // how 'result' progresses with each iteration
}
return result
}
console.log(getPerms('medium-one', 'm'))
console.log(getPerms('medium-one', 'dn'))
console.log(getPerms('medium-one', 'md'))
console.log(getPerms('medium-one', 'mdn'))
console.log(getPerms('medium-one', 'dnm'))
console.log(getPerms('medium-one', 'edon'))
console.log(getPerms('medium-one', 'medon'))
console.log(getPerms('medium-one-man', 'mdn'))
// Exercise 2 (my solution; I was clued into this approach by being advised to learn about Binary Search)
function getMedian(arr1, arr2) { // arr1 and arr2 are sorted
if (arr1.length !== 2) { // since arr1 and arr2 are the same length, either can be used here...and this comment applies to several lines below
let middleFloored = Math.floor(arr1.length / 2)
// console.log(middleFloored)
let m1
let m2
if (arr1.length % 2 !== 0) {
m1 = arr1[middleFloored]
m2 = arr2[middleFloored]
} else {
m1 = (arr1[middleFloored] + arr1[middleFloored - 1]) / 2
m2 = (arr2[middleFloored] + arr2[middleFloored - 1]) / 2
}
// console.log(m1)
// console.log(m2)
if (m1 === m2) {
return m1 // Note: m1 or m2 can be returned here. Why? Because either will be the median for the merged array. How do we know this? Because: The merged array will always be even in length, m1 and m2 will always be the two middle numbers, and the average of two identical numbers is either number.
} else if (m1 > m2) {
if (arr1.length % 2 !== 0) {
return getMedian(arr1.slice(0, middleFloored + 1), arr2.slice(middleFloored))
} else {
return getMedian(arr1.slice(0, middleFloored + 1), arr2.slice(middleFloored - 1))
}
} else if (m1 < m2) {
if (arr1.length % 2 !== 0) {
return getMedian(arr1.slice(middleFloored), arr2.slice(0, middleFloored + 1))
} else {
return getMedian(arr1.slice(middleFloored - 1), arr2.slice(0, middleFloored + 1))
}
} else {
return -1
}
} else {
return (Math.max(arr1[0], arr2[0]) + Math.min(arr1[1], arr2[1])) / 2
}
}
console.log(getMedian([10, 20, 30, 40, 51, 61, 71], [15, 25, 31, 86, 600, 700, 900])) // 45.5
// console.log(getMedian([3, 5, 8, 12, 15, 76, 85, 101, 354], [8, 9, 14, 17, 28, 52, 83, 95, 411])) // 22.5
// console.log(getMedian([3, 5, 8, 12, 15, 76, 85, 101], [8, 9, 14, 17, 28, 52, 83, 95])) // 16
// console.log(getMedian([15, 25, 31, 86, 600, 700, 900], [10, 20, 30, 40, 51, 61, 71])) // 45.5
// console.log(getMedian([3, 5, 8, 12, 15, 76, 85], [8, 9, 14, 17, 28, 52, 83])) // 14.5
// console.log(getMedian([1, 12, 15, 26, 38], [2, 13, 17, 30, 45])) // 16
// console.log(getMedian([-10, -4, 2, 5], [-8, 1, 4, 7])) // 1.5
// console.log(getMedian([], [])) // -1
benboorstein
Posted on
Top comments (0)