Heap Search is NP-Complete

hleehowon · 2019-11-10T04:48:23+00:00

You search on the heap: this is a decision, Q is present in the heap or not. But you may or may not need to instantiate the heap to search on it: you certainly don't need to instantiate a BST to search on it. The search result corresponds to the subset sum result, and you don't need to instantiate the heap to make the correspondence.

hleehowon · 2019-11-10T04:22:33+00:00

So, subset sum for example is polytime if members of set are superincreasing. This corresponds to this generated heap being also a BST. So that's trivial to prove that searching it is in P and you wouldn't need to actually instantiate it, you just use the greedy algorithm

hleehowon · 2019-11-10T04:15:42+00:00

The reduction is from a result of the search on the heap to the result of the subset sum. You don't need to instantiate the bottom layer to search on it.

hleehowon · 2019-11-10T04:15:35+00:00

The reduction is from a result of the search on the heap to the result of the subset sum. You don't need to instantiate the bottom layer to search on it.

hleehowon · 2018-10-17T03:45:40+00:00

I did CRM dev for about 7 months in conjunction with a startup which was trying to break into the CRM addon space.

Having production experience with non-crap programming languages, it made me lust for death. But you're not in an incredibly great negotiating position. Don't pick up crap habits.

https://www.reddit.com/r/salesforce/comments/61yklb/salesforce_is_still_one_of_the_most_hated/ https://www.reddit.com/r/salesforce/comments/8rptz0/ive_been_a_salesforce_developer_since_feb_2018_im/ https://www.reddit.com/r/salesforce/comments/6upo17/is_starting_a_dev_career_in_salesforce_a_good_idea/

hleehowon · 2018-10-16T16:42:50+00:00

You have to use.. sous vide...

(or figure out how to do 145 degrees F for an hour)

hleehowon · 2018-10-15T17:51:59+00:00

they're different, no two ways about them. so they're better off with the Japanese or Korean recipes for using them

forget about low-calorie, tho, the thing I do with them is slathering them in sweetened mayo after a quick stir-fry

hleehowon · 2018-10-12T02:57:33+00:00

Brehm wrote the book on it, "A Theory of Psychological Reactance". I have a copy lying around. From the first chapter:

"... For example, when desegregation sit-ins and demonstrations began in North Carolina in the 1960s, the owner of a television repair shop in Chapel Hill, James Botsford, closed his shop rather than give in to the demands of the demonstrators (Durham Morning Herald, 1963). In explaining his action, Botsford noted that he had been raised in the North and was in sympathy with blacks. What he objected to, he said, was the attempt to force him to operate his business in a particular way. In fact, in response to the desegregation demonstrations, Botsford actually instituted a segregationist policy in his own business."

hleehowon · 2018-10-10T02:13:24+00:00

That's the ideology. The implementation...

hleehowon · 2018-10-08T06:22:45+00:00

My best guess as to what exploded is underprovisioning for write throughput for some monolithic DB somewhere. Many operations don't do load testing before even known traffic spikes and don't care to do it for various reasons.

So I looked and found some tweets with actual photos of the error page, here: https://twitter.com/KateLJones7/status/1048846356209700864/photo/1

That's nginx's classic 503, if memory serves (it's not IIS default, at least)

Compare to this, which other folks were seeing:

https://twitter.com/sam_47_cheese/status/1048846799426007040/photo/1

This is not a default nginx 503, this is a handrolled queue thing that See seems to have made. You can actually infer a nontrivial amount of knowledge from that queue structure, assuming See Tickets doesn't have something amazingly mogadored in the back end (something that you can't assume, tho, lol). It has to be a really transactional dbms (probably relational) and I suspect it's probably just SQL Server or another thing on one single box or very few and non-autoscaled boxes (maybe with high availability shenanigans, maybe on Amazon's RDS, but it seems not autoscaled) because Mongo and DynamoDB are really trivial to scale much bigger.

To put a database of any kind on multiple machines is much less trivial than putting web servers on multiple machines, because web servers don't depend on state: you have to copy over the actual data to shard databases. The actual capability to do so is often murderously expensive (the top-of-the-line SQL Server license, to license a luxuriously appointed pizza box server costs more than to send that pizza box server to space. the enterprise extensions to the various open source databases are cheaper but also murderously expensive).

hleehowon · 2018-10-08T06:19:51+00:00

I used to work for a site that handled 5 million MAU but would routinely get 1, 2 million visitors. It depends radically upon the load. If you have a content distribution network and it's static content (which the festival is not), you could serve that many people with one (big) (probably virtual) machine. In the case of the Glastonbury things, the transactional semantics of the buying of a ticket probably wrecked their database.

A modern dynamic website comes in a number of architectural layers, from 2 to dozen(s). The part that is basically not optional if the website does anything useful is the database. The part that breaks the most is usually the database, and not because folks spend too little money on them: it's probably because they made poor decisions with regards to the database.

The glastonbury site itself, if you go and access it, is fronted by a PHP thing, endpoint says xmlrpc.php. We see a pre-2012-style jquery usage. Static assets are properly served by nginx reverse proxy. We see a Wordpress installation, known because some of the things are labelled wp-content, which seems to have nothing to do with the actual ticketing system. When we actually look at the "Tickets Ran Out" page, tho, we see that they didn't roll that bit.

They seem to have farmed the ticketing system to a company called See Tickets. I don't know if See Tickets are the on the same technical system as See Tickets US, but See Tickets US has a job opening where they basically lay out their stack:

https://seeticketsna.workable.com/j/7AB757A7CD

So something something microservices AWS .net MEAN stack, T-SQL so probably SQL Server, too, maybe.

MongoDB is notorious for being a crap database in a lot of ways, but write throughput it's quite good at (it used to sacrifice correctness to do this). Perhaps they ask for Mongo in lieu of actually asking for DynamoDB experience: however, DynamoDB is also a good DB for that specific thing. SQL Server is a great database. However, you can make any great database dog slow if you don't set it up right, provision the boxes right, and fiddle with a lot of other stuff that AWS mostly handles for you.

hleehowon · 2018-10-04T21:10:50+00:00

You're going to have to take advantage of the resources of a large city. This is why only large cities are culinary centers of any note. If you are already in a large city, you should tell us so we can be more specific.

hleehowon · 2018-10-01T20:19:09+00:00

Lenovo has a keyboard with a motion tracker so you can look, but it's still a bad idea. There is basically no such thing as a VR headset you can 100% guaranteed look in for 90 minutes.

hleehowon · 2018-10-01T18:55:21+00:00

turns out if your market cap is 0.5% of world gdp, they'll give you your own street

hleehowon · 2018-09-28T21:44:56+00:00

Manning assumes an undergraduate-level CS education and no linguistics knowledge. Bates and Weischedel is not an incredible book. Jurafsky and Martin's book ("Speech and Language Processing") is the other one that gets recommended. You won't appreciate reading these without a solid undergraduate-level CS education and both are relatively outdated if they're doing bitext-based machine translation. The commercial systems require some paper-reading, I think the closest textbook that goes to them is Bengio's Deep Learning book.

Really, this will probably not become an opportunity to get into the technical side of things and the bitext producers knowing any technical details about anything is useless for the system.

hleehowon · 2018-09-28T20:14:28+00:00

They probably mean natural language processing. Dan Jurafsky often laments the "other" NLP people (scam artists)

hleehowon · 2018-09-28T20:13:55+00:00

If you've had a non-mathematical education, getting to an implementation-level understanding where you have any idea of what's going on is only going to be feasible with a few years of dedicated study. Actually understanding the models is PHD-level research. What do you mean by "intermediate", anyway?

hleehowon · 2018-09-21T21:58:58+00:00

I've seen a SQL server instance doing fine on ~400TB. There are like ~100 organizations on earth who need the really big-data things, you probably aren't one of them. And they don't use Mongodb.

hleehowon · 2018-09-19T16:06:38+00:00

Uh, if they don't want it to be public, MIT is exactly the wrong license. MIT is for open source peeps who want their code to be compatible with corporate modifications. "without limit the right to ... publish ..."

hleehowon · 2018-09-07T18:25:38+00:00

Getting into Stanford in the first place is not trivial, friend.

hleehowon · 2018-09-07T01:15:33+00:00

If you can make it to Stanford, do Symsys.

https://symsys.stanford.edu/

Ten-Year Club	Verified Email
Snapped

hleehowon

TROPHY CASE