Some riddley interview questions.. how would you answer these?

[pouncer]

Hi guys, just wanted input on how you would go about answering riddle/analytical questions. I have these in particular:

How many runs up a ladder an egg can be dropped from, before it will break on the surface (using the least number of attempts)

How to determine the same thing using the least number of eggs?

Given a string of open/close brackets of all 3 types: (, {, [, ), }, ], how to determine that the open/close brackets are in the correct mathematical sequence, e.g ({[]{}()})

[MrViggy]

Just answer them? Seriously, though, what would your answers be.

Viggy

[pouncer]

Well, for the first one I'd start in the middle of the ladder, and if the egg reaches the surface without breaking, i'd then go the rung between the middle and the highest one etc and start again from that point.. binary search

For the 2nd one, I think it's a trick question. The above applies to 'least attempts' which is the same as 'least number of eggs' right?

For the 3rd one, probably a regular expression that applies to these rules

Inside () we can have any number of []'s and {}'s
Inside [] we can have any numner of ()'s and {}'s
Inside {} we can have any number of []'s and ()'s

regex(<string>, \( \([]\)*|(\{\})* \) ) <-- this is just the first rule, but id add || (or) clauses to adjust to the other rules too

What do you think?

[MrViggy]

For #1, yep.

For #2, it's actually a linear search. Start at the lowest rung (assuming the egg will not break at this rung), and keep trying each successive rung until the egg breaks. You only need 1 egg.

For #3, using three stacks (one for each type), when you see an "open", push it onto the appropriate stack. When you see a close, pop from the appropriate stack. If (a) you try to pop an empty stack, then you've seen a mismatch; (b) if you're all done, and any of the stacks still have items in them, you've seen a mismatch.

Viggy

[TheGreatCthulhu]

I'm with MrViggy on #2; also assuming that the egg won't get weakened after each hit.
There, we have developed a model for the problem domain - now we're talking science!

[Eri523]

For #3, using three stacks (one for each type), when you see an "open", push it onto the appropriate stack. When you see a close, pop from the appropriate stack. If (a) you try to pop an empty stack, then you've seen a mismatch; (b) if you're all done, and any of the stacks still have items in them, you've seen a mismatch.

Maybe I misunderstood your approach, but wouldn't that let something like ([)] pass? My first thought would've been a single-stack approach like I've seen many times as a homework assignment around here, but of course that wouldn't care about any special nesting rules except that the brackets need to match.

I'm also not sure whether the OP described the mathematical rules for the brackets correctly in post #3. Consulting my math lexicon I was surprised that I didn't find any rules about that at all. I also found nothing concrete on Wikipedia but maybe I didn't look close enough yet again... But thinking back to my math lessons in school, I think I remember I was taught the hierarchy {[()]}, used inside out, i.e. the first one to consider would be (), and of course with the ability to enter and leave any nesting level any number of times. But what if I have more than three levels of nesting?

[TheGreatCthulhu]

Maybe I misunderstood your approach, but wouldn't that let something like ([)] pass?

You are right, but:

For #3, using three stacks (one for each type), when you see an "open", push it onto the appropriate stack. When you see a close, pop from the appropriate stack. If (a) you try to pop an empty stack, then you've seen a mismatch; (b) if you're all done, and any of the stacks still have items in them, you've seen a mismatch.

If you add one more rule to that, then it should work - the rule being:
(assuming you keep track of the type of the last symbol) if you detect a "close" of a different type, then you also have a mismatch.

I'm not sure if I'm right... Darn! Where's a compiler expert when you need one?

I'm also not sure whether the OP described the mathematical rules for the brackets correctly in post #3. Consulting my math lexicon I was surprised that I didn't find any rules about that at all. I also found nothing concrete on Wikipedia but maybe I didn't look close enough yet again... But thinking back to my math lessons in school, I think I remember I was taught the hierarchy {[()]}, used inside out, i.e. the first one to consider would be (), and of course with the ability to enter and leave any nesting level any number of times. But what if I have more that three levels of nesting?

I think that what the OP meant by verifying the "correct mathematical sequence" is that the algorithm should verify the syntax, and that "({[]{}()})" was just an example (sample). I don't think that mathematics defines a hierarchical arrangement for these. I guess it just became an unwritten rule, with the informal hierarchy based on the difficulty to write down each of the symbols using a pen (or a chalk ). Anyway, just like in programming, it is perfectly valid in math to have as many levels of nesting as you desire using only '(' and ')'. And the informal rule can be broken: consider an order pair where the two elements are sets. The standard notation for an ordered pair is [x, y]. This is an ordered pair of sets: [{s, e, t, _, A}, {s, e, t, _, B}].

[jcaccia]

If you add one more rule to that, then it should work - the rule being:
(assuming you keep track of the type of the last symbol) if you detect a "close" of a different type, then you also have a mismatch.

I'm not sure if I'm right... Darn! Where's a compiler expert when you need one?

You are right, but it is still simpler to use just one stack.

[Ledidas]

Hi guys, ...
Given a string of open/close brackets of all 3 types: (, {, [, ), }, ], how to determine that the open/close brackets are in the correct mathematical sequence, e.g ({[]{}()})

Checking for symmetry is simple. Look at how a human body is made up; you have right hand and left hand, a left eye and a right eye, etc. They all contribute to our own body as a complete entity. Why our hand is not grown in the lower part and the leg is in the upper part is not a myth in developmental biology, but the fitness during natural selection would count. Therefore, a body without some symmetrical part is sadly ill-formed. You have an open bracket, then a close bracket. But how an open bracket is continued with another and another open brackets ? Like in a tree, it has branches, and their sub-branches. I can look at the system this way: A<B<C<D<E<F<G...>>>>>>. You see ALPHABETS=NON_ALPHBETS/2+1 ? If you program in C#, you might notice that whenever you type in an open and a close brackets, they are both highlighted, I am unsure how its actual implementation is, but using a stack seems unnecessary, it might also be GetCurPos, then FindSibling to color the brackets'brackground.

[TheGreatCthulhu]

You are right, but it is still simpler to use just one stack.

Right - the type doesn't matter for the stack; this can even be done with integer addition (start from 0, +1 if "open", -1 if "close", check if 0 AND what I said before). Good abstract thinking, jcaccia.

Checking for symmetry is simple. Look at how a human body is made up; you have right hand and left hand, a left eye and a right eye, etc. They all contribute to our own body as a complete entity. Why our hand is not grown in the lower part and the leg is in the upper part is not a myth in developmental biology, but the fitness during natural selection would count. Therefore, a body without some symmetrical part is sadly ill-formed. You have an open bracket, then a close bracket. But how an open bracket is continued with another and another open brackets ? Like in a tree, it has branches, and their sub-branches. I can look at the system this way: A<B<C<D<E<F<G...>>>>>>. You see ALPHABETS=NON_ALPHBETS/2+1 ? If you program in C#, you might notice that whenever you type in an open and a close brackets, they are both highlighted, I am unsure how its actual implementation is, but using a stack seems unnecessary, it might also be GetCurPos, then FindSibling to color the brackets'brackground.

You must be some poetic type...
The point is to do it as quickly as possible using as little resources as possible, while, of course, using an approach with sound logic.
Now, I'm not much of an algorithms guy, but IMO what you said doesn't really hit the spot.