CSE 212: Programming with Data Structures

W04: Interview Question

Overview

This assignment must be completed individually to ensure you are meeting all course outcomes. You should not complete this assignment with a group. If you obtain help from a tutor, the tutor should help you understand principles but should not help you answer these problems. It is an honor code violation to obtain answers for these problems from others including using the internet (i.e. sites that allow students to share their solutions).

Instructions

This assignment is meant to simulate the kind of question you might receive in a job interview. It is important for you to understand the problem, develop a quality solution, and communicate it in a clear and professional manner.

You will need to record and upload a short video with your response to the question below. When making your video, please remember the following:

Scenario: Using Linked Lists for Other Data Structures

Stacks and queues define a set of functionality that can be implemented using various internal storage techniques. In particular, they could both be implemented to use a linked list internally to store the data.

Questions

In your video, provide a response to each of the following questions:

  1. Explain how you would use a linked list internally to implement a Stack. Make sure to explain the way you would use the linked list AND the time complexity associated with each of the following operations:
    • Push
    • Pop
    • GetTop
    • IsEmpty
  2. Explain how you would use a linked list internally to implement a Queue. Make sure to explain the way you would use the linked list AND the time complexity associated with each of the following operations:
    • Enqueue
    • Dequeue
    • Size
    • IsEmpty

Submission

When you have finished the video:

  1. Upload the video as a public, unlisted video.
  2. Return to I-Learn to submit a link to your video.

Other Links: