WeekB Flashcards
What is a Datastructure?
A data organization, management and storage format that enables efficient access and modification through convenient operations
What are the different types of DataStructures?
Linear
Hierarchical
Types of Linear Data Structures
- Arrays
- Linked-List
- Stack
- Queues
Types of Hierarchical Data Structures
- Trees
- Graphs
- Heaps
What is a Linear Data Structure
The data items are arranged in an orderly manner where the elements are attached adjacently.
The data elements can be accessed in one time single run).
Simpler to implement, Single level, memory inefficient.
What is a Hierarchical Data Structure
It arranges the data in a sorted order and there exists a relationship between the data elements.
Traversing of data elements in one go is not possible.
Complex to implementation, Multiple levels, memory efficient.
What is an Array?
Basic Data Structure, often used in the implementation of other data structures.
Fixed number of elements, accessed by their index.
Homogenous (of the same data type), and sequential in memory.
What is a Linked List
A sequence of data structures called nodes in which one nodes reference points to the next.
The first node is called the head, the last is called the tail.
Linked List vs Arrays
Linked List are better at insertion and deletion than arrays.
One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements.
If you want to access a particular item then you have to start at the head and follow the references until you get to that item.
Another disadvantage is that a linked list uses more memory compared with an array - we extra 4 bytes (on 32-bit CPU) to store a reference to the next node.
What is a Stack?
A Linear data structure and a type of list that operations to the element follows LIFO (Last In First Out) aka operations only occur on the top element.
Like a stack of plates.
Removing the top element is called popping.
To obtain the value at the top but not removing it is called peaking.
Placing an object on the top is called pushing.
What is a Queue?
An interface within the Collections API.
it’s implementations operates under FIFO(First In First Out). Both ends are open for operations.
Methods: poll, remove, peek, and element
Adding elements is enqueuing (only to the backend)
Removing elements is dequeuing(only to the front end).
What is a Tree?
A very common heirarchical data structure, Much like an OS file system structure or an In memory representation of an HTML document.
Each element is represented by a node.
Root node is the first node
Parent nodes have references to child nodes.
Sibling nodes have the same parent
Leaf nodes are nodes that have no child
A branch is a complete line (path) from the leaf to the root
collection (lower case)
a collection of entities, or an aggregate Data Structure i.e. Arrays and Maps
Collection (uppercasae)
Interface within the Collection API
Collections (with an s)
Utility Class that has static, convenient methods that operate on Data Structures in the Collections API or return them.
Collections API
Iterable-I
|
Collection-I
/ | \
List-I Set-I Queues-I
| | | \
ArrayList HashSet Priority Queue Deque-I
| | | |
LinkedList TreeSet Array Q LinkedList
| |
Stack LinkedList
|
Vector
What is a List
Lists are an interface that have positional access i.e. indexing, allows duplicates, and is always sequentially ordered.
Real world example is like a train, each train car resembles a node, linked to the other.
What is an ArrayList?
Access via index(positional access):allows you to interact with the elements based on their position in the ArrayList * get, set, add, addAll, and remove.
A re-sizable array Implemented using arrays Increases size by 50% each time it needs to increase size Default size is 10 Can only hold objects
ArrayList vs LinkedList
Link list is only good if yours adding and removing a lot of elements
Array List is more efficient overall
What is a set?
an interface apart of Collections API
Does not allow duplicated objects
Does not in general guarantee insertion order
Sets are equal if they contain the same elements
Examples:
Hashset: Maintains no order, stores in hash table, best performance
treeset: Maintains value order (it will compare each value order and printout in order)
very slow performance
LinkedHashSet Maintains insertion order, weaker performance
What is a map?
A part of the aggregate data Structures //Consist of key, value pairs. //Each key has to be unique and can be only mapped to one value //A key can be mapped to a duplicate value
Maps are not iterable, but the set of their keys are iterable
HashMap vs TreeMap vs HashTable vs LinkedHashMap
•HashMap:
allows duplicate values, not duplicate keys
* allows a single null key and its allows multiple null value
* does not guarantee order
•TreeMap:
does not allow null key, but does allow null values
* Sorted according to the natural ordering of the keys
LinkedHashMap
it maintains insertion order
•HashTable: No null keys No null values Thread safe Deprecated
abstract class
special class that can’t be instantiated.
You need abstract class to set up a structure/feature.
Able to reuse.
every abstract class is going to contain atleast 1 abstract methods
can contain concrete methods. .
“contract based” - abstract methods MUST be overridden in subclass
abstract class syntex
public abstract class Animal {
//abstract method
public abstract void breathe(); }
interface
special type of class that can't be instantiated specify what a class must do but not how it does it lack instance variable * characterized by behavior * can mimic multiple inheritance w/ interfaces * classes can implements interface 0+ * interfaces can extend (inherit) other interfaces 0+ * All variable are implicitly static, public, and final (java8)
abstract parent with abstract child syntex
Animal Parent, Fish Child
public abstract class Fish extends Animal{
public abstract void swim(); }
interface syntax
public interface Hunt {
void findPrey();
}abstract parent, abstract child, interface syntax
public class Shark extends Fish implements Hunt {
@Override
public void swim() {
System.out.println("I'm swimming underwater and I'm terrifying");
}
@Override
public void breathe() {
System.out.println("I breathe underwater, meeeeeegh");
}
@Override
public void findPrey() {
System.out.println("I ate fishes!");
}
}
constructor method syntax (Driver)
public class Driver {
public static void main(String[] args) {
Shark shark= new Shark();
shark.breathe();
shark.findPrey();
shark.swim();
} }
Stream
Abstraction that either produces or consumes info.
Types
Character Stream
Byte Stream
Character Stream
Human readable
FileReader and FileWriter
Byte Stream
Machine readable, byte code, binary data
FileInputStream and FileOutputStream
For serializing (Serializable marker interface aka “tag”)
Serializing
converting a Serializable Java object to a byte stream.
ObjectInputStream - for serializing
ObjectOutputStream - for serializing
Serialized ID
Transient
keyword that marks a variable that will not be serialized
If there’s a field we don’t want to make Serializable, give it the transient modifier
Reflection
is a way for Java to inspect itself at runtime
* break encapsulation * contains methods for runtime inspection of objects * -Class of objects * -Fields * -methods * -Constructors * This can include private members * can modify and instantiate, call methods etc * java.land.reflect
Test-Driven Development (TDD)
Working requirement-by-requirement
Designing tests to match those requirements
Writing methods that will cause those tests to pass
Automated Testing
For continuous integration (DevOps stuff) Types Service UI Unit Testing
What is a Heap?
A specialized tree structures, Binary tree
Binary tree structure is each node has 2 children at most.
Max heap is where the root node is the max value.
Min heap is where the root node is the min value.
There is a HeapSort algorithm.
How does Binary Search work?
Looks at the middle indice of the collection and then determine if the value you are looking for is greater than or less than that value, then
move to either half depending on that result. Can only be preformed on ordered data structures
What is Generics?
A type of polymorphism, parametric polymorphism(compile time)
Looks like ArrayListx;
x.add(5);
Generics provides type safety i.e. it makes type errors occur at compile time rather than failing at runtime.
Can have place holders for any type of value
Standard conventions for placeholder values are KENTV
•K for Key
•E for element
•N for number
•T for Type
•V for Value
Generics is the ability to parameterize the types declared within the class that makes the class flexible.
What is Covariance
AKA subtyping, a type of polymorphism(runtime). The ability to declare a variable as the parents type while assigning or instantiating that variable to its child type. Such as List xlist = new ArrayList(); Or Animal mon = new Monkey();
What is an Exception?
It is an event that occurs during the execution of a program that disrupts the normal flow of the applications logic.
What is an Error?
Unlike exceptions, errors are unrecoverable faults/events outside of the programs logic that halts the applicaction.
Common Errors:
StackOverflow, OutOfMemory
What is a Checked Exception?
Are fault scenarios that the Java compiler forces you to handle.
Examples:
IOException, FileNotFoundException, SQLException, ClassNotFoundException
What is an Unchecked Exception?
Are exceptions not checked at compile time, and are not forced to be handled by the compiler.
It is common behavior in logic that can arise exceptions when executed.
Examples:
Arithmetic, NullPointer, ArrayIndexOutOfBounds
throw vs throws vs Throwable
throw - How to manually trigger an Exception. throws - added to the method declaration to "Duck" the responsablitiy of handling a specific exception in that method Throwable- The root class in the exception class Heirarchy
What combinations of try, catch, finally
blocks can happen?
- try{//risky logic}catch(Exception e){//recovery logic}
- try{//risky logic}catch(Exception e){//recovery logic}finally{//logging and clean up logic}
- try{//risky logic}finally{//logging and clean up logic}
What is maven?
it is a build tool and dependancy manager. Each project contains a file called a POM (Project Object Model), which is just an XML file
containing details of the project. Some of these details might include project name, version, package type, dependencies, Maven plugins,
etc.
Comparator vs Comparable
Comparable interface is used to sort the objects with natural ordering. Comparator in Java is used to sort attributes of different objects. Comparable interface compares “this” reference with the object specified. Comparator in Java compares two different class objects provided.
What do the Serializable interface do?
It allows an object to be changed in to a form that allows it to be transfered over a ByteStream or network.
Iterator
- Anything that can be used as the subject of an for each loop uses an iterator
- AKA they implement the Iterable interface
- every collection has an iterator that allows traversal between elements and
- allows sage removal of elements in place
What are some of the annotations used in JUnit
@BeforeClass @AfterClass @Before @After @Test
What is JUnit?
JUnit is a test framework which uses annotations to identify methods that specify a test.
Benefits of unit testing
Unit testing increases confidence in changing/ maintaining code. If good unit tests are written and if they are run every time any code is
changed, we will be able to promptly catch any defects introduced due to the change.
Codes are more reusable. In order to make unit testing possible, codes need to be modular. This means that codes are easier to reuse.
The cost of fixing a defect detected during unit testing is lesser in comparison to that of defects detected at higher levels.
Debugging is easy. When a test fails, only the latest changes need to be debugged.
Codes are more reliable.
What is Unit testing?
is a level of software testing where individual units/ components of a software are tested.
A unit is the smallest testable part of any software. It usually has one or a few inputs and usually a single output.
The purpose is to validate that each unit of the software performs as designed.
What is a Thread?
A process or a line of logic
What is a Subprocess
A child process of the main parent thread’s logic
What is Multi-threading?
concurrently running processies
What are the different types of interfaces?
•Marker - It is an empty interface (no field or methods). Examples of marker interface are Serializable, Clonnable and Remote interface. They
provide run-time type information about objects.
•Functional - It is an interface that contains only a single abstract (unimplemented) method. A functional interface can contain default and
static methods which do have an implementation, in addition to the single unimplemented method.
What is an algorithm
a process or set of steps to solving a problem
What is a Vector?
Vectors are similar to ArrayLists in which they can be accessed by get
and set methods and size dynamically. The only major differences is
Vectors are thread-safe as opposed to ArrayLists. Which are not.
Addittionally while an ArrayList increases its size by 50% each time it
needs to. A Vector increases its size by 100%
map methods
/*methods
* Basic Operations: * put,get, remove containsKey, containsValues, size and empty * Bulk Operations: * putAll, clear * Collection Views: * keySet, entrySet and values.
Priority queue
will print in alpha order
poll, remove, peek, and element
poll: returns and removes the element at the head of the container, returns null if empty.
remove: will also return the value at the head of the queue and removes it, but will throw an exception if empty
peek: allows you to see the head and return null
element() method of Queue Interface returns the element at the front the container. It does not deletes the element in the container. This method returns the head of the queue. will throw an exception if empty
Collection Framework
List, Set, Queue All interfaces in the Collection
WHy?
Array object within Java is limited. Mainly that the array is immutable and you’re given not many methods to work with.
Called a framework (more library), provides interface and classes that allow developers to more easily manage a group of objects.
* Advantages:
* Reduces effort (provides datastructure and algorithms for you)
* Increase performance
* Encourages software reuse
*
* BUT!
* convert primitive values into object
* ints -> Integer
* boolean -> Boolean
* byte ->Byte
*
The process of converting a primitive data types into its wrapper class is called boxing
What is a Deque?
A interface apart of the Collections API that extends from Queue and is a double ended Queue that can add and remove from both ends, FIFO and LIFO
