fucking all the study questions

What is the difference between overloading and overriding a function?

Overloading: same name, different parameter list (compile-time). Overriding: same signature in derived class using virtual (run-time).

Can you override a function that is not a member function of a class?

No. Only virtual member functions can be overridden.

Write an example of a function with default arguments.

int f(int x, int y = 10) { return x + y; }

When might it be ok to use friend functions?

When a non-member must access private data (symmetry like operator<<, efficiency, tightly-coupled helper).

Write a new member function for the class Bag: intersection which returns a new Bag containing the elements found in both the Bag receiving the call to the method and the Bag that is the method’s single argument. Define this method independently of the implementation, by using only the Bag ADT operations.

Algorithm: result empty Bag. For each item x in *this: if other.contains(x) then result.add(x). Return result. (Use only ADT ops like contains/add; do not touch internal nodes/array.)

Write the interface of a simple class Polygon with two integer private members height_ and width_ a parameterized constructor that takes two parameters height and width, and three public members: int getHeight(); int getWidth; and double area();

class Polygon{private:int height;int width;public:Polygon(int height,int width);int getHeight();int getWidth();virtual double area();};

Write the interface and implementation of two classes Triangle and Rectangle that inherit from Polygon. Thus Polygon is the base class and Triangle and Rectangle are two derived classes. Write the implementation for both the derived classes. Remember, the constructor is not inherited. You must override area() which is computed differently in each class. What about getWidth()and getHeight()?

Triangle/Rectangle constructors call Polygon(h,w). Override area(): Triangle = 0.5hw, Rectangle = h*w. getWidth/getHeight usually inherited unchanged (no override needed).

When would you declare class members as protected?

When derived classes need direct access, but outside code should not.

What is the call order for Constructors with inheritance? For Destructors?

Constructors: base then derived. Destructors: derived then base.

When should a base class Constructor be called explicitly. Give a C++ example of how you would do that.

When base has no default constructor or you need specific base initialization. Example: Derived(int x): Base(x) {}

What is an abstract class?

A class with at least one pure virtual function, so it cannot be instantiated.

What does T mean in bool Bag::add(const T& new_entry);

T is a template type parameter (the element type stored in the Bag).

Using Big O notation, indicate the worst case time requirement of each of the following tasks.

Worst-case: choose the tightest common Big-O for each task below (answers follow on separate cards).

Computing the sum of the first n even integers by using a for loop

O(n)

Displaying all n integers in an array

O(n)

Displaying all n integers in a sorted linked chain

O(n)

Displaying all items in n linked chains of size n each

O(n^2)

Displaying one array element

O(1)

Displaying the last integer in a linked chain

O(n)

Searching an array for one particular value

O(n)

Searching a sorted array for one particular value

O(log n)

Adding an item to a stack of n items

O(1)

Adding an item to a bag of n items

O(1)

What is the Big O run time for the following algorithm? Justify your answer. Assume that the operations that are not shown are independent of n. for (int pass = 1; pass <= n; pass++) { for (int index = 0; index < n; index++) { for (int count = 1; count < 10; count++) { //operations here independent of n }//end for }//end for }//end for

O(n^2). Reason: outer pass loop n times, middle index loop n times, inner count loop is constant (9 times), so nnconstant = O(n^2).

Consider an array of length n containing positive and negative integers in random order. Write C++ code that rearranges the integers so that the negative integers appear before the positive integers. Your solution should be O(n).

Two-pointer swap: i=0, j=n-1. While i=0; if i<j swap(a[i],a[j]). O(n).

Prove that T(n) = 25n+14 is O(n) (i.e. find n0 and k such that, for all n >= n0 25n+14>= kn)

Choose k=26, n0=14. For n≥14: 25n+14 ≤ 26n because 14 ≤ n. Therefore T(n) ≤ k·n so T(n) is O(n).

Which of the following expressions correctly describe T (n) = n log 2(n)? Circle all that apply: a) O(n) b) Ω (n) c) Θ (n2) d) O(n2) e) Ω (n2)

Correct: b) Ω(n) and d) O(n^2). Not O(n), not Θ(n^2), not Ω(n^2).

What is an obvious advantage of using a Linked Chain to implement the Bag ADT?

Dynamic size (no resizing/shifting) and easy insert/remove without moving items.

Modify LinkedBag::remove() to preserve the order of items in the bag.

Find target node, relink prev->next to curr->next (no “swap with head”). Need prev pointer traversal; removal becomes O(n).

Which are the most efficient (requiring least work/time) operations in LinkedBag? The least efficient?

Most efficient: add at head, remove head, isEmpty, getCurrentSize (O(1)). Least efficient: contains / remove-by-value (needs search, O(n)).

In what situations is the copy constructor invoked?

When creating a new object from an existing one (initialization), passing/returning by value.

What does the following statement effectively do? somepointer = somepointer.getNext()

Moves the pointer/reference to the next node in the chain (advance one link).

When does a class need to provide a copy constructor? Why?

When it owns dynamic memory/resources (needs deep copy to avoid double-free/shallow copy bugs).

When does a class need to provide a destructor? Why?

When it allocates dynamic memory/resources (must free them to prevent leaks).

What would you need to change to Node or LinkedBag to add or remove from the middle (preserve bag order)

Need ability to track previous node (or use doubly-linked nodes) so you can relink around a middle node.

If a list has n elements, how many legal positions are there for inserting a new element? For removing an element?

Insert: n+1 positions. Remove: n positions.

Given the drawing of a list and a code snippet, what does the list look like after executing the code? (think different possibilities, come up with the details of the question yourself)

Exam method: trace pointers step-by-step, update next/prev links, then redraw nodes in order after each pointer change.

What are the advantages and disadvantages of lists over arrays?

Advantages: fast insert/remove (no shifting), dynamic size. Disadvantages: slow random access (O(n)), extra memory for pointers, worse cache locality.

Consider the efficiency of locating the k th element in a singly-linked list. How does that compare to locating the kth element in a doubly-linked list? You may assume both lists have first and last pointers.

Singly: O(k) from first. Doubly: still O(k) but can choose direction: O(min(k, n-1-k)) by starting from first or last_.

How could you modify an Array implementation of the List ADT to accommodate varying sizes?

Use dynamic array resizing: allocate bigger array (often double), copy elements, update capacity.

Modify the insert method to include fewer “special cases” for empty lists.

Use a dummy head (sentinel) node (and/or dummy tail) so insert logic is uniform.

Design an application that maintains dat for a simple social network. Each person in the network should have a profile that contains the person’s name, optional image, current status, and a list of friends. Your application should allow a user to join the network, leave the network, create a profile, modify the profile, search for other profiles and add friends.

Store users in map(name->Profile). Profile fields: name, image(optional), status, friends(list/set of names). Ops: join(add), leave(remove + remove from others’ friends), update fields, search by name, add friend (mutual add).

What is the benefit of having a tail pointer?

O(1) insert at end (enqueue-style), no traversal.

Trace the insertion sort algorithm as it sorts the following sequence into ascending order. Show all steps and clearly indicate the sorted and unsorted portions of the sequence 20 80 40 25 60 40

Final sorted order: 20 25 40 40 60 80. Memory rule: grow sorted prefix; take next key, shift bigger items right, insert key.

Trace the selection sort algorithm as it sorts the following sequence into ascending order. Show all steps and clearly indicate the sorted and unsorted portions of the sequence 7 12 24 4 19 32

Final sorted order: 4 7 12 19 24 32. Memory rule: each pass pick minimum from unsorted and swap into next sorted position.

Trace the bubble sort algorithm as it sorts the following sequence into descending order. Show all steps and clearly indicate the sorted and unsorted portions of the sequence 12 23 5 10 34

Final sorted order (descending): 34 23 12 10 5. Memory rule: swap adjacent if left < right (for descending), largest “bubbles” to front with repeated passes.

How many comparisons would be needed to sort an array containing 25 entries using the bubble sort algorithm in - The worst case?

Worst case comparisons: 25*24/2 = 300.

How many comparisons would be needed to sort an array containing 25 entries using the bubble sort algorithm in - The best case?

Best case (with early-exit optimized bubble): 24 comparisons (one pass, no swaps).

Write both an iterative and recursive version of the insertion sort algorithm.

Iterative idea: for i=1..n-1 insert a[i] into sorted left via shifting. Recursive idea: sort first n-1, then insert last into correct spot by shifting.

Trace the merge sort algorithm as it sorts the following sequence into ascending order. List all calls to mergeSort and merge in the order in which they occur. 20 80 40 25 60 30

Final sorted order: 20 25 30 40 60 80. Memory rule: mergeSort splits until size 1, then merges back: merge pairs, then merge the merged halves.

What does the keyword virtual do?

Makes calls through base pointers/references use the derived override (runtime dispatch).

What does the keyword override do?

Compiler-check that you are actually overriding a base virtual function (same signature).

What does =0 mean?

Pure virtual function (no base implementation required); makes class abstract.

What is an abstract class?

A class with at least one pure virtual function; cannot instantiate.

Why would you use an abstract class?

To enforce an interface/common behavior across derived classes.

In which situations would you use polymorphism?

When you want one interface (base pointer/reference) to handle many derived behaviors.

What is a virtual table or v-table?

Runtime table of function pointers used to dispatch virtual calls.

How is polymorphism different from basic inheritance?

Inheritance shares structure/code; polymorphism enables different behavior via virtual overrides at runtime.

What is late binding?

Choosing which function to call at runtime (virtual dispatch).

What does FIFO mean?

First In, First Out.

How is FIFO related to the ordering of the items in a stack? Think about what happens to the data if it is all pushed onto a stack and then popped.

It’s not FIFO. A stack is LIFO, so popping returns items in reverse order of pushing.

Describe two applications of a stack data structure.

Undo/redo; call stack/recursion; expression evaluation; backtracking.

Write pseudocode for an algorithm that uses a stack to check if parentheses are balanced given a string as input.

Push opening brackets. On closing bracket: if stack empty or top not matching opener return false; else pop. End: balanced if stack empty.

What is a prefix algebraic expression? What is a postfix algebraic expression?

Prefix: operator before operands (e.g., + A B). Postfix: operator after operands (e.g., A B +).

How can you use a stack to evaluate a postfix expression? Think about the relationship between stack and postfix.

Scan tokens: if operand push; if operator pop two operands b,a then push (a op b). Final stack top is result.

Why do we use a stack for backtracking?

Last choice is the first to undo; stack stores decision history.

What is the complexity of pop()? push()? top()? size()? isEmpty()?

All O(1).

Write a C++ implementation of push() in a linked-chain implementation of stack()

Create new node, set node->next = head, head = node, size++.

Write a C++ implementation of pop() in a linked-chain implementation of stack()

If empty error. temp=head; head=head->next; delete temp; size--.

What does LIFO mean?

Last In, First Out.

How is LIFO related to the ordering of the items in a queue? Think about what happens to the data if it is all enqueued and then dequeued.

It’s not LIFO. A queue is FIFO, so dequeue returns items in the same order as enqueue.

Describe two applications of the queue data structure.

BFS/level-order traversal; scheduling (printer/jobs); buffering.

Write pseudocode for an algorithm that takes a string s as input and uses a queue to generate all possible binary strings in Breadth First Search, until it produces the input string.

Queue starts with "0","1". While front != s: pop x; push x+"0"; push x+"1". Stop when x==s.

What is a deque?

Double-ended queue (push/pop at both front and back).

What is a priority queue?

A queue where removal returns the highest (or lowest) priority element.

What is the complexity of deque

O(1)