Data_Structures_Basics

Data Structures Basics

The efficient use of algorithms depends on the scenario, such as a task list that needs to be sorted and the structure type such as an array.


Arrays - Collection of elements identified by index or key.

Calcualte item index: O(1)
Insert or delete item at beginning or middle O(n)
Insert or delete item at end: O(1)


LinkedLists - Linear collection of data elements called Nodes. Faster than arrays to iterate sequentially.
Contain reference to the next node in the list. First item is head and last is tail that points to Node.

Single LL: each data item only knows about it next neighbor
Double LL: each data has a reference to previous and next items

Elements can be easily inserted and removed and underlying memory does not need to be reorginized (Indiviudal nodes do not need to be stored continously)

Item lookup is O(n). Achieving operations are done by reorganizing nodes.
Underlying memory doe not need to be contiguous.

Stacks and Queues

Stack- Last in (push or append) First out (pop) (constant time operation). Used to parse expression statements. And backtracing (back button)
Queue 0 First in First out. Order processing, or message processing.


HashTables - 
also called (dictionaries) uses keys to compute an index and map key to a value. Hash function assigns each key to the value.
A hash table is an associative array where a hash function uses a key to compute an index value and to map to the data value.

when you add a redundant entry to a hash table the new entry replaces the old one.




for item in items:
  if (item in counter.keys():
  counter[item] +=1
  else:
  counter[item]=1 //creates a dictionary entry for item and sets its value to one.


items = ["apple", "pear", "orange", "banana", "apple","orange", "apple", "pear", "banana", "orange","apple", "kiwi", "pear", "apple", "orange"]
 
filter = dict()
   for key in items: // The code in line 3 performs a loop over each defined item and then adds it to the hash table.
       filter[key] = 0

 result = set(filter.keys())
       print(result)


def find_max(items):
     if len(items) == 1:
         return items[0]
 op1 = items[0]
 print(op1)
 op2 = find_max(items[1:]) //Recursion occurs when a function calls itself. With this code snippet, a function find_max is defined and that function is         
                            called within itself at line 6. This repeats the process of the function.
 print(op1, op2)

-----------------------------------------------------------------------------------------------------------------
Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function.
Example of use case is searching in a directory that has multiple directories for a specific file.

1.Recursive functions need a breaking condition.
2.Each time the function is called the old agruments are saved using a Stack Data Struct.

ex.
function countdown(x){
    if (x == 0)
        print("done")
    return 
    else
        print(x,"...")
        countdown(x-1)
}
countdown(4)

When executing a return statement in a recursive function the program returns to the statement after the function call was made. 
The algorithmic steps for implementing recursion in a function are as follows:

1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself.

2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem.

3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop.

step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.



What is the difference between direct and indirect recursion? 
A function fun is called direct recursive if it calls the same function fun. A function fun is called indirect recursive if it calls another function say fun_new and fun_new calls fun directly or indirectly.
-----------------------------------------------------------------------------------------------------------------
Important Algorithms to know

Sorting Algorithms: Bubble Sort, Insetion Sort, Heap Sort etc
Searching Algorithms: Linear Search, Binary Search
String Algorithms: Rabin Karp Algorithm, KMP Algorithm, Z Algo
Divide and Conquer: Quick Sort, Merge Sort, Matrix Multiplication 
Recursion & Backtracking: N-queens, Rat in a maze, Sudoku
Greedy Algorithms: Job Sequencing Problem, Prims Algo for MST, Fractional Knapsack problem
Dynamic Programming: 0/1 Knapsack Problem, Longest Palindromic subsequence, Longest common subsequence
Tree-Related Algo: in-order, pre-order, post-oder, level-order
Graph Algorithms: Breadth first search, depth first search, Dijkstra Algo, Floyd Warshall Algo, bellman-Forst Algo, Prim's alog, Kruskal's algo 
Sliding Window: Fixed size sliding window, Variable-size sliding window.


Problems to Try

Two Sum - Done
Roman to Integer - Done
Palindrome Number - DOne
Maximum Subarray - Done
Remove Element 
Contains Duplicate 
Add Two Numbers
Majority Element
Remove Duplicates from Sorted Array