Linear Data Structures Flashcards
1
Q
What is Big O notation?
A
Big O is a mathematical notation that describes the limiting behavior of a function where the argument tends toward a particular value or infinity.
2
Q
What is Big-O?
A
Helps us determine if an algorithm is scale-able or not
3
Q
When do we use Big O notation?
A
Describe the performance of an algorithm
4
Q
What are the five common Big-O curves?
A
O( 1 ) - constant time
O ( n ) - linear time
5
Q
What are the five common time complexity curves?
A
6
Q
How does linear big - O grow?
A
Linearly and in direct proportion to the size of the input
7
Q
What is O(n^2)?
A
Quadratic.
Nested loops
8
Q
How does the logarithmic curve behave?
A
It slows down as the input size grows
9
Q
What is exponential time complexity?
A
The exponential curve grows faster as the input grows.
10
Q
What is the shortcut to run JVM in debug?
A
Control + D
11
Q
When would we have a quadratic Big-O value?
A
When we use nested loops that each performs an iteration over the entire set of values.
12
Q
What are the linear data structures?
A
- Arrays
- Linked Lists
- Stacks
- Queues
- Hash Tables
13
Q
What are arrays?
A
Reference type
fixed-length data structure.
Values are indexed sequentially in memory.
Optimal for looking up values by their index.
14
Q
What can we use arrays for?
A
We use arrays to store lists of values like strings, objects or anything.
These items are stored sequentially in memory.
Can store strings, objects, numbers or anything.
15
Q
What are the pro’s of arrays?
A
Looking up the index is very fast
why?
item index lookup doesn’t involve loops or complex data access operations.
16
Q
What are the disadvantages of arrays?
A
They’re fixed length.
Not good for storing values that need to be added or deleted frequently.
Adding or deleting an item requires copying old array into a new array with a cost of O(n).
17
Q
How do we keep track of the number of items in our array?
A
Using a private variable “count”
increment count for each new item
18
Q
How do we implement resizeIfRequire ( ) in our addItem method of our array class?
A
Create a new array x 2 size
copy items into new array
O ( n ) operation!
19
Q
How do we implement the removeAt ( ) method in our array class?
A
Shift items left
Copy items from [index + 1] into [index]
20
Q
How can we implement the print ( ) method in our custom array class?
A
Use a for loop to iterate over each index
+ print on console
21
Q
How can we implement the max ( ) method in our Array class?
A
What is run time complexity?
O(n):
have to iterate over the entire array to find the largest number.
This number may be at the end of the array (worst case scenario).
22
Q
How to implement the insertAt ( ) method in our Array class?
A
23
Q
How to implement the reverse ( ) method in our Array class?
A
24
Q
How to implement the intersect ( ) method in our Array class?
A
Foreach loop + nested if loop
25
What is the **Big-O** of the **addItem ( ) to an array**?
It's **O(n)**
**linear time complexity**
**Why?**
Array's are **static in size**.
In the **worst case**, we have to **create a new array**, **copy all items** to this array
26
What is the **Big O** of the **removeAt ( )** operation in **arrays**?
**O(n) - Linear time complexity**.
**Why?**
**Worst case** it's the first item in the array, then we have to **shift all items** over which is an **O(n) operation**!
27
**What** is the **Big O** of **find by value** in an **array**?
**O ( n )**
**Worst case** have to iterate the **entire array**!
28
What is the **Big-O** of **lookup by index** in an **array**?
**O(1)**
why?
29
What is the **syntax** for working with **Arrays in Java**?
**Two ways** :
Create with an **empty array**
Insert values, omit the **new operator**
30
What is the **Array's class** in Java?
Declared in **Java.util**
Static methods to **perform operations** on Arrays
31
What are the **two implementations** of **dynamic arrays** in **Java**?
**Vector class:**
will grow by **100% of size** when full
methods are synchronized (**single thread** access)
**ArrayList class:**
will grow by **50% of size** when full
32
What are useful **ArrayList** methods?
**.add(item)** - dynamic adds item
**.remove(index)** - removes item at index
**.contains(item)** - boolean if item is in list
**.size( )**- # of items in array
**.toArray** - converts to regular array object, not arrayList class
33
AA What are circular arrays?
Very important, powerful concept in data structures
34
**What** is **covered** in the **linked-list** **collection**?
35
What are **linked lists**?
A **data structure** consisting of a **group of nodes** in **sequence**.
Each node contains **one value** and **one address** for the **next node.**
Unlike **array's** **linked-lists** can **grow automatically**.
36
**When** do we use **linked-lists**?
In **building** more **complex data structures**
**they are the second most common after Arrays**
37
What are the **key difference**s between **Arrays** and **LinkedLists**?
**Dynamic arrays**:
ArrayList - **Grow by 50-100%** of the size, **wasting memory**
LinkedLists:
**Don't waste memory**
**require extra memory** for storing the **next node location**
38
How do you work with a linked-list in java?
java.util.LinkedList package
can access pre-built methods
.insert ( )
.delete ( )
39
What should we always access when we **use java.util LinkedList class?**
**Integer class** (primitive wrapper)
**Because** we are using the **integer class**
A **wrapper class** for the **primitive integer**
**Not**, a primitive type
40
LL If we **don't declare** the type in a **LinkedList** class what can we store **automatically**?
Any **type of object**
could be **a string**
could be an **integer**
41
What are the **operations** on **Linked Lists**?
AddLast ( )
AddFirst ( )
IndexOf ( )
Contains ( )
RemoveFirst
RemoveLast
Reversing LinkedList
kth-node from end
42
LL What are the **run time complexities** of the insert ( ) method on **linked - lists**?
43
What is the **Big-O tim**e complexity for **various operations** on **linked-lists**?
**addFirst** - O(1)
**addLast** - O(1)
**removeFirst** - O(1) - update head to point to next item
**removeLast** - O(n) - getPrevious method is an O(n) operation
**contains** - O(n) - traverses entire list to look for item (worst case))
**indexOf** - O(n) - traverses entire list to look for item (worst case))
**toArray** - O(n) - traverse entire list of nodes, storing into an array
**getPrevious** - O(n) - traverse entire list
44
What is the **run-time complexity** of the various **linked operations**?
**Lookup**
## Footnote
**By value** = **O(n)** - because the value we are looking for may be stored in the last node (worst case).
**By index** = **O(n)** - the nodes of the linkedlist may be all over in memory, each node has to keep a reference of the next node, in worst case scenario you have to traverse all the nodes to find the index.
**Insert**
**At end** = O(1) - Just need to create a new node and have end (tail) point to it.
**at beginning** = O(1) - just need to create a new node and have start (head) point to it.
**middle** = O(n) - have to iterate over entire list, incrementing an index variable before inserting new node.
Delete
**at end** = O(n) because have to interate entire list to find the reference to the last node (tail).
**at beginning** = O(1)
**middle** = O(n)
45
How do we **implement** the **private Node class** in our **LinkedList class** in Java?
46
How do we **implement** the **addLast method** in our LinkedList class in Java?
**O(1) operation** -
create a new node, update **last.next to** point to it.
47
How do we **implement** the **addFirst** method?
**O(1) operation**
Create a node, set **node.next** to first
48
How do we **implement** the **removeFirst** method in our **LinkedList** class?
**O(1) operation**
update the second item as the **first item**
49
How do we **implemen**t the **removeLast ( )** method in our **LinkedList** class?
**O (n) operation**
getPrevious ()
iterates the entire list
50
How do we implement the **IsEmpty( )** method in a clean modern way?
**Extract into a private method** and call that method
51
How do we **implement** the **indexOf (int item)** method in our **LinkedList class**?
**O(n) operation**
traverses entire list search for item (worst case)
52
How do we **implement** the **contains ( )** method in our LinkedList class?
**O(n) operation**
**indexOf ( )** method
Searches **entire list** worst case
53
How do we **implement** the **getPrevious ( )** method in our LinkedList class?
**O(n) operation**
search **entire list** for node **worst case**
54
How do we **implement** the **toArray ( )** method in our **LinkedList**?
**O (n) operation**
copy **every node** in the list **into an array**
55
How do we **implement** the **reverse ( )** method in our **LinkedList** class?
**Popular interview question**:
Reverse LinkedList in place.
O(n) runtime complexity
Establish two pointer variables
previous (last) and current (first)
Keep track of the last node with a variable next (n)
iterate through changing the direction of links
then set the last and first nodes
56
How do we **implement** the **getKthFromEnd ( )** in our Linked List class?
**O(n) operation**
Iterate until the end!
**Popular Interview Question**:
Find the **Kth node** from the end of a Linked List in **one pass**
57
LL How do we **implement** **printMiddle ( )** in our **Linked List** class?
Find relationships between pointers
Nodes increases by 2 as middle increases by one
58
How do we **implement** **hasLoop ( )** method in our **Linked List** class?
59
What are **circular LinkedLists**?
**Last node** references **first node**
**Doubly** and **Singly** LinkedLists can be **circular**!
**Benefits:**
circular navigation!
**UI in a form** that moves to the **first item after completion**
**Playlists that repeat** after the last song
60
What is a **doubly linked-list**?
**Doubly** LinkedList:
**O(1)** operation for **removeLast** ( ) !
It has an extra field to **reference** the **next node** and the **previous node**!
**Singly** linked-lists:
Only have a **reference** to the **next node**!
O(n) for delete at end.
61
What are **stacks**?
A **wrapper** around **Arrays** or **LinkedLists**
Allows special **data access** (LIFO)
62
How can we **solve real-world** **problems** with **stacks**?
**solve** many complex **real-world problems**.
**undue** feature
**forward/backward navigation** in a web browser
build **compilers**
evaluate **arithmetic expression**
63
What is the **LIFO** principle?
**Think of a stack of books**
Imagine a **stack of books.**
**Can only add/remove** the **top book.**
**Last In First Out Principle (LIFO)**
64
What are the **four stack** operations?
Imagine a **stack of books.**
**push ( )** : adds item on top
**pop( ) :** removes item on top
**peek( ) :** returns item without removing
**isEmpty( ):** determine if empty.
65
S What is the **internal implementation of stack**s?
**Internally, data** and **objects** are stored in a LinkedList or an Array
Stacks are a special data access wrapper (LIFO)
66
S What is the **runtime complexity** of **various operations** on **stacks**?
**O ( 1 ) operation**
push ( ) : adds item on top
pop( ) : removes item on top
peek( ) : returns item without removing
Why?
**addLast ( )**, **addFirst ( )** , **removeLast ( )** are all **O ( 1 )** operations in **LinkedLists**.
67
How can we work with **Stacks** in **Java.util package**?
Defined in **Java.Util package like other data structure classes!**
Stacks are **generic** - can work with **any data type** (characters, strings, custom objects, integers)
68
How can we **implement** the **reverse ( )** method using a **stack**?
**O (n) operation**!
Stacks are best friends for reversing the order.
**Popular Interview Question:**
Write code to reverse a string.
69
What is **wrong** with how **data structure books** teach **implementatio**n of **isBalance ( )** using a **stack**?
It's **really ugly**!
**refactor** using private **helper methods** and **arraylists**
70
How do we **implement** the **isBalanced ( )** method using a **stack**?
**O (n) operation**! forreach ch in input
**Popular Interview Question**:
Write code to example whether **order and pairs of brackets** are **balanced in a string**.
71
How do we **implement** the **push()** method using an **array** in our **stack class**?
72
How do we implement the **pop ()** method using an array in our Stack class?
73
**How** can we **implement** the **peek ()** method in our **stack class**?
74
How do we **implement** the **isEmpty ( )** using an **array** in our Stack class?
75
How do we implement **two stacks** using **one array** to support **push ( ), pop ( ), isEmpty ( ) , isFull ( )** on both stacks?
76
S How do we **implement** a **MinStack** using **two stacks**?
77
What is a **queue**?
A **data structure** uses **removeLast ( )**
**(FIFO) - first in first out**
Think of a **line at a restaurant.**
**First in line**, **first out of line**
78
What **real-world** problems can **queues** solve?
**Specific**:
printers
OS allocation
Web Servers
live chat applications
**General:**
Any **application** in which a client (**mobile device**) needs access to a **single resource (server)**.
79
What are the **queue operations**?
**enqueue ( ):** add the item to back of the queue
**dequeue ( )**: remove the item from the front of the queue
**peek ( )**: look at the item at front of the queue without removing it
**isEmpty( ):** check if queue is empty
**isFull( )** : check if queue is full
80
What are the various **run-time complexities** for **operations** on **queues**?
81
What is a **queue** in Java?
**An interface** - cannot instantiate it
**Implementing class (Java)**:
**ArrayDeque** (double-ended) - uses resizeable array
**LinkedList** (**90% of time**) - uses linkedlist
\*\***Interface** - tells implementing classes what methods a queue should have
82
What are the two most common implementations of the queue interface?
**ArrayDeque**
**LinkedList**
\*two most common interface implementation
\*interface cannot be instantiated
\*interface contains methods
83
What are the **queue methods** in **Java**?
**Computer Science:**
**enqueue** ( )
dequeue ( )
**Java Programming**:
**add ( )** - adds item to queue, throws exception if full
**offer ( )** - adds item to queue
**poll ( )** - removes item from queue, if empty returns null
**remove ( )** - removes item from queue, if empty returns exception
84
What are the **three ways** to **implement** the **queue data structure**?
**Array**, **LinkedList**, **Stack**
**Popular Interview Question:**
**implementations** queue using **Array**, **Stack** or **LinkedList**
85
How do we **implement** the **reverse( )** method on a **queue** using **a stack**?
**Popular Interview Question**:
Reverse a queue
86
What is the **algorithm** for implementing **dequeue ( )** using **an array**?
**O (1) operation**!
87
How do we implement **enqueue()** using **an array**?
88
How do we implement the **dequeue()** method using an array?
create a variable front.
change item in front to 0
increase front++
89
Why do we need **circular arrays** for our **queue class**?
The deQueue operation causes **empty spaces in the array**.
The rear variable eventually points to an index out of bounds
we need a way to store items in the previous index positions while maintaining our queue order
the array **index from previously deleted elements** could be used to i**ncrease array capacity using an equation**
90
What is the circular array implementation of dequeue() method?
91
What is a **circular array**?
**Technically,** we don't have circular memory
Use this algorithm to find the **next index position**
the **algorithm** provides **circular indexing**
92
How can we implement a queue using a stack?
use two stacks
use stack 1 for enqueue method
use stack 2 for dequeue method (reverse)
93
Q What is a popular **queue interview question** involving **stacks**?
Create a **queue using stacks**
94
Q How do we implement **enqueue ( )** and **dequeue ( )** using **circular array indexing**?
95
**What** is the **implementatio**n of the **dequeue ( )** method using **two stacks**?
96
How can we **refactor our code**?
Extract the method
97
What are **priority queues**?
processed in the **order of their importance**
not the order in which they are **added to the queue**!
In Java, the **smallest numbers come out first**!
All **numbers are sorted**!
98
What is an **application** of **priorty queues**?
**OS system** uses **PriorityQueue** to **schedule tasks** (**highest priority task first**)
99
**What** is the **algorithm** for sorting items in a **priority queue** using an **array**?
Sorting algorithm
100
How do we implement the **enqueue()** method in our **priority queue** using an **array**?
Sort **based on values** then **insert at index**
101
**How** do we **implement** the **dequeue ( )** method in a **priority queue** using an **array**?
updating the pointer position
value is still stored in the array
could copy over item
use a circular array
102
What is an **interview question?**
removeFirst ( )
addLast ( )
103
Q What's an interview question?
104
Q What is an **interview question**?
105
What are **hash tables**?
**Data structures**
**superfast lookup** and **many applications**.
**Come up** in **interviews often**!
106
HT What **real-world problems** can hash tables solve?
**spell-checkers**
**dictionaries**
**compilers**
**code editors**
**Why?**
Can lookup words **amongst thousands** **super fast**
**Quickly** lookup a word and translation
Lookup **address** of **functions and variables**
optimizing **many algorithms**
Anywhere to **lookup an item super fast**!
107
How do **hash tables** work?
Internally, uses **an array** to **store values**
**Items** stored as **k****ey-value** pairs
**Key** is passed to **hash function**
**The hash function** gives the index of **object in memory**!
Give hash function the **same input (key),** it will give us the same **output (value)**!
**Read** / **Write**
108
What are the **hash table operation**s?
***.put ( )*** - maps specified key to the spefiied value in the hashtable
**O(1) operation**
.***putIfAbsent ( )*** - if specified key is not associated w/ a value, associates it with the given value, otherwise returns current value
**O(1) operation**
*.**contains ( )*** - tests if some key maps into a specified value in the hashtable
**O(1) operation**
**.*containsKey ( )* -** Tests if the specified object is a key in the hashtable
***.get ( )*** - returns value to which spefieid key is mapped
**O(1) operation**
***.remove ( )*** removes entry for the specified key only if it is currently mapped to a specified value
**O(1) operation**
**Why?**
The **hash function** tells us where a **value is stored in memory**
We **don't have to iterate** over **the entire array**
109
What are the **names** for **hash maps** in various **programming languages**?
Exactly the **same things!**
110
How do we work with **hash maps** in Java?
Java **map interface**:
**generic map interface** declares **all methods** **map data structures** should **provide**
**HashMap** (**80% of time** used)
**ConcurrentHashMap** (multi-threaded applications)
111
How do we **refactor** this **if-statement** into a **ternary operator**?
112
Do **hash maps** allow **null keys** and **null values**?
**Yes**!
113
HT How do we **iterate** over **hash maps**?
114
What are the **hash table operation**s in **HashMap** class?
**.put ( )** pass key-value pair
**.remove ( )** pass key, removes key-value pair
**.get ( )** pass key, returns value
**.containsKey ( )** pass value to hash function, returns boolean
**.containsValue ( )** O(n) - iterate over all objects
**.keySet ( )** returns list of keys
**.entrySet ( )** returns list of key-value pairs
115
How do we implement **findFirstRepeatingChar ( )** in a hash map using a ternary operator?
**Popular Interview Question**:
Find first **non-repeated character** in a string
116
What is a **set**?
A **data structure** using a **hash function**
but only **storing keys**.
117
How can we **use a set** to **remove duplicates** in a **list**?
118
Why are **sets** useful in **solving** a lot of **problems**?
Don't allow duplicate keys
Ex.
remove duplicates
add each item to a set
unique list of items
119
What are **sets in Java**?
**Generic Interface**
**Implementing Class:**
**HashSet** (most often)
120
What are the **set operations**?
**.remove** pass key, removes key
**.removeAll** removes all keys in set
**.contains** pass key, returns boolean
**.clear**
121
How can we **findFirstRepeatedChar ( )** using a **set**?
Popular **set interview question!**
**O(1) operation**!
122
How does the **hash function work**?
It maps a **number (key)** to an **index in the array**
**Hash function maps** a **key**
to an **index value** in an **array**
we call this **index..**
**hash value**,
**hash code**,
**digest** or
just **hash**!
123
HT How does the **hash function** work?
Gets a **value** and matches it to **another value**
**Maps** a **key value** to an **index value**
124
Where are **hash functions** used?
In **cryptography**
125
How do we **map a key** to an index in **an array**?
Using the **modulus operator**
## Footnote
**hash % array.length = index**
126
How can a **string-hash map** to an **array index**?
**Numeric representation** of **characters** summed
**total number (hash)** % **array.size = index** in array
127
What is **special** about the **hashing function**?
**It's Deterministic**
every time we give it the **same input (key)**
it will return the **same value (object)**
**Store** and **Retrieve**
128
What is a **collision** in a hash map?
It's when the **hash function** generates the **same hash** (index location) to **store two separate values**!
129
Why do **collisions happen**?
It is possible that **two unique keys** generate the same **hash value**.
This is **called a collision**.
130
What is the first way to **handle a collision**?
**Chaining**
**Wrap** the **values** in a **LinkedList** node at each **index in an array**.
If there is a **collision,** store the value in the **next node** of the **LinkedLis**t.
131
What is **chaining** in **hash tables**?
Each **key-value** pair is **stored** in the **node** of a **LinkedList**
If there is a **collision**, the **second value** is added to the **next node** in the **LinkedList** at that **index**.
132
What are **buckets or slots**?
**Each index** in an **array** points to a **LinkedList**
133
What is the **second way** to **handle a collision**?
**Open addressing**
Finding an open **index** to store the **second value**
Various **algorithms for finding open indexes:**
**Linear Probing**
**Quadratic Probing**
**Double Hashing**
134
What is **probing**?
**Array index** **not determined** by the **hash function**.
**open addressing algorithms:**
**linear probing** - look in next index
**quadratic probing -** look in index squared
**double hashing -** two hash functions
135
What are the **equations** **linear, quadratic and double hashing** **probing algorithms**?
**Linear** - **i** **+** **1**
**Quadratic** - **i** **\*** **i**
**Double** - **i \* secondHash function**
136
What is **linear probing**?
going to **next index** to store a **collided value**
**If we cannot find a slot, the table is full, must resize array**
**Formula:**
**hash** (key) + **i % array.length**
137
What is a **cluster**?
**Dense groups of filled indexes**
Why?
**Linear probing** creates clusters by **storing values** in **next open index**
**Result?**
The next probe will **take longer!**
cluster will **get bigger!**
138
What is **quadratic probing**?
**Look** for next **open index** at position **index squared**
**Why?**
Solves the **clustering problem**
**But**
can **create an infinite loop**!
**Formula**:
**hash** (key) +**i^2 % array.length**
139
What is **double hashing**?
**Find the next open index by**
**Multiplying** i by a **second hash function** then **apply modulus operator** to find array index.
**Formula**:
**index** = [**hashOne**(key) + i \* **hashTwo** (key)] % **array.length**
140
How do we create a **hash table** from **scratch**?
**Interview Question**:
Create a **hash table** from **scratch**
use **chaining** (using LinkedLists)
Hint: create a class KeyValue with two fields (int, char)
141
How do we implement **hash ( )** method in our HashTable class?
142
How do we implement the Entry class in our HashTable class?
create a **private class inside Entry** the HashTable class
143
What is the final refactored implementation of the put method in our hash table?
144
How can we refactor our **put ( )** method in our **HashTable** class?
145
How can we **refactor** the **get ( )** method in our **HashTable** class?
146
How can we **refactor** the **remove ( )** method in our **HashTable** class?
Extract **getBucket ( )** and **getEntry ( ) helper** methods
147
HT How can we refactor this **if-statement** using the ternary operator?
148
**Why** shouldn't our **getBucket ( )** method **create** a **new bucket** if **no bucket** is **found**?
**Command-Query Separation:**
Software design principle
Methods/functions should either be **queries**, return answer
OR
or be **commands**, c**hange the state**
149
What is an interview question using Hash Tables?
150
What is another **interview questio**n for **Hash Tables**?
151
What is another interview question for Hash Tables?
152
HT What is another interview question for Hash Tables?
