coding interview concepts Flashcards
Describe the difference between singly and doubly linked lists.
- Singly linked list: Each node contains data and a reference to the next node. \n* Doubly linked list: Each node contains data, a reference to the next node, and a reference to the previous node.
Doubly linked lists allow for easier traversal in both directions compared to singly linked lists.
What is a stack and how does it differ from a queue?
Stacks operate on the LIFO principle, while queues operate on the FIFO principle.
LIFO: Last In, First Out; FIFO: First In, First Out. Stacks are used for backtracking, recursion, etc., while queues are used for scheduling, order processing, etc.
Explain what a binary search tree is.
A tree data structure where each node has at most two children, and every node to the left is less than the parent node, while every node to the right is greater.
Binary search trees are used for efficient searching and sorting.
Define hash tables and their primary use.
A data structure that maps keys to values for highly efficient lookup.
Hash tables use a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
What are tries and where are they typically used?
A tree-like data structure used to store a dynamic set or associative array where the keys are usually strings.
Tries are commonly used in searching applications, like autocomplete and spell checking.
Describe the two ways of representing graphs in data structures.
- Adjacency List: Represents a graph as an array of lists. \n* Adjacency Matrix: Represents a graph as a 2D array of vertices.
Adjacency lists are more space-efficient for sparse graphs, while adjacency matrices provide faster access for dense graphs.
What is the time complexity of Bubble Sort in the worst case?
O(n^2)
Bubble Sort is less efficient on large lists, as it compares all the elements one-by-one and swaps them if they are in the wrong order.
Define the concept of recursion in programming.
A method of solving a problem where the solution involves solving smaller instances of the same problem.
Recursion often simplifies a complex problem and can be used in sorting, searching algorithms, and more.
What does Big O notation generally describe?
The upper limit of the time or space complexity of an algorithm as the size of the input data increases.
Big O notation helps in understanding the efficiency and scalability of an algorithm.
What is a greedy algorithm and its typical use?
An algorithm that makes the locally optimal choice at each stage with the hope of finding a global optimum.
Greedy algorithms are used in optimization problems and often provide a good approximation for complex problems.
How does merge sort work?
An algorithm that divides the array into halves, sorts each half, and then merges them back together.
Merge sort has a time complexity of O(n log n) and is efficient for large datasets.
What is the primary application of the two pointers technique?
Used to scan an array or sequence from two ends to find a pair or calculate a sum.
This technique is efficient for problems involving sequences, such as finding a pair with a given sum.
Explain the principle of Divide and Conquer.
An algorithm design paradigm that works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
Commonly used in algorithms like quicksort, mergesort, and binary search.
What is a binary heap and its common use?
A complete binary tree that satisfies the heap property, used primarily in priority queues.
In a max heap, each parent node is greater than its child nodes, while in a min heap, each parent node is smaller.
Describe the function of Dijkstra’s Algorithm.
An algorithm for finding the shortest paths between nodes in a graph.
Dijkstra’s Algorithm is used for graph traversal and pathfinding in networks.
What does Big O notation express about an algorithm’s space complexity?
The total amount of memory space that an algorithm needs to run, in terms of the size of the input data.
Space complexity is crucial for evaluating the efficiency of an algorithm in terms of memory usage.
Define the concept of backtracking in algorithms.
A form of recursion where you try to build a solution incrementally and abandon a path as soon as it is determined that this path cannot possibly lead to a solution.
Backtracking is used in problems like puzzle solving, game theory, and more.
How do hash table lookups work?
By using a hash function to compute an index where a value is stored in a data structure.
Hash tables provide constant time complexity for search, insert, and delete operations in the average case.
What is the main idea behind the sliding window technique?
A method of tracking a subset of data within a larger set by maintaining a window that slides over the data to examine different sections of it.
Typically used in array or string problems to find or calculate something among all contiguous subarrays or substrings of a given size.
Explain the concept of linear search.
A method of finding a specific value in a list that checks each element in sequence until the desired element is found or the list ends.
Linear search is simple but inefficient compared to other searching algorithms for large lists.
What is the core principle of dynamic programming?
A method of solving complex problems by breaking them down into simpler subproblems, storing the results of these subproblems to avoid computing the same results again.
Used in a wide range of applications, from computer algorithms to mathematical problems.
Describe the binary search algorithm.
A method of finding an item in a sorted list by repeatedly dividing the search interval in half.
The key condition for binary search is that the array must be sorted beforehand.
What are the basic principles of object-oriented programming (OOP)?
Encapsulation, Abstraction, Inheritance, and Polymorphism.
OOP focuses on using objects that are instances of classes, which can contain data and methods.
How is a graph represented using an adjacency list?
Each node of the graph is represented as a list, with the list containing the adjacent nodes that are directly connected to it.
Adjacency lists are preferred for representing sparse graphs, as they are more space-efficient.
What is a stack data structure?
A linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Mainly used for backtracking, undo mechanisms in software, and for balancing of symbols.
Explain the Quick Sort algorithm.
An efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. It works on the divide and conquer principle.
Quick Sort is generally faster than other O(n log n) algorithms like Merge Sort and Heap Sort.
Define the concept of a queue data structure.
A linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
Commonly used in breadth-first search, caching, task scheduling.
What is Depth-First Search (DFS) in graph theory?
An algorithm for traversing or searching tree or graph data structures. It starts at the root and explores as far as possible along each branch before backtracking.
Used in puzzle solving, topological sorting, finding connected components.
How does Selection Sort work?
A simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the front (or end).
Selection Sort has a time complexity of O(n^2) making it inefficient on large lists.
Describe the Bubble Sort algorithm.
A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.
The pass through the list is repeated until the list is sorted.
What is a singly linked list?
A type of linked list in which each node contains data and a reference to the next node in the list.
Singly linked lists allow sequential traversal of data; however, reverse traversal is not possible.
Explain the Insertion Sort algorithm.
A simple sorting algorithm that builds the final sorted array (or list) one item at a time.
Useful for small data sets, but inefficient for larger lists.
Define the concept of a doubly linked list.
A type of linked list in which each node contains data and references to both the next and the previous node in the list.
Allows for a greater variety of O(1) operations, including insertions and deletions from both ends.
What is a binary heap?
A complete binary tree which is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap.
The same property must be recursively true for all nodes in Binary Tree.
Describe the Merge Sort algorithm.
A divide and conquer algorithm that divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
Merge Sort is useful for sorting linked lists in O(nLogn) time.
Explain the Heap Sort algorithm.
A comparison-based sorting technique based on the binary heap data structure. It’s similar to selection sort where we first find the maximum element and place the maximum element at the end.
Repeatedly adjusts the heap and finds the next largest element to move to the sorted array.
What is the Counting Sort algorithm?
An integer sorting algorithm that operates by counting the number of objects that have each distinct key value, and using arithmetic to determine the positions of each key value in the output sequence.
Effective when the range of input data is not significantly greater than the number of objects to be sorted.
Define the Radix Sort algorithm.
A non-comparative sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.
One of the most efficient ways to sort large lists of numbers.
What is Linear Search?
A method for finding a target value within a list that sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
Linear search is rarely practical because other search algorithms and schemes are more efficient for large lists.
Explain the Binary Search algorithm.
A search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array; if they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful.
Binary search is faster than linear search except for small arrays. It has a time complexity of O(log n).
