Arrays Flashcards
(50 cards)
What is an array?
A linear data structure that stores elements in a contiguous block of memory.
How are elements accessed in an array?
By using an index, with indexing typically starting at 0.
What is the time complexity of accessing an element by index in an array?
O(1), because arrays support constant-time random access.
What is the time complexity of inserting an element at the end of an array?
O(1) for static arrays if space is available, O(n) for dynamic arrays when resizing is required.
What is the time complexity of inserting at the beginning of an array?
O(n), since all other elements must be shifted.
What is the time complexity of deleting the last element in an array?
O(1) for most implementations.
What is the time complexity of deleting the first element in an array?
O(n), due to the need to shift remaining elements left.
What does it mean that arrays have a fixed size?
In static arrays, the size is determined at creation and cannot be changed without reallocating memory.
What is a dynamic array?
An array that can resize itself automatically when more space is needed (e.g., Python lists, Java ArrayList).
How does a dynamic array resize?
By allocating a larger block of memory (usually double the size) and copying over elements.
What is the tradeoff in using dynamic arrays?
They offer flexibility in size but may have occasional O(n) operations during resizing.
What happens when you access an index outside the bounds of an array?
It results in an error or undefined behavior, depending on the language.
What is the difference between an array and a linked list?
Arrays offer fast random access; linked lists offer faster insertion and deletion at arbitrary positions.
What is array traversal?
Visiting each element in the array, typically using a loop.
What is the time complexity of traversing an array?
O(n), where n is the number of elements.
How can you reverse an array in place?
By swapping elements from the start and end moving toward the middle.
What does it mean to rotate an array?
Shifting all elements left or right by a certain number of positions.
What is the difference between shallow and deep copy in arrays?
Shallow copy copies references; deep copy duplicates the actual values.
What is a 2D array?
An array where each element is itself an array, forming rows and columns.
How is a 2D array stored in memory?
Typically in row-major order, where rows are stored one after another.
What is the time complexity of searching an unsorted array?
O(n), since each element may need to be checked.
What is the time complexity of searching a sorted array using binary search?
O(log n), since the array can be halved repeatedly.
What are common algorithms used with arrays?
Sorting (merge sort, quicksort), searching (linear, binary), sliding window, prefix sum.
What is the sliding window technique?
A method for maintaining a subset of elements while iterating, often used for subarrays.
