vaibhavrastogi4
BAN USER- 0of 0 votes
AnswersHi, I was asked a this one at the interview. Below is the problem statement:
- vaibhavrastogi4 in United States
1) I have a array of n bitstring elements of width m bits, for example:
{1001, 0101, 1100, 0011, 1111, 0000, 0001}
2) We have to apply a filter such that out of these n elements, only k elements pass through the filter while the rest gets blocked, for example
{1001, 0101, 1100, 0011, 1111, 0000, 0001} -- filter -- > {1001, 1100, 1111}
3) Filter has been designed based on a concept of mask and ID.
mask: It tells which bits to consider out of the m bit bitstring elements. Only those bits which are set to '1' would be used for checking while the rest be ignored. for example, a mask of {1000} would mean only 4th bit would be considered for checking while the filter won't care about the other bits of an element.
ID: It is the allowed value for the designed mask. for example, an ID of 1xxx (where x is don't care) with a mask of 1000 means that any element which has 4th bit as '1' would be allowed while if the 4th bit is '0', that element would be blocked. Since the mask doesn't check the 1st, 2nd and 3rd bit, any value, '1' or '0' would be allowed to be passed through the filter
For the above example, a single mask of 1000 and ID of 1xxx solves the problem. We need to find a generic solution for any set of n elements and k allowed elements. All of the k element might not get covered by a single mask and ID. We need to find the optimum solution using minimum number of mask,ID sets with their values.| Report Duplicate | Flag | PURGE
Cisco Systems SDE-2 Algorithm
Result needs to be passed as an list of all the filters. In best case, one filter would cover all elements. Otherwise, we need to get the optimum number of filters to do the same.
- vaibhavrastogi4 August 14, 2014