Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Math/CompSci Interview Question - Thoughts?

Reply
Thread Tools

Math/CompSci Interview Question - Thoughts?

 
 
Andrew Tomazos
Guest
Posts: n/a
 
      11-21-2009
I was posed the following question in a technical interview for a
Software Engineering position by a major multinational NASDAQ company:

[Paraphrasing] "You are given an array of 1,000,000 32-bit integers.
One int value x occurs 500,001 times or more in the array. Specify an
algorithm to determine x."

The assumption being extra points for efficiency.

I initially came up with a linear space, linear time solution. With
some prompting and hints from the interviewer we worked our way to a
smaller constant space and linear time algorithm. That being
basically:

int findmode(int* p, int n)
{
int count[32];
for(int i = 0; i < 32; i++)
count[i] = 0;

for (int i = 0; i < n; i++)
for (int j = 0; j < 32; j++)
if (p[i] & (1 << j)) // if bit j is on
count[j]++;
else
count[j]--;

int x = 0;
for (int i = 0; i < 32; i++)
if (count[i] > 0)
x = x | (1 << i);

return x;
}

The idea here is to count the frequency of each of the 32 bits in the
array separately, knowing that these bit counts will be dominated by
the mode.

The interviewer already knew the answer, so I can only assume the test
was based on how much help he had to give me to arrive at it.

My question about this is as follows. I, perhaps boldly, claim to
employers to have a "masters-equivilant" experience/knowledge of
computer science and math. Should I have been able to come up with
this solution without prompting or help?

Would you expect someone with a CompSci Masters or PhD from some major
ivy league university to be able to come up with this solution without
help?

If so in what course or from which book would you expect to learn the
required knowledge to come up with the above solution?

Is the skill to be able to come up with such an algorithm something
that is learned by studying lots of algorithms and being able to mix
and match the "tricks"? If so, what is a similar commonly known
algorithm(s) on which the above solution could have been based?

Or, is the ability to invent such a solution simply a matter of IQ?
Some people have the talent to solve the puzzle, see the pattern and
come up with the solution - and some just don't?

Thanks,
Andrew.
 
Reply With Quote
 
 
 
 
Pascal J. Bourguignon
Guest
Posts: n/a
 
      11-21-2009
Andrew Tomazos <(E-Mail Removed)> writes:

> I was posed the following question in a technical interview for a
> Software Engineering position by a major multinational NASDAQ company:
>
> [Paraphrasing] "You are given an array of 1,000,000 32-bit integers.
> One int value x occurs 500,001 times or more in the array. Specify an
> algorithm to determine x."
>
> The assumption being extra points for efficiency.
>
> I initially came up with a linear space, linear time solution. With
> some prompting and hints from the interviewer we worked our way to a
> smaller constant space and linear time algorithm. That being
> basically:
>
> int findmode(int* p, int n)
> {
> int count[32];
> for(int i = 0; i < 32; i++)
> count[i] = 0;
>
> for (int i = 0; i < n; i++)
> for (int j = 0; j < 32; j++)
> if (p[i] & (1 << j)) // if bit j is on
> count[j]++;
> else
> count[j]--;
>
> int x = 0;
> for (int i = 0; i < 32; i++)
> if (count[i] > 0)
> x = x | (1 << i);
>
> return x;
> }
>
> The idea here is to count the frequency of each of the 32 bits in the
> array separately, knowing that these bit counts will be dominated by
> the mode.
>
> The interviewer already knew the answer, so I can only assume the test
> was based on how much help he had to give me to arrive at it.
>
> My question about this is as follows. I, perhaps boldly, claim to
> employers to have a "masters-equivalant" experience/knowledge of
> computer science and math. Should I have been able to come up with
> this solution without prompting or help?


If what you're asking is whether anybody having a master in CS and
maths would have been able to come up with this solution in the
interview time, I guess we can answer that definitely no, otherwise
there would be no point in trying to select candidates with this test.

Obviously, it's because some people (with or without a master diploma,
this really isn't relevant) get or don't get it, that this test is
useful for the recruiter.



Now if you want this kind of jobs, yes you should better be able to
come up with smart solutions to little puzzles like this in
interviews.




> Would you expect someone with a CompSci Masters or PhD from some major
> ivy league university to be able to come up with this solution without
> help?
>
> If so in what course or from which book would you expect to learn the
> required knowledge to come up with the above solution?


Not a single one. You have to develop your knowledge of algorithms,
mathematics, your symbolic thinking and your imagination in these
matters.


> Is the skill to be able to come up with such an algorithm something
> that is learned by studying lots of algorithms and being able to mix
> and match the "tricks"?


That could help yes. I'd tend to think that imagination is the most
important ingredient here, to be able to come with a possible solution
fast enough.

Also, don't limit yourself to CS and maths, there are ideas to be
taken from other domains too.


> If so, what is a similar commonly known
> algorithm(s) on which the above solution could have been based?
>
> Or, is the ability to invent such a solution simply a matter of IQ?


CS IQ, yes, if such a IQ test exists.


> Some people have the talent to solve the puzzle, see the pattern and
> come up with the solution - and some just don't?


It seems so. At least, in a given time.

--
__Pascal Bourguignon__
 
Reply With Quote
 
 
 
 
GJ Woeginger
Guest
Posts: n/a
 
      11-21-2009
In comp.theory Andrew Tomazos <(E-Mail Removed)> wrote:
# I was posed the following question in a technical interview for a
# Software Engineering position by a major multinational NASDAQ company:
#
# [Paraphrasing] "You are given an array of 1,000,000 32-bit integers.
# One int value x occurs 500,001 times or more in the array. Specify an
# algorithm to determine x."
#
# The assumption being extra points for efficiency.

There is an old analysis of this problem by Fischer and Salzberg.
M.J. Fisher and S.L. Salzberg (1982)
Finding a majority among n votes.
Journal of Algorithms 3, pp 143-152.

If 2k elements contain a majority element (= an element that occurs at
least k+1 times), then you can find it with 3k-2 element comparisons
(and some small overhead). The basic idea in their algorithm is that
whenever you find two distinct elements, then you can destroy both without
changing the majority element among the remaining elements. This yields:

Run once through the array, and maintain a majority-candidate and a counter.
The majority-candidate is initialized as the first element, and
the counter (counting how often you have seen the candidate) is
initialized at 1.
If you hit the current candidate again, increment the counter.
If you hit another element, decrement the counter.
If the counter becomes 0, drop the current candidate and start from
scratch with the remaining part of the array.

Fischer and Salzberg also show that this bound 3k-2 is best possible in
the worst case (and that's the main part of their paper).

--Gerhard

__________________________________________________ _________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
 
Reply With Quote
 
A.G.McDowell
Guest
Posts: n/a
 
      11-21-2009
In article <(E-Mail Removed)
s.com>, Andrew Tomazos <(E-Mail Removed)> writes
>I was posed the following question in a technical interview for a
>Software Engineering position by a major multinational NASDAQ company:
>
>[Paraphrasing] "You are given an array of 1,000,000 32-bit integers.
>One int value x occurs 500,001 times or more in the array. Specify an
>algorithm to determine x."
>
>The assumption being extra points for efficiency.
>
>I initially came up with a linear space, linear time solution. With
>some prompting and hints from the interviewer we worked our way to a
>smaller constant space and linear time algorithm. That being
>basically:
>

This sort of problem is covered by articles on Data Stream Processing in
CACM Oct 2009. (CACM is a lot more interesting these days than it was
some years ago). There are some very neat ideas in there, of which the
algorithm "MAJORITY" matches the question reasonably well. Proving that
it works under interview conditions would be extremely impressive,
though.

This is not the first time that I have heard of interview questions that
discuss issues recently covered in the computing literature. I am unable
to tell whether these come from a desire to know if the candidate keeps
themselves abreast of the subject, or from the interviewer grasping the
first thing that comes to hand when they are trying to think up a
question. The few times that I have posed interview questions, I have
tried to find evidence in the candidate of a knowledge of basic theory
or mathematics that I could show was relevant to the job for which we
were trying to recruit.
--
A.G.McDowell
 
Reply With Quote
 
Bill Dubuque
Guest
Posts: n/a
 
      11-21-2009
http://www.velocityreviews.com/forums/(E-Mail Removed) (Richard Harter) wrote:
>Andrew Tomazos <(E-Mail Removed)> wrote:
>>
>>I was posed the following question in a technical interview for a
>>Software Engineering position by a major multinational NASDAQ company:
>>
>>[Paraphrasing] "You are given an array of 1,000,000 32-bit integers.
>>One int value x occurs 500,001 times or more in the array. Specify an
>>algorithm to determine x."
>>
>>The assumption being extra points for efficiency. [snip code] The idea
>>is to count the frequency of each of the 32 bits in the array separately,
>>knowing that these bit counts will be dominated by the mode. [...]
>>
>>My question about this is as follows. I, perhaps boldly, claim to
>>employers to have a "masters-equivilant" experience/knowledge of
>>computer science and math. Should I have been able to come up with
>>this solution without prompting or help?
>>Would you expect someone with a CompSci Masters or PhD from some major
>>ivy league university to be able to come up with this solution without
>>help? If so in what course or from which book would you expect to learn
>>the required knowledge to come up with the above solution?

>
> That's an interesting question with an interesting presupposition.
> The first thing to understand is that this is a puzzle rather than
> a programming problem.


I disagree. Saying that it's a puzzle rather than a programming problem
seems to imply that the solution is ad-hoc, rather than a special case
of some more universal technique. But that is not true here. Namely,
the proposed solution follows immediately from the obvious fact that
majority elts on product sets are preserved by component projections.
So the solution is simply an instance of well-known divide-and-conquer
techniques for product objects. Such reductions are ubiquitous in both
mathematics and computer science. So I would expect a good student
to find this solution given enough time. I'd also expect a student
from a top-tier school to discover the more optimal solution, viz.

bi != a => Maj({a^k b1 b2... bk} \/ S) = Maj(S)

via m/n > 1/2 => (m-k)/(n-2k) > 1/2 via mediants/arithmetic

again, assuming enough time. But that assumption is highly problematic
when it comes to designing tests that quickly measure various skills.
It's impossible to test such in the short time span of an interview.
It remains difficult even in much longer timed tests. For example
many of the most successful mathematicians did not perform well on
the Putnam competition, and some of those who did well didn't turn
out to be exceptional mathematicians. Thus there isn't necessarily
much correlation between intelligence and random test scores.

Marilyn vos Savant is a prime example. The woman who supposedly
has the "world's highest IQ" published a Parade magazine column [1]
and book [2] on Wiles proof of FLT. Her nonsensical arguments proved
beyond a doubt that she has absolutely no clue about higher math
and, worse, doesn't have the intelligence to know that (even after
many experts pointed out gaping flaws in her very naive arguments).
So much for IQ tests.

--Bill Dubuque

[1] sci.math, 11/29/1993, Full Text of Savant FLT Parade Article
http://google.com/group/sci.math/msg/8cb44534c63372ad
http://google.com/groups?selm=WGD.93...gny.ai.mit.edu

[2] Boston, Nigel; Granville, Andrew.
Review of: The World's Most Famous Math Problem (The Proof
of Fermat's Last Theorem and Other Mathematical Mysteries)
by Marilyn vos Savant
The American Mathematical Monthly, 102, 5, 1995, 470-473
http://www.dms.umontreal.ca/~andrew/PDF/VS.pdf
http://www.jstor.org/stable/2975048
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      11-21-2009
* Bill Dubuque:
>
> I disagree. Saying that it's a puzzle rather than a programming problem
> seems to imply that the solution is ad-hoc, rather than a special case
> of some more universal technique. But that is not true here. Namely,
> the proposed solution follows immediately from the obvious fact that
> majority elts on product sets are preserved by component projections.
> So the solution is simply an instance of well-known divide-and-conquer
> techniques for product objects. Such reductions are ubiquitous in both
> mathematics and computer science. So I would expect a good student
> to find this solution given enough time. I'd also expect a student
> from a top-tier school to discover the more optimal solution, viz.
>
> bi != a => Maj({a^k b1 b2... bk} \/ S) = Maj(S)
>
> via m/n > 1/2 => (m-k)/(n-2k) > 1/2 via mediants/arithmetic


Hiya. Could you please explain the above more optimal solution. I'm unfamiliar
with the notation and not from a top-tier school, but in my experience anything
that's not nonsense can be visualized or explained in simple terms (e.g., Albert
Einstein did that beautifully with his book on special relativity, which except
for one little proof in an appendix -- I didn't yet know anything about
solving sets of equations with multiple variables -- I found eminently
grokkable as a teenager, so should also be possible for the above, yes?).

Cheers & TIA.,

- Alf
 
Reply With Quote
 
Axel Vogt
Guest
Posts: n/a
 
      11-21-2009
Andrew Tomazos wrote:
> I was posed the following question in a technical interview for a
> Software Engineering position by a major multinational NASDAQ company:
>
> [Paraphrasing] "You are given an array of 1,000,000 32-bit integers.
> One int value x occurs 500,001 times or more in the array. Specify an
> algorithm to determine x."
>
> The assumption being extra points for efficiency.

<snipped>

Being a bit stupid I first would ask "Why? What do you do with it?"
and then I would pick on random. I am almost certain, that even at
a low number of draws the chance to get the very integer is higher
than implementing an algo without coding errors.
 
Reply With Quote
 
Andrew Tomazos
Guest
Posts: n/a
 
      11-21-2009
On Nov 21, 10:53*pm, "Alf P. Steinbach" <(E-Mail Removed)> wrote:
> * Bill Dubuque:
>
>
>
> > I disagree. Saying that it's a puzzle rather than a programming problem
> > seems to imply that the solution is ad-hoc, rather than a special case
> > of some more universal technique. But that is not true here. Namely,
> > the proposed solution follows immediately from the obvious fact that
> > majority elts on product sets are preserved by component projections.
> > So the solution is simply an instance of well-known divide-and-conquer
> > techniques for product objects. Such reductions are ubiquitous in both
> > mathematics and computer science. So I would expect a good student
> > to find this solution given enough time. I'd also expect a student
> > from a top-tier school to discover the more optimal solution, viz.

>
> > * * * * bi != a *=> *Maj({a^k b1 b2... bk} \/ S) *= *Maj(S)

>
> > *via *m/n > 1/2 *=> *(m-k)/(n-2k) > 1/2 * via mediants/arithmetic

>
> Hiya. Could you please explain the above more optimal solution.


Dubuque is referring to the solution that Woeginger more lucidly
described above. Both it and the bit counting method are
asymptotically equivalent solutions to the original problem. I'm sure
either of these solutions provided on the spot would have received
"full marks".

I guess what I am curious about is exactly what percentage of, say...
CS PhD students at tier one universities, would be able to come up
with either of these solutions on the spot. 80%, 50% or 20% ? I
guess only someone that has interviewed many people with these sort of
problems has the necessary data to answer my question.
-Andrew.
 
Reply With Quote
 
Andrew Tomazos
Guest
Posts: n/a
 
      11-22-2009
On Nov 21, 6:29*pm, (E-Mail Removed)-graz.ac.at (GJ Woeginger)
wrote:
> In comp.theory Andrew Tomazos <(E-Mail Removed)> wrote:
> # I was posed the following question in a technical interview for a
> # Software Engineering position by a major multinational NASDAQ company:
> #
> # [Paraphrasing] *"You are given an array of 1,000,000 32-bit integers.
> # One int value x occurs 500,001 times or more in the array. *Specify an
> # algorithm to determine x."
> #
> # The assumption being extra points for efficiency.
>
> There is an old analysis of this problem by Fischer and Salzberg.
> * M.J. Fisher and S.L. Salzberg *(1982)
> * Finding a majority among n votes.
> * Journal of Algorithms 3, pp 143-152.
>
> If 2k elements contain a majority element (= an element that occurs at
> least k+1 times), then you can find it with 3k-2 element comparisons
> (and some small overhead). *The basic idea in their algorithm is that
> whenever you find two distinct elements, then you can destroy both without
> changing the majority element among the remaining elements. *This yields:
>
> *Run once through the array, and maintain a majority-candidate and a counter.
> *The majority-candidate is initialized as the first element, and
> * *the counter (counting how often you have seen the candidate) is
> * *initialized at 1.
> *If you hit the current candidate again, increment the counter.
> *If you hit another element, decrement the counter.
> *If the counter becomes 0, drop the current candidate and start from
> * *scratch with the remaining part of the array.
>
> Fischer and Salzberg also show that this bound 3k-2 is best possible in
> the worst case (and that's the main part of their paper).


If I understand your description than it would look like:

int findmode(int* p, int n)
{
int x = p[0];
int c = 1;

for (int i = 1; i < n; i++)
{
if (c == 0)
{
x = p[i];
c = 1;
}
else if (p[i] == x)
c++;
else
c--;
}

return x;
}

It seems that this could only produce at maximum (2k-1) comparisions
in the worst case, not (3k-2) as you claim?
-Andrew.
 
Reply With Quote
 
Andrew Tomazos
Guest
Posts: n/a
 
      11-22-2009
On Nov 22, 1:01*am, Andrew Tomazos <(E-Mail Removed)> wrote:
> On Nov 21, 6:29*pm, (E-Mail Removed)-graz.ac.at (GJ Woeginger)
> wrote:
>
>
>
> > In comp.theory Andrew Tomazos <(E-Mail Removed)> wrote:
> > # I was posed the following question in a technical interview for a
> > # Software Engineering position by a major multinational NASDAQ company:
> > #
> > # [Paraphrasing] *"You are given an array of 1,000,000 32-bit integers.
> > # One int value x occurs 500,001 times or more in the array. *Specify an
> > # algorithm to determine x."
> > #
> > # The assumption being extra points for efficiency.

>
> > There is an old analysis of this problem by Fischer and Salzberg.
> > * M.J. Fisher and S.L. Salzberg *(1982)
> > * Finding a majority among n votes.
> > * Journal of Algorithms 3, pp 143-152.

>
> > If 2k elements contain a majority element (= an element that occurs at
> > least k+1 times), then you can find it with 3k-2 element comparisons
> > (and some small overhead). *The basic idea in their algorithm is that
> > whenever you find two distinct elements, then you can destroy both without
> > changing the majority element among the remaining elements. *This yields:

>
> > *Run once through the array, and maintain a majority-candidate and a counter.
> > *The majority-candidate is initialized as the first element, and
> > * *the counter (counting how often you have seen the candidate) is
> > * *initialized at 1.
> > *If you hit the current candidate again, increment the counter.
> > *If you hit another element, decrement the counter.
> > *If the counter becomes 0, drop the current candidate and start from
> > * *scratch with the remaining part of the array.

>
> > Fischer and Salzberg also show that this bound 3k-2 is best possible in
> > the worst case (and that's the main part of their paper).

>
> If I understand your description than it would look like:
>
> int findmode(int* p, int n)
> {
> * * int x = p[0];
> * * int c = 1;
>
> * * for (int i = 1; i < n; i++)
> * * {
> * * * *if (c == 0)
> * * * *{
> * * * * * x = p[i];
> * * * * * c = 1;
> * * * *}
> * * * *else if (p[i] == x)
> * * * * * *c++;
> * * * *else
> * * * * * *c--;
> * * }
>
> * * return x;
>
> }
>
> It seems that this could only produce at maximum (2k-1) comparisions
> in the worst case, not (3k-2) as you claim?
> * -Andrew.


Oh wait... the (c==0) counts as a comparison. I see it now. Ignore
me.
-Andrew.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
ASP Interview Questions ASP Interview Questions reema ASP General 0 08-26-2008 11:57 AM
.NET Interview Question, C#, ASP.NET Interview Questions dotnetuncle Javascript 0 10-30-2007 03:08 PM
An interview question Jerry Java 22 06-12-2005 03:55 PM
Interview question Gopal Krish ASP .Net 10 10-23-2004 10:18 AM
interview question (toughest bug you've fixed)? Digital Puer Java 17 12-27-2003 09:35 AM



Advertisments