Maybe I’m underthinking the puzzle here, but it seems like heap sort solves the problem. It’s certainly meets the time requirements, but I wonder about the space issue. Does the array representation of a binary heap require a log number of pointers?
More importantly, if this was my answer, would I get a job at Google?
UPDATE: I don’t know the linear time solution, but I feel like if I could grok smoothsort I could figure it out.
All over the country, thousands of armed cops have been deployed to stand around and surveil and even assault the polite crowds of Occupy protesters. This deployment of law-enforcement resources already dwarfs the amount of money and manpower that the government “committed” to fighting crime and corruption during the financial crisis. One OWS protester steps in the wrong place, and she immediately has police roping her off like wayward cattle. But in the skyscrapers above the protests, anything goes.
The occupy movement juxtaposed with recent warrantless GPS tracker cases has really crystallized an idea for me about the two sides of the surveillance state. The key to normalizing a privacy free culture is to trade off the civil liberty issues with the clarity brought about by careful observation of the state. In short, as the government peers into us, we peer into it.
This seems like a new and different equilibrium, one that hasn’t ever been explored at superpower scale. For every warrantless wiretap and NSA datamining sweep, we have videos of cops beating protesters, wikileaks, and open mics. These moments allow us all to reacquire a shared truth, a common state of being. This happened. There’s no denying it. Information flows in all directions. The truth does not just want to be free, it wants to be ever present.
For every dusty DEA agent secretly slapping a transponder on a beater car (how depressing that job must be), we have a new revelation about the private lives of Texas judges, or the free hand NYC lieutenants take towards the liberal application of pepper spray. These things don’t have to be whispered about. They don’t even have to be reported. They can just be shown.
I guess sometimes I feel like both the state and the people think they’re looking through one-way mirrors.
It’s a window people. A window.
I’ve been following the horror show at Penn State with quite a bit of morbid curiosity. At first I wasn’t sure I had anything more beyond a few pithy tweets to say about the matter, but now I think there is a larger truth that’s worth serious consideration by anyone involved in large human institutions with complex and sometimes ill-defined goals. To start, you should know that I’m of the opinion that there was serious wrongdoing on the part of the administration and football staff and believe that the governing body of PSU hasn’t done nearly enough to avoid serious long term harm to the institution. If you don’t feel that way, you should probably stop reading. Nothing a nobody from Texas could say to convince you, so I’m not going to try. This isn’t like other cases. There is no doubt. The facts are not in dispute. There are multiple eye witness accounts to child rape that span years. These accounts were given under oath. And for years nothing was done to prevent further harm.
Contra Deadspin, I think this is the biggest sports scandal in modern history. Yes, the OJ murder was a circus, but it was a single (and terrible) crime of violence by a lone individual that was investigated and prosecuted in a timely fashion. What this situation at PSU exposes is the compromised moral center of the entire institution. As we look into this PSU mess, we ought to look at ourselves and more importantly our participation in institutions closer to home. I’m not saying there’s a Sandusky at the center of football programs all over the country. What I am saying is that the same moral calculus exists for everybody else. Football is king. Football fans are the great enablers. And nobody in any position of power is willing to peak inside and criticize the machine.
I’m a recent convert to fandom. I’m a student at a big time football school (some say the biggest). I enjoy watching the games. I think the massive tailgating that goes on around Austin on game day is a good and positive expression of community in a world that otherwise likes to strip away community in the face of acerbic progress. And all of this sets up a space where the main players fail to properly evaluate the toll of big time (and big money) athletics on many student athletes, or the way the educational mission of a large and varied institution is reduced to being a conduit for huge television deals. Because student athletes are not properly compensated (and are forced into grey and black market transactions), and because coaches and programs extract disproportionate rents due to NCAA regulations, as long as the BCS remains an “old boys club” and entertainers on ESPN make bank while the educational institutions themselves hemorrhage cash amidst declining state support and rising tuition, I’m done with college football.
Done.
UPDATE: I guess I should be clear that I do think that Mack Brown runs one of the cleanest programs in college football, even as I think that football at the college level is hopelessly corrupt.
I wrote a Python class for manipulating normal distributions. I use it as part of some code for GMMs (https://github.com/stober/gmm). I was looking for code that supported conditioning and marginalization on arbitrary indices. There didn’t seem to be any out there so I wrote this to fill in the gap (at least for Python).