DSA Final Exam

What is an Abstract Class?

A class that cannot be instantiated on its own and may contain abstract (unimplemented) methods. It serves as a blueprint for other classes, providing a common base. Subclasses must implement all abstract methods or be declared abstract themselves.

What is Inheritance in OOP?

A mechanism where one class (subclass/child) acquires the properties and behaviors (fields and methods) of another class (superclass/parent). It promotes code reusability and establishes an 'is-a' relationship.

What is an Interface?

A blueprint of a class that defines a set of abstract methods that must be implemented by any class that implements the interface. It supports multiple inheritance of type and specifies behavior that implementing classes must have.

What are Generics?

A feature that allows types (classes and interfaces) to be parameters when defining classes, interfaces, and methods. Generics enable clearer, reusable code by checking type safety at compile time and avoiding class cast exceptions at runtime.

What are Wrapper Classes?

Classes that encapsulate primitive data types (like int, char, double) into objects. They are used when primitive types need to be treated as objects, such as when working with collections or java.util packages. Examples include Integer, Character, Double.

What is the Comparable interface?

An interface (from java.lang) used by objects to define their 'natural ordering.' Classes implementing Comparable must provide an implementation for the compareTo(Object o) method, dictating how instances of that class are compared to each other.

What is the Comparator interface?

An interface (from java.util) used to define an 'external ordering' for objects. It provides a way to sort collections based on different criteria without modifying the class itself, requiring an implementation for the compare(Object o1, Object o2) method.

What is an Array?

A fixed-size, contiguous block of memory that stores a collection of elements of the same data type. Elements are accessed by an integer index, starting from 0.

What is an ArrayList?

A dynamic array implementation in Java that is part of the Collections Framework. It allows for resizable arrays and provides methods for adding, removing, and accessing elements. It stores elements in a contiguous block of memory but can grow or shrink as needed.

What is a LinkedList?

A linear data structure where elements are not stored in contiguous memory locations. Each element (node) stores the data and a reference (or pointer) to the next element in the sequence. It's efficient for insertions and deletions but slower for random access.

What is Algorithm Analysis (Big O Notation)?

A mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it's used to classify algorithms by how their running time or space requirements grow as the input size grows, often denoted as O(n), O(logn), O(n^2), etc.

What is a Stack?

A linear data structure that follows the LIFO (Last In, First Out) principle. Elements are added (pushed) and removed (popped) from the same end, called the 'top' of the stack.

What is a Queue?

A linear data structure that follows the FIFO (First In, First Out) principle. Elements are added (enqueued) at one end (rear) and removed (dequeued) from the other end (front).

What is a Sorting Algorithm?

An algorithm that arranges elements of a list in a specified order (e.g., numerical or lexicographical increasing or decreasing order). Common examples include Bubble Sort, Merge Sort, Quick Sort, and Selection Sort.

What is a Tree (Data Structure)?

A non-linear hierarchical data structure consisting of nodes connected by edges, where each node has at most one parent and zero or more children. It has a single root node and no cycles.

What is a Binary Search Tree (BST)?

A special type of binary tree where for each node, all nodes in its left subtree have values less than the node's value, and all nodes in its right subtree have values greater than the node's value. This property allows for efficient searching, insertion, and deletion.

What is a Heap (Data Structure)?

A specialized tree-based data structure that satisfies the heap property: either the value of a parent node is always greater than or equal to the values of its children (Max Heap) or less than or equal to (Min Heap). It is typically implemented as an array.

Node

A fundamental part of a tree data structure that contains a value or data, and may link to other nodes (children) through edges. Each node may also maintain a reference to its parent and has the potential to facilitate data organization.

Leaf

A node in a tree data structure that has no children, meaning it is the last node in that path of the tree.

Root

The topmost node of a tree data structure, which serves as the starting point from which all other nodes descend. It is the only node in the tree that has no parent.

peek()

A method used in data structures like stacks or queues to access the element at the top of the stack or the front of the queue without removing it.

pop()

Removes the top element from the stack and returns it.

push()

Adds an element to the top of the stack.

Element

An item stored in a data structure, such as a stack or queue, that can be added, removed, or accessed.

Implements keyword

when a class agrees to follow the rules of an interface.

Extends keyword

Used in class inheritance to signify that a class derives from a superclass, inheriting its properties and methods.

Super keyword

A keyword in Java that references the superclass of the current object, allowing access to superclass methods and constructors.

List

An ordered collection of elements, typically allowing duplicates and enabling indexed access.

Array

A collection of items stored at contiguous memory locations, allowing for efficient indexing and manipulation of data.

ArrayList

A resizable array implementation of the List interface in Java that allows for dynamic storage of elements and efficient access. It can grow and shrink in size as needed, providing flexibility over standard arrays.

LinkedList

A data structure that consists of a sequence of elements, each pointing to the next, allowing for efficient insertion and deletion of elements at any position.

Queue

A collection of elements that follows the First In First Out (FIFO) principle, where elements are added at the back and removed from the front, often used for managing tasks in a sequential order.

Priority Queue

A type of queue that orders elements based on their priority, allowing the highest (or lowest) priority element to be processed first, regardless of the order they were added.

Doubly LinkedList

A data structure similar to a linked list, where each element points to both the next and the previous elements, allowing traversal in both directions.

Abstract Class

A class in object-oriented programming that cannot be instantiated on its own and is meant to be subclassed. It can contain both fully implemented methods and abstract methods that must be implemented by derived classes.

Constructor

A special method in a class that is automatically called when an object of the class is created. It initializes the object's attributes and can set default values.

Inheritance 

A mechanism in object-oriented programming that allows a new class to inherit properties and behaviors (methods) from an existing class, promoting code reusability.

add()

A method used to perform addition operations, typically defined within classes to add values or elements.

poll()

Removes and returns the head (first element) of the queue.

If the queue is empty, it returns null instead of throwing an error.

offer()

A method used to insert an element into a queue without violating capacity restrictions, returning true on success or false if the queue is full.

peek()

A method used to access the head of a queue without removing it, allowing inspection of the first element.

remove()

Removes and returns the head of the queue.

If the queue is empty, it throws a NoSuchElementException.

Comparable

An interface that defines a method for comparing objects to determine their order, enabling sorting and comparison operations.

Extends

A keyword used in Java to indicate that a class is inheriting from a superclass, allowing code reusability and the addition of new functionalities.

super()

A special method in Java used to call the constructor of a superclass, allowing initialization of inherited properties.

Interface

A reference type in Java that defines a contract of methods which classes can implement, allowing for multiple inheritance of type.

Big O Notation

A mathematical notation used to describe the performance or complexity of an algorithm in terms of time or space as the input size grows.

O(n)

Represents linear time complexity, where the execution time of an algorithm increases linearly with the size of the input data.

O(1)

Describes constant time complexity, indicating that the algorithm's performance is unaffected by the size of the input.

O(n)²

Refers to an algorithm whose performance is directly proportional to the square of the input size, indicating that the time or space complexity grows quadratically.

size()

A method used to determine the number of elements in a collection, such as an array or list, often employed to assess the data structure's capacity.

isEmpty()

Checks whether a data structure is empty, returning a boolean value indicating if it contains no elements.

compareTo()

A method used for comparing two objects, typically in a sorting context, returning an integer value that indicates their relative order.

Array.sort

A method used to sort the elements of an array in a specified order, typically either ascending or descending.

array.length

A property that returns the number of elements in an array, providing information about its size.

polymorphism

The ability of different classes to be treated as instances of the same class through a common interface, allowing methods to use objects of different types interchangeably.

superclass

A class that is extended by one or more subclasses, allowing for shared attributes and behaviors among related classes.

toArray()

A method that converts a collection into an array, returning an array containing all elements of the collection.

Heap

Area of memory used to store objects, arrays, and data structures that need to persist beyond the life of a single function call

Stack

a special region used to store temporary data — mainly related to function calls and local variables.

Dynamic Binding

A programming concept where the method that gets executed is determined at runtime based on the object type, allowing for more flexible and dynamic code behavior.

Wrapper Class

A class that encapsulates a primitive data type and provides methods to manipulate it as an object.

Comparator 

Interface for defining an external, custom ordering.

Enqueue

add an element to the rear (back) of a queue.

Dequeue

remove an element from the front of a queue.

Kruskal

The algorithm for finding the minimum spanning tree of a graph by sorting the edges and adding them one by one while avoiding cycles.

Prim’s Algorithm

An algorithm that finds the minimum spanning tree for a weighted undirected graph by growing the tree one vertex at a time.

Spanning tree

A subgraph that includes all the vertices of the original graph and is a tree, meaning it has no cycles and is minimally connected.

Vertices

The points in a graph that represent the endpoints of edges. Each vertex can connect to others through edges to form various structures in the graph.

Edges

The lines connecting vertices in a graph, which represent relationships or paths between them.