Linear Data Structures Flashcards
What is Big O notation?
Big O is a mathematical notation that describes the limiting behavior of a function where the argument tends toward a particular value or infinity.
What is Big-O?
Helps us determine if an algorithm is scale-able or not
When do we use Big O notation?
Describe the performance of an algorithm
What are the five common Big-O curves?
O( 1 ) - constant time
O ( n ) - linear time
What are the five common time complexity curves?
How does linear big - O grow?
Linearly and in direct proportion to the size of the input
What is O(n^2)?
Quadratic.
Nested loops
How does the logarithmic curve behave?
It slows down as the input size grows
What is exponential time complexity?
The exponential curve grows faster as the input grows.
What is the shortcut to run JVM in debug?
Control + D
When would we have a quadratic Big-O value?
When we use nested loops that each performs an iteration over the entire set of values.
What are the linear data structures?
- Arrays
- Linked Lists
- Stacks
- Queues
- Hash Tables
What are arrays?
Reference type
fixed-length data structure.
Values are indexed sequentially in memory.
Optimal for looking up values by their index.
What can we use arrays for?
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.
What are the pro’s of arrays?
Looking up the index is very fast
why?
item index lookup doesn’t involve loops or complex data access operations.
What are the disadvantages of arrays?
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).
How do we keep track of the number of items in our array?
Using a private variable “count”
increment count for each new item
How do we implement resizeIfRequire ( ) in our addItem method of our array class?
Create a new array x 2 size
copy items into new array
O ( n ) operation!
How do we implement the removeAt ( ) method in our array class?
Shift items left
Copy items from [index + 1] into [index]
How can we implement the print ( ) method in our custom array class?
Use a for loop to iterate over each index
+ print on console
How can we implement the max ( ) method in our Array class?
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).
How to implement the insertAt ( ) method in our Array class?
How to implement the reverse ( ) method in our Array class?
How to implement the intersect ( ) method in our Array class?
Foreach loop + nested if loop
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
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!
What is the Big O of find by value in an array?
O ( n )
Worst case have to iterate the entire array!
What is the Big-O of lookup by index in an array?
O(1)
why?
What is the syntax for working with Arrays in Java?
Two ways :
Create with an empty array
Insert values, omit the new operator
What is the Array’s class in Java?
Declared in Java.util
Static methods to perform operations on Arrays
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
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
AA What are circular arrays?
Very important, powerful concept in data structures
What is covered in the linked-list collection?
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.
When do we use linked-lists?
In building more complex data structures
they are the second most common after Arrays
What are the key differences 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
How do you work with a linked-list in java?
java.util.LinkedList package
can access pre-built methods
.insert ( )
.delete ( )
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
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
What are the operations on Linked Lists?
AddLast ( )
AddFirst ( )
IndexOf ( )
Contains ( )
RemoveFirst
RemoveLast
Reversing LinkedList
kth-node from end
LL What are the run time complexities of the insert ( ) method on linked - lists?
What is the Big-O time 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
What is the run-time complexity of the various linked operations?
Lookup
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)
How do we implement the private Node class in our LinkedList class in Java?
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.
How do we implement the addFirst method?
O(1) operation
Create a node, set node.next to first
How do we implement the removeFirst method in our LinkedList class?
O(1) operation
update the second item as the first item
How do we implement the removeLast ( ) method in our LinkedList class?
O (n) operation
getPrevious ()
iterates the entire list
How do we implement the IsEmpty( ) method in a clean modern way?
Extract into a private method and call that method
How do we implement the indexOf (int item) method in our LinkedList class?
O(n) operation
traverses entire list search for item (worst case)
How do we implement the contains ( ) method in our LinkedList class?
O(n) operation
indexOf ( ) method
Searches entire list worst case
How do we implement the getPrevious ( ) method in our LinkedList class?
O(n) operation
search entire list for node worst case
How do we implement the toArray ( ) method in our LinkedList?
O (n) operation
copy every node in the list into an array
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
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
LL How do we implement printMiddle ( ) in our Linked List class?
Find relationships between pointers
Nodes increases by 2 as middle increases by one
How do we implement hasLoop ( ) method in our Linked List class?
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
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.
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
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.
What is wrong with how data structure books teach implementation of isBalance ( ) using a stack?
It’s really ugly!
refactor using private helper methods and arraylists
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.
How do we implement the push() method using an array in our stack class?
How do we implement the pop () method using an array in our Stack class?
How can we implement the peek () method in our stack class?
How do we implement the isEmpty ( ) using an array in our Stack class?
How do we implement two stacks using one array to support push ( ), pop ( ), isEmpty ( ) , isFull ( ) on both stacks?
S How do we implement a MinStack using two stacks?
What are the various run-time complexities for operations on queues?
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
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
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
How do we implement the reverse( ) method on a queue using a stack?
Popular Interview Question:
Reverse a queue
What is the algorithm for implementing dequeue ( ) using an array?
O (1) operation!
How do we implement enqueue() using an array?
How do we implement the dequeue() method using an array?
create a variable front.
change item in front to 0
increase front++
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 increase array capacity using an equation
What is the circular array implementation of dequeue() method?
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
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)
Q What is a popular queue interview question involving stacks?
Create a queue using stacks
Q How do we implement enqueue ( ) and dequeue ( ) using circular array indexing?
What is the implementation of the dequeue ( ) method using two stacks?
How can we refactor our code?
Extract the method
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!
What is the algorithm for sorting items in a priority queue using an array?
Sorting algorithm
How do we implement the enqueue() method in our priority queue using an array?
Sort based on values then insert at index
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
What is an interview question?
removeFirst ( )
addLast ( )
Q What’s an interview question?
Q What is an interview question?
How do hash tables work?
Internally, uses an array to store values
Items stored as key-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
What are the names for hash maps in various programming languages?
Exactly the same things!
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)
How do we refactor this if-statement into a ternary operator?
HT How do we iterate over hash maps?
What are the hash table operations 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
How do we implement findFirstRepeatingChar ( ) in a hash map using a ternary operator?
Popular Interview Question:
Find first non-repeated character in a string
What is a set?
A data structure using a hash function
but only storing keys.
How can we use a set to remove duplicates in a list?
What are sets in Java?
Generic Interface
Implementing Class:
HashSet (most often)
How can we findFirstRepeatedChar ( ) using a set?
Popular set interview question!
O(1) operation!
HT How does the hash function work?
Gets a value and matches it to another value
Maps a key value to an index value
How do we map a key to an index in an array?
Using the modulus operator
hash % array.length = index
How can a string-hash map to an array index?
Numeric representation of characters summed
total number (hash) % array.size = index in array
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!
Why do collisions happen?
It is possible that two unique keys generate the same hash value.
This is called a collision.
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 LinkedList.
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.
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
What are the equations linear, quadratic and double hashing probing algorithms?
Linear - i + 1
Quadratic - i * i
Double - i * secondHash function
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
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!
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
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
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)
How do we implement hash ( ) method in our HashTable class?
How do we implement the Entry class in our HashTable class?
create a private class inside Entry the HashTable class
What is the final refactored implementation of the put method in our hash table?
How can we refactor our put ( ) method in our HashTable class?
How can we refactor the get ( ) method in our HashTable class?
How can we refactor the remove ( ) method in our HashTable class?
Extract getBucket ( ) and getEntry ( ) helper methods
HT How can we refactor this if-statement using the ternary operator?
What is an interview question using Hash Tables?
What is another interview question for Hash Tables?
What is another interview question for Hash Tables?
HT What is another interview question for Hash Tables?
