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

[Ajin Kabeer]

Thank you!

[Thorsten Hirsch]

But [...s1].filter(x => s2.has(x)) is still O(n²), isn't it?

• filter() will step through s1 (=outer forEach)
• s2.has() will check against each element in s2 (=inner forEach), probably exiting early

I'm pretty sure there is a O(s1) + O(s2) = O(n) solution.

[sleepingnapster]

Good answer but you lost the ordering when using sets.

[Thorsten Hirsch]

Yes, I've looked up how Set works and you're right. Thanks for clarifying.

Another cool solution (but not as readable as yours) however is this "destructive" one on SO.

[Idan Arye]

Rust solution - works for any number of strings:

fn find_intersection(strings: &[&str]) -> String {
    if strings.is_empty() {
        // NOTE: mathematically speaking, the result here should be **all** the numbers - but we
        // obviously can't return that...
        return "".to_owned(); // no arrays to intersect
    }
    let mut iterators: Vec<_> = strings.iter().map(
        |s| s.split(',').map(|n| n.trim().parse::<isize>().unwrap())
    ).collect();
    let mut current_values = Vec::with_capacity(iterators.len());
    for it in iterators.iter_mut() {
        if let Some(value) = it.next() {
            current_values.push(value);
        } else {
            return "".to_owned(); // at least one array is empty => intersection is empty
        }
    }
    let mut result = Vec::<String>::new();

    loop {
        let (min_value, min_count) = {
            let mut min_value = current_values[0];
            let mut min_count = 1;
            for value in current_values.iter().skip(1) {
                use std::cmp::Ordering::*;
                match value.cmp(&min_value) {
                    Less => {
                        min_value = *value;
                        min_count = 1;
                    },
                    Equal => {
                        min_count += 1;
                    },
                    Greater => {},
                }
            };
            (min_value, min_count)
        };
        if min_count == current_values.len() {
            result.push(min_value.to_string());
        }
        for (current_value, it) in current_values.iter_mut().zip(iterators.iter_mut()) {
            if *current_value == min_value {
                if let Some(value) = it.next() {
                    assert!(*current_value <= value, "numbers must be ordered");
                    *current_value = value;
                } else {
                    return result.join(", ");
                }
            }
        }
    }
}

[DownloadPizza]

Is there any difference between

String::from("")

and

"".to_owned()

?

[Idan Arye]

None that I'm aware of. I prefer "".to_owned() over String::from("") or "".to_string() to avoid the confusion of "why are you converting a string to a string?" that I've seen in some newbie Rust threads.

[Daan Wilmer]

function findIntersection($numbersAsStrings) {
    // parse the strings into numbers
    $numbersAsArrays = array_map(function($string) {
        return explode(', ', $string);
    }, $numbersAsStrings);

    // find the intersections
    $intersection = array_intersect(...$numbersAsArrays);

    // if empty, return string "false"; otherwise, return the numbers as a string
    if (empty($intersection)) {
        return 'false';
    } else {
        return implode(', ', $intersection);
    }
}

because I'd argue that letting your language work for you, and therefore optimizing developer time, is better than optimizing execution time when not strictly necessary.

[elisabethgross]

When the language solves the problem for you... touché

[Daan Wilmer]

To follow up: I made three versions of this code. The first version is as above, the second version has the naive approach to finding the intersection:

// find the intersections
$arrA = $numbersAsArrays[0];
$arrB = $numbersAsArrays[1];
$intersection = [];
foreach ($arrA as $num) {
    if (in_array($num, $arrB)) {
        $intersection[] = $num;
    }
}

and a third approach uses a map for lookup:

// find the intersections
$mapA = array_combine($numbersAsArrays[0], $numbersAsArrays[0]);
$mapB = array_combine($numbersAsArrays[1], $numbersAsArrays[1]);

$intersection = [];
foreach ($mapA as $num) {
    if (isset($mapB[$num])) {
        $intersection[] = $num;
    }
}

Performing some timed tests shows that using the built-in function consistently takes about two to three times as long as the self-built map-based function, growing at roughly O(n) using a random array of size 1000 and 10000. Only in exceptional cases would I not use the built-in function.
The naive approach, on the other hand, grows with O(n²) and takes significantly longer at larger array sizes. However, with 26ms with an array size of 1000, it depends on the use case whether I would start optimizing this (if this isn't easily replaced with a built-in function).

[elisabethgross]

Nice work!! Always always interesting to test out a language's built in methods and know whats what when it comes to time complexity.

[elisabethgross]

Nice solution! Love your use of Sets. Very concise and clear.

[Jonathan Jasson Huamani Cuadros]

This is my approach.

function intersection(stringArray) {
    const parseArray = (array) => [...new Set(array.split(',').map(item => item.trim()))];
    const [a, b] = stringArray;
    const aParsed = parseArray(a);
    const bParsed = parseArray(b);
    const mergedData = [...aParsed, ...bParsed];
    const counter = {};
    mergedData.forEach(item => {
        counter[item] = (counter[item] || 0) + 1;
    });
    return Object.entries(counter).filter(item => item[1] > 1).map(item => item[0]).join(',');
}

[elisabethgross]

Nice custom parseArray function!! And I like that use of Object.entries().

[artezan]

I used for loop so that improve the performance

const input = ["1, 3, 4, 7, 13", "1, 2, 4, 13, 15"]
function FindIntersection(strArr) {
  const inBothStrings = []
   const [arr1,arr2] = strArr.map(item => item.split(", "))

  for (let index = 0; index < arr1.length; index++) {
    const element1 = arr1[index];
    const indexFound= arr2.findIndex(element2 => element2 === element1)

    if (indexFound !== -1) {
      inBothStrings.push(element1)
      arr2.splice(indexFound, 1)
    }
  }
  return inBothStrings.length ? inBothStrings.join(',') : false 
}
console.log(FindIntersection(input))

[DownloadPizza]

Clarification question: can the lists have duplicate values?

[elisabethgross]

Good question! Nope, the lists will not have duplicates in themselves.

[Julian Finkler]

function FindIntersection(strArr) { 

  const allNumbers = strArr.reduce((c, a) => c = [...c, ...a.split(',').map(n => Number(n.trim()))], []);
  const numberCounts = {};
  const duplicates = [];
  allNumbers.forEach((n) => {
    if(!numberCounts.hasOwnProperty(n)){
      numberCounts[n] = 0;
    }
    if(++numberCounts[n] == strArr.length){
      duplicates.push(n);
    }
  })

  return duplicates.join(','); 

}