Skip to content

Instantly share code, notes, and snippets.

@benmarten
Created February 6, 2018 00:56
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save benmarten/bfa8a5370df5b6672c4e04763c778404 to your computer and use it in GitHub Desktop.
// Problem: Generate two random lists, filled with integers.
// Find the second highest common number. Optimize for performance.
const SIZE_MAX = 100
const INT_MAX = SIZE_MAX
class List {
static generateRandomList() {
let size = Math.round(Math.random() * SIZE_MAX)
let result = [size]
for (let i = 0; i < size; i++) {
result[i] = Math.round(Math.random() * INT_MAX)
}
return result
}
static toMap(list) {
let result = {}
for (let i = 0; i < list.length; i++) {
result[list[i]] = i;
}
return result
}
}
class Solver {
static recordHighs(highs, item) {
// Record highest and second highest numbers
if (item > highs.first) {
highs.second = highs.first // Shift first to second place
highs.first = item
}
if (item != highs.first && item > highs.second) {
highs.second = item
}
}
static findHighestCommonNumber(listA, listB) {
// Convert first list to a Hashmap
let mapA = List.toMap(listA) // O(n)
let mapB = List.toMap(listB) // O(n)
let highs = {
first: -1,
second: -1
}
// Loop over all items of list B and check if they are in hashmap A
// O(n)
for (let i = 0; i < listB.length; i++) {
let itemInB = listB[i]
if (mapA[itemInB] !== undefined) {
// Delete item from list A, to keep track of processed numbers
delete mapA[itemInB]
this.recordHighs(highs, itemInB)
}
}
// Loop over the rest of the items from hashmap a, that haven't been checked yet.
// At worst O(n)
let restOfA = Object.keys(mapA)
for (var i = 0; i < restOfA.length; i++) {
let itemInA = restOfA[i]
if (mapB[itemInA] !== undefined) {
this.recordHighs(highs, itemInA)
}
}
return highs
}
}
function main() {
let listA = List.generateRandomList()
let listB = List.generateRandomList()
console.log(`List A: ${JSON.stringify(listA)}`)
console.log(`List B: ${JSON.stringify(listB)}`)
let highs = Solver.findHighestCommonNumber(listA, listB)
if (highs.second > -1) {
console.log(`Second highest number in common, is: ${highs.second}`)
} else if (highs.first > -1) {
console.log(
`There's no second highest number in common, only number in common is: ${highs.first}`)
} else {
console.log(`There's no numbers in common.`)
}
}
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment