Hard problem identification. You are applying for a job at a new software techno

Question

Hard problem identification. You are applying for a job at a new software technology company. Your interviewer asks you to identify the following tasks as easy (E) or impossible (I). _______ Build a balanced BST containing N keys using 8N compares (where the array of keys are given to you in ascending order). ________ Build a balanced BST containing N keys using 8N compares (where the array of keys are given to you in arbitrary order). _____ Build a binary heap containing N keys using 2N compares (where the array of keys are given to you in arbitrary order). ______ Build a BST containing N keys that has height at most 1/2 lgN. _______ Design a priority queue that does insert and delete-max in lg lgN compares per operation, where N is the number of items in the data structure.

Explanation / Answer

Easy(E) build a balanced BST, array of keys are ascending order.

Impossible(I) : build a balanced BST, array of keys are arbitrary order.

Easy (E): build binary heap ,array of keys are arbitrary order.

Impossible (I) :build a balanced BST N keys that has height at most 1/2

easy(E): priority queue

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.