# Week 1 - DS&A Flashcards

What is time complexity?

The amount of time taken by an algorithm to run, as a function of the length of the input. It measures the time taken to execute each statement of code in an algorithm

What is space complexity?

Measures the total amount of memory an algorithm or operation needs to run according to its input size

What are data structures?

Is used to organize, manage and store data

Enables efficient access and modification when applied correctly to a specific situation/problem

What is an algorithm?

Is a set of instructions for solving a problem

One example would be a recipe, it tells us how to create a dish, and what ingredients we would need

What is the big O notation?

Is a way developers can use to analyze the running time of algorithms

Explain the concept of Brute Force?

Systematically checking for all possible solutions through an exhaustive search

What are some benefits of Brute Force?

Allows us to reach the solution faster if we do not know about the correct data structure to solve the problem in the most efficient manner

Generally the first thing that comes to mind when solving coding challenges so it’s simply the easiest go-to solution

What are some downsides of Brute Force?

May not be the most optimal solution to a certain problem in the majority of cases

May easily run out of time due to the exhaustive search nature, brute force would have to check against all values which is time consuming, with problems that have runtime constraints this would not be ideal

Explain the concept of Binary Search?

Search a sorted array by repeatedly dividing the search interval in half

If x is less than the item in the middle, look for the left half

If x is higher than mid, then we look at the right

What is the time complexity of Binary Search?

O(log n)

What issues might implementing Binary Search have in Java?

- m = (l + r) / 2
- Sum overflows to a negative value, it stays negative when divided by two
- Solve doing:

- m = l + (( r - l) / 2)

- M = (l + r)»_space;> 1;

- Unsigned right bit-shift op in Java

Can you tell me the time complexity of this piece of code? ----------------------------------------------------------------------------------- public int fibo (int n) { System.out.println("Calling fibonaccis with input: " + n); if (n < 2) { return n; } return fibo(n-1) + fibo (n-2); }

Recursive solution, time complexity is O(2 (to the nth power))

What is a linked list?

- Linear data structure, in which elements are not stored at contiguous memory locations
- Elements are linked using pointers
- Linked lists are dynamic meaning that they can increase or decrease in size

What is a single linked list?

- Defined as all nodes are linked together in a few sequential manner, hence it is also known as a linear linked list
- Clearly is has the beginning and the end.
- Main problem is that we cannot access the predecessor of the node from the current node

What are some advantages of a singly linked list?

Insertions and deletions can be done easily in O(1) time

Space is not wasted as we can get space according to our requirements

what are some disadvantages of a singly linked list?

- Accessing the preceding node of a current node is not possible as there is no backward traversal
- If we have to go to a particular element then we have to go through all those elements that come before that element in O(n) time
- We cannot traverse it starting from the end node, we can only do so from the beginning first node

What is a double linked list?

Similar to a linked list but here each node has an extra pointer that stores the address of the previous node

Internally, the java.util.LinkedList is implemented using a Doubly Linked List Data Structure

What are some advantages to a Doubly Linked List?

Allows us to iterate in both directions

We can delete a node easily as we have access to its previous node

Reversing is easy

What are some disadvantages to a Doubly Linked List?

Compared to a singly linked list, each node stores an extra pointer which consumes extra memory

Operations require more time due to the overhead of handling extra pointers as compared to singly-linked lists

Where would we use Linked Lists/Doubly Linked Lists?

- Can be used to implement various data structures like hash-tables, stacks, binary trees etc.
- Can be used to implement functionalities such as undo/redo
- Used by a thread scheduler in many OS to maintain a list of all running processes
- Can also be used in games e.g. representing a deck of cards
- Can be used in any software that requires forward and backward navigation e.g. music players, in web-browsers to move between previously visited and current page etc.

What is Merge Sort?

Uses the divide and conquer strategy for sorting elements in an array

Recursively breaking down a problem into 2 or more sub-problems of the same or related type

What is the time complexity of Merge Sort?

Runtime is O(n log n) which is much faster and requires less operations than Insertion or Selection Sort O(n^2)

What is a Heap?

- Is a special type of tree where the tree is a complete binary tree
- Generally 2 types of heap:
- Max-Heap: The root node must be the greatest among all of the elements present within the tree and all of the sub-nodes must also be larger than their children
- Min-Heap: The root node must be the smallest among all the elements in the tree and all of the sub-nodes must also be smaller than their children

What is Heap Sort?

Eliminate the elements one by one from the heap part of the list, and then insert them into the sorted part of the list

How does Heap Sort work?

2 phases

- First step includes the creation of a heap by adjusting the elements of the array
- Remove the root element of the heap repeatedly by shifting it to the end of the array
- Store the heap structure with the remaining elements

What is the worst case time complexity for heap sort? Why?

- O(n log n)
- Occurs when the array elements are required to be sorted in reverse order
- EX - You have to sort in ascending order but its elements are in descending order