Identify trees, lists, and array search costs

Q: Identify trees, lists, and array search costs

This question evaluates knowledge of fundamental data structures (tree hierarchies, linear lists, and arrays), algorithmic time and space complexity, and cycle-detection concepts.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Answer all parts concisely and justify time complexities.

a) A data model requires each node to have at most two children and a single parent. Name the data structure and describe the typical fields per node. If keys are stored to enable ordered searches, state the average and worst-case time to search by key and what property must hold to achieve the average case.

b) You need a structure where each element points to the next element and supports O(1) insertion at the head. Name the structure. Describe how to detect whether it contains a cycle and give the time and space complexity of your method.

c) For an unsorted array of n integers, what is the worst-case time complexity to determine whether a target value exists? If the array is sorted, what algorithm would you use and what is the new time complexity? Yes/No: Is binary search valid on an unsorted array? Explain in one sentence.

Identify trees, lists, and array search costs

Overview

Comments (0)