Java Collections and Data Structures Flashcards

Question

LinkedHashMap vs TreeMap LinkedHashSet vs TreeSet

Answer 1

LinkedHashMap maintain in which items are inserted in Map but TreeMap sort entries based on sorting key in ascending order => Same goes for LinkedHashSet vs TreeSet

Answer 2

Enumeration ( it's not a data structure , but important in the context of DS ) BitSet Stack Vector Dictionary HashTable Properties

Answer 3

Enumeration is an interface that is used to retrieve successive elements from DS

Answer 4

elements() keys() hasMoreElements() nextElement()

Answer 5

BitSet class used for set of Boolean values

Answer 6

Vector is a class similar to array except it can increase and decrease its size dynamically depending on how much elements

Answer 7

Stack is a class that implements LIFO

Answer 8

Dictionary is an abstract class for mapping keys to values

Answer 9

HashTable is a class that extends Dictionary. It is a collection of key value pairs (Entry). Each key value pair known as entry

Answer 10

Properties is a subclass of HashTable , its key and value type is String

Answer 11

Iterator is an object that implement Iterator() or ListIterator() interface , to pass through elements in collections (or remove elements)

Answer 12

List al = new ArrayList<>(); // Use iterator to display contents of al Iterator itr = al.iterator(); while(itr.hasNext()) { Object element = itr.next(); System.out.print(element + " "); }

Answer 13

Comparator is an interface that defines what sorted order means

Answer 14

Compare(obj1,obj1) equals()

Answer 15

Comparable is an interface used for to compare and sort collections objects

Answer 16

obj.compareTo(obj1) equals

Answer 17

Tree is hierarchichal (non-linear) data structure consisting of nodes connected by edges

Answer 18

*node:basic unit of tree that holds values *root:the higher node in tree , having no parent *parent: have other nodes connected to it (children). *child: node under parent *leaf:a node with no children *edge: link between two nodes *subtree:any node and its descendants *depth: number of edges from root to a specific node *height: the longest path from root to leaf

Answer 19

*Binary Tree :all node have at most two children(left and right) *Binary Search Tree (BST):A binary tree where the left child is smaller and the right one is larger than the parent *AVL Tree: A balanced binary search tree where the heights of two child subtrees of any node differ at most by one. *Heap:heap has two concepts : => Heap memory: it's where object are dynamically allocated , and it is managed by JVM => Heap Data Structure : it's a binary tree structure for retrieving min or max element,it is used in algorithms like priority queues

Answer 20

We use tree in scenarios like data representation(file systems) , search algorithms ...

Answer 21

Graph is data structure that consists on connecting vertices ( nodes ) with edges.

Answer 22

Directed graph (unidirectional) : graph with a directed edges , have only one sense. Undirected graph (bidirectional) : graph wih undirected edges , have two senses Weighted graph : are graps which have weights on their edges.

Answer 23

*Adjacency 2D :Consist of a 2D array which has nodes/vertices values on their line and column , if their is a connection we put 1 , otherwise 0. *Adjacency List : consist of a linkedList where each one correspand to a vertex and contains list of all other vertices that is connected to.

Answer 24

How code slows in terms of data size. *Time Complexity : Describes how the runtime of an algorithm increases with the size of the input. *Space Complexity :Describes how the memory usage of an algorithm grows with the size of the input.

Answer 25

O(1):Constant time O(log(n)):Logarithimic time O(n):Linear time O(nlog(n)):Linearithmic time O(n^2):Quadratic time O(2^n):Exponential time O(n!):Factoriel time

Answer 26

iterate through array comparing between each 2 elements until replacing max at last , repeating until all is sorted ____________________________________ Time complexity : O(n^2) Space complexity : O(1) Stable : Yes

Answer 27

Iterating through array until finding min element and place it first ,repeat until all is sorted ( or search max instead of min ) _____________________________________ Time Complexity: O(n^2) Space Complexity:O(1) Stable:Yes

Answer 28

We start with comparing first two elements , after that we have a sub array already sorted (of length = 2) , now ,we reached third element , we compare it to the whole precedent array , we sort all elements ( we have array with length 3 sorted ) we continue until the whole array is sorted. __________________________________ Time Complexity: O(n^2) Space Complexity:O(1) Stable:Yes

Answer 29

Consist on dividing array by 2 until we can't divide anymore after that we compare left to right and sort then merge sub arrays until it give us the sorted array =>Merge Sort is a "divide-and-conquer" algorithm. _____________________________________ Time complexity : O(nlog(n)) Space complexity : O(n) Stable : Yes _____________________________________ Code key points : *left

Answer 30

We use pivot, we choose a random position of pivot , and we use two index (i=-1 and j=0), we iterate through array if arr[j] Quick Sort use "divide and conquer" algorithm _________________________________________ Time Complexity: for average : O(nlog(n)), worst case O(n^2) Space Complexity:O(log(n)) Stable : No _________________________________________ Code key points: *low

Answer 31

Consist of heapify array , array will have properties as a heap ( array become like binary tree ) then we sort array by having it each parent value bigger than its children, the last step is to swap root node (max val) with last array value ( like remove it from tree ) and again heapify array then do things recursively until the array is sorted _________________________________________________ Time Complexity: O(nlog(n)) Space Complexity: O(1) Stable:No __________________________________________________ Code key points: we code on heapSort() method + we add heapify() inside it(called 2 times inside 2 loops separated)

Answer 32

int[] arr = {5, 3, 8, 4, 2}; Arrays.sort(arr); // Sorts primitive arrays _______________________________________________ List list = Arrays.asList(5, 3, 8, 4, 2); Collections.sort(list); // Sorts collections

Answer 33

*Merge Sort have always always O(nlogn) time complexity but Quick Sort can have O(n^2) because merge sort consist on split and merge element which don t depend on order of element like choosing a bad pivot. *Quick Sort does not require additional space for merging, making it more space-efficient than Merge Sort, which needs O(n) extra space

Answer 34

Preorder traversal; root->left->right Inorder traversal: left -> root -> right Postorder traversal: left -> right -> root

Answer 35

a search alogrithm that consist on traversing a tree or a graph data structure => to traverse from Start to reach End we first pick a route we traverse until "dead end" / "previously visited node", we go back (Backtrack) to last node that has unvisited adjacent neighbors nodes and repeat the previous process until we reach the end _______________________________________________ We use Recursion (better) or Stack here. _______________________________________________ Agorithm: *We mark the start node as visited *for all adjacent of current node : We visit all unvisited adjacent neighbors and mark them as visited ( with recursion) *When all adjacent nodes have been visited , backtrack to the previous node

Answer 36

a search algorithm that consist on traversing a tree or a graph data structure This is done one "level" at a time (BFS) instead of one "branch" at a time (DFS) !!!!!!!!!!!!!! ____________________________________________________ we use Queue here. ____________________________________________________ Algorithm: *Start by marking root or starting node as visited *Add root node to queue *while queue still not empty : remove front node from it and add all its unvisited neighbors and mark then as visited one by one * repeat until all nodes are visited or queue is Empty

Answer 37

Better for finding shortest path for unweighted graph

Answer 38

Better for finding cycles and connected components

Answer 39

numVertices and adjList/adjMatrix as attributes , with a param constructor to fill attributes then addEdge()(+removeEdge() for matrix representation) method and printGraph().

Answer 40

A search algorithm to find index of a target value on a **Sorted** array. Half the array is eliminated on each step => Binary Search is efficient on large Dataset => Time Complexity : O(log(n))

Answer 41

A search algorithm that improves binary search by calculating the estimated position where target value is. -------------------------------------------------------------------------- pos=low+((target-arr[low])/(arr[high]-arr[low]))*(high-low) _____________________________________________________ if (arr[pos] == target ) : we return pos if (arr[pos] < target) : low=pos+1; if (arr[pos] > target): high=pos-1; ______________________________________________________ Time Complexity : O(log(log(n))) , worst case : O(n) Space Complexity : O(1)

Answer 42

also dynamic array, is an array with a resizable capacity, it store elements in a "Contiguous" memeory location.

Answer 43

is a data structure, a chain of nodes , where each Node contains 2 parts , data and a next pointer that contains address to the next node. LinkedList doesn t have an index. LinkedList have a head ( points on 1st node address ) and the address on the last node is null

Answer 44

It is similar to singly LinkedList , except that it contains on each node 3 parts , it adds prevrious pointer which is the address to the previous node. It has a head and a tail ( points on last node address ). The previous of head is null like the next of tail is null

Answer 45

*Read an element by index with O(1) Time complexity *Contiguous Memory location *Easy to insert/delete at the end

Answer 46

*Wastes more memory *Shifting elements is time consuming O(n) *Expanding/shrinking an array is time consuming O(n)

Answer 47

*LinkedList always insert/delete elements with O(1) time complexity *ArrayList have index which read element in a O(1) time complexity not like LinkedList ( O(n) )

Answer 48

Recursion is when a thing is defined in terms of itself

Answer 49

*Easy to read/write *Easy to debug

Answer 50

*Sometimes Slower *Sometimes Uses more memory => Cause : Call Stack, to keeps track of the order of a lot methods.

Answer 51

Call Stack is a data structure that keeps track of the order in which our program needs to function ( implements LIFO )

Answer 52

key.hashCode()%Capacity is equal to index ; If two hashes calculated to be on the same value , that's known as a collision.

Answer 53

Each of the stored location in Hashtable known as bucket, if a bucket have already an entry ,within the first entry we will add an address to the location of the next entry and keep on adding more if there is more entries on this bucket , this will become as a separate linkedlist (this process is known as Chaining). In this case , if we are searching for a key inside a bucket of more than one entry we will iterate through the linkedlist until we find the wanted key. The less there is a collision , the more efficient a Hashtable will lookup for a value.

Answer 54

To reduce number of collision , you can increase the size of Hashtable. But then again Hashtable will use more memory. =>You should find balance between having a hashtable with less possible collision and memory usage.

Answer 55

See document table

Answer 56

See document table

Answer 57

See document table

Java Collections and Data Structures Flashcards

(81 cards)