DEV Community

A common coding interview question

elisabethgross on November 25, 2019

Hey everyone! Welcome back to Code Review, a series of interview challenges released weekly that are completely free for the community. This week w...

Read full post

Daan Wilmer • Nov 25 '19

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.

Daan Wilmer • Nov 25 '19

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 • Nov 26 '19

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 • Nov 25 '19

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

Firee80 • Nov 27 '19

Hi! I wrote a solution that should be able to handle n-number of lines.
Also it does not care if there are duplicate numbers or they are out of order.
It just uses .map and .reduce.. probably it still could be optimized by using Set.

const lines = ['1,2,3,4,5,6', '2,4,6,7,8,9,10', '1,2,3,4,5,6,8']

const mapArrayToHashTable = items => {
  return items.reduce((last, item) => ({...last, [''+item]: item}), {}) 
}

const getHashTable = line => {
  const textNumbers = line.split(',')
  const numbers = textNumbers.map(number => parseInt(number))
  return mapArrayToHashTable(numbers)
}

const [firstTable, ...otherTables] = lines.map(getHashTable)

const result = otherTables.reduce((last, table) => {
  const keyObjs = Object.keys(table).map(key => last[key] ? {[key]: last[key]} : {})
  return keyObjs.reduce((last, keyObj) => ({...last, ...keyObj}), {})
}, firstTable)

console.log(Object.values(result)) // returns [2,4,6]

Firee80 • Nov 27 '19

simplified the solution by using Sets and corrected the answer to correspond the assignment

const lines = ['1,2,3,4,5,6', '2,4,6,7,8,9,10', '1,2,3,4,5,6,8']

function FindIntersection(lines) {
  const getSet = line => new Set(line.split(',').map(number => parseInt(number)))
  const [firstSet, ...otherSets] = lines.map(getSet)
  const result = [...otherSets.reduce((lastSet, set) => new Set([...set].filter(number => lastSet.has(number))), firstSet)]
  return result.length > 0 ? result : 'false'
}

console.log(FindIntersection(lines)) // outputs: [2,4,6]

Firee80 • Nov 27 '19

couldn't help myself.. improved the performance by sorting sets and checking result set. Changed the api from array input to n-amount of params. Also input is filtered from not a number

function FindIntersection(...lines) {  
  const getSet = (line = '') => {
    const numbers = line.split(',').map(number => parseInt(number))
    return new Set(numbers.filter(number => !isNaN(number)))
  }
  const sets = lines.map(getSet)
  const [shortestSet, ...otherSets] = [...sets].sort((setA, setB) => setA.size - setB.size)
  const defaultSet = lines.length > 1 ? shortestSet : new Set([])
  const resultSet = otherSets.reduce((resultSet, set) => {
    const commonNumbers = [...resultSet].filter(number => set.has(number))
    return new Set(commonNumbers)
  }, defaultSet)
  const result = [...resultSet]
  return result.length > 0 ? result : 'false'
}

console.log(FindIntersection()) // outputs: false
console.log(FindIntersection('1')) // outputs: false
console.log(FindIntersection('2', '3')) // outputs: false
console.log(FindIntersection('-1, 0', '0')) // outputs: [0]
console.log(FindIntersection('a, 3', 'b, c, 3')) // outputs: [3]
console.log(FindIntersection('-2, 3', '-4, -2')) // outputs: [-2]
console.log(FindIntersection('1,2,3,4', '2,3,4,5', '3,4,5,6')) // outputs: [3, 4]
console.log(FindIntersection('1,2,3,4,5,6', '2,4,6,7,8,9,10', '1,2,3,4,5,6,8')) // outputs: [2, 4, 6]
console.log(FindIntersection(...['1, 3, 4, 7, 13', '1, 2, 4, 13, 15'])) // outputs: [1, 4, 13]

Firee80 • Nov 28 '19

Decided to have a one more improvement for performance (when one Set has size = 0, so no need to reduce other Sets. Also result from reduce is directly an array of numbers).
Also my apologies to @elisabethgross as I noticed the tag #codenewbie in the challenge and my answer isn't really for newbies.

function FindIntersection(...lines) {  
  const getSet = (line = '') => {
    const numbers = line.split(',').map(number => parseInt(number))
    return new Set(numbers.filter(number => !isNaN(number)))
  }
  const sets = lines.map(getSet)
  const [shortestSet, ...otherSets] = [...sets].sort((setA, setB) => setA.size - setB.size)
  const setsToReduce = shortestSet && shortestSet.size > 0 ? otherSets : [] 
  const defaultCommonNumbers = lines.length > 1 ? [...shortestSet] : []
  const resultCommonNumbers = setsToReduce.reduce((commonNumbers, set) => 
    commonNumbers.filter(number => set.has(number)), defaultCommonNumbers)
  return resultCommonNumbers.length > 0 ? resultCommonNumbers : 'false'
}

console.log(FindIntersection()) // outputs: false
console.log(FindIntersection('1')) // outputs: false
console.log(FindIntersection('2', '3')) // outputs: false
console.log(FindIntersection('-1, 0', '0')) // outputs: [0]
console.log(FindIntersection('a, 3', 'b, c, 3')) // outputs: [3]
console.log(FindIntersection('-2, 3', '-4, -2')) // outputs: [-2]
console.log(FindIntersection('1,2,3,4', '2,3,4,5', '3,4,5,6')) // outputs: [3, 4]
console.log(FindIntersection('1,2,3,4,5,6', '2,4,6,7,8,9,10', '1,2,3,4,5,6,8')) // outputs: [2, 4, 6]
console.log(FindIntersection(...['1, 3, 4, 7, 13', '1, 2, 4, 13, 15'])) // outputs: [1, 4, 13]

Julian Finkler • Nov 26 '19

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(','); 

}

Juan Castillo • Nov 26 '19 • Edited

this is my solution, Im no pretty good at JS but I want to be a master on it :)

const FindIntersection  = (str) => {
  const arr = str.flatMap(i => i.split(', '))
  const itr = [...new Set(arr.filter((unique, index) => arr.indexOf(unique) !== index))]
  return itr.length ? itr : false
}

Juan Castillo • Nov 26 '19

ok, i have no idea to make my code look like editor

elisabethgross • Nov 27 '19 • Edited

Nice job! And try surrounding your code with triple backticks to format the code ;)

Juan Castillo • Dec 2 '19

thanks I made it :D i'll wait for more

DownloadPizza • Dec 4 '19

also you can put javascript directly after your backticks to make it have syntax highlighting (maybe its js, dont know, also works for other languages)

elisabethgross • Dec 4 '19

Pro tip!!

Idan Arye • Nov 25 '19

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 • Dec 2 '19

Is there any difference between

String::from("")

and

"".to_owned()

Idan Arye • Dec 2 '19

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.

Jonathan Jasson Huamani Cuadros • Nov 25 '19

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 • Nov 26 '19

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

Thorsten Hirsch • Nov 25 '19

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.

artezan • Nov 26 '19

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

Lisa Benmore • Nov 27 '19 • Edited

fwiw, another js option:

jsfiddle.net/4usxLhyo/1/

sorry, first post, not sure how to get the js syntax highlighting...
Edit: thanks @elisabethgross for the syntax highlighting help!

console.clear()

const one = '1,3,5,5,7,9,9';
const two = '2,4,5,6,8,9,9';
const three = '1,3,5,7,9';
const four = '2,4,6,8';

function findThings (str1, str2) {
  const arr1 = str1.split(',');
  const arr2 = str2.split(',');
  const result = [];

  for (const i of arr1) {
    if (arr2.indexOf(i) > -1) {
      result.push(i);
      arr2.splice(arr2.indexOf(i), 1);
    }
  }

  return result.length ? result : false;
}

console.log(findThings(one, two));
console.log(findThings(three, four )); ```

elisabethgross • Nov 28 '19 • Edited

Nice! If you use the triple backticks, you can write javascript next to the top triple backticks. Check out this helpful markdown cheat sheet!

Assaf Schwartz • Nov 28 '19 • Edited

Not a JS guy, so I decided to do it in Python.
As an interviewer, for these kind of question I'm not a fan of leveraging too much of the language built-ins (such as sets), as it masks algorithmic thinking, which I believe is an important part of the interview.

My solution uses a dictionary to count the number of occurrences for every item.

from collections import defaultdict

def find_intersect(strings):
    a, b = strings
    a = a.split(",")
    b = b.split(",")
    counter = defaultdict(int)
    intersect = list()
    for idx in range(max(len(a), len(b))):
        if idx < len(a):
            item = int(a[idx])
            counter[item]=counter[item]+1
            if counter[item] > 1:
                intersect.append(item)
        if idx < len(b):
            item = int(b[idx])
            counter[item]=counter[item]+1
            if counter[item] > 1:
                intersect.append(item)
    return intersect if intersect else "false"

elisabethgross • Nov 28 '19

I agree about not leveraging too many language built-ins, or, making sure to talk about the time complexity of those built-ins!

dillan teagle • Dec 7 '19 • Edited

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

Soham Mondal • Dec 8 '19

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" ;
}

Stoian Dan • Nov 28 '19 • Edited

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

SaiKumar Immadi • Dec 9 '19 • Edited

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.

Thorsten Hirsch • Nov 25 '19

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 • Dec 2 '19

Good answer but you lost the ordering when using sets.

Leonardo Alipazaga • Dec 4 '19

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;
    });
}

Philip Georgiev • Nov 26 '19

coderbyte.com/results/philipgg:Fin...

I submitted a 0(2n-a) where a is the number of repetitive elements.

The idea is to use that the arrays are sorted so always increment from where we are.

if the elements are matching, save and then increment both counters.

Else increment the count of the array which has the lower number, to try to find the bigger one. (this is auto-switching between the two.)

elisabethgross • Nov 27 '19

Nice! Was waiting for someone to come up with this one!

ferceg • Nov 28 '19

My solution was the same.
When it comes to challenges I prefer algorithms that can be written in pseudocode and don't use many special (or language-specific) data types.

DownloadPizza • Dec 2 '19 • Edited

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

Vaibhav Yadav • Dec 9 '19 • Edited

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;
}

Orion Aegis • Nov 26 '19

def sortedIntersection([a,b]):
  return any([map(set,a.split(', ')).intersection(b.split(', '))])

Would be the easiest to implement (I'm on my phone so I can't check it, also, python)

hariadon • Nov 26 '19

// I believe key here is that both arrays are sorted
function FindIntersection (strArr) {
const inBothStrings = []
const arr1 = strArr[0].split(', ')
const arr2 = strArr[1].split(', ')

let i=0,j=0;
while (i<arr1.length&&j<arr2.length){

//casting to numbers
let a = arr1[i]|0;
let b = arr2[j]|0;

if(a==b){
inBothStrings.push(a)
i++;
j++;
}
else if(a>b){

j++;
}
else if(b>a){
i++;
}

}

return inBothStrings.join(',')
}

elisabethgross • Nov 27 '19

Bingo! Nice work!

Anonymous • Feb 13 '20 • Edited

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

Ajin Kabeer • Nov 25 '19

Thank you!

elisabethgross • Nov 25 '19

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

Marko Bilal • Dec 6 '19

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

DownloadPizza • Nov 26 '19

Clarification question: can the lists have duplicate values?

elisabethgross • Nov 27 '19

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

DownloadPizza • Dec 4 '19 • Edited

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