Algorithms and data structures
Detailed Specification As part of a summer internship, you are joining a growing start-up company. The startup is hoping to expand its technical team and are looking for junior developers. Your manager wants you to be involved in the interview process for the appointment. You are asked to design a coding interview question in Python that tests a candidate’s knowledge and skill in both basic data structures and algorithms. Along with the question, you also need to develop sample solutions with complexity analysis of the problem including Python codes and test cases. Since your manager will only allow a maximum of 1 hour for the interview, 45 minutes will be allocated for this technical element, so the proposed exercise should be concise, clear and cover at least 2 of the following topics: • Topic 1: Basic data types: array, list, stack, queue • Topic 2: Trees • Topic 3: Recursion[unique_solution] • Topic 4: Sorting • Topic 5: Maps, Hash tables You also need to provide your sample solutions with Python code which includes the following: 1. A short explanation of your algorithm and data structures for the problem. 2. What is the basic solution and what would be a more sophisticated solution? 3. Python code for both solutions. The programmes can use Python built-in libraries and should NOT be longer than 100 lines of code. 4. A diagram to compare the time complexity of the two solutions with different inputs. 5. At least 5 inputs (test cases) that you have chosen for testing the robustness (i.e. correctness) and the complexity of the solutions. Your problem, solutions and test cases need to be assessed by your peers. Deliverables Deliverable 1 – the report in PDF format Your report must contain: a. The desсrіption of the interview question including the problem name, desсrіption, constraints and requirements, some short examples of input and output of the problem. This should NOT be longer than 300 words. [15%] b. Your proposed solutions include a basic solution and a more optimised solution. You should explain how your solution covers different topics of algorithms and data structures (listed above), how the latter one is more optimised. You should cover at least two topics. This should NOT be longer than 300 words. [15%] c. Design at least 5 input test cases for verifying the correctness and the running complexity of the two solutions. Short explanation of the purpose of its test cases including outputs if possible. This should NOT be longer than 200 words. [10%] d. Measure the running time of the two solutions against the testing inputs and plot a comparison diagram (you might need more than 5 inputs to plot clearly). State the big-O performance of each solution. This should NOT be longer than 200 words. [10%] e. Peer assessment feedback from a classmate on your proposed problem, solutions and test cases design. This is done during a lab hour, and the template will be given by the tutor. [20%] Deliverable 2 – Source code & test case input files. The Python source code (one for each solution), test cases (one file for each test input). They should be placed in a zip file which must be uploaded separately from the report. [30%] You must implement your solution using the Python programming language. You may use any sample code provided in the course lectures and laboratories/tutorials as an aid, but make sure you reference any source code. Unreferenced codes may involve an investigation into an academic misconduct offence.