daily[#391].js

// This problem was asked by Facebook.

// We have some historical clickstream data gathered from our site anonymously using cookies. 
// The histories contain URLs that users have visited in chronological order.
 
// Write a function that takes two users' browsing histories as input and returns 
// the longest contiguous sequence of URLs that appear in both.

// For example, given the following two users' histories:

// user1 = ['/home', '/register', '/login', '/user', '/one', '/two']
// user2 = ['/home', '/red', '/login', '/user', '/one', '/pink']

// You should return the following:
// ['/login', '/user', '/one']

function getLongestContiguous(arr1, arr2) {
  const transformInIndexes = (arr1, arr2) => {
    return arr1.map((e) => arr2.indexOf(e))
  }

  const getIndexLongestContiguous = (arr) => {
    let group = []
    let temp = []

    for (const [i, v] of arr.entries()) {
      if (arr[i+1] - v === 1 || v - arr[i-1] === 1) {
        temp.push(v)
      } else {
        if (temp.length > group.length) {
          group.push(temp[0])
          group.push(temp[temp.length - 1])
          temp = []
        }
      }
    }
    return group
  }

  const [start, end] = getIndexLongestContiguous(transformInIndexes(arr1, arr2))
  return arr2.slice(start, end + 1)
}


// Complexity: O(n^2)