Report the minimum of a min-heap array.
Acceptance criteria
- 1.#out should show root 1.
DSA Tutorial · Heaps and Priority Queues
These 10 tasks go with the Heaps and Priority Queues chapter. 5 of them ask you to build something small from scratch; 5 give you code that is already broken and ask you to work out why. Set aside about 90 minutes for the whole set, though you can do them in any order.
Nothing here is marked by a person. When you press Submit, the editor checks your code against the points listed under each task and tells you straight away what passed and what didn't (you need a free account to submit). If you get stuck, there are hints, and a worked solution once you've had a go. The first 2 tasks are free; the rest are part of the practice plan.
If it's been a while since you read the chapter, here is how it starts: “JavaScript has no heap. You will have to write one, and it is the single most useful structure you can carry into an interview — it turns every 'top k' question from a sort into a scan.” .
1.Root is the smallestexercise · easy · 10 min
Report the minimum of a min-heap array.
Passes when: #out should show root 1.
2.Parent indexexercise · easy · 10 min · practice plan
Show the parent index of position five.
Passes when: #out should show parent at 2.
3.Child indicesexercise · easy · 10 min · practice plan
Show the two child indices of position one, joined by a dash.
Passes when: #out should show 3-4.
4.Swim a value upexercise · easy · 10 min · practice plan
Insert a small value and let it rise, then show the new root.
Passes when: #out should show root 0.
5.Search costs a scanexercise · medium · 10 min · practice plan
Report the cost of finding an arbitrary value in a heap.
Passes when: #out should show linear.
6.Fix the parent index using divisionbug fix · easy · 8 min
Plain division gives a fraction, which is not a valid index.
Passes when: #out should show whole index.
7.Fix the child indices off by onebug fix · easy · 8 min · practice plan
Children sit at 2i+1 and 2i+2, not 2i and 2i+1.
Passes when: #out should show 3-4.
8.Fix the swim comparing the wrong waybug fix · medium · 8 min · practice plan
Stopping when the parent is larger leaves the value stranded.
Passes when: #out should show root 0.
9.Fix the heap assumed fully sortedbug fix · easy · 8 min · practice plan
Only the root is guaranteed; the rest is partially ordered.
Passes when: #out should show not sorted.
10.Fix the search assumed logarithmicbug fix · easy · 8 min · practice plan
A heap is not a lookup structure, so finding a value scans it.
Passes when: #out should show linear.
Between them these tasks cover Heap property, Swim and sink and Array indexing.
Looking for a different chapter? See every practice set, or switch to the interview theory questions.