Case study: next steps

Loading...

Do curso por University of California San Diego

Mastering the Software Engineering Interview

424 classificações

University of California San Diego

Mastering the Software Engineering Interview

424 classificações

Curso 4 de 5 em Specialization Programação Java: Design Orientado a Objetos de Estruturas de Dados

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.

Na lição

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

Conheça os instrutores

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]

>> All right, so now for something completely different,

we're going to find yet a third algorithm, it's not going to be

the sort then probe algorithm we started with and coded on the white board.

It's not going to be the algorithm that relies on the max heap that we just

talked through.

But rather what we can think about is

Going through our arsenal of sorting algorithms, what else is useful?

We have a really interesting sorting algorithm from Quick sort where we use

a pivot behavior and we recursively sort different parts of the array based

on partitioning the array into the smaller than the pivot and larger than the pivot.

And so, what we can do now is recognize that sorting was useful for

solving our new problem.

And so maybe we can use a sorting algorithm and modify it in some way to

make a new algorithm that's useful for the current problem.

The problem of finding the k'ths smallest element.

So what if we picked a pivot in our elements, in our array of elements and

thought through what happens when we sort the, not sort,

partition the array into the elements that are smaller than the pivot and

those that are bigger than the pivot.

Now, we're not looking for fully sorted array at the end of this procedure,

what we want is the k'ths smallest element.

And what's really useful here is that if we partition the array into those

that are smaller than the pivot and those bigger than the pivot,

than if we only have say three elements that are smaller than the pivot.

Then the third smallest element over all is going to be the maximum of those three

elements because the pivot's going to be bigger and all of the other elements

in the array are going to be bigger than those bottom three elements.

And so they're not going to be the third smallest and so the beauty of this

approach is going to be that we only need to recursively look at only roughly half

of the elements each time if we're lucky with our choice of pivot.

And so what we can do is at each stage pick some random element of the array.

Partition the array into those elements that are smaller than the pivot,

those elements that are bigger than the pivot.

And then look at the size of the set of elements, is it smaller than the pivot and

compare that size to the ring.

Because that size of that set is going to tell us whether the k'th smallest element

belongs in that set of elements that are smaller than the pivot, or

maybe that k'th smallest element is the pivot.

Or maybe that case smallest element is bigger than the pivot and so

we need to look in the rest of the elements in the array.

And so we can code up this strategy and

notice that this is going to be a recursive method.

Which is great if we can come up with a recursive solution.

To our problem strategy, we're demonstrating yet

another skill in programming and algorithmic development in our interview,

we're demonstrating our breadth of knowledge, and

we want to still be careful about the code that we write.

We're doing the input validation.

We have a helper method, and so we're demonstrating that we know the difference

between the private helper methods And the public method call that we have.

And then as we go through this recursive function development,

it's going to be very important to test the code,

which is why we had that base example that we can keep tracing through.

Now as we develop this new strategy,

we still want to think about performance, and the performance is going to hinge on

the fact that when we compare to the pivot at each recursive function call.

We hope that we're going to divide our array of elements into

the smaller thans and the bigger thans and those are going to be hopefully,

roughly the same size to one another and so we get to reduce our

problem size exponentially by reducing the array size in half each time.

And so what we're hoping for, on average at least, is linear time.

And a careful analysis of the recursive performance

of that function would really get us at its expected on time.

Now in an interview situation this might seem a little daunting to

come up with such an elaborate algorithm and to do its performance analysis.

But here's the punchline.

What we want to make sure to do in the interview is always keep going.

We never want to be content with the solution that we have at hand.

And so when we do have a solution, it's really important that we think about,

does it match the assumptions that we made at the beginning?

How will we change it if we had different assumptions, if for example we allowed

repeated elements in the array, what would we have to do differently in our methods?

We want to consider performance every time we come up with a new problem

solving strategy.

Have we made progress or maybe have we gone backwards?

Are we coming up with better solutions or

are we coming up with just different solutions?

And then are there tradeoffs that we can consider there for time versus memory?

And keep going, keep going.

Think of ways that we can bring in our tools.

What we want to do is through our practice,

have a wide array of tools that we can apply to new problems.

It may well happen that you've done so much practice that

in the interview situation you're asked a question that you've already solved.

Now, it's really important in this situation to mention that you've actually

worked through that solution.

And then the interviewer might ask you to still write out the solution, but then

they might ask you to go further, like we did, with those different algorithms and

take different assumptions or take different paths so

you can demonstrate your novel problem solving skills.

And when we are approaching a problem that's very new

what's useful is when we've done all that practice that we can go

through a mental checklist of all the useful data structures that we have and

all of the known algorithms that we've worked through.

And really help solve the new problem using what we've done before.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play