Back to notes
What are the key differences between DFS and BFS?
Press to flip
DFS (Depth-First Search) uses a stack or recursion and explores as far as possible before backtracking. BFS (Breadth-First Search) uses a queue and explores neighbors level by level.
Explain the basic structure and traversal methods of a binary tree.
A binary tree's nodes have at most two children. Traversal methods include in-order (left, root, right), pre-order (root, left, right), and post-order (left, right, root).
What is a data structure and why is it important in programming?
A data structure is a named location that can store and organize data. It is important because it allows for efficient code and is commonly used in coding job interviews.
When would you choose an ArrayList over a LinkedList and vice versa?
Choose an ArrayList for better indexed access and lower memory overhead. Choose a LinkedList for better performance with frequent insertions or deletions.
Explain the LIFO and FIFO principles with examples.
LIFO (Last In, First Out) is used in stacks where the last element added is the first to be removed (e.g., browser history). FIFO (First In, First Out) is used in queues where the first element added is the first to be removed (e.g., printer queues).
Compare and contrast singly and doubly linked lists.
Singly linked lists have nodes containing data and a pointer to the next node. Doubly linked lists have nodes with data and pointers to both the next and previous nodes, allowing bi-directional traversal.
What are the key characteristics and methods of a queue?
Queues operate on a FIFO basis. Key methods include `enqueue` (add to end), `dequeue` (remove from front), `peek`, `isEmpty`, `size`, and `contains`.
How do priority queues differ from regular queues?
In priority queues, elements are served based on priority rather than order of arrival. This is often implemented using a heap structure where either the smallest (min-heap) or largest (max-heap) element is at the root.
What are the complexities of different searching algorithms?
Linear Search: O(n). Binary Search: O(log n). Interpolation Search: O(log log n) - best for uniformly distributed data.
Compare the efficiencies of common sorting algorithms.
Bubble Sort: O(n^2). Selection Sort: O(n^2). Insertion Sort: O(n^2). Merge Sort: O(n log n). Quick Sort: O(n log n) on average, O(n^2) worst case.
How are graphs represented and traversed efficiently?
Graphs are represented using an adjacency matrix or adjacency list. Efficient traversals include Depth-First Search (DFS) using a stack or recursion, and Breadth-First Search (BFS) using a queue.
Describe the main methods used in a stack.
The primary methods are `push` (add to top), `pop` (remove from top), `peek` (view top), `isEmpty` (check if empty), and `search` (find an element).
What does Big O notation describe and give examples of different complexities.
Big O notation describes the performance of algorithms as data size increases. Examples: O(1) - Constant time, O(n) - Linear time, O(log n) - Logarithmic time, O(n^2) - Quadratic time, O(n log n) - Quasi-linear time, O(n!) - Factorial time.
What sets dynamic arrays apart from regular arrays?
Dynamic arrays, such as `ArrayList`, have a resizable capacity. They allow random access and efficient memory usage but have slower middle insertions/deletions compared to linked lists.
List and explain the advantages and disadvantages of linked lists.
Advantages: Easy insertion and deletion. Disadvantages: Poor random access and higher memory overhead compared to arrays.
Previous
Next