You can follow up on mostyfriedman's idea where you use open addressing to make the index-of method run in constant time.

When comparing two arrays c1 and c2 you can find the lowest number m and the highest number n.
Then create two int arrays a1 and a2 of size n-m initializing them to 0.
For each number i in c1 increment a1[i-m] by one.
For each number i in c2 increment a2[i-m] by one.
Now you can compare a1 and a2 to find not only the common elements but also the number of the duplicate elements.

O(N) for k = 2 and O(k*N) more generally.
There are some possible nasty complexities not shown in those variables as the running time and space requirement is dependent on the difference between the maximum and minimum numbers.

pbl, on 17 February 2012 - 10:05 PM, said:

It is not true because one of the loops relies on the number of k collections not the length of the longest array. It definitely holds that the algorithms runs in O(kn²) because that is an upper bound.
Remember, you only have to consider the worst case running time.

Using BitSet was an interesting idea and definitely something worth knowing, but I don't see how your application of it works in this case when duplicates must be counted. You improve the performance by discarding information. Do not that it does not change the worst case running time as expressed in O-notation.

I read through your assignment and it said both that it must be comparsion based that the running time must be less than kN^2, i.e. less than quadratic time. It also said that you should only consider worst-case running time.

It doesn't appear that you have to find a linear algorithm. Am I missing something?
Btw. note that the worst case running time with hash tables is not linear unless you have perfect hashing.

Crap, didn't notice
I didn't consider the dates using the Related Topics.
Sorry about that

As you clearly know a formula in prenex normal form is a formula which starts with all the quantifiers over a quantifier-free formula.
Converting a formula to prenex normal form means to create an equivalent formula which is in prenex normal form.
So the answer to your question is that your conversion is correct if: (By === I mean equivalence)

ExAy ( B(x,y) OR AxEy (S(x,y) AND R(y)) ) === ExAyAgEh ( B(x,y) OR (S(g,h) AND R(h)) )


To help us verify this we can check the correctness of each step.
The renaming is done to prevent ambiguity. I will not go into why your renaming is correct.
The second part where you take the quantifiers outside the parenthesis concerns me.
Not because it is wrong, but because that while simply moving the quantifiers outside the parenthesis preserves equivalence with disjunction it is not the case with negation and some implications.

You have that:
B(x) OR Ag(S(g)) = Ag(B(x) OR S(g))
B(x) OR Eh(R(h)) = Eh(B(x) OR R(h))

On the other hand with negation the rules are like this:
~Ag(S(g)) = Eg~(S(g))
~Eh(R(h)) = Ah~(R(h))

For implications with quantifications in the antecedent the rules are like this:
Ag(S(g)) => B(x) = Eg(S(g) => B(x))
Eg(R(h)) => B(x) = Ag(R(h) => B(x))


It is sorta strange to understand this as first. You can test yourself by trying to convert this formula into prenex normal form:
ExAy ( B(x,y) OR ~Ax((EyS(x,y)) => R(x)) )

I started to laugh when she answered the phone. That was great.

Of course you shouldn't take the advices too literally. If you think something works better for the job you are getting an interview for you should naturally go for that.
If for example you know that people normally wears jeans and t-shirts then I would go for that, if people normally wear suits I would go for that. (This should be taken with a grain of salt as well)

Preparation increases the likelihood of acing an interview. That is one thing you can do. Study the employer. Find standard/common interview questions and reflect over them. You can perhaps write down answer as well as possible discussions. Don't take it with you, it's more to help make your thoughts more concrete. This helps should the nerves get to you.
This is what I'll intend to do

I had an interesting job interview experience once. One of the interviewers asked me to tell a joke. Taken aback I told a perverted joke. I got the job so that was nice, but it still was a memorable experience.