A common coding interview question

Hey everyone! Welcome back to Code Review, a series of interview challenges released weekly that are completely free for the community. This week we’ll be working on a common, relatively straightforward question that I personally have been asked multiple times in interviews. I chose this challenge because there are multiple ways to approach the problem, each with various time and space trade-offs.

The Challenge:

Write a function, FindIntersection, that reads an array of strings which will contain two elements: the first element will represent a list of comma-separated numbers sorted in ascending order, the second element will represent a second list of comma-separated numbers (also sorted). Your goal is to return a string of numbers that occur in both elements of the input array in sorted order. If there is no intersection, return the string "false".

For example: if the input array is ["1, 3, 4, 7, 13", "1, 2, 4, 13, 15"] the output string should be "1, 4, 13" because those numbers appear in both strings. The array given will not be empty, and each string inside the array will be of numbers sorted in ascending order and may contain negative numbers.

The Brute Force Solution:

A brute-force solution is to loop over the numbers of the first string, and for each number in the first string, loop over all numbers of the other string, looking for a match. If a match is found, concat that value to a result string.

function FindIntersection (strArr) {
  const inBothStrings = []
  const arr1 = strArr[0].split(', ')
  const arr2 = strArr[1].split(', ')
  arr1.forEach(elementArr1 => {
    const numArr1 = parseInt(elementArr1)
    arr2.forEach(elementArr2 => {
      const numArr2 = parseInt(elementArr2)
      if (numArr1 === numArr2) {
        inBothStrings.push(numArr1)
      }
    })
  })
  return inBothStrings.join(',')
}

Although this will work, it is not the most optimal solution. The worst case scenario (if there are no matches) is that for every element in the first string, we will have to iterate through every element in the second string. This has a time complexity of O(nm) where n and m are the size of the given strings.

If you haven’t heard of Big O notation, check out this great article which goes into all the details. Understanding Big O notation and being able to communicate how optimal your solution is to an interviewer is an extremely important part of any technical interview.

Try it Out:

Head on over to Coderbyte and try and solve the problem in a more optimized way. Remember to come back next week where I’ll discuss some other solutions and common pitfalls to this problem. Good luck coding :)

Our newsletter 📫

We’re going to be sending out a small, feature reveal snippet every time we release something big, so our community is the first to know when we break out something new. Give us your email here and we'll add you to our "first to know" list :)

Comments

[Anonymous]

const FindIntersection = arr => {
  return arr[0].match(/\d+/g).filter(v => (
    arr[1].match(/\d+/g).includes(v)
  )).join`,` || false
}

[SaiKumar Immadi]

A simple and straightforward O(m+n) solution.

const FindIntersection = array => {
  const commonNumbers = [];

  const array1 = array[0].split(", ").map(num => Number(num));
  const array2 = array[1].split(", ").map(num => Number(num));

  let index1 = 0;
  let index2 = 0;

  while (index1 < array1.length && index2 < array2.length) {
    if (array1[index1] < array2[index2]) {
      index1 += 1;
    } else if (array2[index2] < array1[index1]) {
      index2 += 1;
    } else {
      commonNumbers.push(array1[index1]);
      index1 += 1;
      index2 += 1;
    }
  }

  return commonNumbers.join(", ");
};

EDIT: I just checked the next article and it has the same solution listed. Sorry I did not check that before posting this here.

[Vaibhav Yadav]

In JavaScript.

function findIntersection(strArr) {
  const arr = strArr.join(",").replace(/\s+/g, "").split(",");
  const count = {};
  const common = [];

  arr.map(i => count[i] ? count[i]++ : count[i] = 1);

  for (const i in count) {
    if (count[i] > 1) {
      common.push(parseInt(i, 10));
    }
  }

  return common.length ? common.sort((a, b) => a > b).join(",") : false;
}

[Soham Mondal]

This is my O(n) solution. We don't need to parse any of the strings to an integer.

const findIntersection = (arr) => {

  // n1 - larger array
  // n2 - smaller array

  let n1, n2;

  if (arr[0].split(',').length > arr[1].split(',').length) {
    n1 = arr[0].split(',');
    n2 = arr[1].split(',');
  } else {
    n1 = arr[1].split(',');
    n2 = arr[0].split(',');
  }

  let len = n1.length;

  // store the common items
  let common = [];

  for (let i = 0; i < len; i++) {

    // check if an item of one array (larger one) exists in the other array (smaller one)
    if (n2.includes(n1[i])) {
      common.push(n1[i]);
    }


  }

  return common.length ? common.join() : "false" ;
}

[dillan teagle]

import pytest



def findIntersection(arr):
    unique = list()
    duplicates = []
    for string in arr: 
        for char in string.split(','):
            if int("".join(char)) in unique:
                duplicates.append(int("".join(char)))
            else:
                unique.append(int("".join(char)))

    return duplicates



@pytest.mark.parametrize(
    ("arr_s", "expected"),
    (["1, 3, 4, 7, 13", "1, 2, 4, 13, 15"], [1, 4, 13]),
)
def test(arr_s, expected):
    assert findIntersection(arr_s) == expected




if __name__ == "__main__":
    x = ["1, 3, 4, 7, 13", "1, 2, 4, 13, 15"]
    print(findIntersection(x))

[Marko Bilal]

I dont understand why anyone would ask you this in an interview ? A massive red flag for me.

[Leonardo Alipazaga]

function FindIntersection(strArr) {
  return
    strArr
    .map(e => e.split(','))
    .reduce((listA, listB) => {
      const listFiltered = listA.filter(itemA => listB.includes(itemA));
      return listFiltered.length ? listFiltered : false;
    });
}

[DownloadPizza]

Kotlin (any number of strings): pl.kotl.in/Lgfcz5KnV?theme=darcula

[DownloadPizza]

use std::cmp::Ordering;

fn main() {
    let a = find_intersections([
        String::from("-2, -1, 1, 1, 1, 2, 3, 6"),
        String::from("-1, 1, 1, 3, 4, 5, 6")
    ]);
    println!("{}", a);
}

fn find_intersections(arr: [String; 2]) -> String {
    let mut inter : Vec<isize> = Vec::new();
    let mut a = arr[0].split(",").map(
        |e| e.trim().parse::<isize>().unwrap()
    );
    let mut b = arr[1].split(",").map(
        |e| e.trim().parse::<isize>().unwrap()
    );

    let mut tmp_a = a.next();
    let mut tmp_b = b.next();

    while tmp_a.is_some() && tmp_b.is_some() {
        match tmp_a.unwrap().partial_cmp(&tmp_b.unwrap()).expect("NAN is evil") {
            Ordering::Less => tmp_a = a.next(),
            Ordering::Equal => {inter.push(tmp_a.unwrap()); tmp_a = a.next();tmp_b = b.next()},
            Ordering::Greater => tmp_b = b.next(),
        }
    }

    if inter.is_empty() {
        return String::from("false")
    }
    return inter.into_iter().map(|x| x.to_string()).collect::<Vec<String>>().join(", ")
}

A rust solution, im quite new to rust, so this is probably quite ugly

[Stoian Dan]

Python solution, not in a nice format, and assuming the input are two integer arrays:

def common_arr(first, second):
    mi, ma = (first,second) if len(first) <= len(second) else (second,first)
    common = []
    i = 0
    j = 0
    while(i < len(mi)):
        if(mi[i] == ma[j]):
                common.append(mi[i])
                i += 1
                if j < len(ma)-1:
                    j += 1
                else:
                    break
        elif mi[i] < ma[j]:
            i += 1
        else:
            if j < len(ma)-1:
                j += 1
            else:
                break

    return common

arr = common_arr([1,2,3,4,5,9],[3,5,6,8,9])
print(arr)

So idea:
You iterate over the smallest array, at each step, you are in one of 3 situations

arr1[i] == arra2[j] // you increment i and j because of the invariant, that says the arrays are sorted, so if you found a match you can safely increment.

arr1[i] < arr2[j] // since at index i we have the smallest element, we increment that one because being sorter we ca safely increment until we hit what is at index j or greater

arr1[i] < arr2[j] // same as above only for j