CodeGround
DashboardProblemsInterviewsAssessmentsCourses
CodeGround
DashboardProblemsInterviewsAssessmentsCourses
The Technical Interview Course

0 of 170 lessons complete

  • Choose, explore, undo
  • What the start index controls
  • When order matters
  • Duplicates in the input
  • When the branching factor comes from the data
  • Pruning: never build what cannot work
  • Choosing where to cut
  • Backtracking on a grid
  • Several constraints at once
  • Retrieval: the four decisions

Backtracking

103 / 170

Backtracking/Lesson 10 of 10·About 50 min

Retrieval: the four decisions

Two problems rebuilt cold, plus the checklist that determines any backtracking solution.

Key idea

Answer these and the code writes itself

What is a choice at each level? An item, a direction, a cut point, a placement.

What does the next call receive? The same index for reuse, the next index for single use, zero or a used-set when order matters.

What state changes, and is every change undone? Count them. Most bugs in this unit are an uncounted change.

What makes a branch impossible, and can it be detected before descending? That is the pruning, and it is the difference between a search that finishes and one that does not.

Tip

And the one that is always the same

Store a copy of the result, never the working list. If every answer comes back identical or empty, that is why.

Quick check· 5 min

Which decision is wrong here?

A search for all distinct combinations from a list with repeated values returns duplicates. Sorting is present and the copy is correct. Which decision is most likely wrong?

Problem· 18 min

Subsets II, from scratch

You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.

Problem· 22 min

Find Median from Data Stream, from scratch

You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.

PreviousSeveral constraints at once
NextSharing the prefix

0 of 4 parts complete