coding interview concepts Flashcards

Question

What is a stack data structure?

Answer 1

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). ## Footnote Mainly used for backtracking, undo mechanisms in software, and for balancing of symbols.

Answer 2

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. ## Footnote Quick Sort is generally faster than other O(n log n) algorithms like Merge Sort and Heap Sort.

Answer 3

A linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). ## Footnote Commonly used in breadth-first search, caching, task scheduling.

Answer 4

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. ## Footnote Used in puzzle solving, topological sorting, finding connected components.

Answer 5

A simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the front (or end). ## Footnote Selection Sort has a time complexity of O(n^2) making it inefficient on large lists.

Answer 6

A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. ## Footnote The pass through the list is repeated until the list is sorted.

Answer 7

A type of linked list in which each node contains data and a reference to the next node in the list. ## Footnote Singly linked lists allow sequential traversal of data; however, reverse traversal is not possible.

Answer 8

A simple sorting algorithm that builds the final sorted array (or list) one item at a time. ## Footnote Useful for small data sets, but inefficient for larger lists.

Answer 9

A type of linked list in which each node contains data and references to both the next and the previous node in the list. ## Footnote Allows for a greater variety of O(1) operations, including insertions and deletions from both ends.

Answer 10

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. ## Footnote The same property must be recursively true for all nodes in Binary Tree.

Answer 11

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. ## Footnote Merge Sort is useful for sorting linked lists in O(nLogn) time.

Answer 12

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. ## Footnote Repeatedly adjusts the heap and finds the next largest element to move to the sorted array.

Answer 13

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. ## Footnote Effective when the range of input data is not significantly greater than the number of objects to be sorted.

Answer 14

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. ## Footnote One of the most efficient ways to sort large lists of numbers.

Answer 15

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. ## Footnote Linear search is rarely practical because other search algorithms and schemes are more efficient for large lists.

Answer 16

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. ## Footnote Binary search is faster than linear search except for small arrays. It has a time complexity of O(log n).

Answer 17

A searching algorithm for ordered lists. It works by jumping ahead a fixed number of elements and then performing a linear search backward. ## Footnote The optimal block size to be skipped is the square root of the list length. Its time complexity is between linear search and binary search.

Answer 18

An improvement over binary search for instances, where the values in a sorted array are uniformly distributed. It positions the probe based on the value of the key being searched and the distribution of the keys. ## Footnote Its average case time complexity is O(log log n), but it can be as bad as O(n) in the worst case.

Answer 19

By computing an index using a hash function and using this index to find the desired value in the hash table quickly. ## Footnote Hash table lookups generally require a very small, constant amount of time on average.

Answer 20

An algorithm for traversing or searching tree or graph data structures. It starts at a selected node and explores all of the neighbor nodes at the present depth before moving on to the nodes at the next depth level. ## Footnote BFS is particularly useful for finding the shortest path on unweighted graphs.

Answer 21

An algorithm used on a directed graph to produce a linear ordering of its vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. ## Footnote Topological Sorting is mainly used to schedule jobs from the given dependencies among jobs.

Answer 22

An algorithm that finds the shortest path from a node to every other node in a graph. It works for both directed and undirected graphs with non-negative weights. ## Footnote Widely used in network routing protocols, for it can handle graphs with cycles.

Answer 23

An algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. ## Footnote Unlike Dijkstra's, it is capable of handling graphs in which some of the edge weights are negative.

Answer 24

An algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (without any negative cycles). ## Footnote A key characteristic is its ability to calculate the transitive closure of a graph.

Answer 25

A method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure. ## Footnote Used in a variety of contexts from algorithmic to economic and biological.

Answer 26

A method for solving problems by making a sequence of choices, each of which seems best at the moment. The goal is to find a local optimum solution, which may or may not be the global optimum. ## Footnote Greedy algorithms are used in optimization problems and are often easier to conceptualize and faster to implement.

Answer 27

A paradigm based on multi-branched recursion. It involves breaking a problem into two or more sub-problems of the same or related type, solving them and combining their solutions. ## Footnote Divide and Conquer is used in many powerful algorithms including Merge Sort, Quick Sort, and Binary Search.

Answer 28

An algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time. ## Footnote Often used for solving constraint satisfaction problems such as puzzles, crosswords, and Sudoku.

Answer 29

A problem where you are given an array of numbers and a target sum, and you need to find two numbers in the array that add up to the target sum. ## Footnote Can be solved using various methods, including hashing and two-pointer techniques.

Answer 30

A problem where you need to find the length of the longest substring without repeating characters in a given string. ## Footnote Can be solved using techniques like the sliding window method.

Answer 31

A problem where the task is to reverse the digits of an integer, considering the overflow of values and maintaining the sign of the original number. ## Footnote Care must be taken to handle overflow/underflow conditions and negative numbers.

Answer 32

A problem that involves determining whether an integer is a palindrome, meaning it reads the same backward as forward. ## Footnote This can be solved by reversing the integer or by comparing the integer's digits from the beginning and end.

Answer 33

A problem where the task is to convert Roman numerals to integers and vice versa, understanding the value of each Roman symbol and their rules for combination. ## Footnote It requires an understanding of the Roman numeral system, where letters represent values and are combined to form numbers.

Answer 34

For a stack, one can use an array or a linked list to add (push) or remove (pop) items from the end. For a queue, items are added (enqueue) at the end and removed (dequeue) from the front. ## Footnote The key difference is that stacks are LIFO (Last In First Out), while queues are FIFO (First In First Out).

Answer 35

Operations include insertion, deletion, search, and traversal (in-order, pre-order, post-order). ## Footnote BSTs allow for efficient searching, insertion, and deletion operations.

Answer 36

Collision resolution can be implemented using techniques like chaining, where each bucket of the hash table contains a linked list of entries, or linear probing, where the next empty slot in the hash table is used. ## Footnote Chaining allows for unlimited entries but can potentially degrade to a linked list, while linear probing maintains a fixed size but requires rehashing when full.

Answer 37

BFS explores the nearest nodes first and gradually moves outwards, while DFS explores as far as possible along a branch before backtracking. ## Footnote BFS uses a queue, while DFS uses a stack or recursion.

Answer 38

It's used to find the shortest path from a single source node to all other nodes in a weighted graph, where weights represent the cost or distance between nodes. ## Footnote Dijkstra's Algorithm cannot handle negative edge weights.

Answer 39

It calculates shortest paths in a weighted graph with positive or negative edge weights and can detect negative weight cycles. ## Footnote It is slower than Dijkstra's but more versatile, as it is capable of handling graphs with negative weight edges.

Answer 40

An algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights. It computes the shortest paths between all pairs of vertices. ## Footnote Unlike Dijkstra's, it works on all pairs of nodes, making it suitable for dense graphs.

Answer 41

Dynamic Programming is used for solving complex problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant work. ## Footnote It is particularly powerful for problems that involve recursive calculations with overlapping subproblems, like the Fibonacci sequence or shortest path problems.

Answer 42

A Greedy Algorithm makes the locally optimal choice at each stage with the intent of finding a global optimum. ## Footnote Greedy algorithms are used in optimization problems but may not always provide the best solution.

Answer 43

A strategy that involves dividing a problem into smaller subproblems, solving each subproblem independently, and then combining their solutions to solve the original problem. ## Footnote It is used in algorithms like quicksort, mergesort, and binary search.

Answer 44

Backtracking is an algorithmic technique for solving problems recursively by trying different solutions and abandoning a path as soon as it is determined that the path does not lead to a viable solution. ## Footnote Typically used in problems with many possible configurations, like puzzles and games.

Answer 45

The 'Two Sum' problem involves finding two numbers in an array that add up to a specific target. Solutions include using a hash table for faster lookups or a two-pointer approach for a sorted array. ## Footnote The hash table approach provides a more efficient solution with a time complexity of O(n).

Answer 46

The problem involves finding the length of the longest substring in a given string without repeating characters. A common approach is using the sliding window technique. ## Footnote This technique involves maintaining a dynamic window that adjusts as the algorithm iterates through the string.

Answer 47

The problem involves reversing the digits of an integer. This can be done by repeatedly extracting the last digit of the number and adding it to a new reversed number. ## Footnote Care must be taken to handle potential integer overflow and negative numbers.

Answer 48

The problem involves determining whether an integer is a palindrome. A common method is to reverse half of the number and compare it with the other half. ## Footnote This avoids the need to handle integer overflow that might occur if the entire number is reversed.

Answer 49

The problem involves converting Roman numerals to integers and vice versa, using the values of Roman numerals and their rules of combination. ## Footnote Special attention is needed for cases where smaller numerals precede larger ones, indicating subtraction.

Answer 50

A stack can be implemented using an array or linked list, where elements are added or removed from the top of the stack (LIFO - Last In First Out). ## Footnote Using an array is generally simpler, but a linked list allows for a dynamic size stack.

Answer 51

A queue can be implemented using an array or linked list, where elements are added at the rear and removed from the front (FIFO - First In First Out). ## Footnote Linked lists are more efficient for queues, as they allow for constant time insertions and deletions.

Answer 52

Operations include insertion (adding a new node), deletion (removing a node), searching (finding a node), and various types of traversal such as in-order, pre-order, and post-order. ## Footnote Traversal operations are important for printing, converting the tree to an array, or analyzing its structure.

Answer 53

Key aspects include designing a good hash function, handling collisions through methods like chaining or open addressing, and resizing the table for efficiency. ## Footnote The efficiency of a hash table is significantly affected by how well the hash function distributes values and the method used for collision resolution.

Answer 54

BFS is used for finding the shortest path in unweighted graphs. DFS is used in scenarios like cycle detection, path finding, and topological sorting. ## Footnote While BFS provides the shortest path in terms of the number of edges, DFS is useful for exploring as much as possible along each branch.

Answer 55

Dijkstra's algorithm is used for shortest paths in graphs without negative weights, whereas Bellman-Ford can handle negative weights and detect negative cycles. ## Footnote Dijkstra's algorithm is usually faster but less versatile compared to Bellman-Ford.

Answer 56

A mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity, commonly used in computer science to describe the performance or complexity of an algorithm. ## Footnote Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used by an algorithm.

Answer 57

A process in which a function calls itself as a subroutine. This enables the function to repeat itself several times, outputting the result and the end of each iteration. ## Footnote Recursion is often used in solving problems involving iterative data structures like trees and graphs.

Answer 58

A technique in programming to perform operations at the bit level or work with bits. It's used for low-level programming, encryption, compression, and optimization. ## Footnote Common bit manipulation operations include AND, OR, XOR, NOT, shifting, and masking.

Answer 59

A technique where two pointers are used, which could move towards each other, away from each other, or can be used in a nested manner, to solve array/string problems efficiently. ## Footnote This technique is useful in problems like finding a pair with a given sum, reversing an array, or finding a palindrome.

Answer 60

A method for performing required operation on a subset of array/string data, which can be considered as a window, and then sliding that window within the data structure in a constant direction. ## Footnote This technique is useful in problems related to contiguous subarrays or substrings, like finding maximum sum subarray of a given size.

Answer 61

Common patterns include memoization, tabulation, and solving problems with overlapping subproblems and optimal substructure. ## Footnote These patterns help in reducing the time complexity by storing results of subproblems and reusing them.

Answer 62

System Design involves designing the architecture of a system, which includes understanding the system requirements, breaking down the system into components, and then designing the interactions between these components. ## Footnote Key considerations include scalability, reliability, and efficiency.

Answer 63

Key concepts include encapsulation (binding data and methods), inheritance (deriving new classes from existing ones), polymorphism (using methods in different ways), and abstraction (hiding complex reality while exposing only necessary parts). ## Footnote OOP allows for more modular, reusable, and organized code.

Answer 64

By using a hash table to store the difference between the target sum and each element in the array, checking if this difference exists in the array as we iterate through it. ## Footnote This approach allows for a time complexity of O(n), which is more efficient than the brute-force method.

Answer 65

Using a hash set or map to keep track of the characters in the current substring and updating the maximum length accordingly while iterating through the string. ## Footnote The sliding window technique is often applied here, adjusting the window's start and end to skip repeated characters.

Answer 66

By repeatedly popping the last digit off the original number and pushing it onto the reversed number, taking care of overflow situations. ## Footnote Special attention is needed to handle the case where the reversed integer overflows.

Answer 67

By comparing the first half of the digits of the number with the reversed second half, ensuring they are the same. ## Footnote Alternatively, the entire number can be reversed and compared with the original, but this might lead to overflow issues.

Answer 68

For conversion to integers, each Roman numeral is replaced with its value and summed up, considering subtraction rules. For conversion from integers, the process is reversed using the highest values first. ## Footnote Attention is needed for the subtraction rule, where a smaller numeral before a larger numeral means subtraction.

Answer 69

A stack can be implemented using an array or a linked list, where elements are added and removed from the top in a LIFO (Last In, First Out) manner. ## Footnote Stacks are used in scenarios like undo mechanisms, parsing, and tree traversals.

Answer 70

A queue can be implemented using an array or a linked list, where elements are added at the rear and removed from the front, following a FIFO (First In, First Out) principle. ## Footnote Queues are used in breadth-first search, caching mechanisms, and scheduling algorithms.

Answer 71

Essential operations include insert, search, delete, and traversals (in-order, pre-order, post-order). ## Footnote Each operation has its significance, like in-order traversal for sorted order of elements and search for finding elements.

Answer 72

Implementation involves creating a hash function for mapping keys to array indices, resolving collisions using techniques like chaining or open addressing, and possibly resizing the table for efficiency. ## Footnote The efficiency of a hash table is heavily dependent on the hash function and collision resolution strategy.

Answer 73

BFS is used to traverse graphs level by level, starting from a selected node and exploring all neighboring nodes before moving to the next level. ## Footnote It's particularly effective for finding the shortest path in unweighted graphs.

Answer 74

Dijkstra's algorithm is used for shortest paths in graphs without negative weights. Bellman-Ford can handle graphs with negative weights and can detect negative weight cycles. ## Footnote Dijkstra's is typically faster but cannot handle negative weights, unlike Bellman-Ford.

Answer 75

Big O Notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows. ## Footnote It's a critical tool for evaluating the scalability and efficiency of algorithms, especially in worst-case scenarios.