Software Engineer Intern Flashcards
Q: What is an array?
A: An array is a collection of elements stored at contiguous memory locations, identified by an index or key.
What is the time complexity for accessing an element in an array?
O(1) - constant time, because arrays provide direct access via index.
What is the time complexity for inserting/deleting an element at the end of an array?
O(1) - constant time, if there’s space available.
What is the time complexity for inserting/deleting an element at an arbitrary position in an array?
O(n) - linear time, because elements may need to be shifted.
Q: What is a dynamic array?
A dynamic array automatically resizes itself when it reaches capacity, allowing for flexible sizing.
What is the time complexity for resizing a dynamic array?
A: O(n) - linear time, because all elements need to be copied to the new array.
What is a multi-dimensional array?
An array where each element can be accessed using multiple indices (e.g., matrix with rows and columns).
What is a linked list?
A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence.
What are the main components of a linked list node?
A: A data element and a reference (pointer) to the next node.
Q: What is a doubly linked list?
A: A linked list where each node has pointers to both the next and previous nodes.
Q: What is a singly linked list?
A: A linked list where each node points only to the next node in the sequence.
Q: What is a circular linked list?
A: A linked list where the last node points back to the first node, forming a circle.
Q: What is the time complexity for accessing an element in a linked list?
A: O(n) - linear time, because you need to traverse from the head.
Q: What is the time complexity for insertion/deletion at the beginning of a linked list?
A: O(1) - constant time, if you have a reference to the head.
Q: What is the time complexity for insertion/deletion at the end of a linked list?
A: O(n) for singly linked list (need to traverse), O(1) for doubly linked list if you have a tail reference.
Q: What are the advantages of linked lists over arrays?
A: Dynamic size, efficient insertions/deletions, no need for contiguous memory.
Q: What are the disadvantages of linked lists compared to arrays?
A: Higher memory usage (due to pointers), sequential access only (no random access), poor cache locality.
Q: What is a stack data structure?
A: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements can only be inserted or removed from one end, called the “top” of the stack.
Q: What are the two primary operations of a stack?
A: The two primary operations are:
Push: adds an element to the top of the stack
Pop: removes the element from the top of the stack
Q: What is the time complexity of push and pop operations in a stack?
A: Both push and pop operations have O(1) time complexity (constant time).
Q: What happens when you try to pop from an empty stack?
A: This results in a stack underflow error/exception.
Q: What’s the difference between peek and pop in a stack?
A: Peek returns the top element without removing it, while pop returns AND removes the top element.
Q: Name real-world examples of a stack.
A: A stack of plates, browser history (back button), function call stack in programming, undo functionality in text editors.
Q: What is a queue data structure?
A: A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Elements are added at one end (rear) and removed from the other end (front).
Q: What are the two primary operations of a queue?
A: The two primary operations are:
Enqueue: adds an element to the rear of the queue
Dequeue: removes the element from the front of the queue
Q: What is the time complexity of enqueue and dequeue operations in a queue?
A: Both enqueue and dequeue operations have O(1) time complexity (constant time) when implemented optimally.
Q: What is a circular queue?
A: A circular queue is an improvement over the standard queue where the last position is connected to the first position to form a circle, preventing wasted space when elements are dequeued.
Q: What is a priority queue?
A: A priority queue is a special type of queue where elements have associated priorities, and elements with higher priority are served before elements with lower priority.
Q: What is a deque (double-ended queue)?
A: A deque is a queue that allows insertion and deletion at both ends (front and rear).
Q: What data structure is typically used to implement a priority queue efficiently?
: A heap data structure (typically a binary heap) is used for efficient priority queue implementation.
Q: What is a hash table?
A: A hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values using a hash function.
Q: What is a hash function?
A: A hash function is a function that converts input data of arbitrary size to a fixed-size value, used to compute an index into an array for storing the data
Q: What is a collision in hash tables?
A: A collision occurs when two different keys produce the same hash value (index).
Q: What are common collision resolution techniques?
A: Common techniques include:
Chaining (using linked lists at each index)
Open addressing (linear probing, quadratic probing, double hashing)
Robin Hood hashing
Cuckoo hashing
Q: What is a tree data structure?
A: A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges, with one node designated as the root.
Q: What is a binary tree?
A: A binary tree is a tree where each node has at most two children, referred to as the left child and the right child.
Q: What is tree traversal?
A: Tree traversal is the process of visiting each node in a tree data structure exactly once.
Q: What is a heap?
A heap is sort of a warehouse, where data is stored, and is not in any particular order.
Q: What is the heap property for a min-heap?
A: In a min-heap, for every node i, the value of i is less than or equal to the values of its children.
Q: What is the difference between time complexity and space complexity?
A: Time complexity measures the amount of time an algorithm takes to run as a function of input size, while space complexity measures the amount of memory it uses.
Q: What is Big O notation?
Big O notation is a way to describe time complexity (how fast an algorithm runs) and space complexity (how much memory it uses).
Q: What is Breadth-First Search (BFS)?
A: BFS is a graph traversal algorithm that explores all neighbors at the present depth before moving to nodes at the next depth level.
