DhiwaTdG - 2 months ago 16

C Question

I need to write a function which returns the intersection

`(AND condition)`

If my query is given by:

`query[] = {"num>20", "avg==5", "deviation != 0.5"}`

`n`

`0`

`length of query`

`get_sample_ids`

`get_sample_ids`

`query[] = {"num>20", "avg==5", "deviation != 0.5"}`

int intersected_array*;

for n=0:query.length-1

int arr* = get_sample_ids(query[n]);

// n=0: [1, 7, 4, 2, 6]

// n=1: [3, 6, 2]

// n=2: [6, 2]

end;

Expected output: intersected_array* = [6, 2]

I've coded an implementation which has 2 arrays (

`arr*`

`temp*`

`temp*`

`arr*`

`temp*`

`arr*`

Answer

This is quite efficient but could be tiresome to implement (haven't tried it).

- Determine the
`shortest`

array. Benefit of using C is that if you don't know their length, you can use the pointers to arrays to determine it if they are placed sequentially in memory. - Make a
`<entry,boolean>`

hash`map`

for the entries in`shortest`

. We know the size and if anything it's only going down in next steps. - Iterate through an array. Start by initiating the whole
`map`

to false. For each entry check it in`map`

. - Iterate through
`map`

deleting all the entries that weren't checked. Set all the values to false. - If there any new arrays left go back to step
**3.**with a new array. - The result are the keys in the final
`map`

.

It looks like much but we didn't have to resort to any high complexity measures. Key to good performance is using hash map because of constant access time.

**Alternatively:**

Make the `map`

be `<entry,int>`

. This way you can count up all the recurrences and don't have to reset it at every iteration, which adds to complexity.

At the end just compare the number of array's to the the values in `map`

. Those that match are your solution.

**Complexity:**

Seems like O(n).