with ramda, the essense of the algorithm distills into a single line:



EDIT: eh, just noticed sholar's answer takes the same approach. still, i think the ramda version is more readable.

resigning yourself to not using the good solution is only 1 of 2 possible escapes from your predicament

Hah well I have no choice re: using C in my job.

thinking about this more, i actually think it's probably the right approach even in C.

Recursion is easy in C, so all you need are the helper methods to transpose and reverse (to give you rotate). sure, writing those helpers is a bit more verbose in C, but after you have them you can now write essentially the same code as above, and you have a succinct, clear high-level algorithm.

It's interesting but "right" approach is a stretch given that it takes an O(M*N) algorithm and turns it into something like O(M*N*min(M, N)). Even a naive virtual rotation algorithm is I think is the same (rotation then takes constant time but element look up is now number of cumulative rotations) - this is what I meant by optimization for multiple rotations btw.

This is true. I write processor tests, and one of our highest priorities is minimizing simulation time, so I tend to take a dirtier approach (limiting helper methods) because it cuts down on # of operations. That's why I'm stuck with C; because we have to be cognizant of how the program breaks down into assembly, as well as performing DMAs and register accesses, it's as high level as I can practically get. I do enjoy when I have to do some scripting, because I do that in Perl or Python and it's nice to use those for a change.

my feeling is that clarity and simplicty are orders of magnitude more important than performance until performance specifically asserts itself as a pressing need.

so i have no problem with the word "right" here. i'll concede that i have a strong pov on the subject, and reasonable people disagree sometimes, but they're wrong

this is a good followup to my response to candybar, because low-level jobs like yours are places where my pov is genuinely not appropriate. that said, i think when you're doing puzzles like these your habitual workplace constraints no longer apply

I agree with everything you said. In an actual interview case I would use an approach more language appropriate for the position. I knew most here would be responding with high-level language solutions, so I took it as a chance to offer something unique. I don't think this type of puzzle would be used in an interview for a C job, it's something you'd have to code in C for a CS class homework assignment or something but that'd be the only time.

It's an algorithm interview question specifically designed to test your understanding of things like runtime complexity of algorithms. And we're not talking about constant time differences - going from O(1) space to O(M*N) space (and times min(M,N) for the actual amount of garbage generated) and going from O(M*N) time to O(M*N*min(M,N)) are massive. And if the context is C, it's even more so - people don't use C these days for situations where performance is not a pressing need.

And for actual clarity and simplicity, not theoretical clarity and simplicity in a world only inhabited by functional programming enthusiasts, you need to use idioms and tools that are likely to be easily understood by your audience, instead of rolling your own. This is simply not idiomatic in C (because even properly handling memory is painful here) and it's going to be hard for people to follow and understand.

fyp

I'm not sure what you mean here then - what does it mean for something to be a "right" approach for a puzzle? Why does an answer to a puzzle have to any particular attribute, whether clarity or simplicity? Note how I went for the exact opposite in my answer

In production C code, you would not do this because it's a less efficient solution that requires far more lines of code to express and is much harder for C programmers to understand or review. In an interview situation, you're trying to demonstrate your ability to write clear, efficient code and that you understand runtime complexity. Code that offloads most of the responsibility to the libraries which the interviewer may or may not be familiar with, thus failing to demonstrate your ability to write code, which the interviewer wants to see, is counterproductive. Likewise, writing code with runtime characteristics that are worse than a naive solution - well if you could get the interviewer to even understand how your code is actually going to run - seems extremely counterproductive.

One week from today I have a technical phone interview where I will be writing code on a google doc. Recruiter sent me prep material telling me to basically learn everything about CS.

I am expecting an epic fail next week

interview big o stuff aside, and excepting jobs like lattimers, the programmer's cognitive load is almost always the true bottleneck in software and the source of most bugs. that's the sense in which im right.

GM, even on a conceptual level I don't really see your solution as the most clear and simple.

I think there's a fairly small group of people for whom answers like this would appear simple and clear. Many of the best people would want to see exactly what is happening because they are used to abstractions failing and don't trust the underlying abstractions. Many normal developers are not all that comfortable with dealing with high levels of abstraction because it stretches their model of computation.

Also, don't forget that the context in which we most often read other people's code is when something is not working and we don't know where the not-working thing is. High-level indirection of this sort can add a lot of overhead if the reader isn't intimately familiar with all the edge cases for the abstractions that are being used.

disagree but what is there to say? Id be willing to bet a couple hundo that if you posted our solutions side by side on hn or as answers on code review and asked a bunch of ppl to vote mine would win

sorry this is nonsense. its easier to debug 2 lines of functional code than 10+ of procedural. i have lots of experience with both and it's not close

I feel like if we gave our solutions to 100 average developers and didn't tell them what the code did, more people would correctly identify what mine does and faster.

But who knows. I'm probably not betting on it.

yeah I mean it's tricky to remove the confound thay more ppl, as an actual number, know procederal constructs like for loops than even something like ternary. you could restrict to ppl with x years experience, blah, etc. but cmon on some gut level you know im right? I know you do

I legitimately don't think you're right. But its hard to remove my experience/background too.

agree to disagree then. also, post more!

when I compile and run this post it displays "HU4ROLLZ"

I think making this about functional vs procedural is a little off the mark though there's certainly correlation - functional code doesn't have to use a lot of abstractions and procedural code can use tons of abstractions that can make the resulting code hard to debug. I think you're also forgetting the context for this - I'm specifically objecting to you saying this is the right approach in C.

I don't understand - reality is not a confounding variable. It's like saying that we should write everything in Esperanto because it is theoretically easier to understand, ignoring that 1000 times more people can read English.