It's a classical problem that has been done to death which is why it might be marked easy.

If you can think of the brute force solution, there is a slight optimization to make it faster.

I recall the optimal solution requires knowledge of dynamic programming, so not an "easy" question.

I have 3 questions I've asked many times.
1) merge two sorted double linked lists - Sounds straightforward but most can't code this cleanly and correctly without a bunch of errors and help
2) parse and deserialize a json string to a Java object - Requires good code organization, recursion (or state machine), and string parsing. This one has everything it's great for a 1 hour question. I think 1 person has solved it completely but I evaluate for how they approach the problem and how far they get.
3) design an image sharing site like imgur or instagram. Open ended design. I dig into various parts of the stack to test how deeply they know a topic and how they approach the problem.

you have them write a parser?

Easy/hard is always a bit weird; many problems are easy once you know the answer, although here the best solution is very straightforward/single-pass once you know the main idea (making it sort of a silly interview question) and quite a bit better than O(n^2) brute force.

no dynamic programming needed. there is a "trick" for the efficient solution, but it's not too hard to find.

Because you have to check all permutations, not simply all permutations generated by a single swap.

Eg, say you move N into position i and i into the final position. It could be that N is now in a valid position, but i is not -- but, swapping i with some other element now makes both of them valid, leading to a valid arrangement that you missed.

This is not guaranteed, though. Worst case for quick select is O(n^2)

Max subarray is the first algorithm in CLRS, so I suppose it's "easy" compared to others. I always forget how to do it, so it's not easy to me.

I thought everyone is implementing median-of-medians in their whiteboard interviews these days...

Yea I don't think people are expected to code out median-of-medians.

And yes you are right gaming_mouse, it's not O(n), but it's expected O(n) using a random pivot from what I remember.

If you are interested in learning about median-of-medians, I always found this as a good read through http://www.ics.uci.edu/~eppstein/161/960130.html

Right. I solved this the other day when browsing through "cracking the coding interview". It's a good pattern that applies to many problems. Keeping 2 pointers and moving one of them at each step, so the algorithm never goes backwards and is O(n).

not totally sure what you mean, but i don't think about it as 2 pointers. if replace the original array with scan sum (which costs O(n)), then you just need to keep track of two quantities -- the max value of scan sum to the right, and the min value of the scan sum to the left. you'll have these for the first position, and you can then calculate then for all positions in a single pass, since at each new index each quantity's change depends only on the value at that index.

The optimal answer is O(n) and doesn't require a heap.