Month: September 2016

September 25 2016, 16:54

This is a high school American football competition, Liz’s school is playing against South Lakes. Liz’s school lost with a score of 8:75.

Note that each team brought their own cheerleaders. A few spectators came with the guests, but half of the stands on the home side of the tournament were filled with students in red shirts – these are the colors of McLean High School. Right there in the stands, the school band plays intermittently.

September 22 2016, 14:48

I read Grisha on Facebook with interest. Instead of replying with a comment to questions about sorting algorithms (https://goo.gl/pPcJEd), I’ll write a post, which is slightly more convenient, as there’s a lot to cover. Grisha’s post discussed whether it’s necessary to challenge candidates with algorithms that have long been obsolete in those languages (and he rightly explains why).

At TEAMIDEA, I chose three problems that I almost always presented to programmers during interviews. Sometimes, the whole interview revolved around discussing these problems (although I had a larger pool of problems, these three came up more often).

The first problem is about how to search through a million text documents. That is, you need to write your own search engine from scratch. You enter three words – you find three hundred documents that contain these words.

I find it interesting to discuss because I once wrote a search engine myself and know the associated challenges. I consider the task easy, but if the candidate handles it, there are “follow-ups”, like “what if there are multiple words, you need to intersect sets of documents for each word, and the sets are large”, as well as about pagination and fuzzy search. At a minimum, the candidate was supposed to guess about WordId -> PageId pairs, and even that was beyond 50% of the applicants with good resumes.

The second problem is about creating a URL shortener. You input a URL into the form – it gives you something short. You input the short one – it redirects to the long URL. You need to think through the project and identify technical risks, devise architecture, and algorithms. I evaluate the task as easy.

In this task, it’s helpful to know about bits and bytes, encodings. The solution is actually incredibly simple – just save the URL in NoSQL, and convert the index into a base-65 system, which will be the short URL.

Very few, in fact, solved this task in this form. People came up with all kinds of inventions…

The third problem is about data compression. The setting is open – there’s text in Russian, and it needs to take up fewer bytes. But without any loss. Any methods would work. The difficulty is similar to the first one.

Many tried replacing frequent combinations of letters with identifiers, but truth be told, they broke down at how many bits were needed for these identifiers. No one thought of using a variable number of bits per identifier, up to Huffman coding. About 10 percent guessed Lempel-Ziv, but overall, it was also not great. At best, they compressed the text by removing unnecessary bits (since the text was in Russian), which was already quite good.

Why these three? Theoretically, one could have prepared in advance, but thankfully, no company sending programmers ever found out or passed on the details to others. Not sure if it was a plus for them or not 🙂 Even if someone had read about search or compression beforehand, it might have been a plus as you can’t know everything, but the very fact of preparing for an interview adds points.

Each problem doesn’t have a single correct answer. Different solutions can be imagined, and I assessed how much a person’s technical imagination works and how broad their perspective is. How well they can reason and defend their point of view.

Grigoriy Dobryakov, a certain percentage of visitors gave answers like “well, I’ll use Solr and a data compression library.” That’s better than nothing, especially if the person KNOWS or HAS USED all that, but in almost all these cases they couldn’t explain how it works internally. Sometimes, not at all.

With rare exceptions, this system never failed 🙂

September 22 2016, 03:58

A major update on the blog about Hybris. Managed to figure out Apache PredictionIO. An interesting addition to any major online store. The store can send logs to this system, and the system can supply the store with tips on how to earn more. Mechanisms are arranged in templates that just work. It’s possible to delve deeper and tweak the algorithms, but it’s hard to think of a scenario where this would be necessary: the algorithms are quite universal for e-commerce.

I processed some data array from a real online store, and got recommendations from the system based on the purchase history. In another experiment, I received a list of products that the customer is likely interested in.

In short, welcome, likes and shares are appreciated)

https://hybrismart.com/2016/09/21/predictionio-machine-learning-in-e-commerce/

September 20 2016, 21:18

We’ve lived to see it. A 1TB SD card. It’s just a working prototype for now. At Costco near the checkout, they sell 256GB flash drives for 15 bucks. Thirty years ago, my computer had 8 kilobytes of memory. That’s 134 million times less than this flash drive. You could fill a whole pocket with these flash drives. Next, they’ll speed up the input-output. We live in interesting times, comrades 🙂

http://www.theverge.com/circuitbreaker/2016/9/20/12986234/biggest-sd-card-1-terabyte-sandisk