Math/CompSci Interview Question - Thoughts?

[James Kanze]

On Nov 21, 6:29 pm, (e-mail address removed)-graz.ac.at (GJ Woeginger)
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;
c = 1;
}
else if (p == 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?

Oh wait... the (c==0) counts as a comparison. I see it now.
Ignore me.

I don't think the (c==0) counts as a comparison.

Of course it does. Why wouldn't it?

I think the other k-1 comparisons are for the 2nd
part of the algorithm, when you make one more pass
through the array verifying the candidate found in
the 1st part. [You already know the index i for
one occurrence of the candidate, so only the other
k-1 indices have to be checked.]

What second part? There is no second pass.

 

[GJ Woeginger]

# (e-mail address removed)-graz.ac.at (GJ Woeginger) writes:
#
# > 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.
#
# I can't track this down. Have I got the right Journal of Algorithms?
#
# http://www.informatik.uni-trier.de/~ley/db/journals/jal/jal3.html
#
# does not list that paper. Of course, this table of contents might be
# wrong. The horrendous link:
#
# http://www.sciencedirect.com/scienc...serid=10&md5=2c8bc9013d6025d08b7d24d3207dfe18
#
# appears to be for the journal itself. The paper does not appear
# there, either.


I gave the wrong page numbers. It should be
M.J. Fisher and S.L. Salzberg (1982)
Finding a majority among n votes.
Journal of Algorithms 3, pp 375-379

And it is not an independent paper, but the discussion of
problem 81-5 in the problems column of Leo Guibas.

I also messed up the statement of the main result of Fisher and Salzberg:
The 3k-2 comparisons are for the problem where you have to decide
whether there exists some majority element.

--Gerhard


# > 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 J. Woeginger http://www.win.tue.nl/~gwoegi/

 

[Ben Bacarisse]

# (e-mail address removed)-graz.ac.at (GJ Woeginger) writes:
#
# > 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.
#
# I can't track this down. Have I got the right Journal of Algorithms?
#
# http://www.informatik.uni-trier.de/~ley/db/journals/jal/jal3.html
#
# does not list that paper. Of course, this table of contents might be
# wrong. The horrendous link:
#
# http://www.sciencedirect.com/scienc...serid=10&md5=2c8bc9013d6025d08b7d24d3207dfe18
#
# appears to be for the journal itself. The paper does not appear
# there, either.


I gave the wrong page numbers. It should be
M.J. Fisher and S.L. Salzberg (1982)
Finding a majority among n votes.
Journal of Algorithms 3, pp 375-379

And it is not an independent paper, but the discussion of
problem 81-5 in the problems column of Leo Guibas.

Ah! I can't get access to the text (no library anymore) so I could
not find it. I thought it might be in the "Problems" column, but the
page numbers did stop me checking that.

[Rant: Is it reasonable to ask $20 for a PDF of a 27 year old paper?
It would cost me that to get to a library, so I suppose so. I'd be
happier if the authors, editors and reviewers got a cut of that, but I
know they won't.]

I also messed up the statement of the main result of Fisher and Salzberg:
The 3k-2 comparisons are for the problem where you have to decide
whether there exists some majority element.

Ah (again). I now get it. Their algorithm has two phases. What you
describe is phase one. In the particular case where we know (from the
definition of the problem) that there *is* a majority we can stop
there. Because we don't need their phase two, there is no need for
the list they maintain in phase one.

I think their original problem is more interesting. Determining if
there is a majority at all (and what that majority element is) is more
subtle than the rather fake 500,001 of 1,000,000 element problem.

When you know a majority exists, you can find it in n-1 candidate
comparisons (that is, excluding the housekeeping tests like count ==
0). This is less than the 3n/2 - 2 (= 3k - 2 in the posted interview
problem) required if it is not known that there is a majority.

<snip>

 

[jbriggs444]

On Nov 21, 6:29 pm, (e-mail address removed)-graz.ac.at (GJ Woeginger)
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;
          c = 1;
       }
       else if (p == 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?
Oh wait... the (c==0) counts as a comparison.  I see it now.
Ignore me.

I don't think the (c==0) counts as a comparison.

Of course it does.  Why wouldn't it?

Because the statement in question was:

"[...] then you can find it with 3k-2 element comparisons"

Index comparisons and element comparisons are not at all the same
thing when one generalizes the problem away from arrays of 32 bit
values to arrays of arbitrary abstract values.

 

[Bruce Wheeler]

# (e-mail address removed)-graz.ac.at (GJ Woeginger) writes:
#
# > 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.
#
# I can't track this down. Have I got the right Journal of Algorithms?
#
# http://www.informatik.uni-trier.de/~ley/db/journals/jal/jal3.html
#
# does not list that paper. Of course, this table of contents might be
# wrong. The horrendous link:
#
# http://www.sciencedirect.com/scienc...serid=10&md5=2c8bc9013d6025d08b7d24d3207dfe18
#
# appears to be for the journal itself. The paper does not appear
# there, either.


I gave the wrong page numbers. It should be
M.J. Fisher and S.L. Salzberg (1982)
Finding a majority among n votes.
Journal of Algorithms 3, pp 375-379

And it is not an independent paper, but the discussion of
problem 81-5 in the problems column of Leo Guibas.

Ah! I can't get access to the text (no library anymore) so I could
not find it. I thought it might be in the "Problems" column, but the
page numbers did stop me checking that.

[Rant: Is it reasonable to ask $20 for a PDF of a 27 year old paper?
It would cost me that to get to a library, so I suppose so. I'd be
happier if the authors, editors and reviewers got a cut of that, but I
know they won't.]

Note: it is Fischer (sp) and Salzberg.

Doing a Google search on fischer salzberg majority produced the
following, a scanned version of the paper.

www.cs.yale.edu/publications/techreports/tr252.pdf

Regards,
Bruce Wheeler

 

[Bruce Wheeler]

# (e-mail address removed)-graz.ac.at (GJ Woeginger) writes:
#
# > 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.
#
# I can't track this down. Have I got the right Journal of Algorithms?
#
# http://www.informatik.uni-trier.de/~ley/db/journals/jal/jal3.html
#
# does not list that paper. Of course, this table of contents might be
# wrong. The horrendous link:
#
# http://www.sciencedirect.com/scienc...serid=10&md5=2c8bc9013d6025d08b7d24d3207dfe18
#
# appears to be for the journal itself. The paper does not appear
# there, either.


I gave the wrong page numbers. It should be
M.J. Fisher and S.L. Salzberg (1982)
Finding a majority among n votes.
Journal of Algorithms 3, pp 375-379

And it is not an independent paper, but the discussion of
problem 81-5 in the problems column of Leo Guibas.

Ah! I can't get access to the text (no library anymore) so I could
not find it. I thought it might be in the "Problems" column, but the
page numbers did stop me checking that.

[Rant: Is it reasonable to ask $20 for a PDF of a 27 year old paper?
It would cost me that to get to a library, so I suppose so. I'd be
happier if the authors, editors and reviewers got a cut of that, but I
know they won't.]

Note: it is Fischer (sp) and Salzberg.

Doing a Google search on fischer salzberg majority produced the
following, a scanned version of the paper.

www.cs.yale.edu/publications/techreports/tr252.pdf

Regards,
Bruce Wheeler

I see that this is a reference to the technical report you (Ben
Bacarisse) mentioned a few messages before, so you can ignore my
previous post (but note the spelling).

Regards,
Bruce Wheeler

 

[Balog Pal]

One point of using puzzles in interviews is that it tests the
preparedness of interviewees. These things are chestnuts. If
you are serious about getting the job, you go through the
chestnuts in advance. It's similar to finding what a company
does before you interview with it.

Joel Spolsky had a bunch of great articles on interviews for sw developers.
They include stuff for the trivia-based form. His opinion matches mine:
that is as crappy as it is widespread. :-(

The point would be to find people to fit certain job/work. Going for trivia
will eliminate many good workers, and get you those with irrelevant
knowledge or luck.

Also it will make the company look dumb and incompetent in the eyes of an
ACE candidate if you happened to stumble on one...


Well, that's for general -- the particular story said here may not be in the
category, as the asker was about to grant hints. That may suggest he was not
after the trivia answer, but was seeking a topic the looks "new" to the
candidate, but he can wolk on the given hints. If the question appeared
in the "known" category he would pull something other without going deep.

What suggests go ahead to learn many trivia answers is not very productive.
Unless you are so eager to find a WTF job at a WTF company that is... ;-/

The hope of the interviewer is that you've never seen that kind
of puzzle before and they get to see how agile you are on your
mental feet. Speaking from the interviewers side of the fence
those sort of tests are mostly good for checking out bright young
puppies who are short on hard experience. When one is dealing
with more experienced people the important thing is to discover
if they know what they are supposed to know and how alive their
intellectual curiosity is. Oh yes, the most important thing to
discover whether they are BS artists giving you a snow job. BS
artists are deadly in the technical world.

Indeed, too bad so many of them are put in the interviewer role too. Keeping
the Parkinson schema working without much chance for a counter.

 

[Paul E. Black]

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."

... [PEB]

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.

I often ask questions to understand an applicant's approach, not for
their specific knowledge. (I asked one candidate to write a
quicksort, and he replied he would look it up. I was not impressed.)

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"?

I took an algorithms or analysis of algorithms class. We solved a ton
of problems like "design an O(n^2) algorithm for ..." (or n log n or
whatever). After a semester of this, we were pretty good at coming up
with stuff. Note: just "knowing" the complexity of a solution went a
long way as a hint to how it might be solved.

So yes, studying how to come up with algorithms should help people in
similar circumstances.

Did *I* solve the problem? hmm, uh, its been a coupla' decades, and
I'm, uh, kinda' busy ...

-paul-

 

[James Kanze]

"Richard Harter" <[email protected]>

Joel Spolsky had a bunch of great articles on interviews for
sw developers. They include stuff for the trivia-based form.
His opinion matches mine: that is as crappy as it is
widespread. :-(

The point would be to find people to fit certain job/work.
Going for trivia will eliminate many good workers, and get you
those with irrelevant knowledge or luck.

It depends on what you consider a good answer. Of the answers
I've seen posted here, the only one I would consider acceptable
(but I wouldn't ask such a question) was the one which said to
use one of the known and established linear algorithms to find
the median; at least in the environements I've worked in
previously, any of the other answers are just mental
masturbation and make work.

Also it will make the company look dumb and incompetent in the
eyes of an ACE candidate if you happened to stumble on one...

Well, that's for general -- the particular story said here may
not be in the category, as the asker was about to grant hints.
That may suggest he was not after the trivia answer, but was
seeking a topic the looks "new" to the candidate, but he can
wolk on the given hints. If the question appeared in the
"known" category he would pull something other without going
deep.

That may be the key. If the question was just meant to provoke
discussion, in order to find out how the candidate thinks, and
expresses his ideas, then fine.

 

[tchow]

I often ask questions to understand an applicant's approach, not for
their specific knowledge. (I asked one candidate to write a
quicksort, and he replied he would look it up. I was not impressed.)

To be fair to the candidate, your question was a poor choice if your
intention was to "understand an applicant's approach, not for their
specific knowledge." Did you really ask for *quicksort* specifically?
If so, how is that *not* testing for specific knowledge? In real life,
if for some reason I really needed to write a *quicksort*, guess what?
I would look it up. Not in a book, of course; I'd find a library routine
that somebody had already written. Why reinvent the wheel?

 

[bill]

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 = 0;

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

    int x = 0;
    for (int i = 0; i < 32; i++)
        if (count > 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.

Compare the number of 1's and 0's in each bit position.
Which ever bit is in the majority is the bit in 'x' for
that bit position.

Creating an appropriate algorithm might be considerably
more difficult than I suspect! But the approach works if
x is something like 01111111111111111111111111111111.

regards, Bill J.

 

[mohangupta13]

I was also given this problem as part of an interview quiz. My answer
was: Use one of the known O(n) median algorithms and use that value.

How do you use median algorithm ( as i get it .those refer to the
selection algorithm ,like (n+1)/2 th order statistic) to solve the
above problem??
Mohan

 

[mohangupta13]

On Nov 21, 6:29 pm, (e-mail address removed)-graz.ac.at (GJ Woeginger)
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;
          c = 1;
       }
       else if (p == 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?
Oh wait... the (c==0) counts as a comparison.  I see it now.
Ignore me.

I don't think the (c==0) counts as a comparison.

Of course it does.  Why wouldn't it?

Why should it count? Its just a simple instruction like c++ or c-- ,
it should count
As comparison should refer to the comparison of input entities (with
their satellite data's) .

I think the other k-1 comparisons are for the 2nd
part of the algorithm, when you make one more pass
through the array verifying the candidate found in
the 1st part.  [You already know the index i for
one occurrence of the candidate, so only the other
k-1 indices have to be checked.]

But I still don't get how is it 3k -2 comparisons i just see a single
loop (of n) in which comparison is done just once.
Mohan

 

[Paul E. Black]

To be fair to the candidate, your question was a poor choice if your
intention was to "understand an applicant's approach, not for their
specific knowledge." Did you really ask for *quicksort*
specifically?

I think so.

If so, how is that *not* testing for specific knowledge?

Because I didn't really care if they could write quicksort off the top
of their head. I wanted to see if they would work with me or try to
fake it. If they said, I don't remember, but I could look it up, I'd
help them (or switch to simpler algorithm). I'd typically guide them
through whatever they were writing. Did they think about correctness?
Did they talk about testing or noting (documenting) what they were
doing? What language should it be in? Did they think about
alternatives? The type of input parameters? Should the input
parameters be checked? Will they ask if they *don't* know something,
or will they just guess and write garbage?

It was the candidate's attitude of "I'm so far beyond that that I
don't even bother remembering such trivia." When I tried to push to
see what he *did* know, I could not get a feel of engagement.

In real life,
if for some reason I really needed to write a *quicksort*, guess what?
I would look it up. Not in a book, of course; I'd find a library routine
that somebody had already written. Why reinvent the wheel?

Excellent point. And I respect that answer.

-paul-

 

[Ben Bacarisse]

But I still don't get how is it 3k -2 comparisons i just see a single
loop (of n) in which comparison is done just once.

That bound was quoted in error. It is for a closely related but
sightly different algorithm. The algorithm given here uses n-1
element comparisons.

The paper from which the 3k - 2 comes describes a method to determine
*if* there is a majority and, if so, what the majority element is.
That needs 3n/2 - 2 element comparisons, but since we know there a
majority, we can stop after what the authors call phase one:
http://www.cs.yale.edu/publications/techreports/tr252.pdf

A good overview of similar problems is given here:
http://www2.research.att.com/~marioh/papers/cacm09.pdf

 

[Ben Bacarisse]

How do you use median algorithm ( as i get it .those refer to the
selection algorithm ,like (n+1)/2 th order statistic) to solve the
above problem??

Imagine the 1,000,000 items sorted. How can the middle item be
anything but one of 500,001 that make up the majority?

 

[mohangupta13]

Imagine the 1,000,000 items sorted.  How can the middle item be
anything but one of 500,001 that make up the majority?

sorry for giving much thought before writing.
Mohan

 

[mike3]

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 = 0;

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

    int x = 0;
    for (int i = 0; i < 32; i++)
        if (count > 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.

You mean he should be able to come up with them without prompting,
right?

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

You say not a "single" one, so does that mean no course would do it,
or
you'd need multiple ones? After all, courses and books (multiple) can
be used to increase the first 2 areas (knowledge of algorithms and
mathematics).

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.

And how does one develop that? More specifically, the "speed" of
coming
up with the solution, not just being able to come up with one.

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

What would that be?

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

Heh.


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

Hmm.

 

[mike3]

On Nov 21, 10:24 am, (e-mail address removed) (Pascal J. Bourguignon)
wrote:

You say not a "single" one, so does that mean no course would do it,
or
you'd need multiple ones? After all, courses and books (multiple) can
be used to increase the first 2 areas (knowledge of algorithms and
mathematics).

<snip>

Oh yes, and I forgot to add: how does one train the "symbolic"
thinking?

 

[John W. Krahn]

In
<805a7a21-f99b-4eb9-abb0-fbde47cb955e@k19g2000yqc.googlegroups.com>,
mike3 wrote:



Step 1: obtain a pointy stick.

Or some fresh fruit.


John