findHighestCommonNumberLists

// 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()