Homework $2$: First Unique

Number in Data Stream

Design and implement a data structure for

efficiently tracking the first unique number in a

data stream.

Submission Deadline: March $06,2024,$ at $11$:$59$ PM

Challenge Overview

In many real$-$world applications, such as network data monitoring or sales

tracking, identifying unique events or items dynamically as data continuously

arrives is crucial. This assignment focuses on designing and implementing a

data structure that efficiently tracks the first unique number in a stream of

non$-$negative integers. Your task is to implement a system capable of adding

numbers to the stream and identifying the first unique number at any moment.

Problem Statement

Your implementation should support two primary operations:

$-$ add$($number$)$: Adds a number to the data stream.

$-$ showFirstUnique$()$: Returns the first number that appears only once in the

data stream. If there is no such number, return $-1.$

Key Requirements

Utilize a Hashmap to track the counts and positions of each number within a

linked list, efficiently managing duplicates and their occurrences.

Implement a Doubly Linked List to maintain numbers that currently have a

unique occurrence, preserving the order they were added.

Aim for O$(1)$ average time complexity for both add and showFirstUnique

operations, ensuring optimal performance as the data stream grows.

Implement the add and showFirstUnique methods as specified.

Ensure your code is functional, as non$-$functional code will result in a zero

score.

Example Workflow

add$(3)//$ Stream: $[3]$

showFirstUnique$()//$ Returns $3$

add$(3)//$ Stream: $[3,3]$

showFirstUnique$()//$ Returns $-1$

add$(2)//$ Stream: $[3,3,2]$

showFirstUnique$()//$ Returns $2$

add$(2)//$ Stream: $[3,3,2,2]$

showFirstUnique$()//$ Returns $-1$

add$(4)//$ Stream: $[3,3,2,2,4]$

showFirstUnique$()//$ Returns $4$

Academic Integrity and Usage of Tools

This assignment is designed to assess your understanding and ability to apply

key concepts learned in this course. As such, it is crucial that the work you

submit is entirely your own. To uphold the standards of academic integrity:

$-**$No Cheating$**$: Collaboration on the design and implementation of your

solution is not allowed.

$-**$No Plagiarism$**$: You must not "copy" the code from any source.

$-**$Usage of AI Tools$**$: The use of AI programming assistants like ChatGPT for

converting your algorithm$/$idea into real code is $*$okay$*.$ However, if that's

the case, you must cite its usage. We encourage you to make use of external

resources as necessary to solve this problem, just do not completely rely on

it for everything. Come up with your own plan to solve this problem, since

this homework will likely help you prepare for the midterm exam.

$-**$Referencing Sources$**$: If you use any external resources like

StackOverflow for understanding the concepts, you must cite these sources.

Submission Instructions

Submissions are accepted in Python, Java, C$,$ C$++,$ and JavaScript. Python

submissions are preferred due to compatibility with the autograder software.

Submit your source code $($with the correct file extension such as $.$py$,.$c$,$

$.$java etc.$)$ as a single file through the designated submission platform.

Include comments in your code to explain your logic and data structure

choices. If you choose to attach a documentation file $($which is optional$)$ for

your code, please submit a zip file containing both the source code and the

documentation file. Remember, the documentation is for reference only and not

considered for grading.

Your implementation will be graded based on specific method signatures

provided in the template file. Do not modify the method names or parameters.

Ensure your add function accepts only one parameter $($the new integer to be

added$),$ and the showFirstUnique function returns only the result $($the first

unique number in the data stream or $-1$ if there are no matches$).$

Evaluation Criteria

Correctness: The implementation accurately identifies and returns the first

unique number in the stream.

Efficiency: The implementation maintains O$(1)$ average time complexity for

operations.

Code Quality: The code should be well$-$commented, easy to read, and logically

organized.

Autograder Script: autograder.py

import importlib.util

import sys

def load$\_$submission$($path$)$:

$"""$Dynamically loads the student's submission given the file path."""

spec $=$ importlib.util.spec$\_$from$\_$file$\_$location$("$submission$",$ path$)$

submission $=$ importlib.util.module$\_$from$\_$spec$($spec$)$

spec.loader.exec$\_$module$($submission$)$

return submission.FirstUnique

def run$\_$public$\_$tests$($FirstUniqueClass$)$:

print$("$Running Public Test Cases"$)$

tests $=[$

# Test Case $1$: Basic functionality

$([2,3,5],[("$add$",2),("$add$",3)],5),$

# Test Case $2$: Adding a unique number after non$-$uniques

$([2,2,3,3],[("$add$",4)],4),$

# Test Case $3$: Empty initialization

$([],[("$add$",1)],1),$

# Test Case $4$: Repeatedly adding the same number

$([1],[("$add$",1),("$add$",1),$