Sollicitatiegesprek voor de functie Front End Engineer

-Waterloo, ON


You are given an array of N elements in the form "property1: value1; property2: value2;...;propertyX: valueX;" for some some N and any X. There is also another array of M elements of the form "property: value". You are supposed to write an algorithm to remove every element in the N length array that has a "property: value" pair in the M length array. The trick is that the most intuitive solution of iterating through the M array and filtering the N array at each element is already written. You must come up with a solution that solves the problem in less than O(NM) time.


Antwoorden op sollicitatievragen

3 antwoorden


You can use HashMap to solve it with a time complexity of Max of O(N), O(M)

Akshay op


If I understand the question correctly, array N contain objects that only have one property value pair. 1. Sort array N by property name O(nlogn); 2. Iterate M and perform binary search on array N to remove. O(mlogn) You get O(2mlogn) by the end, which is still faster than O(mn)

Anoniem op


My interpretation of the problem - 1st array = [ { car: "honda", "name": "John"}, { car: "bmw", "name": "Johnny", "os": "ios"}, { car: "toyota", "name": "JohnX", "os": "android"}, ] 2nd array = [{ "car":"honda" }, { "os": "android" }]; As per the 1st post - create a map of the 2nd array - so it'll be O(1) lookup time, although a new space of O(M). I can't think of any other way besides filtering through the entire 1st array. So, if that 2nd array has N objects with max of X key, value pairs - just iterating through them will be O(NX). Qn for 2nd poster - how do you sort the 1st array?

Anoniem op

Voeg antwoorden of opmerkingen toe

Meld u aan of registreer u om hier een opmerking over te maken.