Brainscape's Knowledge GenomeTM

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


See full index

Java > Java Collections and Data Structures > Flashcards

Java Collections and Data Structures Flashcards

1
Q

what are “ad hoc” classes

A

before java 2 , java provide Dictionary,Vector,Stack and Properties classes.

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

What is Collection

A

Collection is an interface that extends Iterable and extended by List , Queue and Set Interfaces.

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

Collection package

A

java.util

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

Collection hierarchy

A

https://www.tutorialspoint.com/java/images/hierarchy-of-collection-framework.jpg

Or tutorialspoint website in Collections Framework section ( if website not found ).

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

Some Collections methods

A

.sort(),shuffle(),max(),min()

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

Some List interface methods

A

add(val)/add(i,val)
addAll(i,collection)/addAll(collection),
remove(i),
set(i,val),
get(i)

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

What is Queue

A

Queue interface implements FIFO

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

What is the objective of Queue ?

A

it’s holding elements before processing them.After the process, the element is deleted from queue and we pass to next one.

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

Classes that implements Queue

A

LinkedList
ArrayDeque
PriorityQueue

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

Interfaces that extends Queue

A

Deque
BlockingQueue
BlockingDeque

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

Some Queue methods

A

.add()
.peek() : give head (1st element ) of queue
.remove()
.size()

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

What is Map

A

Map is an interface which has a unique key object and their values

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

Map and Collection

A

Map doesn t implements Collection !!!!!!!!!!!!!!!!!

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

Some Map Exception

A

*NullPointerException : is thrown when we try to use a null object ( which is not allowed in map )
*ClassCastException : is thrown when an object is incompatible with the map elements type.

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

Classes that implements Map

A

HashMap
LinkedHashMap
TreeMap

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

Interface that implements Map

A

SortedMap

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

some Map methods

A

put(key,val)
remove(key)
getOrDefault(key,defaultValue)
containsKey(key)
containsValue(val)
keySet()
entrySet()
values()
size()

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

SortedMap Interface

A

SortedMap extends Map interface , it ensures that entries are maintained in ascending key order.

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

Some SortedMap Exception

A

*NoSuchElementException : when no items in the invoking map
*Others exceptions of Map : look above

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

Class that implements SortedMap

A

TreeMap

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

SortedMap Disadvantage

A

every time we add an item it does resort so it affects performance negatively

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

Why we use Set Interface ?

A

Set interface can’t contains duplicates

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

Some Set methods

A

contains()
add()
clear()
remove()
size()
isEmpty()

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

SortedSet

A

it’s like SortedMap in Map

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

LinkedHashMap vs TreeMap
LinkedHashSet vs TreeSet

A

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

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

Data Structure

A

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

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

What is Enumeration ?

A

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

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

Some Enumeration methods

A

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

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

What is BitSet ?

A

BitSet class used for set of Boolean values

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

What is Vector ?

A

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

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

What is Stack ?

A

Stack is a class that implements LIFO

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

What is Dictionary ?

A

Dictionary is an abstract class for mapping keys to values

33
Q

What is HashTable ?

A

HashTable is a class that implements Dictionary.
It is a collection of key value pairs (Entry<K,V>). Each key value pair known as entry

34
Q

What is Properties ?

A

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

35
Q

What is Iterator ?

A

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

36
Q

Example of Iterator use

A

List<String> al = new ArrayList<>();</String>

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

What is Comparator ?

A

Comparator is an interface that defines what sorted order means

38
Q

Comparator methods

A

Compare(obj1,obj1)
equals()

39
Q

What is Comparable ?

A

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

40
Q

Comparable methods

A

obj.compareTo(obj1)
equals

41
Q

What is Tree ?

A

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

42
Q

What is Key concepts of Tree ?

A

*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

43
Q

What are common types of Tree ? and what is their defs ?

A

*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

44
Q

Where we use Tree ?

A

We use tree in scenarios like date representation(file systems) , search algorithms …

45
Q

What is Graph ?

A

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

46
Q

What are types of Graph ?

A

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.

47
Q

What are the two common approaches to represent a Graph ?

A

*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.

48
Q

Big O notation

A

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.

49
Q

Common Big O Notations

A

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

50
Q

Bubble Sort

A

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

51
Q

Selection Sort

A

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

52
Q

Insertion Sort

A

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

53
Q

Merge Sort

A

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<right
two functions: mergeSort(…)2 then merge(…)

54
Q

Quick Sort

A

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]<arr[pivot] we increment i and swap i and j values , and then increment j , else we ignore things and increment j, once j=pivot we swap arr[pivot] with arr[i+1].after that all values on left small than pivot value and the opposite for the ones on right.
After that we divide array to sub-arrays and we choose a random pivot position again and when all sorted we gather array partitions. this is done recursively .
=> 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<high
two functions : partition(return pivot) then quickSort()2

55
Q

Heap Sort

A

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)

56
Q

Java’s Built-in Sorting

A

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

57
Q

Merge Sort vs Quick Sort

A

*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

58
Q

Traversal in binary tree

A

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

59
Q

Depth First Search (DFS)

A

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

60
Q

Breadth First Search (BFS)

A

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

61
Q

Use of BFS

A

Better for finding shortest path for unweighted graph

62
Q

Use of DFS

A

Better for finding cycles and connected components

63
Q

Graph implementation

A

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

64
Q

Binary Search

A

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))

65
Q

Interpolation Search

A

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)

66
Q

What is ArrayList ?

A

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

67
Q

What is LinkedList (singly)

A

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

68
Q

What is Doubly LinkedList

A

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

69
Q

What are ArrayList advantages ?

A

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

70
Q

What are ArrayList disadvantages ?

A

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

71
Q

ArrayList vs LinkedList

A

*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) )

72
Q

What is recursion ?

A

Recursion is when a thing is defined in terms of itself

73
Q

What are recursion benefits ?

A

*Easy to read/write
*Easy to debug

74
Q

What are recursion disadvantages ?

A

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

75
Q

What is Call Stack ?

A

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

76
Q

How Hashtable insert its element

A

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

77
Q

What we do during collision (for hashtable) ?

A

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.

78
Q

How to reduce the number of collision ?

A

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.

Java (9 decks)

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