You are right that most of the work does not involve O(N^2) but what can we do. Customer is king. These companies are my customer (in the sense that they pay me money and I write code for them!) They are free to come up with all sorts of stupid ways guage applicants. Either I fight the system or I work hard to get out of it :D