CompSci Exam

Order these complexities from fastest growth to slowest growth O(1) O(log n) O(n) O(n log n) O(n^2)

From fastest to slowest growth the order is O(1) then O(log n) then O(n) then O(n log n) then O(n^2)

What does it mean if an algorithm runs in O(1) time

The number of operations does not depend on n so the running time is constant even as n increases

What does it mean if an algorithm runs in O(n) time

The number of operations grows in direct proportion to n so doubling n roughly doubles running time

What does it mean if an algorithm runs in O(log n) time

Each step reduces the remaining search space by a constant factor so running time grows with the logarithm of n

Why do we ignore constant factors in Big O analysis

We focus on the growth rate for large n because constant factors and lower order terms have much less effect than the dominant term

How is a C style array like int arr[10] stored in memory

The elements are stored in one contiguous block so element i is at the base address plus i times the element size

What is one key advantage of arrays over linked lists

Arrays support O(1) random access by index using arr[i]

What is one key disadvantage of arrays compared to linked lists

Inserting or removing near the front or middle requires shifting many elements so it takes O(n) time

What is a C++ vector

A vector is a dynamic array class that tracks its own size and capacity and lets you grow or shrink the sequence while still using index access

What is a C style string

A C style string is an array of char that ends with a null terminator character backslash zero

Why might you still use a C style string

You may need a C style string when you call low level libraries that expect a raw char pointer

What is pointer arithmetic on an int pointer

Pointer arithmetic adds or subtracts an integer from the pointer to move by that many elements in memory not by single bytes

If int* p points to the first element of an array what does star open paren p plus three close paren access

It accesses the fourth element of the array which is index three

Why are the Big Three important for classes that allocate dynamic memory

They ensure deep copies and correct cleanup so each object manages its own memory without leaks or double deletion

What does the call stack represent during program execution

It represents the chain of active function calls each with its own parameters and local variables

When a function parameter is written as int arr[] what does the function actually receive

The function actually receives a pointer to the first element of the array

Why can a function change the contents of an array argument

Because the parameter points to the original elements so writing through the pointer changes the caller data

What fields does a typical singly linked list node struct contain

It contains a data field such as an int and a pointer to the next node

What does the head pointer of a linked list represent

Head points to the first node in the list or is nullptr when the list is empty

In a non empty singly linked list what does the next pointer of the last node store

The next pointer of the last node stores nullptr to mark the end of the list

Why does accessing the i th element of a linked list take O(n) time

You must start at head and follow next pointers through i nodes so the work grows linearly with i

What is the time complexity of traversing a linked list of size n once

Traversing the list once has time complexity O(n)

What is one advantage of a linked list over an array

Inserting or removing nodes at known positions can be done by changing a few pointers without shifting many elements

What is one disadvantage of a linked list compared to an array

Linked lists use extra memory for pointers and do not support O(1) random access by index

Describe the idea of selection sort

For each position choose the smallest remaining element in the unsorted part and swap it into that position

Describe the idea of insertion sort

Treat the left part as sorted and insert each new element into its correct place by moving larger elements one step to the right

Describe the idea of bubble sort

Repeat passes over the array swapping adjacent out of order elements so large values bubble toward the end

What is the worst case time complexity of selection sort insertion sort and bubble sort on n elements

All three algorithms have worst case time complexity O(n^2)

What is the main idea of merge sort

Recursively split the array into halves until subarrays have size one then merge the sorted halves back together

What is the time complexity of merge sort and why

Merge sort runs in O(n log n) time because the array is split in half for about log n levels and each level performs O(n) work while merging

What is the worst case time complexity of linear search in an array of size n

Linear search takes O(n) time in the worst case because you may need to check every element

What is the worst case time complexity of binary search in a sorted array of size n

Binary search takes O(log n) time in the worst case because each step discards half of the remaining elements

What is a base case in a recursive function and why is it needed

A base case is a simple situation that returns a result without any recursive call and it is needed to stop infinite recursion

What is the recursive case in a recursive function

The recursive case calls the same function on a smaller or simpler input and combines that result into the answer

In merge sort what happens in the recursive step

The algorithm calls itself to sort the left half and the right half of the array

In merge sort what happens in the merge step

The algorithm repeatedly chooses the smaller front element from the two sorted halves and copies it into the result until all elements are used

What is a stack data structure and what access order does it use

A stack stores items with last in first out order where the most recently pushed item is popped first

What are the two main stack operations

Push adds an item to the top of the stack and pop removes and returns the item from the top

What is a queue data structure and what access order does it use

A queue stores items with first in first out order where the earliest enqueued item is dequeued first

What are the two main queue operations

Enqueue adds an item at the back of the queue and dequeue removes and returns the item at the front

How does breadth first search use a queue

Breadth first search enqueues the start node then repeatedly dequeues a node visits it and enqueues its unvisited neighbors exploring level by level

How does depth first search typically use recursion

Depth first search calls itself on each neighbor in turn which uses the call stack to remember where to backtrack

How do you index into a two dimensional array declared as int grid[ROWS][COLS]

Use grid[row][col] where row chooses the row index and col chooses the column index

What is a function pointer in C++

A function pointer is a variable that stores the address of a function so code can call that function indirectly through the pointer

How can a comparison function pointer be used with a sorting algorithm

The sorting function can call the comparison pointer on two elements to decide their order without knowing the element type

What is a class in C++

A class is a user defined type that groups related data members and member functions into one abstraction

What is an object in C++

An object is a specific instance of a class with its own copy of the data members

What is inheritance in C++

Inheritance lets a derived class reuse and extend data and behavior from a base class forming an is a relationship

What is runtime polymorphism in C++

Runtime polymorphism means code uses a base class pointer or reference but virtual functions cause the correct derived class implementation to run at runtime

What is an abstract class in C++

An abstract class is a class that has at least one pure virtual function and cannot be instantiated directly

What is an interface in C++ style design

An interface is usually an abstract class that declares pure virtual functions and defines a contract that derived classes must implement

What is ad hoc polymorphism in C++

Ad hoc polymorphism happens when you overload functions or operators so the same name can work with different parameter types

What is subtype polymorphism

Subtype polymorphism is when objects of derived classes can be used through pointers or references to a base class

Why can subtype polymorphism be dangerous if misused

If derived classes do not honor the expectations of the base class or if virtual functions and destructors are incorrect calls through a base pointer can lead to subtle bugs

What does the Single Responsibility Principle say

Each class should have one main reason to change which means it should focus on one responsibility

What does the Open Closed Principle say

Software units should be open for extension but closed for modification so new behavior comes from adding new code not changing tested code

What does the Liskov Substitution Principle say

Objects of a derived class should be usable anywhere a base class object is expected without breaking correctness

What does the Interface Segregation Principle say

Clients should not be forced to depend on methods they do not use so it is better to have several small specific interfaces rather than one huge interface

What does the Dependency Inversion Principle say

High level modules should depend on abstractions not concrete details and low level details should depend on those abstractions

What does Program to an Interface mean

Code should use base classes or interfaces in its variables and function parameters so specific implementations can be swapped without changing the client code

What does Favor Composition Over Inheritance mean

It is often better to build behavior by combining objects as members instead of inheriting which keeps components more flexible and loosely coupled

What is the purpose of a try block in C++ exception handling

A try block surrounds code that might throw an exception so that the program can jump to a matching catch block when an error occurs

What is the purpose of a catch block in C++ exception handling

A catch block defines how to respond when a specific type of exception is thrown from the associated try block

Why can a catch all handler be risky

It hides the exact exception type and can swallow serious errors which makes debugging and recovery harder

Why are compiled code libraries often shipped as archives with headers

They allow reuse of compiled implementations without exposing all source code and they can speed up builds by linking against prebuilt objects

What is a virtual function in C++

A virtual function is a member function declared with the keyword virtual so that when it is called through a base class pointer or reference the version in the actual derived object is chosen at runtime

What is dynamic dispatch

Dynamic dispatch is the process where the program chooses which overridden function to call at runtime based on the actual object type rather than the static pointer or reference type

When do you need virtual functions

You need virtual functions when you plan to call methods through base class pointers or references and want derived classes to be able to customize that behavior

What happens if a function is not virtual but is redefined in a derived class

If it is not virtual and you call it through a base pointer the base version is used even if the object is actually of the derived type

What does the override keyword mean on a function

Override tells the compiler that this function is meant to override a virtual function from a base class and will cause a compile time error if it does not match any base signature

Why is using override helpful

Override catches bugs where the function signature is slightly wrong such as a const mismatch or parameter type change so the derived function would not really override

What does it mean if a function is declared virtual in the base class but not marked override in the derived class

It can still override correctly if the signature matches but the compiler cannot check it as strictly so it is easier to make mistakes

What is a virtual destructor

A virtual destructor is a destructor declared with virtual so that when deleting an object through a base class pointer the destructor of the most derived class is called

Why do polymorphic base classes need a virtual destructor

Without a virtual destructor deleting a derived object through a base pointer can skip the derived destructor and leak resources or leave the object partially destroyed

What is a pure virtual function

A pure virtual function is a virtual function with no implementation in the base class written with equals zero at the end of its declaration which forces derived classes to provide an implementation

How do you declare a pure virtual function in C++

Use syntax like virtual void draw() const = 0 semicolon inside the class definition

What is an abstract class in C++

An abstract class is a class with at least one pure virtual function so it cannot be instantiated directly and is meant to be a base class for other classes

Why cant you create objects of an abstract class

Because the class has at least one function with no implementation so the compiler prevents constructing incomplete types

How does a derived concrete class become instantiable when its base is abstract

The derived class must override and implement all inherited pure virtual functions so that the derived type has complete implementations

What is meant by an interface in C++ style design

An interface is usually represented by a class that only has pure virtual functions and a virtual destructor and no data members so it only specifies behavior

How is an interface different from a regular abstract class

A regular abstract class may include some data members and implemented functions while an interface contains only pure virtual behavior and no stored state

Why is programming to an interface useful for polymorphism

Client code depends only on the abstract operations not on specific implementations so different concrete classes can be swapped without changing the client code

What does the final keyword on a class mean

Marking a class as final means no other class can inherit from it which stops further subclassing

What does the final keyword on a virtual function mean

Marking a virtual function as final prevents derived classes from overriding that function further while still allowing other virtual functions to be overridden

When might you mark a class final in your design

When you want to prevent inheritance to keep the design simple or for safety reasons or when the class is not intended to be a base class

When might you mark a virtual function final

When a base or mid level class has established the correct override behavior for that function and any further overrides would be unsafe or confusing

What is subtype polymorphism

Subtype polymorphism is when code uses base class pointers or references to refer to objects of different derived classes and virtual functions make each object behave according to its own type

Give an example of runtime polymorphism with a duck and quack behavior

A pointer to a duck base class can point to a mallard duck or a decoy duck and calling quack on that base pointer will call the mallard or decoy implementation depending on the actual object

What is one danger of subtype polymorphism

If a derived class does not respect the behavior promised by the base class or if the base destructor is not virtual then code using base pointers may see inconsistent or unsafe behavior

Why can calling a pure virtual function from a base class constructor be a problem

During base construction the derived part of the object is not fully set up so calling a pure virtual function can lead to undefined or unexpected behavior

What is the typical pattern for setting up behavior that depends on derived classes instead of calling a pure virtual in the base constructor

Let each derived constructor initialize its own state then call a protected virtual setup function after the base construction is complete or use a separate factory to finish initialization

How does runtime polymorphism relate to arrays or lists of base pointers

You can store base class pointers in an array or list where each pointer refers to a different derived object and calling a virtual function on each element will automatically dispatch to the correct derived implementation

Explain how interfaces and abstract classes help follow the dependency inversion principle

High level code depends on interface or abstract base types instead of concrete implementations so low level derived classes can be swapped or extended without changing the high level code