Write an algorithm to return the intersect of two arrays.

Question

AB · Accepted Answer

Martigan's answer should generally work but it has an O(n^2) running time. There's a better way using hashtables. Create a hashtable with all the elements in the first list. Then go through the second list, hash each entry, and compare to the first table. If there is a collision then the entry exists in both lists and should be added to the intersection list.

Harp B · Answer

In my interview, I first gave the first answer above, and then I gave the 2nd one mentioned above :p

Sigiloso · Answer

if no additional space is available for hash tables then the best time complexity seems to be n Log n + m Log m. Sort each array independently and then compare.

Martigan · Answer

/// 
/// Finds the array intersection points.
/// 
/// The first array list.
/// The second array list.
/// 
public static List FindArrayIntersections(List firstArrayList, List secondArrayList)
        {
            var intersectionPoints = new List();

            foreach (object firstObject in firstArrayList)
            {   
                foreach (object secondObject in secondArrayList)
                {
                    if(firstObject.Equals(secondObject))
                    {
                        intersectionPoints.Add(firstObject);
                    }
                }
            }
            return intersectionPoints;
        }

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas