Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Data structures and algorithms interview questions and their solutions

techiedelight.quora.com

Post reply on HN
Print view View original

21–30 of 36 posts

Re: Data structures and algorithms interview questions and their solutions

#21

Post by NiceGuy_Ty »

bloaf wrote: post #10

Am I stupid or do both of the solutions to the problem "Replace each element of array with product of every other element without using / operator" use the / operator? My solution would involve summing the log() of the values in the array.

There was just a post on HN to a site that went over this exact problem. Essentially, you do two linear scans to calculate the product of every number before an index, and to calculate the product of every number after an index. Then, for each index, the answer is just multiplying those two numbers you found for that index.

Re: Data structures and algorithms interview questions and their solutions

#22

Post by manigandham »

If anyone asks these questions without a particular scenario to actually deal with in the course of the position you're interviewing for, you are in for some bullshit at that company. This has become all too common at the major corporations sadly.

Re: Data structures and algorithms interview questions and their solutions

#24

Post by bogomipz »

userbinator wrote: post #8
munin wrote: post #6

If this isn't a metaphor for the programming interview I don't know what is: http://www.techiedelight.com/multiply-two-numbers-without-us... "Implement multiplication without using loops." "Uh, okay. What do you mean by loops?" "Don't use a conditional loop." "What do you mean by a conditional loop?" "Oh, you know, the standard definition." Time passes. "I'm stuck. What is the answer?" "Oh, you just have a loop on b…

The real way to multiply without loops is to use a lookup table, or unroll the (fixed iteration) shift-and-add loop. That page is both hilarious and sad at the same time. Hilarious because the second "solution" clearly has a loop, and sad because sites like those don't really help anyone. Some of the pages on that site are downright WTF s: http://www.techiedelight.com/generate-binary-numbers-1-n/

>"or unroll the (fixed iteration) shift-and-add loop"

Can you elaborate on this? I understand the shifting but didn't understand the "loop unrolling fixed iteration part"

Re: Data structures and algorithms interview questions and their solutions

#25

Post by bloaf »

mike_ivanov wrote: post #19
bloaf wrote: post #17

Earlier quoted context omitted.

Mult(A,B) = Exp(Log(A) + Log(B))

You didn't pass (overqualified, will likely be bored by the job).

More like: bad culture fit, expects a standard library that handles infinite quantities and complex numbers out of the box.

Edit: how about

(Math.Pow(a+b, 2) - Math.Pow(a,2) - Math.Pow(b,2))/2

Re: Data structures and algorithms interview questions and their solutions

#26

Post by userbinator »

bogomipz wrote: post #24
userbinator wrote: post #8

Earlier quoted context omitted.

The real way to multiply without loops is to use a lookup table, or unroll the (fixed iteration) shift-and-add loop. That page is both hilarious and sad at the same time. Hilarious because the second "solution" clearly has a loop, and sad because sites like those don't really help anyone. Some of the pages on that site are downright WTF s: http://www.techiedelight.com/generate-binary-numbers-1-n/

>"or unroll the (fixed iteration) shift-and-add loop" Can you elaborate on this? I understand the shifting but didn't understand the "loop unrolling fixed iteration part"

The shift-and-add algorithm for multiplication is usually implemented as a loop that iterates for the number of bits of the operand, so e.g. for an 8-bit x 8-bit multiplication, the loop runs 8 times. (An "early out" algorithm when one of the operands becomes 0 is also common, but let's not complicate things here.) It's trivial to unroll this loop into the 8 individual shift-and-add steps.

Re: Data structures and algorithms interview questions and their solutions

#27

Post by psergeant »

ccleary00 wrote: post #20

I'd rather just not interview at companies that have these kinds of interviews and save myself the hassle.

Fair enough, but you're not usually learning some deeper truth about the company based on whether or not they use these kinds of interviews.

Interview processes are generally completely arbitrary, the interviewers chosen at the last minute by the hiring manager, and they're not changed because they're sort of good enough.

If you dislike these types of interviews sufficiently on their own merits that you want to avoid them, fine. But don't think you're learning anything about companies just because they use them.

Re: Data structures and algorithms interview questions and their solutions

#28

Post by mathattack »

hanoz wrote: post #4

Didn't most of us get in to this mathsy line of work precisely because we didn't need to memorise a load of stuff and could just work things out from first principles as and when required?

This is certainly why I enjoyed Calculus and Physics. :-)

Re: Data structures and algorithms interview questions and their solutions

#29

Post by alexee »

munin wrote: post #6

If this isn't a metaphor for the programming interview I don't know what is: http://www.techiedelight.com/multiply-two-numbers-without-us... "Implement multiplication without using loops." "Uh, okay. What do you mean by loops?" "Don't use a conditional loop." "What do you mean by a conditional loop?" "Oh, you know, the standard definition." Time passes. "I'm stuck. What is the answer?" "Oh, you just have a loop on b…

I was asked something like this in Amazon SE interview - find something without using loops, the answer was to use recursion. Sigh.

Re: Data structures and algorithms interview questions and their solutions

#30

Post by SomeStupidPoint »

alexee wrote: post #29
munin wrote: post #6

If this isn't a metaphor for the programming interview I don't know what is: http://www.techiedelight.com/multiply-two-numbers-without-us... "Implement multiplication without using loops." "Uh, okay. What do you mean by loops?" "Don't use a conditional loop." "What do you mean by a conditional loop?" "Oh, you know, the standard definition." Time passes. "I'm stuck. What is the answer?" "Oh, you just have a loop on b…

I was asked something like this in Amazon SE interview - find something without using loops, the answer was to use recursion. Sigh.

Isn't there an actual distinction here -- induction versus co-induction?

I would argue that a loop constructs an answer, while recursion deconstructs input.

There's a duality, so you can port algorithms between the two models, but there is an actual distinction.

Post reply on HN