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.
What are stacks?
A wrapper around Arrays or LinkedLists
Allows special data access (LIFO)
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
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)
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.
S What is the internal implementation of stacks?
Internally, data and objects are stored in a LinkedList or an Array
Stacks are a special data access wrapper (LIFO)
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.
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)
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 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
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).
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
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
What are the three ways to implement the queue data structure?
Array, LinkedList, Stack
Popular Interview Question:
implementations queue using Array, Stack or LinkedList
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 an application of priorty queues?
OS system uses PriorityQueue to schedule tasks (highest priority task first)
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?
What are hash tables?
Data structures
superfast lookup and many applications.
Come up in interviews often!
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!
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 hash table operations?
.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
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?
Do hash maps allow null keys and null values?
Yes!
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?
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
What are sets in Java?
Generic Interface
Implementing Class:
HashSet (most often)
What are the set operations?
.remove pass key, removes key
.removeAll removes all keys in set
.contains pass key, returns boolean
.clear
How can we findFirstRepeatedChar ( ) using a set?
Popular set interview question!
O(1) operation!
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!
HT How does the hash function work?
Gets a value and matches it to another value
Maps a key value to an index value
Where are hash functions used?
In cryptography
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 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
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 are buckets or slots?
Each index in an array points to a LinkedList
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
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?
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, change the state
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?
