I joined my company as an intern ~5 years ago & when I interviewed for the position I didn't have to solve any white-board style interview questions etc., since it was an un-paid internship. After a few months I had demonstrated my ability to write code they made me an offer.
When I now casually look around and apply for mid-to-senior level positions I cannot seem to get past phone (coding interview) part, that involves solving some basic algorithm on collabedit. I get nervous and given I need to solve (perhaps a simple) problem in an optimal/sub-optimal way in 30 minutes, my brain sort of shuts off and I cannot arrive at a clean solution, let alone solve the problem end-to-end.
I'm respected within the company, if you were to ask any colleague I have worked with whether I can write clean testable code that solves real business problems, everyone would attest that I absolutely can.
How do you create that environment of - "Coding under pressure and someone looking at your code while you're trying to think of how to solve a problem and your brain is thinking about everything other than a problem itself"???
One idea is to just keep applying and failing until I become immune to it. But each failure kind of brings me down, and makes me think that I'm a bad engineer.
Last thing I want to mention is that I don't blame the process itself. I think white-board style questions eliminate a lot of bad candidates. I know that the process has to be rigorous because those jobs pay well. But there's also extreme examples like the inventor of homebrew that got rejected by google because he couldn't reverse a binary tree.
What’s your goal? I assume, get a new, higher paying job. What’s the barrier? Interview style coding problems, apparently.
So, things that will help you achieve your goal (IMHO):
- Buying and reading cracking the coding interview
- practice solving problems on sites like hacker rank and leet code
- when you practice, try simulating interview conditions. Use pen and paper or a whiteboard if your interviews will involve that
The more familiar and mundane the problems become, the less likely you are to feel nervous with an audience. Just practice the problems until it is like tying your shoes.
If asked to tie your shoe with someone watching, would you be so nervous as to be unable? If so you may have some serious anxiety issue you might want to work on before starting a job search.
Things that definitely won’t help you achieve your goal:
- ruminating on life’s injustices
- ruminating on your own shortcomings
- comparing your self with others
- ruminating on the decidedly capricious and error prone hiring practices of Silicon Valley companies.
Life is not fair and there is a time and place to think about those things. But doing so is counter productive to your goal, so I wouldn’t recommend it at the moment.
I worked with a guy, Bob, in our college computer room. Bob had returned to get his BS after many years in industry. He had great stories. He also had great advice. He taught me that you can learn a lot about how a company will treat their employees by paying attention to the way they treat you during the interview. He suggested several sign that indicated it was best to just "walk away".
If you go into a restaurant for a professional lunch meeting and they have a ball-pit / swing set /etc. it might not be the most professional place to hold the meeting. Just walk away.
If you go to a 5 star restaurant and they want you to wear a clown nose (Everybody Does It!) Just walk away.
The big scam is "We hire the best and the brightest". "We mandate a whiteboard test (Everybody Does It)". It is my opinion (based on experience) that companies that insist on a whiteboard test, despite years of programming on your resume and open source code, are either Ball-Pit companies (who don't know what it means to be a professional) or Clown-Nose companies (who know what it means to be a professional but still treat you like a commodity). Just walk away.
I understand why Google does it. I've even interviewed there. They get thousands of resumes (which they never read, at least nobody did at my interviews). They have to weed out the "learn coding in 6 weeks" crowd. But you're a professional. You should expect to be treated like one. You don't ask your surgeon to cut up hams in an interview. You don't ask your builder to nail two boards together. Professional accountants are not interviewd by bank tellers and ask to count change.
Google, like Microsoft before it (remember the "why are manholes round? quizes?"), have combined the marketing claim "We hire the best and brightest" with the ball-pit mentality of whiteboarding. Google HR (sorry, People Resource?) SHOULD be embarrassed but apparently they, and upper management, LIKE ball-pits.
A real professional interview involves a discussion about what the company does, what it current problems are (aka why are they hiring), and a discussion of if you, as a professional, have the skills to solve the problem. What do they need? How can you contribute?
We, as professionals, should consider whiteboarding as an insult.
Just walk away.
This is the typical HN vs the world attitude. "Boycott the world!" I understand the sentiment and I certainly have heard and experienced a good deal of interview horror stories.
But as career advice, I think your anger is getting in the way of your reasoning. "Turn down Google and Facebook because they don't respect you enough!" is most likely terrible career advice for the OP. The big tech companies pay world class salaries and (despite your experience) do not have a reputation for being terrible places to work. Indeed, big tech companies (the same ones with Kafkaesque and soulless interview practices) regularly make lists of the top 10 best places to work in the US.
My own experience is that every company I have ever worked at had varying level of bullshit, but that there has not so far been any correlation with the interview technique used.
As for the myth of "world class salaries" I know, for example, that my nephew who works at one of the Top 5 companies, has a salary that is higher than I ever made. But he also lives near the company and has to share the rent with 4 other "world class salary" colleagues because he can't afford an apartment. I used to work in NYC with a "world class salary". One place I looked at to rent was $2000/month... which was a couch in the living room behind a japanese screen and kitchen privileges. Salary is relative (as in, it helps to have a relative with a basement apartment).
I've been to Google. What I saw was a large area of desks with no partitions, a literal sea of "the best and brightest". A historically accurate counterpart might be https://bakethiscake.files.wordpress.com/2012/07/sewing-room...
However, the coffee is fresh and free. The sleeping pods are available. Laundry and haircuts can be had onsite. The food is first class and available for breakfast, lunch, and dinner. There is, in fact, no valid reason to leave the building. It's almost like working from home.
If you're fresh out of college and just passed your data structures final you probably can quote the order of an algorithm off the top of your head. If you hate your current job enough to put up with anything, sure do the whiteboarding. I certainly have done it. I'm not above it for some jobs. If you don't mind travelling to a location and talking to people who have no idea what you might do, why you're there, or who you might report to, then go for it. If you're being laid off and need a new job in a hurry, go for it. If you're not confident in your abilities as a professional, go for it.
But if you're job shopping and looking for a company that respects you as a professional, give some thought to the interview process. That process is dictated by management so it is a direct representation of how management views you. If you are considering a job change and looking at other companies, look carefully at what is being presented.
I've had bad interviews that were directly with the hiring managers. But at least I was pretty sure that I was turned down because they didn't need or didn't want what I could do for them. And I didn't have to remember that Coopersmith-Winograd is O(n^2.375477).
And adding noise to the hiring process increases the effect of "we are the best".
If you flipped a coin, it would be more honest and less expensive than putting people through a "difficult" whiteboard test. But you wouldn't get the "we only hire geniuses" effect.
As these "difficult" tests are usually based on a corner of the CS field that the interviewer enjoys, it is essentially random, while appearing to be totally meritocratic.
You end up with a process that filters out 90% of qualified candidates, but nobody that was hired by that process wants to change it.
At small companies, the people that interview you are likely to participate in the hiring decision, so it stands to reason that they would read your CV. At companies like Google, interviewers are tasked with providing data that's not on your CV. Your CV would definitely be read by several people before an offer is extended.
"real professional interview involves a discussion about what the company does, what it current problems are (aka why are they hiring)"
For a company as large as Google, there is probably no one who could tell you what all the current problems are. Or even what all the open software engineering roles are about. And there's a lot of information on the web about Google, what they've done, what they're doing and trying to do.
(If I were being considered at a role at a small company, of course I'd expect the type of discussion you envisage, early on in the process. But at Google etc. I'd expect for those issues to be discussed with the recruiter (early in the process) and then with specific hiring managers (when they're ready to make an offer, but need to match you with a team)).
You're entitled to your opinion.
I even happen to hold part of it.
But discounting the entire idea of whiteboarding is incredibly stupid.
No, you should not be writing more than pseudocode/logical outlines on the board.
But you absolutely must be able to convey ideas - and visual conveyance is the best way to convey them.
Draw basic flow diagrams.
Write logical steps.
Document, explain, and argue for not only why this approach "will work", but why it's appropriate for the given scenario (could be, "if I only have an hour to get this to work, this is how I'll do it: it will work, but it may not be efficient or pretty", or "here's the high-level overview with a couple zoom-ins - obviously the full solution will take some time to fully architect, but this is a very strong start", or "there are many better ways of solving riddles like this - I don't waste my time recalling those trivialities when I can look them up in a few seconds in <name of book/website>").
What I, personally, have a problem with is using it as the catch-all filter to weed out 'bad candidates' when in reality all it does is prove someone can grind leetcode and is good under pressure. Arguments can be made that those are desirable skills to have, but I hate that it's becoming the default pass/fail section of an interview.
In OPs case, and what I am generally against, is that white boarding is being weighted more than any other portion, including relevant and measurable experience. Sure, give a simple problem if you're worried the candidate is BSing about their experience/skills, but it should be set up for success and not failure.
Unfortunately, as long as the 'best companies' (i.e. FANG) are doing it, everyone else will follow suit. And yeah, it'd be great if job seekers had the opportunity to walk away from these types of interviews, but in reality it is very much a company favored market when it comes to hiring in tech right now. Despite the constant supply of new job openings, nobody seems desperate enough for engineers to change things up.
There's also a bit of engineer hubris involved. Most people who are into CS seem to be highly competitive and willing to show off, and white boarding sets up a great environment to get your ego stroked over how well you can optimize something for no reason at all.
It was in another recent thread someone was insisting you should "just walk away" if the company doesn't have private offices.
It's not practical for most people.
IBM often had "hiring freezes", nobody could hire anyone... well, except that I still did some interviews at IBM Research. There were people we would hire under any circumstance. In fact, one of the people I interviewed during a hiring freeze was offered a job and a whole new lab. She really was one of "the best and brightest". (She actually did walk away and went elsewhere.)
Do you really think that Geoff Hinton, Andrew Ng, and Yann LeCun got whiteboarded?
I would strongly to suggest finding interviews at some stage of our lives with the pure intent to walk away from. If you feel strongly about the process, it's one thing to grumble, but this is the only way change will happen.
If you're desperate for a another job however, and are really feeling like you need to be in a new place within 6 months, then go through a phase of sucking it up, finding a daily challenge on hackerrank, and seeing if "you've still got it" with these silly problems that we all know are exclusive to undergrad studies and nowhere else.
Great analogy with the ball pit and clown nose btw, I'm going to use that.
Just walk away."
Absolutely disagree.
There are tons of developers who have many years under their belt and have glaring holes in their skillsets, or have a complete skillset mismatch, or who are simply not very bright.
Conversely, there are some people who are absolutely brilliant, or deeply knowledgable in some areas, and this is one way to possibly determine this.
Though a whiteboard discussion is not always going to be entirely efficient, and can be used to test all the wrong things - it is an opportunity to talk with someone directly about the kinds of problems they will solve.
Any developer that won't do whiteboard work is displaying 'negative signals' and you should not hire them.
Of course, asking potential hires ridiculously difficult or specific questions which essentially tests their ability to memorize CS algorithms is futile as well ... but whiteboard chats are generally positive and it's why all the best companies use them.
It is a sign of "an attitude and discipline problem", what IBM Research used to call "wild ducks". They placed great value on finding and hiring "wild ducks" (well, they used to, until they decided to "manage" IBM Research). A wild duck doesn't look for the most efficient algorithm, they look for the most efficient solution. They are rarely the same thing.
Most companies decide to hire someone when they have a problem that needs a solution, when they plan to expand in a new direction, to enhance the skillset of a team, or to cover work based on a new or expanded contract. It is very odd to hire because, hey, we want "the best and the brightest".
So the most efficient method of hiring for a solution, direction, skillset, or contract work is DISCUSSION between the person who has the problem and the person who might be the right fit for the problem. If you're looking to move your bank into digital currency it is a pointless waste of everyone's time to schedule interviews with four bank tellers.
Also, in my experience, whiteboarding is usually conducted by new hires (maybe it's just me?) who recently graduated. So their questions involve either an algorithm they know well or a discussion of the order complexity of the algorithm. Odds are good the questions were on their data structures final exam last semester. Perhaps I never get past this level because I don't know how to program.
Whiteboarding is the same level of nonsense as the old Microsoft "How many gas stations are there in NYC?" interviews. It is supposed to show that you can "reason" and give you an idea of how intelligent someone is. In my experience interacting with intelligent people, their "intelligence" shines through in conversation.
First off, you are not a bad engineer for failing a technical interview. Over the past 3 years, I've applied for hundreds of roles across dozens of companies. I've been through dozens of interviews and I've got offers from (or worked at) Uber, Twitter, Microsoft, Tesla, etc. The side of the story I don't focus on is that I've had over 200+ rejections. Some after first rounds, some just after they look at my resume. Rejection is part of the game but you just need to push through it. Here's my advice.
- As other comments have said, it's definitely a numbers game. Some days you just don't mesh with your interviewer, others you know the answer to their coding question before they've even finished asking it. Just apply over and over if you want the best odds. You can't get too emotionally attached to any single interview opportunity. I've had to apply for ~50 roles for each offer I get. That's just the way it works.
- Practice a ton. It sounds like you are more worried about coding under pressure and thinking through the answer while you are in the middle of trying to explain your thought process to the person interviewing you. I recommend pramp.com You interview someone for 30 minutes over the webcam and then they interview you for 30 minutes. It's super convenient and gets you very comfortable thinking through problems on spot with someone else watching you. I normally do ~10 pramp.com interviews while I'm preparing for an upcoming interview. In person interviews with friends is good too but less convenient than just signing up online for a time slot.
Just remember that bad interviews don't make you a bad engineer. At the end of the day, no one will remember dozens of rejections, but they will remember the job you eventually land. Keep interviewing till you get an offer that you're excited about. Good luck!
That said, getting rejected from a company that you had your sights on... that does suck, at first. But usually you can apply again in a year.
Yeah I've been through this many rejections total, and some of them have been pretty tough emotionally, but it only takes 25-50 before landing another really cool job I've been excited about. 200 rejections is pretty soul wrenching, but getting the other big companies on the resume makes it more than worth it.
not to bite on what you're saying (it's mostly accurate) but you've interned - the bar is much lower for interns than even junior devs.
>I've applied for 300+ roles across 90+ companies
i am interested in how you've managed to apply to multiple roles at the same company? is this across 3 internship seasons?
A lot of companies will list the same roles across different teams. Applying to (or interviewing with) all the different teams helps your chances. I'm at Tesla right now and I applied for 15 different roles over the span of 3 years before they gave me an offer.
HN has rehashed this debate plenty, but I don't think you should necessarily see this as an example of a dramatic failure of the Google SWE interview process.
Homebrew became a success due to great vision and execution, not because it solved a challenging technical problem. Howell seems like a great guy who would probably make a great senior developer, founder or PM at any company that aims to solve customer needs.
Google's focus, however, is on hiring SWEs that can solve uniquely complex and difficult technical problems. The merits of such a narrow focus is obviously up for debate, but if that is to be your goal, this hiring decision aligns with it.
I think that's kinda just marketing TBH. How else do you explain things like their habit of overhauling the graphics while removing functionality on many of their popular offerings? The last update of Google News looked a lot nicer but removed all user customization of the news feed - you can't even filter out sources any more.
I mean, maybe there are a lot of super-clever SWEs at google who are bored and frustrated with everyday consumer-centric product development and so do a terrible job at it until they're rotated onto something more interesting. I can't think of any other reason to inflict such a product on the public.
I can't speak to any specific instances, but generally when this happens it's because the front-end needed replacing, and not because they had to give up on supporting the functionality on the backend.
For example, the front-end may have been mobile or offline hostile, while the new one works great with both but only reimplemented 80% of the massive feature set that the old UI accumulated.
It sucks if you primarily used the site on desktop and heavily leveraged the missing 20%, but I can see the value in such a trade-off.
Huh? Isn't all difficulty in software complexity management? Isn't writing a package manager a sufficient demonstration of that? What's a "difficult technical problem"?
Isn't solving customer needs through managing technical complexity what Google should be hiring for, full stop?
I'm actually confused at the philosophy here.
Another way to think about it is that Google wants SWEs who can also act like researchers (e.g. PhD students).
He joined Apple after that and was interviewed on the Changelog not long after he left.
Honestly he sounds like a really difficult dude to work with.
PS: I also failed much easier interviews at CrowdStrike and SourceGraph so maybe I just suck at being interviewed in a way that's not clear to me. It really takes a toll on your confidence though.
Try not to take things personally, it could have just been a bot. https://news.ycombinator.com/item?id=17334552
1. Pick up leetcode (or whatever rocks ur boat).
2. Do a lot easy questions and understand the pattern.
3. Do medium level questions and understand the pattern.
4 If you are aiming for Big 4 do Hard.
Coding interviews is all about finding the pattern and applying it. Only way to be good at it is practice. Don't give interviews without some practice.
My unsolicited advice is to:
A. Come to terms with the fact that there has been a shift in expectations from employers. Understand that to get the really plum jobs it will require a lot of dedication to get to where you need to be interview performance wise.
B. If you are really rusty, start off with Firecode.io. It provides a more structured approach to studying these interview questions. Once you feel comfortable with the questions there then you can go for Leetcode.
C. Go to interviewing.io and pramp and practice with actual engineers. This will allow you to work on your communication skills. A big part of interviews is just basic communication. You could be rock solid with your algorithms but if you still can't communicate what you are thinking to interviewers in an effective manner you still won't pass the screen.
D. It's not a particularly popular corner of the internet but reddit.com/r/cscareerquestions has a lot of good advice on how you can improve your interview skills. It's also a good place to get a sense of how interviews are structured, how people typically prepare, expectations etc. It's skewed towards getting jobs at the FAANG type of companies but the good advice you will get in the sub is pretty solid and will help regardless of the direction you want to go.
Overall, try not to be too hard on yourself. Technical interviews are an inherently noisy screening tool, and a lot of great engineers fall through the cracks. Preparing for these interviews just like you would prepare for any other important assessment will help you in being more competitive.
> good advice
That place is literally college confidential for CS students. It really doesn't help anyone when the people who are giving job advice haven't even left school yet.
I signed for the role of Senior Product Engineer just today in a pretty fast growing startup company.
Contrast this to my daily work, which is often highly technical and high pressure in a wide variety of areas.
The tech interview is broken. The problem is that there aren't many good ideas to replace it. Every large company is focused on eliminating personal bias, easing the process of training new interviewers, and improving repeatability. Pass/fail-type challenges (or perhaps a simple grading system) are the easiest way to achieve those things.
Additionally, companies like Google and Facebook can absorb large numbers of junior candidates directly from schools. Most of these exams are geared toward those fresh from an academic setting.
Small companies adopt these techniques because they also want "the best" without actually considering their real needs. As a result, a cargo cult has arisen around making the technical interview increasingly long and baroque.
Here is some practical advice:
1. Talk to your doctor about your situation and tell them you've heard beta blockers[0] help stop the flight-or-fight response.
2. As others have said, practice over the course of months. Do the same problems again and again. If you can't solve these toy problems without pressure, you definitely won't solve them with pressure.
3. Ask the company ahead of time for a take-home as an alternative. Explain the situation.
Ultimately this situation won't change until engineers in decision-making positions force it to change. Interviewers also need to be trained on how to recognize test anxiety and what strategies they can employ to ease that.
One of the most effective ways I've found to deal with this is be open. Say, "Yeah, I suffer a bit from anxiety and interviews in particular are difficult. Do you have a take home interview? I can easily commit to git in near real time if you want a blockchain-quality log of my process, and I'm happy to review it with an engineer." I have gotten a surprising number of takes on this (and in general I annihilate these).
As a bolster to your confidence, try not to take these too seriously as an indicator of your personal skill. Having worked a bit on my current and past employer's interview process, tbh an awful lot of orgs have questions that are more like riddles than actual coding exercises; they often have a simple solution you have to "know" otherwise the problem is excruciating and every solution is obviously bad. Examples of this include "chocolate bar" division problems, skyline problems, or rainfall problems. All of them are bad examples.
We also enjoy a sellers market for many tech skills right now. In such a market, interviews can also be information for you to save your time not proceeding. This feels very strange for people normalized to the creepy feudal culture of tech where you align yourself with a company body and soul and only state laws allows you to escape their clutches, but it's pretty powerful. If an interview seems deliberately excruciating, just say, "I've seen all I need to see. Thanks for your time, but I don't think you're a good fit for what I'm looking for in an employer."
Finally, it's also worth remembering that just modest reading in PL, CS and database literature written in the last 10 years often gives you ammunition to completely break down these questions. The folks that structure and ask these only seldom actually their theoretical basis. I've managed to break out of ugly and tedious interview questions by flipping the conversation to something I do know well and am confident speaking to, like modern O(n) sorts (discrimination, american flag), wavelet trees, recursion schemes, CRDTs and strategies for gossip protocols. Appeal to their greed and interest and show them that you DO know things, you just may not know THIS thing RIGHT NOW.
1. Others already recommended to practice solving problems on LeetCode;
2. While solving these problems don't spend too much time if you got stuck, look for answer or discussion after hour or two;
3. If you feel weak on some topic (e.g. dynamic programming), try to read up related material, lecture notes, familiarize yourself with classical problems on this topic;
4. Even if you solved problem, look for other answers. You often be surprised how much shorter and concise solution can be;
5. Read some books on algorithms like Skiena or Papadimitriou. I don't recommend you to read Knuth or CLRS unless you have strong math background. Skiena or Papadimitriou are much easier to read for beginner. Also, separately, I do recommend the book - Programming Pearls by Bentley;
6. Once you practised for two months or more, start taking mock interviews on Gainlo;
7. Enjoy algorithms and solving programming puzzles. Enjoying algorithms is a must because if you really want to master it to the Google interview level, it may take years;
Same for coding interviews. Practice, then interview. 5-10 years down the line, every time you're looking to switch jobs, it gets easier, and you get the insights from the past experiences.
NB
The phone screen isn't easier than on-site; it can often be harder, and often is the same level of difficulty, with more pressure.
NB 2
If you're mid-level they'll ask a few systems design questions. Make sure for the systems you've built, you know at a high level how each individual component was built and what abstraction it stands for.
Good luck! And ping me at my tw email (check profile) if you want to follow up
Here's a tip that they either don't tell you, or that I managed to overlook. You are allowed to mutate inputs.
I had assumed that inputs were read-only, and spent about three months trying to solve "Given an array of N integers, find the smallest positive integer that is not in the array, in O(N) time and O(1) space". (It wasn't three months of constantly working on it...it was more for three months it was one of my "something to think about while falling asleep in bed or while sitting at a red light" problems).
I then came across a site that talked about the problem and mentioned doing it in O(1) space involved overwriting the input. It was only a couple minutes to solve after that.
Possibly interesting variant of that problem: Can you still solve it in O(N) time and O(1) space if when your code returns the answer the input must be unchanged? You can still mutate the input while your code is running, but you have to undo any changes you make before returning.
I'm pretty sure that the answer to this is "no" in the general case, but if you are allowed to limit the size of the input so that N is not a significant fraction of MAXINT on your machine you can do it.
I don't think that is possible in general. In some cases, such as your "small integers only" case, the program can get extra working memory by essentially compressing the input, doing some work in the freed-up memory, and uncompressing; but if the input memory is already used optimally, there should proveably be no way to store the input plus additional data in those bits.
(Obviously, you can e.g. store one bit of the input in the program counter by splitting the entire program on an initial "if (first_bit) ..."; but that's just moving information around without gaining additional storage.)
FWIW, mutating the input array is a neat trick, but I wouldn't be inclined to accept such a solution, either.
(Note: I'm going to use Python3-based pseudo code, except I'm going to assume 1-based array numbers, so the input is in a[1], a[2], a[3], ..., a[N].)
Suppose the input input list has N integers. Then the smallest positive integer not in the list must be one of 1, 2, 3, ..., N+1. (Prove by noting that all positive integers less than the smallest missing positive integer must be in the list, and then apply the pigeonhole principle).
In the classic problem, where you can use the input list as scratch memory and do not have to restore it, there are two approaches I've seen.
1. The sorting/permuting approach. With this approach you go through the list, and for a[k] you do
while 1 <= a[k] <= N and a[a[k]] != a[k]:
a[k], a[a[k]] = a[a[k]], a[k]
If one takes this approach, I don't see much hope in restoring the input back to its original state after identifying the missing integer.
2. The flagging approach. Conceptually you have an array, b, of N Boolean values, initialized to all False, and do this:
for k in range(1,N+1):
if 1 <= a[k] <= N:
b[k] = True
Note that if all of the input integers were known to be positive, we could use the sign bits of a[] as out b[].
for k in range(1,N+1):
if 1 <= abs(a[k]) <= N:
a[a[k]] = -abs(a[a[k]])
Then we can scan a[] looking for the first positive a[k], and k is the missing integer, or N+1 if all a[k] < 0.
In this special case, where we know all of the input is positive, we can restore the input back to its original value after finding the missing by simply setting a[k] = abs(a[k]) for each k.
The flagging using sign bit approach also works if not all the input is positive. Just add this at the start:
for k in range(1,N+1):
if a[k] <= 0:
a[k] = N+2
But now we cannot reverse this after we find the number. If we had a way to get rid of the non-positive entries that we could later reverse, we'd be good. One approach would be to find the most negative value, m, in the list, and then add abs(m) + 1 to everything. Then we could do the prior positive-only sign flagging approach, remembering that when we want the value at position k it is a[k] - m - 1, not a[k]. At the end, we then just subtract m + 1 from a[].
This works as long as M + m + 1, where M is the most positive value in the list, is not greater than the maximum positive integer.
Here's some working Python3 code for this (so arrays are back to 0-based, and so there are "- 1"s here and there):
def firstMissingPositive(a):
s = min(a)
if s > 1:
return 1
s = abs(s) + 1
for i in range(len(a)):
a[i] += s
for i in range(len(a)):
v = abs(a[i]) - s
if 1 <= v <= len(a):
a[v-1] = -abs(a[v-1])
missing = len(a) + 1
for i in range(len(a)):
if a[i] > 0:
missing = i+1
break
for i in range(len(a)):
a[i] = abs(a[i]) - s
return missing
For systems where that can overflow, we need another approach. I've had some ideas, but they all would also run into overflow problems, so I'm currently stumped.
I think this subproblem is interesting enough on its own to state as a separate problem:
Write a function that given a list S of integers, returns an invertible integer function f and its inverse f', such that for all k in S, f(k) exists, is > 0, and INT_MIN <= -f(k) <= f(k) <= INT_MAX where INT_MIN and INT_MAX are the smallest and largest integers, respectively, your language handles. This should run in O(N) or better time and O(1) space.
Then to solve the restoring variant of missing integer, find f for your input, apply f to the input, and then do the positive-only flagging version of missing integer (using f' to get to the original values of a[]). Use f' to restore the input at the end.
This can be further generalized, because flagging by sign is not the only way to flag. For instance, if we happened to know that all of the input was even, we could use a[k] |= 1 to flag it, and we could clear the flag at the end with a[k] &= ~1. If not all of the input is even, we could start with a pass of a[k] *= 2 and undo it at the end with a[k] //= 2.
That gives us this problem to contemplate. Write a function that given a list S of integers, returns using O(N) time and O(1) space an invertible integer function f and its inverse f', invertible integer function m and its inverse m', and integer function t, such that.
1. For all k in S, f(k) exists
2. For all f(k), m(f(k)) exists
3. t(f(k)) = 0, t(m(f(k)) = 1
f, f', m, m', and t should all be O(1) time and O(1) space.
It's like the difference between sorting an array in-place (mutates the array as a whole (by changing order of items), but would not be legal sorting if it deleted or added any items), versus sorting it into a different array, leaving the original array intact. E.g. the difference between Python's lis.sort() and sorted(lis) where lis is a Python list.
I was in exactly the same situation you describe about 4 months ago. 5+ year work experience, making 100k+ and joined my company after an internship. Additionally, as an electrical engineer by training, I had little formal training in algorithms and data structures.
Here are some things that worked for me:
1. Interviewcake.com - worth every cent I paid for the annual subscription. It is an excellent resource - even better than the book “cracking the coding interview” in my experience.
2. Donald Knuth’s Art of Computer Programming - as a person without a formal training in algorithms and data structures, the classic text by Cormen et al was pretty poor. Knuth’s AOCP had much better treatment for multiple topics and really helped me understand what’s going on. (See the treatment on hash tables in both works for an example on the difference in quality)
3. Whiteboarding tips - (here is where my recent interviewers might be able to identify me) - You have to remember how whiteboards are more versatile than text editors. Use the whiteboard to draw things, make notes for yourself, analyze the question. I followed a process of writing and underlining these headings:
i. Problem : Reverse alphabets in a word stored as a linked list ii. Test cases: h-e-l-l-o iii. Algorithm: <write down pseudo code> iv. Final code
This might seem like a lot more work at first, but an organized approach like this really helped me complete complex challenges within 45 mins. Give this a try. It really helps
4. Resume polishing - Some former colleagues were very helpful in reviewing my resume and providing feedback. I saw a dramatic increase in the number of calls I received after revamping my resume.
5. Practice white boarding - Book a conference room for a weekend and practice solving 10 to 15 hard problems with a timer in the conference room. It makes an incredibly huge difference.
I am happy to say that with these, I went from being completely unprepared for interviews to multiple fantastic job offers in the past 4 months.
Here's the thing. There aren't that many different kinds of problems that you'll be asked to solve. The recipe for 80%+ of the interview problems I ever see is this:
1. You have a data structure (tree/array/matrix/graph/string) that may have some special properties (sorted? directed? etc?)
2. You solve one of a few classes of problems: * Find an optimal <blah> (shortest path, highest value node, longest subsequence, etc) * Mutate the output in some interesting way based on the values
3. You do that using some other data structure (Queue, Stack, Hash, Heap) or technique (dynamic programming, recursion, etc) for efficiency.
There's probably also a brute force solution you should be able to implement and that shouldn't take too long to do.
My point is, these interviews should be easy for a good candidate because the fundamental problem space for a typical question isn't huge and there's tons of places to practice online. For most interview problems, you should be able to say "Oh! I recognize the general shape, I can apply a few primitive patterns together and get a solution that's basically correct, and maybe I'll have to tweak it a bit to optimize it later".
Instead, I tend to get candidates with 15 years of experience who think they're so hot but somehow can't implement a trivial depth-first search. I don't want to spend the whole interview on trivial coding problems. I want you to finish that part in 15 minutes so we can spend the rest of the time on interesting topics and technologies.
That said, a surprising number of problems in life tend to reduce or closely resemble a fundamental data structure or computer science problem. (A lot of problems tend to approximate to graphs.) Additionally, even though most languages have support for fundamental data structures or algorithms in their standard libraries, knowing the performance implication of a double-for loop or understanding when to use a binary search tree compared to a B-Tree or RB Tree can make huge performance differences that real users care about.
This is where the value of the coding trivia interview sort-of comes in. It is the clearest indicator of ones skills in CS primitives you can have, and it does a good job in setting a quality bar within an engineering organization (at least everyone knows how to do these).
I personally think that more comprehensive and system-level interview questions are more valuable in assessing the technical abilities of a candidate in toto. In asking something like "How would you design an app like Instagram," you get a clearer sense of how the candidate thinks, how they approach problems, how much of their CS fundamentals they've retained, and, to some degree, what they're like to work with. It also allows more flexibility than the trivia-style interview. If you want to assess coding ability, you can ask them to write their idea of a feed algorithm. Conversely, if you want to assess their abilities as a lead, you can ask them about maintaining the system and finding the right team to build an app like this.
- For that authentic whiteboard performance feeling ask a friend to play the role of an interviewer.
- Maybe set up a local meet up to help people practice this interview skill
Indeed. Many people (including myself) find it hard to reconcile our lived experiences with the hysterical claims in the press about a desperate skills shortage.
To the OP: if it helps, understand that these kinds of interviews and how you do on them are in no way reflective of your skills as an engineer or your worth as a human being. You’re just being hazed, by someone you probably wouldn’t want to work with anyway. Keep at it, and eventually you will get to speak to someone who is basically normal that you can have a real conversation with.
A good book is "Competitive programmer's handbook", available for free in https://cses.fi/book.html. This book is programmer to programmer advice that will take you very very far into these kinds of problems, and gets to the point really fast. The code examples are clean and well formatted. For interviews, it gives you about 70% of the competence you would get from reading much longer books like Skiena's or Sedgewick's.
My approach to these interviews is:
- Read the requirements very well. Try to read between the lines as much as you can.
- Ask if there are follow up questions or if the exercise has multiple parts. This helps you plan your time.
- If you do not have an ideal approach, try a bruteforce approach first.
- Try to narrow down candidate solutions: what happens if I use an array? a list? a tree (binary search, trie, heap, etc)? a stack? a queue? a graph? a combination of them?
You can practice on sites like Leetcode, Hackerearth and so on so forth. If you want to try something harder, you've got this (not for the faint of heart): https://techdevguide.withgoogle.com/
But first, try to implement common data structures from scratch and get a better intuition about them. Remember to try recursive and iterative versions of operations. You can output Graphviz data and use that to debug.
Finally, even if you fail an interview, many companies will let you reapply after some period of time. I failed an interview a few years ago and I still get contacted by that same company today. It's not a life sentence.
As everyone here says, you have to practice.
Then, when you're finally fairly good at coding challenge questions, you'll discover that you also have to be good at system design questions which is a different beast altogether. And then you'll learn that instead/addition to the above, company X actually wants you to complete a take-home exercise, and company Y won't consider you because they do Python while you have Java.
It becomes very hard to know what to focus on when you don't have your eyes set on a particular company.
The first suggested not to spend longer than two hours and had very precise requirements. I passed this.
Second had four questions - first two were clear and the last two were vague hinting that I should spend 5+ hours implementing a authorization system in rails. They got high level answers for those two. We’ll wait and see.
In the event that it works at all, it does so by accident, not by design. Which is often evident in how hit-or-miss hiring someone is in most companies even after they've managed to make it through all these silly contrived crucibles.
To a certain extent it's a cargo culting problem. Insofar as companies like Google do it, and Google appears successful, and so other companies (failing to do any meaningful analysis or meta-analysis of their own) decide to model Google on the basis that surely their company will be successful just like Google. The problem, taking Google as the example, is that Google has AdWords. Which is for all intents and purposes a money printing machine. Google can be basically terrible at almost everything they do and still appear wildly successful so long as they don't disturb their money printer. As a result it's very difficult to just pattern-match to what Google does and evaluate either its benefit or its appropriateness in any context.
The other part of it is inertial. Often the wheel of hiring in a company started this way for lack of any better ideas, and then as the company grew it became proportionally more biased toward people who made it through a process like that, and then it becomes generationally perpetuated. The unfortunate side-effect of this is that biasing the employee population this way makes the job, for a new executive or manager, of changing these ineffective (and sometimes toxic) strategies extra difficult while trying to maintain team cohesion. Because it has a lasting cultural fingerprint.
Honestly, it's really a shame. I'm sorry you're having to go through it. My capacity to try to interact and change this weird marketplace phenomenon extends only about as far as the company for which I'm the Engineering hiring manager. My hope for you, and for others, is that you either find a place to work which doesn't do things this way, and/or you otherwise advance far enough in your career that nobody bothers to foist these silly ceremonies on you. Because your involvement in their pursuits is seen as a priori beneficial or existential.
So, how did I get the last interview? Once I realized that I wasn't doing great, I started writing down all the interviews questions. The aim was to understand what was I doing wrong. But in doing so, I started to see a pattern, most interviews tend to follow a singular script. For example transverse a heat map, merge sorted array etc. And I trained on all those questions. Now this wasn't a perfect solution because I still failed 10+ interviews but over time I got better. And then around the 25th one I finally nailed one as all the questions were repeated.
Nowadays there might be a better options to do this like books/sites which throw tons of whiteboard interviews at you. So try those and best of luck.
Go to networking events and meet-ups. Offer to give mock interviews to people more junior than you. Have coffee with founders to give them feedback on their ideas. Anything that puts you in unstructured conversation with strangers will make you more comfortable and confident in an interview. You get better at reading people and start to see things from both sides.
Being a software engineer often mainly only requires communicating with a mostly unchanging group of people. Interviewing well requires being able to communicate efficiently with someone you just met. During an interview if you can direct less time and mental energy at just communicating you'll have more for demonstrating that you'll be able to do the job.
"It is irrelevant whether you can come up a solution all by yourself. Being able to understand and remember the optimal solutions for those questions is the key. All the interviewer is looking for is whether you can write those optimal solutions literally on the whiteboard."
We can debate (and people have here) about whether it makes sense and the like, but this is the reality. Make this process as mechanical as possible, everyone knows it's a stupid game and yet we all play along.
https://translate.google.com/translate?hl=en&sl=zh-CN&u=http...
The alternative is finding companies that do not ask these types of interview questions. The only big company I know that doesn't ask those types of questions is Stripe but I'm sure there are plenty of others though they may not be 100% what you are looking for.
If they don’t give you the business logic, then you’ll need to practice, practice, practice, but you honestly should be able of reasoning you through a piece of businesslogic and turning it into pseudo code.
Aside from that, it’s a terrible test for hiring people exactly because you, can, memorize it through practice. But American hiring processes are funny like that.
How long would it take you to merge two sorted arrays on a computer without internet access and no one looking?
- the interview questions are invariably things that have already been solved and abstracted away.
- as an experienced programmer it's not your job to solve problems like that. The work you do is more complex and requires sleeping on it, doing research, trying stuff out, talking to people. THAT'S the stuff you're good at, and what you are hired for.
- as a result of doing that increasingly complex work you get out of touch with the simple problems, even worse you develop an instinctive internal block against doing it, you develop a 'spider-sense' for what NOT to waste your time on.
- this gets into my way when doing coding interviews.
- it also makes it harder for me to spend time practicing. I have a family, other stuff to do outside of work, do I need to spend many evenings to practice on things I will only need during coding interviews and will never need afterwards?
The process for hiring experienced engineers is completely broken.
I think the general problem is that I don't deal with such low-level problems on a daily basis.
I can write multi-threaded Kafka consumer app that processes thousands events per second and applies some basic ETL on them, add end-to-end integration test for it in <8 hours.
But it may take me ~1/8th of that time to write a low-level (quick) sort algorithm.
For example, there is almost no engineering question on the planet that people straightforwardly solve from first principles in 30 minutes, unless it’s totally shallow based on memorization or childish rote practice — and has virtually zero relationship to how they would ever solve any problem at work.
But there are all kinds of insanely hard problems that people can give you beautiful solutions for in 10-20 hours, and involve an entirely different way of working than anything possibly representable in 30 minutes.
Engineering and math questions just require burn-in and rumination, tinkering, stop & get a cup of tea, take a walk, tinker more. They just do.
Seeing “how someone thinks” in an artificial 30-60 minute session only tests a completely separate and mostly unnecessary skill set for passing tests and memorizing things.
At one point I interviewed at a couple big ones and got into FB, where I also did a fair amount of interviewing. My tips:
1. Accept it's a numbers game; apply to N, and you'll get an offer from one. I got rejected by Google and Spotify, got an offer from FB. Some people do better and get more offers, but I know I'm a nervous type during interviews and under-perform. It's okay, it's a First World Problem, just apply to more companies. I think most people I know who work at G/FB/Spotify got rejected be a few others.
2. Practice a lot. There are 100s of questions available online. If you're smart, you will pick up the patterns / tricks you can use to solve the coding questions. Eg. when the obvious solution is O(n^2), usually there is a more efficient one involving using a hashmap to do a lookup.
If you think the problems you find online are too hard or stupid (eg. "who cares about implementing an LRU cache"), then read up on core CS topics to appreciate the subject matter.
If you think it's not worth to invest the time to beef up for it, then (i) it is, you can learn a lot at the big ones (ii) you can see how hiring candidates who think it's worth it is better for the company.
3. Think of it as a good thing. You brush up on your core skills (LRU cache), and it probably forces/incentivizes you to look at some recent developments in your sub-field so you feel prepared and can comment on it if it comes up. Although I don't enjoy the interview itself, I find the preparation to be a very fun time, reminds me of the good old days at University; a good break from the usual crunch of the job, which usually leads to rusting of core skills and specializes you in the tools the team/company happens to use.
4. At the big companies, on the initial loops where you solve the shortish interviewing questions, usually they just want you to solve the problem, not talk too much. I found some candidates think they have to talk a lot and relate the problem to their work, but that's not the case. Don't say "At work I'd just use a library for this." That's obvious, that's not the point of the interview. In the initial screens the interviewer just wants you to supply a solution, explain it, and move on. So just do that. Be efficient.
5. Getting rejected feels like shit but doesn't say much about you. It just means you had a bad day, or you were nervous. Or maybe the interviewer actually did a good job of assessing your skills, and you're not a good fit for the team/org that was hiring. I've seen lots of people get rejected from FB where I thought any smaller company would _kill_ to get them onboard, but FB didn't accept them for some weird reason, which at a high level is sth like "Would they be successful here at this role X, in team Y or Z, _given how this role works here_? Maybe, but the hiring manager isn't convinced enough". It's a bit frustrating, but it works for the company: the people who get through the filter are very smart&good, work together very well and efficiently, altogether create products Bs of people use (good for everybody), creates Bs of revenues and Bs of profits. So it works, it's not going to change. Play the game.
It would go a long way towards making the experience better if the interviewer/TSA guy stated right at the beginning said "I realize this experience is degrading and it sucks to be treated like a liar/terrorist but I'll try to make it as pleasant as possible. " ?
A part of the reason we have this current interview process is because there are people out there who can really "sell" themselves and have bogus resumes so they have to screen these guys out i.e. "this is why we can't have nice things".
That's why I volunteer to be massaged. Can't be forced into something you've already went along with.
If your previous work did not actually require you to know them, they probably where not building algorithms from scratch or optimizing parsing/processing of data very much. As without the essential basics of data structures and algorithms it is very hard to build scalable applications that rely on them.
As you grow in your career you will have to learn things outside of your base knowledge as you move up the ranks on the technical skills ladder. This will be standard requirements for senior level positions which you are probably seeing now. At the junior and mid level you are normally not responsible for building the core pieces of data processing software engines or massively scalable applications that run custom in house algorithms.
If you go through some of the below resources they should help fill that skills gap and make you an overall stronger engineer so you can feel confident applying for senior level positions.
I would recommend taking the following course: https://www.coursera.org/specializations/data-structures-alg... https://www.edx.org/course/algorithms-and-data-structures https://in.udacity.com/course/data-structures-and-algorithms...
and reading the following book: https://www.amazon.com/Introduction-Algorithms-Press-Thomas-...
While I don't agree with this type of interview, it is the reality we live in.
Disclaimer: The book was written by a professor of mine in college. [0] https://elementsofprogramminginterviews.com/
You're not. I do these type of interviews and there are plenty of times where a person doesn't pass but I can tell it's just because they need to prepare more. I think your strategy of applying and failing is good, but I would also supplement it with practicing these type of interviews (e.g. get a whiteboard, go to leetcode or wherever, pull up a random question and pretend like you're in the interview).
Have you considered a different option ? How about building your own start-up to serve real business needs? Or working on open source projects. There are a lot of opportunities to look forward into.
Why keep banging your head multiple times on something, when you can use that energy on other meaningful ways.
Email me at the link on my profile if you'd like a list of our open positions.
The Golden Rule: When in doubt, use a hashmap. Almost all code challenges are about finding an algorithm or datastructure to fit the problem/solution. Many of them are solvable efficiently via a hashmap.
Preparation
- Practice on a whiteboard
- Do mock interviews with the most skilled people you can find and get feedback! This is critical to glean any information about how you're actually doing! I could volunteer to do that for you remotely if you like. Send me your contact info. I'm a distributed systems guy but could walk you through some problems and tell you how you're doing with whatever you're using for tech very likely still. Drop a note on how to connect if you're comfortable.
- Take an algorithms course before you interview. (The princeton sedgewick one is great and easy to grokk. see coursera: https://www.coursera.org/learn/algorithms-part1)
During:
- Write tests for your code during the interview to demonstrate production quality code.
Especially if interviewing for eg Google. They don't give super tricky problems in every interviews (eg during phone screen) - focus on writing good code that is tested and will compile and run after the interview, not writing mediocre code fast.
- It's okay to incrementally improve your solution. Talk through your thinking. Start at the naive solution and then work toward optimal. Eg give two lists, find any number from list a sums to any number from list b. To start, you could write a couple quick tests on the board to make sure you understand the problem. Then you could reason about solutions - say you could use nested for loops. That's O(n squared) which isn't suitable as a solution. So you ask if the data is sorted. If they say no, you can sort lists, iterate through one and binary search on the larger list to get to an asymptotically linearithmic solution. That's suitable so you write that fairly swiftly. To improve you discover you only need to sort one list so you change the solution to only sort the larger one and iterate through the smaller. If there is extra time you might start to reason about how you can move toward a linear solution. Remember I said the golden rule is use a hashmap? Why don't you make a hashmap out of one of the lists and iterate through the other one to find values in the map? Don't just sit there and take it away to the corner and try to solve it.
God Mode: - WAYYYY before you take the interview: Stop using an IDE at work if you're working in a statically typed language. Use emacs, or vscode or whatever you fancy. Moving to emacs made my brain learn the qualities of the language at an intimate level faster than anything else. You check the docs if you forget the api until you stop forgetting the API. It slows you down a bit at first so it's an investment but whatever - tack 25% on your estimates for a few weeks. You can revert to the IDE for larger refactoring work.
Don’t waste time on leetcode / HackerRank / etc. It’s not useful. Practice programming by writing code you enjoy, solving problems you are interested in. You’ll be naturally productive at what you enjoy, and just build on that.
Anybody giving advice that comes from the point of view that these interview techniques have any legitimacy is probably just someone who happens to randomly be good at or enjoys interview trivia, and so their opinion is clouded by a selection bias effect. This is especially true on Hacker News.
They do well on interviews, not because their study methods work better and not because they are better at engineering or more effective in a job. They are not. They just benefit randomly from a system set up to reward traits they happen to have already and find easy. Their ideas worked for them but are very unlikely to work for you.
Seriously, just do a lot of interviews, fail a lot, and be fine with it. It’s easier said than done, but it’s necessary for you to weed out the places with foolish interview practices and find the ones which are more holistic, human productivity focused, flexible, etc.
I happen to be good at quickly working through algorithms, mostly in machine learning and search data structures, but in general software too.
If anyone tries to hire me because of that quick “see how you think” whiteboard nonsense, I just walk away. They are doing it wrong; life’s too short.