What is a binary search tree?
Answer: A binary tree where each node's left subtree holds smaller keys and right subtree holds larger keys.
Explanation
Search is O(log n) when balanced, O(n) when degenerate.
Explore · Flashcard deck
Intro to Programming and Data Structures (University)
Data structuresPracticesOOPAlgorithmsBasicsComplexity
Shared from Quizcard. Flip through the cards below, or copy the deck to edit and study it in your own account — free.
Space flips · arrows move · Esc exits
Data structures
What is a graph?
Answer: A set of vertices connected by edges, which may be directed or undirected, weighted or unweighted.
Explanation
Represented by an adjacency list or adjacency matrix.
What is a heap?
Answer: A complete binary tree where each parent is ≤ (min-heap) or ≥ (max-heap) its children.
Explanation
Used to implement priority queues; insert and remove-min are O(log n).
What is a hash table and what is its average lookup time?
Answer: A structure that maps keys to values using a hash function; average O(1) lookup, insert, and delete.
Explanation
Collisions are handled by chaining or open addressing.
Stack vs queue?
Answer: A stack is last-in, first-out (push/pop); a queue is first-in, first-out (enqueue/dequeue).
Explanation
Stacks: undo history, function calls. Queues: print jobs, BFS.
What is a linked list?
Answer: A sequence of nodes where each node holds a value and a pointer to the next node.
Explanation
O(1) insert/delete at a known node, but O(n) access by position.
What is an array and what is its key property?
Answer: A contiguous block of memory holding elements of the same type, with O(1) access by index.
Explanation
Inserting in the middle is O(n) because elements must shift.
Practices
What is version control and what does Git's commit do?
Answer: Version control tracks changes to code over time; a commit records a snapshot with a message.
Explanation
Branches let you work on features without affecting main.
What is a unit test?
Answer: A small automated test that checks one function or component in isolation.
Explanation
Fast feedback; catches regressions.
OOP
What is polymorphism?
Answer: The ability for different classes to respond to the same method call in their own way.
Explanation
Example: shape.area() works for Circle and Square.
What is encapsulation?
Answer: Bundling data with the methods that operate on it and restricting direct access to internal state.
Explanation
Achieved with private fields and public methods.
What is inheritance?
Answer: A mechanism where a class (subclass) acquires the attributes and methods of another class (superclass).
Explanation
Supports code reuse and 'is-a' relationships.
What is a class vs an object?
Answer: A class is a blueprint defining attributes and methods; an object is an instance of a class.
Explanation
Example: class Dog; object my_dog = Dog().
Algorithms
What is dynamic programming?
Answer: Solving a problem by breaking it into overlapping subproblems and storing their results to avoid recomputation.
Explanation
Example: Fibonacci with memoization, or the knapsack problem.
What is Dijkstra's algorithm used for?
Answer: Finding shortest paths from a source in a graph with non-negative edge weights.
Explanation
Uses a priority queue; does not work with negative weights.
How does quicksort work and what is its average complexity?
Answer: Pick a pivot, partition elements into smaller and larger, recurse; average O(n log n), worst O(n²).
Explanation
Worst case happens with bad pivots on sorted data; random pivots help.
How does merge sort work and what is its complexity?
Answer: Divide the array in half, sort each half recursively, then merge; O(n log n) in all cases.
Explanation
Stable, but needs O(n) extra space.
What is the time complexity of bubble sort, and why is it rarely used?
Answer: O(n²); it repeatedly swaps adjacent out-of-order elements, which is slow for large inputs.
Explanation
Fine for teaching, not for production.
Breadth-first search vs depth-first search?
Answer: BFS explores neighbors level by level using a queue; DFS goes as deep as possible first using a stack or recursion.
Explanation
BFS finds shortest paths in unweighted graphs.
Basics
What is a variable?
Answer: A named storage location that holds a value which can change during program execution.
Explanation
Types may be static (declared) or dynamic (inferred), depending on the language.
What is the scope of a variable?
Answer: The region of code where the variable can be accessed.
Explanation
Local variables exist inside a function; global variables are visible throughout.
What is recursion?
Answer: A function that calls itself on a smaller input until it reaches a base case.
Explanation
Every recursive function needs a base case to stop.
What is a function and why use one?
Answer: A reusable block of code that performs a task, optionally taking inputs (parameters) and returning a value.
Explanation
Reduces repetition and makes code easier to test.
What is the difference between a for loop and a while loop?
Answer: A for loop iterates a known number of times or over a collection; a while loop repeats as long as a condition holds.
Explanation
A while loop needs its condition to eventually become false, or it loops forever.
What does a conditional statement do?
Answer: It runs different code depending on whether a boolean condition is true or false.
Explanation
if / else if / else.
What is the difference between compiled and interpreted languages?
Answer: Compiled languages are translated to machine code before running (C, Rust); interpreted languages are executed by an interpreter at runtime (Python, JavaScript).
Explanation
Many modern languages use a mix, such as bytecode plus a JIT compiler.
Complexity
What is the time complexity of linear search?
Answer: O(n).
Explanation
Works on unsorted data.
What is the time complexity of binary search?
Answer: O(log n), on a sorted array.
Explanation
Each comparison halves the remaining search range.
Order these from fastest to slowest growth: O(n²), O(1), O(n log n), O(n), O(log n), O(2^n)
Answer: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n)
Explanation
Logarithmic algorithms halve the problem each step.
What does Big-O notation describe?
Answer: The upper bound on how an algorithm's running time or space grows with input size n.
Explanation
Constants and lower-order terms are dropped.
Make your own deck like this
Upload a PDF, Word doc, or slides and Quizcard writes the cards for you, or build them by hand. Free to start, no credit card required.