analytical Skill for Java Development

[Monique Y. Mudama]

Obviously, the optimal strategy is to research as many of these
problems as possible and memorize their solutions, but then, in
the interview, pretend you are encountering them for the first
time, and work through them a little slowly in front of the
interviewer.

I don't think most engineers are good enough actors to pull this off
successfully.

 

[Tony Morris]

Are you saying that, generally speaking, the more experience a person
has, the less skill they have?

- Oliver

Not exactly - more precisely, I am saying that the orthodox definition of
"experience" is contrived.
I know many people on this planet, but certainly nowhere near the entire set
(6.5 billion or whatever it is).
Of the people I know, there are a few who can learn things 1000 times faster
than I can (conservative estimate), and likewise, there are people who can
learn things 1000 times slower than I can (again, conservative estimate).
Assuming this premise, this means that given a very small subset of the
entire living human population, there exists in general, one person (A) who
can learn 1,000,000 times faster than another person (B). So what then is
the definition of "experience"? Arguably, person B will learn in 1,000,000
years what person A will learn the same thing in 1 year. Does this mean that
person A has 1,000,000 times more experience than person B? Certainly a more
plausible definition than many others that I have heard. I acknowledge that
this logic contains many holes, but my observations come out to around
something similar as well. That is, yes I can take an "experienced" person
and watch their problem solving skills crumble. This also fits my theory
that this industry is based in more ways than one, on "how things appear"
instead of "how things are", however, there has been a recent slight (very
slight in the greater scheme of everything) shift toward "how things are".

 

[Dimitri Maziuk]

Tony Morris sez:[ snip ]

Here's "how things are": given the balls problem upthread,

Skill sez:
Problem statement implies that 1) balls will break when dropped off
*some* floor of the building, and 2) laws of "falling apple" physics
apply, so probability of the ball breaking grows with floor number.

Therefore, probability of balls breaking when dropped from 100th
floor is 100%.

Furthermore, the question is not to "find the lowest-numbered floor
such that balls dropped from it will break", it's "which floor" --
meaning "find *any* floor such that ..."

Ergo, the answer is "Floor 100", and time taken to find it is O(0).

Experience sez:
I've seen "This should never happen" error message on my screen
enough times to know I should take both balls up to 100th floor,
drop them, and watch them actually break before I commit to the
answer.

Therefore, the answer if "Floor 100", and time is O(1).

That's how analytical problem solving skills of an experienced
developer fail to arrive at infinitely faster O(0) solution.

HTH
Dima

 

[Adam Maass]

1) You have two identical glass balls; when dropped from a certain height,
they will break. If they do not break, they are re-usable. Your task is to
find which floor of a 100-storey building the balls will break on.
Describe in words the algorithm you would use. We are interested in the
time complexity of the algorithm; you should spend the majority of your
time on this question attempting to optimize the algorithm.

Hint: you can always do a linear search with one of the balls, though this
a profoundly suboptimal solution to the problem.


2) You have many piles of rocks. The rocks in each pile are identical.
There are an infinite number of rocks in each pile. You know that the
rocks in one of the piles are slightly heavier than the rocks in all the
other piles. (Say 1.1 kg instead of 1 kg.) You have a scale that you may
use exactly once. Describe an algorithm to determine which pile contains
the heavier rocks.

Folks, thank you for your enormously entertaining responses, both serious
and non-serious. I was asked these -- one apiece -- at two different
companies, and they obviously seemed to like my responses since I got offers
from them both.

-- Adam Maass

 

[Roedy Green]

I doubt you could do that as it would tell you that floor 82 is twice
as hard on the balls as floor 81, and this is unlikely to be the case.

Some elementary physics here.

Energy available to break the ball

e = m * v * v;

m = mass, v = velocity

v = a * t;

d = 1/2 * a * t * t;

a = acceleration due to gravity, t = time.

Do a little algebra and you have the energy at any distance (floor).

Still if the ball breaks at 3 feet, none of this means anything.

These same physics will have you questioning Bush's story about he
collapse of the World Trade Towers. They fell too fast in the early
part of the fall for gravity to account for it.

 

[Roedy Green]

One way to think of it, consider a series of possible algorithms:

You could tackle this with a Monte Carlo approach.

You write a simulating that picks a random ball strength and random
tests (subject to a little common sense) where to drop the next
ball).

Let it run for a few hours and keep say the most successful 100 runs.
Look at what it does. See if you can come up with an algorithm to
repeat that performance, not using just blind luck.

 

[Roedy Green]

2) You have many piles of rocks. The rocks in each pile are identical. There
are an infinite number of rocks in each pile. You know that the rocks in one
of the piles are slightly heavier than the rocks in all the other piles.
(Say 1.1 kg instead of 1 kg.) You have a scale that you may use exactly
once. Describe an algorithm to determine which pile contains the heavier
rocks.

Depends what you mean by a scale. With a balance scale the answer is
trivial. Put a rock from one pile in the left pan and a rock from the
other in the right.

In the olden days, when I was in high school, you used to weigh things
with a box of weights and a pair of tweezers and a balance scale with
a knife edge balanced on an agate or some similar hard smooth stone.

 

[Ingo R. Homann]

Hi,

right. Sorry, I should have said as many possibilities as possible as
fast as possible, that is, with the smallest number of throws.
That's why I thought of the binary search

Yes, but because of the fact that in "some" cases you cannot re-use the
ball, binary-search is not exactly what we need.

I didn't read that one. He has a point. So you should choose 10,
10+sqrt(90) = (more or less) 19, 19+sqrt(81) = 28,...

You are correct that the steps have to be adjusted in the way you do it.

BUT: I had choosen my initial start value of '10' with the assumption in
mind that the steps are being *not* adjusted. That assumption was wrong
- and so, the initial value of '10' is wrong!

So, it get's complicated (but I think/hope, now this is really correct):

1. It's optimal, when you maximally do as many steps with the first ball
as you will maximally need with the second ball (that was my first
assumption, which I did not explicitely formulate).

2. If in step 0 the (start-)value is s0, which can be calculated by an
unknown function s0=f(100), then the second value is s1=s0+f(100-s0).
(That's what you are saying - and I agree.)

Continuing that, we generally get s_i = s_(i-1) + f(100-s_(i-1))

Now we know (or "think"), that f must somehow be a square-function with
an (linear?) "adjustment" factor. We further know that s0 - 1 is the
worst case of throws we need with the second ball. The worst case for
the first ball is that w for which the following equation is correct: s_w=99

Considering assumption 1, this should be enough to calculate the function f.

Problem solved. ;-)

Ciao,
Ingo

 

[Ingo R. Homann]

Hi,

your specific solution convinces me. But you must explain your formula:

x = summation(q to x) Where summation <= y AND x <=(q - x)

For me, summation(q to x) is q + (q+1) + (q+2) + ... + (x-1) + (x)
But obviously, you mean something different.

Ciao,
Ingo

 

[Andrea Desole]

I can do it in worse case of 16 right now, maybe even less.

The basic flaw I saw in the original, increase by 10 then drop, is that
your search area increases. First ball, max drops is 10, next is 11,
next is 12, next is 13...all the way up to 19. What I did was try to
equalize the search:
(starting at 0 - 99)
First ball is dropped at 15, worst case of 16.
Next ball is dropped at 29(+14), worst case of 16
Then 42(+13), 54(+12), 65(+11), 75(+10), 84(+9), 92(+8), and finally
99(+7)

All of these(except the final drop), has a worst case of 16 drops. If I
did my math right, which I probably didn't knowing me.

If anyone finds any flaws in my logic and math, please, let me know.

the only thing I can say is that we should minimize the average, not the
worst case. I assume in this case average is also smaller, but the fact
that we now have a variable step makes the problem more complicated

 

[Andrea Desole]

Yes, but because of the fact that in "some" cases you cannot re-use the
ball, binary-search is not exactly what we need.

yes, that's a problem I pointed out already. But I had the idea of using
the first ball to rule out as many floors as possible in the smallest
number of drops. Maybe a binary search is not the best approach in that
sense

You are correct that the steps have to be adjusted in the way you do it.

BUT: I had choosen my initial start value of '10' with the assumption in
mind that the steps are being *not* adjusted. That assumption was wrong
- and so, the initial value of '10' is wrong!

So, it get's complicated (but I think/hope, now this is really correct):

1. It's optimal, when you maximally do as many steps with the first ball
as you will maximally need with the second ball (that was my first
assumption, which I did not explicitely formulate).

2. If in step 0 the (start-)value is s0, which can be calculated by an
unknown function s0=f(100), then the second value is s1=s0+f(100-s0).
(That's what you are saying - and I agree.)

Continuing that, we generally get s_i = s_(i-1) + f(100-s_(i-1))

Now we know (or "think"), that f must somehow be a square-function with
an (linear?) "adjustment" factor. We further know that s0 - 1 is the
worst case of throws we need with the second ball. The worst case for
the first ball is that w for which the following equation is correct:
s_w=99

I would rather go for the "we think" option

 

[Andrea Desole]

Folks, thank you for your enormously entertaining responses, both serious
and non-serious. I was asked these -- one apiece -- at two different
companies, and they obviously seemed to like my responses since I got offers
from them both.

I just tried a search on google for "analytical interview questions",
and I found a couple of cool links with some more questions:

http://www.acetheinterview.com/cgi-bin/qanda.cgi?action=topics&number=3
http://www.geekinterview.com/Global-Interview-Questions/Infosys/Analytical

there are a few interesting questions

 

[Ingo R. Homann]

Hi,

I just tried a search on google for "analytical interview questions",
and I found a couple of cool links with some more questions:

http://www.acetheinterview.com/cgi-bin/qanda.cgi?action=topics&number=3
http://www.geekinterview.com/Global-Interview-Questions/Infosys/Analytical

there are a few interesting questions

I would say "there are few interesting questions" ;-)

Many questions are quite easy or at least well-known. (This one here
with the two balls I dint know before, and I think it is very interesting!)

Some questions do not have anything to do with 'logic', although they
are also quite interesting to guess: "How many kilometers of roads are
there in the US?"

Or, my favourite:

"If you could remove any of the 50 states, which state would it be and why?"

As a German, I would say: There are only 15 states, and it's obvious
that everyone (*) would remove Bavaria.
*=(Including the Bavarians themselves!
Reason: They are unable to speak German. ;-)
(OK, the Bavarians would name a different reason...)
(Oh - but then I also would have to remove "Sachsen-Anhalt" where my
wife comes from! Bad idea! ;-)

Ciao,
Ingo

 

[Ingo R. Homann]

Hi,

It means we're hopeless at these puzzles. Imagine if we were in an
interview situation. It follows absolutely that we must be hopeless
programmers.

Oops

It might also mean that we give new ideas to out employer which did not
consider that the solution is much more complicated than he thought
(which, I think, is often the case ;-)

Ciao,
Ingo

 

[Andrea Desole]

Many questions are quite easy or at least well-known. (This one here
with the two balls I dint know before, and I think it is very interesting!)

i like the mirror one

Some questions do not have anything to do with 'logic', although they
are also quite interesting to guess: "How many kilometers of roads are
there in the US?"

yes, that one is strange. The toaster one is also a bit strange.
The second link has probably more interesting questions

Or, my favourite:

"If you could remove any of the 50 states, which state would it be and
why?"

As a German, I would say: There are only 15 states, and it's obvious
that everyone (*) would remove Bavaria.

I wouldn't. I used to live in Munich.

 

[Thomas Hawtin]

And shit - he's damn right! That means... ehh... yes, was does it mean?

It means we're hopeless at these puzzles. Imagine if we were in an
interview situation. It follows absolutely that we must be hopeless
programmers.

Oops

Tom Hawtin

 

[Ingo R. Homann]

Hi,

i like the mirror one

Yes (I skipped that before), that is really good - since every child
asks that but most parents are unable to give the correct answer.

yes, that one is strange.

I have *no* idea. Only large roads, but also small streets?

I also have nothing to compare (e.g. I have no idea how many kilometers
of roads or rails are in Germany).

Perhaps 500.000 kilometers in total (including every small street)? No,
I think this is not enough... 1 mio?

The toaster one is also a bit strange.
Yes!


I wouldn't. I used to live in Munich.

I tought, <prejudice>all</prejudice> Bavarians think that Bavaria is
much better than "the rest of Germany" (which they like to call
"Northern Germany") and would be glad if it was an own country. ('We are
proud to be a 'Freistaat'." ;-)

You are not a native Bavarian (*), are you?

(*) Then you are no Bavarian at all! ;-)

Ciao,
Ingo

 

[Ingo R. Homann]

Hi,

And I like this one:

"How many points are there on the globe where by walking one mile south,
one mile east and one mile north you reach the place where you started."

Hint: The "obvious" answer ("There is one point.") is *wrong*!

Ciao,
Ingo

 

[Andrea Desole]

Yes (I skipped that before), that is really good - since every child
asks that but most parents are unable to give the correct answer.

really? I never really cared until I saw the question

I have *no* idea. Only large roads, but also small streets?

and mainly: why would someone ask a question like that? It doesn't look
that analytical to me, and it depends on so many factors

I tought, <prejudice>all</prejudice> Bavarians think that Bavaria is
much better than "the rest of Germany" (which they like to call
"Northern Germany") and would be glad if it was an own country. ('We are
proud to be a 'Freistaat'." ;-)

True. Bavaria is Bavaria

You are not a native Bavarian (*), are you?

no. I was just there for a few years

 

[Roedy Green]

I just tried a search on google for "analytical interview questions",
and I found a couple of cool links with some more questions:

Where do you think the interviewers get these? The surely don't make
them up.