Sollicitatievraag

Sollicitatiegesprek voor de functie Front End Engineer

-

Meta

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.

Antwoord

Antwoorden op sollicitatievragen

5 antwoorden

2

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

Akshay op

0

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

0

Store the values of the array of M size in a Set(). Then use a filter method for array of N size, and exclude elements, which are present in the set.

Anoniem op

0

One possible answer looks something like this: 1. You make a hash from N array if form: { "prop1:value1": Set("prop1:value1;prop2,value2"), "prop2:value2": Set("prop1:value1;prop2:value2") ... } 2. Create blacklist set. Iterate over M array. For each entry, add entries from hash for prop to a blacklist set. 3. Iterate over N array again. Collect all props which are not in blacklist set.

Anoniem op

0

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

Voeg antwoorden of opmerkingen toe

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