That wasn’t my intention, and I updated my comment to clarify. Did your interviewer offer suggestions or just sit there?
2,951 karma · joined August 28, 2011
https://programmingpraxis.com/2012/01/20/knights-on-a-keypad...
This is a great question because it has several levels of solutions:
1. A recursive solution that iterates over all sequences, exponential time and logarithmic in space. Interviewing for T3 (entry level, think college grad), getting only this far in 45 minutes earns a "leaning no hire" in my book.
2. The above solution except with memoization, which reduces the runtime to linear but requires linear space. This one earns a "leaning hire" from me.
3. A dynamic programming solution that takes linear time and constant space. This one gets a "hire" to a "strong hire," depending on the elegance of the implementation and the strength of the discussion we have around it.
4. A logarithmic time solution involving adjacency matrices, matrix multiplication, and binary decomposition of numbers. I've never seen anyone get this and I only learned about it after months of asking this question.
It's shocking how few candidates actually got as far as solution 1. I kinda want to open this up to the HN comments section, because this does not strike me as a brutally difficult problem, but the rate at which people fell on their faces when presented with this question suggests either something about our interview process or about the candidates we interview.
EDIT: A clarification about “getting as far as” a particular solution: I’m not sitting there stone faced taking notes, I provide hints and prods and suggestions to push candidates toward more optimal solutions. I want the candidate to get as far as possible because it feels good to watch someone succeed, but oftentimes they run out of steam or take forever to implement their solution. In particular with respect to solution 1, if that’s as far as a candidate can get despite my recommendations, that’s not a good sign for their algorithmic ability.
I'm not sure I follow the math here, can you expand a little?
* You obviously need more than one machine to do computation. Things become more difficult as you go from one machine to many, so learn about parallel programming tactics like MapReduce[1] and Flume[2].
* Storing stuff is also much more difficult. You'll either be working with distributed filesystems like GFS [3] or Colossus [4], NoSQL databases like bigtable [5], or SQL-like databases like Spanner [6] and F1 [7]
* Algorithms are tricky, because things that take no time at all on a single machine get to be very difficult when done on multiple machines. I don't actually know of any resources on this one, but if you know the algorithms and learn distribution tactics like I outlined above, it should make more and more sense with practice.
* Finally, you need to know your operating systems and networks. What operations are cheap (RAM access, local disk access, most local computation, same-cluster network operations, streaming remote disk access) and what operations are expensive (longer network hops, random-access remote disk operations). You also should be able to ballpark (to an order of magnitude) things like latencies of operations, dataset sizes, QPS's per machine, etc.
Also, when reading the papers, pay more attention to the interface than the implementation. One of the hardest things is transitioning from being spoiled by the local OS interface, where everything is cheap, to the distributed world, where seemingly random things are expensive or impossible.
[1] https://static.googleusercontent.com/media/research.google.c...
[2] https://ai.google/research/pubs/pub35650
[3] https://static.googleusercontent.com/media/research.google.c...
[4] https://www.systutorials.com/3202/colossus-successor-to-goog...
[5] https://static.googleusercontent.com/media/research.google.c...
[6] https://static.googleusercontent.com/media/research.google.c...
[7] https://static.googleusercontent.com/media/research.google.c...
As someone with access to the entire canon of Google interview questions, I've gone through the 20 or 30 with the highest rating, and none of them are ridiculously hard. The general pattern is either 1. a coding problem, meaning a relatively easy algorithm with plenty of opportunities to screw up the implementation so we can see how well you code and how well you catch your own errors, test your code, etc and 2. an algorithms problem that's really just a dressed-up version of some basic algorithm like BFS or dynamic programming so we can see if you can make the leap from theory to application.
Obviously I'm at an advantage here because I've seen most of the questions in use today, but whenever I encounter a new one I can intuit what's being asked and what it'll take to solve. I'm sure other companies have different sorts of questions that optimize for different things, but for our questions once you do enough of them you can sort of do any of them.
--
By the way, in my experience, those seem to be the biggest pitfalls for both job candidates at Google and programmers I meet in the real world. Sure, you crammed algorithms before you came here, but can you apply them in any real-world way? Sure you know your web/mobile app framework back to front, but will you hit a wall when asked to do something novel? Sure you can write a for loop to iterate over a data set, but will you fall on your face when that data set is petabytes in size?
I've become good at Google's questions because they generally test for those two things: nitty-gritty coding skills and an ability to generalize basic algorithms. The best candidates are those who know their algorithms inside and out, have the ability to break down and transform a problem until they can apply something in their toolkit, and have the coding chops to translate their concept into an implementation. All skills which, you may notice, make for a good engineer.
If you've ever wondered why we still do whiteboard interviews, that's why. Except you can use a chromebook now if you prefer, but you get the point.
Also, consider the converse of this: 98 percent of users use Alexa for something other than traditional shopping. That's huge! Playing music? That's revenue. Playing a movie? That's revenue. Asking a question? That's traffic not being sent to a traditional search engine.
Also don't discount the value of having a toehold in someone's home. At the end of the day, this isn't a shopping play, this is a platform play. That device can be leveraged to sell new products, push new services, and enhance loyalty to the Amazon brand and ecosystem.
I respond that this is inconsistent with both stated policies and established practice, and such managers can and should be targeted to answer for their bias and have it corrected. I would also respond that if a journalist with an axe to grind were to search hard enough and interview enough people, they're bound to find someone they can put on a pedestal and point to saying "look at how corrupt these people are!"
If anything, a person believing this sort of anecdote about an organization says more about the believer than the organization in question.
> Why is it that so many of my acquaintances who work at Google pig-piled James Damore over his professional competence, despite none of them being in a position to have any idea about that?
That does sound unfair: Damore was a senior engineer, which not a title that's given out lightly. Again, though, peoples' possibly unfair commentary on his professional abilities says nothing about the quality of discourse in the company. And again, one's willingness to balloon these sorts of individual anecdotes into indictments of an organization as a whole say more about the person doing the indicting than the organization in question.
All of which is to say how surprised and thrown off I am by this article: it and previous ones [1] try to portray Google as a place that's roiled by political fighting where the leaders are struggling to keep control over a irresponsible and politically radical workforce. Under this narrative these new policies are just the newest, desperate attempt to restore order to the snowflake cagematch that is Google.
The reality, at least as far as I and practically everyone I've spoken to is concerned, is the exact opposite: people share their views openly, a wide range of opinions are respectfully shared, most people have the right to get into and stay out of political discussions, and the institution does the best it can to set the boundaries of what is appropriate at work while permitting a otherwise anything-goes approach. If this reality is anywhere close to being accurate, the picture this article paints is simply nonsensical.
[1]: https://www.wsj.com/articles/google-vs-google-how-nonstop-po...
What I'd like to know, as an American sitting literally a world away from the people under this system, is to what extent wealth and influence purchase a high social credit score? Some factors are obvious: those with more money are less likely to incur debts, for instance. But what about connections to administrators? I imagine there isn't a politician in all of China who doesn't magically have a sterling social credit score.
I wonder whether the net result is a society in which a high standing resulting from material and social wealth leads to perks that in turn lead to more material and social wealth.
> "When we first deployed and we were learning how to use it... some of the digital images we used weren't of sufficient quality," said Deputy Chief Constable Richard Lewis. "Because of the poor quality, it was identifying people wrongly. They weren't able to get the detail from the picture."
> Information Commissioner Elizabeth Denham said the issue had become a "priority" for her office.
When you roll out facial recognition technology at an event with ten thousand people and expect your magical facial recognition system to pick out just the bad guys, you quickly discover that even a system that's 99.99 percent accurate has a 63 percent change of giving you at least one false positive in that crowd. In reality these systems are probably closer to 95 percent accurate, in which case you're looking at vastly more false positives. Like hundreds per event.
This is the exact same statement as "breast cancer screening is staggeringly inaccurate." Do you know why breast annual cancer screenings aren't recommended for women under 40? Because breast cancer is so rare in that population that the high false positive rate outweighs the benefit of early detection. The correct thing to do is only screen only if there is already a suspicion of cancer.
Similarly, pervasive surveillance where you (statistically) consider everyone a possible criminal is a waste of time. Anyone who's ever taken a probability course will tell you that unless your facial recognition tech is fantastically accurate you'll waste all your police officers' valuable time sorting through false positives.
This is not an image quality issue. It's not a data quality issue. It's not a deployment issue. It's a Bayesian statistics issue. Unless your tech has superhuman 99.999% accuracy, it doesn't matter how accurate your facial recognition is if you're looking for a needle in a haystack. I'm sure the facial recognition is just as wonderfully accurate as breast cancer screening, it's just being applied to a population with a stupidly rare prior.
This is a statistics 101, freshman undergrad-level mistake, and frankly it makes me mad as hell that authorities are stupid enough to make it and boneheaded enough to endanger their entire population's civil liberties in the process.
For more info, check Wikipedia's page on the aptly-named prosecutor's fallacy: https://en.wikipedia.org/wiki/Prosecutor%27s_fallacy
As an anecdote from my own engineering school experience, a staggeringly large proportion of my classes were populated by foreign, usually Chinese and Indian, students. My college has a pretty good brand, and I understand many of these students were willing to pay to have its cachet on their resume. Also, many of these students, especially the Chinese ones, seemed to be from very well-off families (at least if the number of Canada Goose coats and Supreme hoodies is any indication).
This is an anecdote, so take it with a grain of salt, but it suggests a hypothesis: maybe the drop in demand is among American students who are mostly paying discounted prices anyway, while demand among foreign students who are willing and able to pay the staggering sticker price remains high.
The search algorithm goes way out of its way to determine some measure of "legitimacy." Obviously this is a vague and hard-to-define measure, but the goal is commendable: show results that are both relevant to the user according to Google's relevance metrics and legitimate according to who links to it, quality of the page, freshness, etc. Whatever qualms you might have about the vagaries of the search algorithm, you can't dispute that it's difficult to game.
Meanwhile ads are chosen by what brings the most long term value to Google. Gaming this system is much easier, and usually begins with paying more per click. This favors advertisers with higher margins, which is harmless for innocuous queries like "flowers" which make up the bulk of search ads. For bail bonds, however, this favors advertisers with higher margins, which in turn rewards exploitative providers over the legitimate bail bondsmen this author seems to think will be harmed. If anything, this is actually a boon to the more socially-minded bail bondsmen this article is concerned about: exploitative bail bonds businesses that go out of their way to saddle their customers with debt will not appear on the top of the page, raising more legitimate ones.
Another point: one of the consequences of being able to pay for ranking is you can place ads on terms that are not really related to your business. For instance, "Home Depot" queries tend to show ads for Lowes and other competitors. In a similar way, searching for "bail bond counseling" and other terms tends to include at least one for-profit bail bond operation that offers no or nominal counseling. Meanwhile if there are no ads, then the legitimate counseling services will float to the top of the page. Likewise for queries for all the other services this article claims will be hurt.
Source/disclaimer: These are my personal opinions as someone who works in ads at Google, (but was not involved in this decision). All my points come from publicly available info. Please don't mistake this for anything but my own views.
I caution that either conclusion would be unjustified because this is not a UBI experiment, this is a charity and aid distribution experiment. The question at hand here isn't "is UBI a wonderful thing" but rather "how do UBI-like distribution methods compare to others?" If you want proof consider that Tavneet Suri's isn't a UBI economist focusing on western countries, "her expertise is as a development economist, specialized in Sub-Saharan Africa" [1]
I object to labeling this as a UBI experiment. "Universal Basic Income" is used to describe various proposals to address inequality and unemployment in developed countries where economic gains and jobs are being automated away from the masses of low-skilled workers and up to the elite of high-skilled workers. This is far from the sub-Saharan African context where the economy is still developing and leaders are mulling how best to sustainably extract countries from extreme poverty.
[1] http://mitsloan.mit.edu/faculty-and-research/faculty-directo...
* Existing codebases need to be maintained. Small companies tend to be younger, which naturally comes with fewer existing systems that require maintenance, and those systems that do exist are generally smaller. The time spent keeping a large production system up and running feels wasted, but it's absolutely not, especially when you consider the alternative is letting the thing fall over and losing the revenue, users, etc. Contrast this against a smaller company where more projects are fresh and satisfying to write.
* Lots of work centers around adding features instead of greenfield projects with no history. Most of the code is already written, much of the infrastructure is already in place, and oftentimes the problem is similar to one that was solved previously. You end up writing less code to get more results, as opposed to a greenfield project where you write tons of code to even arrive at a baseline.
* Larger companies almost certainly have more irons in the fire than smaller ones. While on an individual level it's annoying to have to wait for input from someone who has half a dozen projects on their plate at once, on a company level this makes sense: when you have to put fifty features into production, you don't organize each one individually, you create a pipeline composed of people and run your work through it.
* As a result, projects at larger companies have more stakeholders, which means you need to get agreement from more parties before you can move forward. Also, you're likely not the only thing on those peoples' radars, meaning you'll have to fight for their attention.
* Larger and older companies tend to encapsulate their lessons learned into this pipeline. I'll hazard a guess that this is what people mean when they talk about "institutional failures" led to damages like Well Fargo or Facebook/CA, etc: no individuals failed, instead the system put into place to pipeline their work was faulty. The "human pipeline" of a larger organization was almost certainly built up in response to a long series of nonpublic failures. More quality in the form of fewer such failures, at the expense of higher latency.
* Politics is a thing. Larger companies almost uniformly have career ladders, with the aim of giving people a way to advance their career besides "take a CTO position somewhere else and come back at a L+1 18 months later." This means at least some of engineers' time will be spent marketing themselves for promotion rather than writing code. This often means choosing and prioritizing their projects by biggest expected impact. This has consequences if that engineer is a stakeholder in some other engineer's project and they disagree on the importance of that project to their respective careers.
* Finally, there's a human component to this. In my experience, the sorts of people who join smaller organizations and get tons of work done tend to be younger and less tied down. You're not going to be working at a 6-days-a-week 8am-8pm startup with a wife and children. You're going to be looking to put in your time and head off to live your life. Meanwhile your management is still going to demand big things from you, so you end up becoming efficient out of necessity.
I'll leave you with the upside to this so you don't come away thinking large organizations are hellish slave pits: The impact of your work is larger simply by virtue of your being at a large company. I won't go into details, but I work in a group that puts in months of work to move revenue by shavings of a percentage point here and there. When you finally launch, you end up thinking "man, all that work for a 0.5% improvement?" when in reality the baseline of that improvement is staggeringly large.
The only place where math was involved was the guts of the training stage of the model. A crucial stage to be sure, but one that's bookended in the front by problem definition, data selection, model selection, and a design for an evaluation process, and behind by the execution of that evaluation and the decision to launch the model. Literally every other stage of this process is driven by human decisions.
I'll say it again, because apparently the point didn't sink in the first time around: Machine learning models are inference and pattern recognition devices, not scientific tools. The fact that it's inhuman and unthinking mathematics that produced a biased model offers no ethical or legal cover to the people who decide to put that model into use.
The decision to apply the model is key here. Contrast two applications: one that takes in a patient's information and diagnosis to compute a dosage for a drug, and one that takes in a potential tenant's request and produces a rent/no rent decision. In the first, there are cases in which the bias is admissible if not necessary, e.g. [1]. However, the legitimacy of that model's application comes not from the supposed objectivity of the model's findings but from volumes of peer (i.e. human) reviewed research. In the second, there is no legal way in which this model can be applied, and I struggle to imagine a moral one. I can't imagine any court of law taking "the machine made me do it" as a defense in an FHA case.
[1] https://www.nytimes.com/2005/06/24/health/fda-approves-a-hea...
Now imagine the same scenario except your app was trained on data instead of hand-written. Make no mistake, the answer to the question of who's to blame is exactly the same: the developer. The response should be exactly the same: a complete loss of confidence in the model.
I'm appalled that this needs to be said, but reading this comments section I'm afraid it does: Machine learning models are inference and pattern recognition devices, not scientific tools. They don't magically reveal hidden patterns in the world, they repeat the patterns that the developers train them on. If you trained a machine learning model to perform psychological evaluations [1] or sentence convicts [2] or recognize faces [3], and your model is biased in a way that is unnecessary and unjust, your model is bad you should be held accountable for its failures.
[1] https://affect.media.mit.edu/projects.php?id=4079
[2] https://www.nytimes.com/2017/05/01/us/politics/sent-to-priso...
[3] https://www.wnycstudios.org/story/deep-problem-deep-learning...
Do you think we should train AI to systematically ignore those sentiments?
Let's not forget, Goldman Sachs and its biotech brethren are businesses. All business involves long-term strategic planning, often behind closed doors, to answer the question of "what application of our existing money will make us the most money in the future?" When viewed through this lens, Goldman's statement can be polished up to "of all the biotech investment options we're weighing, investment in outright cures for infectious diseases is less profitable in the long-term because curing people has a nonlinear effect on the patient population." It's a simple statement of fact.
OP's summary, and I strongly encourage you to actually read it if you haven't, goes on to say that Goldman's research suggests long-term research and product investment would be best applied to medical conditions like cancer and aging, for which a cure for an individual doesn't result in a diminishing market.
This isn't nearly as evil-sounding as the article aims to make it sound. At worst, it highlights something we already know: market-based solutions tend to be flawed, and if we want investment in treatments for infectious diseases we need to turn to forces that are exempt from market forces (i.e. government research funding). At best, it's an indication that we can expect more investment to go into things like cancer and age-related diseases.
We tend to think of large companies as either these monolithic beasts that act according to their own best interests, or as emergent hiveminds that move in a direction because they smell money. These have the advantage of allowing us to presume that the actions taken by these organizations were vetted by many people and arrived at via consensus.
However, there is a third, less popular, way to view organizations, and that's as an organ of a handful of people, if not one person. This is an important framing because it allows us to consider the actions of these large companies as reflecting the foibles of the individuals at the helm. Viewed this way, Apple under Steve Jobs was an extension of one man's vision and design priorities. Microsoft under Ballmer was an extension of one man's putting the MBA approave above the tech approach.
I can't help but wonder if, within these Wall Street companies as well as throughout SV, there wasn't a single person or a handful of people who swallowed the blockchain coolaid and started these projects. Pitched high hopes to developers. Hired developers. Set goals. Failed to meet goals. Made their developers' lives miserable. Gave up. Blamed their subordinates. Moved on.
This is a tale as old as tech itself, but somehow it just keeps happening. To all young developers deciding where to invest their time and talent: be very careful choosing to follow an individual, because individuals are stupid enough to fall for nonsense like "blockchain for banking."
I'm pretty sure this is aimed at enterprise applications.
> there is a CISO position to fill at @facebook I hear
@lcamtuf:
> Waiting for NYTimes to tell me why I am leaving Google first.
This little exchange speaks volumes about what's happening in the the media regarding the tech industry: one company behaves badly and then all get tarred and feathered. Facebook's security leadership starts jumping ship, and when someone analogous from Google, a completely different organization with a completely different (i.e. existent) moral compass and set of security practices leaves his post for unstated reasons at about the same time, the world assumes a similar scandal is on the way.
That's exactly the point of taxing revenue: under a profit-based taxation scheme you'd end up with a net profit of zero. Revenue taxation schemes would double-tax this setup.
Face it: some form of taxation was going to appear no matter what. It's inevitable. You don't just roll into a country, make billions of dollars, and expect to pay no tax in perpetuity. As tax proposals go, this one is pretty reasonable.
This isn't a punitive measure because it sets no one apart for any past behavior. It also isn't a "shield from competition" because all companies have to adhere to it, not just American ones.
* It's done on revenues and not profits. This avoids the impossible question of where profits are realized: if you make money in one country but displace that earning by costs somewhere else, it's practically impossible to determine where the tax should go.
* It's uniform across the EU and so it doesn't incentivize companies to base themselves in any member over another. This avoids the distortion we have now with Ireland's permissive tax system siphoning up all the company headquarters and with it the (scanty) tax revenue.
* Each member receives money based on the number of users they have in their own country, meaning they have a strong incentive to increase usage of digital services and a disincentive to put in place regulatory measures that would decrease adoption and harm growth.
One of the problems of the current situation is that it sets tech companies up as these parasitic monsters that creep into a country, make huge profits, alter the society as they see fit, and give nothing in return. The best thing about this proposal is that it sets up a harmonious relationship: governments get to make money while companies get to have their access to citizens legitimized. With that legitimacy comes better PR and a seat at the table as legal systems everywhere catch up to the world tech companies have created.
Plus it might finally put that ridiculous "tech companies are tax evaders" meme to rest.