Algorithmic problem solving and interviews

Loading...

En provenance du cours de University of California San Diego

Mastering the Software Engineering Interview

451 notes

University of California San Diego

Mastering the Software Engineering Interview

451 notes

Cours 4 sur 5 dans Specialization Object Oriented Java Programming: Data Structures and Beyond

You’ve hit a major milestone as a computer scientist and are becoming a capable programmer. You now know how to solve problems, write algorithms, and analyze solutions; and you have a wealth of tools (like data structures) at your disposal. You may now be ready for an internship or (possibly) an entry-level software engineering job. But can you land the internship/job? It depends in part on how well you can solve new technical problems and communicate during interviews. How can you get better at this? Practice! With the support of Google’s recruiting and engineering teams we’ve provided tips, examples, and practice opportunities in this course that may help you with a number of tech companies. We’ll assist you to organize into teams to practice. Lastly, we’ll give you basic job search advice, and tips for succeeding once you’re on the job.

À partir de la leçon

Algorithmic thinking on the fly

As we saw in week 2, coding on the fly can be a difficult task! In this final week of the course we’ll revisit the skill of live problem solving by looking at how to solve more challenging algorithmic problems (and write the code associated with the solution) on the whiteboard. You’ll recognize these problems as “classic” interview problems you’ve probably heard a lot about, designed to test your problem solving skills as well as your analysis and coding abilities. Don’t worry, we’ll teach you how to approach them with confidence through a 6-step process to addressing technical questions (hint: you don’t have to produce the perfect solution on the first try!). We’ll show you how to use this process in a number of examples. But of course, there is no substitute for practice, so we’ll set you up with how to train and evaluate yourself.

Welcome to algorithmic problem solving0:39

Algorithmic problem solving and interviews4:44

Case study: introduction5:26

Case study: a first solution4:06

Case study: working at the whiteboard5:04

Case study: going deeper7:50

Case study: next steps6:14

When I struggled: dealing with nerves1:20

Rencontrer les enseignants

Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Leo Porter
Assistant Teaching Professor
Computer Science and Engineering
Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering

[MUSIC]

So this week we're talking about Algorithmic Problem Solving.

And this is the strategy that you want to have

when you're faced with a new problem that you've never solved before and

you're being asked to work through during the interview.

So what we'll be doing in this video is talking about a step by step approach

to starting to solve such a problem so that you feel empowered when you're

dealing with the question that you've never thought about before.

So the first thing that you want to do when you're asked a question

is to make sure that you really understand what's being asked.

What the parameters involved are and what the goal for the solution would be.

And so your first task is to ask lots more questions.

When faced with a hard question ask as many questions as you can think of to

tease out the relevant assumptions that the interviewer has in mind,

or that might be relevant for

your solution to tease out the scope of the problem that's being asked.

And to try to understand what it is that you're trying to analyze and to solve.

Now once you've asked a lot of questions to make sure that you clarify the problem

and know where to go, what you should do is confirm your understanding

by working through an example.

And working through an example is really useful because both it lets you

get those creative juices flowing and start thinking towards a solution.

But it also lets you take some time and think through the problem very concretely

about what difficulties might be involved, where are the sticking points of

any solution we'd have to solve and also if there are any hidden assumptions or

implicit questions that you might need to address again and go back to that

first step of asking more questions of the interview to really make sure that you've

mapped out the scope of the solution that you need to come up with.

Okay, so at this point we have a very good sense of the task at hand and

we're ready to solve it.

So in the next stage of the strategy we just try to come up with a first solution.

You want to make sure that at least you got some

approach to solving the problem that's being solved.

So, at least even if it's not a good approach you've been able to

do what's asked of you.

And so we call this the brute force approach.

You take a hammer and you hit the problem with it.

You make sure that you can nail that problem down.

You've got some way of tackling it.

And this approach does not need to be clever.

It doesn't need to be elegant, but

you want to make sure that you've got a correct solution.

And so as you're developing this brute force approach as first naive

solution to the problem, what you want to do is test it.

Now, that means testing it with normal input,

what you'd expect the problem to have to handle.

But also with edge cases.

Make sure that your brute-force approach can handle both.

And then think through a little bit if you were to implement this first solution,

how would you do it?

What data structures would be useful?

How would those data structures would interact with the problem that

you're working with?

In particular, what performance would you get out of this implementation?

And any trade-offs that you might be thinking about in terms of maybe

using more memory to speed up the performance, or vice verse.

So, we've got a solution.

But we didn't spend very much time trying to make it clever or elegant.

So our next step of the strategy is to iterate this whole process of coming

up with a candidate approach to solving the problem, evaluating it,

testing it, poking at it, making sure that it does what you want it to do,

or if it doesn't, thinking about ways to fix it and really try and

nail down as good a solution as we can.

And you'll notice when you're in the interview that often, the interviewer will

try to guide you towards iterating your solution, asking you if it could be

made better, asking you if there are any trade-offs that are in mind.

And you want to think through this checklist of how you evaluate your

strategy at each stage of the problem solving process.

Now we iterate, we iterate, we come up with a great solution,

that we think at the high level we'll do a pretty good job.

We've done an asymptotic analysis.

We have a sense of how long asymptotically, so

in the go notation each of the operations involved were take.

And finally in Step 6 of our strategy, we finally write some code.

And so only once we've done this very thorough analysis of the problem,

I have a very good sense of what we want to implement,

now you can start writing some code on the whiteboard.

Now in the rest of the week what we'll be doing is taking this strategy and

applying it two concrete examples of questions that you might be asked in

an interview and then we'll also be talking about, how to

do this programming on a white board in the interview situation which is really

quite different from typing it out in a computer and so that's coming up next.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play