CS basics, Algorithms & Data structures Flashcards
Data structures e.g. Stack vs queue
Stack vs queue
The primary difference between Stack and Queue Data Structures is that Stack follows LIFO while Queue follows FIFO data structure type. LIFO refers to Last In First Out. It means that when we put data in a Stack, it processes the last entry first. Conversely, FIFO refers to First In First Out.
The stack can be used to solve problems like pre-order, post-order and in-order traversal of the binary tree, which are based on recursion, whereas queue can be used to solve problems like producer-consumer problem involving sequential processing of underlying data.
Boolean operations, short circuits in Boolean operations
t
Complexity of algorithms, big O notation
Big O notation is used to show the performance optimization of the solution. On the other hand, it’s used to demonstrate how fast or resource consumption is the solution.
the common big O notations are as follows:
O(1): this is the best performance. which means the constant time, no matter how big the input is. for instance: a condition or assigning a variable.
O(log n): log n is almost like O(1), it’s a little bit more than that, but in the end, it’s one of the best. for instance: a search algorithm.
O(n): The is a linear time complexity, which means it takes only as long as the input is. for instance: a sorting algorithm.
O(n^2): it is called quadratic which is a high-performance solution, for instance, nested for loop.
O(2^n): it’s a very high-performance solution, for instance, Fibonacci or recursion.
Trees, graphs and ways to traverse graph
Sorting algorithms
Recursion, tail recursion, mutual recursion
Search in binary tree
Linear-time sorting. (count sort)
Sorting of linked list
Prefix and suffix trees
Describe heap
Greedy Algorithm
NP-complete algorithms
Map/reduce and divide and conquer approach in solving tasks
Dynamic programming
