Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Java-Angular-AWS > Week 1 - DS&A > Flashcards

Week 1 - DS&A Flashcards

1
Q

What is time complexity?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is space complexity?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are data structures?

A

Is used to organize, manage and store data

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is an algorithm?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the big O notation?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Explain the concept of Brute Force?

A

Systematically checking for all possible solutions through an exhaustive search

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are some benefits of Brute Force?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are some downsides of Brute Force?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Explain the concept of Binary Search?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the time complexity of Binary Search?

A

O(log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What issues might implementing Binary Search have in Java?

A
  • 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)&raquo_space;> 1;
    - Unsigned right bit-shift op in Java
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q 
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);
}
A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a linked list?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is a single linked list?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are some advantages of a singly linked list?

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

what are some disadvantages of a singly linked list?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is a double linked list?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are some advantages to a Doubly Linked List?

A

Allows us to iterate in both directions

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

Reversing is easy

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are some disadvantages to a Doubly Linked List?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Where would we use Linked Lists/Doubly Linked Lists?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is Merge Sort?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the time complexity of Merge Sort?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is a Heap?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is Heap Sort?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

How does Heap Sort work?

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

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

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is a map?

A

Has a key value pair and allows for fast look up for the value if the key is known

28
Q

What are some real world uses for maps?

A
  • A map of the zip code and cities

- A map of regions and the countries in each region

29
Q

Can maps contain duplicate keys?

A

No, each key can only be mapped to 1 value

30
Q

Do maps allow for null keys and null values?

A
  • Specific implmentations allow it such as HashMap and LinkedHashMap
  • TreeMap does not support null keys and null values
31
Q

What is Insertion Sort?

A

The array is split into a sorted and unsorted part, values from the unsorted part are picked and placed in the correct position in the sorted part

32
Q

What is the time complexity of Insertion Sort?

A

O(n^2)

33
Q

What is Selection Sort?

A
  • We are repeatedly finding the minimum element from unsorted part and putting it at the beginning
  • We have 2 subarrays in 1 array
  • 1 subarray is sorted while the other remains unsorted
34
Q

What is the time complexity for Selection Sort?

A

O(n^2)

35
Q

What is a benefit of Selection Sort?

A

It never makes more than O(n) swaps

Useful when memory writes are a costly operation

36
Q

What is Bubble Sort?

A

Swaps adjacent elements repeatedly if they are in the wrong order

37
Q

What are some downsides to Bubble Sort?

A

The algorithm needs 1 whole extra pass to know if the array is sorted even after the array is done being sorted

38
Q

What is a stack?

A

Linear data type with a predefined capacity or boundary

Last In First Out (LIFO) or First In Last Out (FILO) ordering

39
Q

What are some benefits of using stacks?

A

Implement functions, parsers, expression evaluation, and some algorithms

Great for processing nested structures

40
Q

What would be a simple real-world application of a stack?

A

Reversing a string letter by letter

Undo and redo function on a computer or text editor

41
Q

What is a queue?

A
  • Linear structure that follows a First In First Out (FIFO) order
  • Queues open from both ends
    • One end for inserting data (enqueue), and the other for removing data (dequeue)
  • Stack is only open from one end
42
Q

What is a deque?

A

Elements can be added or removed from either the front or back of the queue

Short for double ended queue

43
Q

When would we want to use a linked list over an ArrayList?

A

When we have a ton of insertions and deletions

Linkedlist insertion/deletion is O(1) while ArrayList insertion/deletion is O(n)

44
Q

What is recursion?

A
  • Occurs when a method invokes itself

public static void foo( ) {
foo( );
}

  • The above will keep calling itself and adding 1 frame on top of another in the stack until we reach a StackOverflowError so we must add a condition for the method to be invoked
public static void reduceByOne(int n) {
    if (n >= 0) {
        reduceByOne(n-1);
    }
    System.out.println("Completed Call: " + n);
}
45
Q

What are Greedy Algorithms?

A
  • Each small piece of the puzzle will provide an immediate output but generally does not consider the larger picture for the problem
  • Works recursively to construct a set of objects from the smallest possible pieces
  • Mainly used for solving optimization problems
46
Q

What are some characteristics of Greedy Algorithms?

A

Creates 2 sets, one set contains all the chosen items, and another set contains the rejected items

Makes good local choices at every step in hope that the solution will either be feasible or optimal

47
Q

What type of situations would Greedy Algorithms be used for?

A
  • Used to find the shortest path
  • Used to find the minimum spanning tree using the prim’s algorithm or the Kruskal’s algorithm
  • Used to solve the fractional knapsack problem
48
Q

What are some downsides of Greedy Algorithm?

A

Since it makes decisions based on the available information at each phase without considering the whole problem, there may be a possibility that the greedy solution does not yield the best solution for said problem

49
Q

What is a set?

A

Stores unordered elements

Cannot contain duplicate elements

50
Q

What is a Hash Set?

A
  • Hash set stores the elements by using a mechanism called hashing
  • HashSet contains unique elements only
  • HashSet allows null values
  • HashSet is non-synchronized
51
Q

What is a tree?

A

The data structure is shaped like a tree

Each data element is stored in a node, all nodes are connected to each other in a hierarchical fashion

52
Q

Where would trees be useful?

A

Creating a family tree

53
Q

What is a graph?

A
  • A non-linear data structure consisting of nodes and edges
  • Nodes are sometimes also referred to as vertices
  • Edges are just lines or arcs that connect any 2 nodes in the graph
54
Q

What types of real world applications would we see graphs being implemented?

A

Commonly used in social networks like linkedIn, Facebook

Each person is represented with a node, each node is a structure and contains info such as a person’s id, name, gender, locale, etc.

55
Q

What is Breadth First Search?

A
  • A graph traversal algorithm
  • Very similar to a binary tree
  • We use queue to traverse a graph
  • Put first node in queue
  • Repeatedly extracts nodes and put its neighbours in the queue
56
Q

How is a graph different than a binary tree?

A
  • We need to track a node if it has been visited before or not in a graph
  • Can easily accomplish tracking a node with a boolean variable
  • If node have been visited then we won’t visit it again
57
Q

What is a spanning tree?

A

A subgraph of an undirected connected graph

58
Q

What is divide and conquer algorithm? 3 parts

A
  1. Divide the problem into smaller bits
  2. Solve the small bits recursively
  3. Combine the small bits to get the final solution of the problem
59
Q

What is a minimum spanning tree?

A

A spanning tree but the sum of the weights of the edge is minimum

The weights of the spanning tree is the sum of the weights given to the edges of the spanning tree

60
Q

What is Kruskal’s algorithm?

A
  • Finds a minimum cost spanning trees using the greedy approach
  • Treats the graph as a forest and every node as an individual tree
  • One of the algorithms that fall under the greedy algorithm in graph theory
61
Q

How does Kruskal’s algorithm work?

A
  • Sort all the edges based on weight from low to high
  • Take the edge with the lowest weight and add it to the spanning tree
  • If the edge that we are going to add creates a cycle, don’t add it
  • Continue to add edges until we reach all the vertices
62
Q

What are some real world applications of Kruskal’s algorithm?

A

LAN connectionsElectrical wiring among cities

63
Q

What algorithms follow the divide and conquer idea?

A

Quick sort

Merge sort

64
Q

What is Quick sort?

A

Picks an element and places all the elements smaller than it on its left and the greater ones on the right then recursively sorts the 2 subarrays on the left and right of the element

65
Q

What is Merge sort?

A

Splits the array into 2 and recursively sorts

Upon completion it will merge the 2 sorted arrays together into 1

Java-Angular-AWS (9 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions