Interview Questions

An array is of size N with integers between 0 ......

Microsoft Interview Questions and Answers


(Continued from previous question...)

104. An array is of size N with integers between 0 ......

Question:
An array is of size N with integers between 0 and 1024(repetitions allowed). Another array of integers is of size M with no constraints on the numbers. Find which elements of first array are present in the second array. (If you are using extra memory, think of minimizing that still, using bitwise operators)


maybe an answer:


// limited array has numbers from 0 to 1024 (inclusive)
// unlimited array has numbers without any constraint
// compute intersection in limited array and return total number of unique values

static int Intersection(int[] limited, int[] unlimited)
{
// 1025 unique values possible in the limited array
byte[] flags = new byte[(1025 + 7) / 8];
int idx, offset, uniqueValues = 0;

foreach (int x in limited)
{
idx = x >> 3;
offset = x & 7;
flags[idx] |= (byte) (1 << offset);
}

foreach (int x in unlimited)
{
idx = x >> 3;
offset = x & 7;
if ((flags[idx] & (byte) (1 << offset)) != 0)
{
limited[uniqueValues++] = x;


// turn off flag to avoid any repetitions
flags[idx] &= (byte) ~(1 << offset);
}
}

return uniqueValues;
}

(Continued on next question...)

Other Interview Questions