Java - data structures

Question 1

primitive data types

Answer 1

data types from which more advanced data structures are made: include ints, doubles, longs, floats, shorts, booleans, and chars

Question 2

Int

Answer 2

whole number (32 bits) - most commonly used

Question 3

Float

Answer 3

decimal (32 bits)

Question 4

Short

Answer 4

whole number (16 bits)

Question 5

Long

Answer 5

whole number (64 bits)

Question 6

Double

Answer 6

decimal (32 bits) - most commonly used

Question 7

reference types

Answer 7

more complex data types

Question 8

String

Answer 8

sequence of chars

Question 9

array

Answer 9

a list that has both an index (number in the list) and data for what’s at that index

Question 10

multidimensional array

Answer 10

an array of arrays – the data at the first index has an array, so the index therefore has two points (0,0). 0 for the first slot in the array, and then the next 0 represents the slot in the array for that data

Question 11

jagged array

Answer 11

a multidimensional array where the number of columns is not fixed. some index positions might have an array of 5, the next an array of 20, the next just 1

Question 12

resizable array

Answer 12

an array whose length you can change as needed

Question 13

how do you search an array

Answer 13

for loop

Question 14

Big O Notation

Answer 14

Describe the performance or complexity of an algorithm

Question 15

O(1) time

Answer 15

consistent duration of algorithm execution in same time (or space) regardless of the size of the input. Also called constant time.

Question 16

O(n) time

Answer 16

if the size of the input increases, the computation time directly increases in proportion to the input’s increase. Sample tasks would be for loops that have to look through everything.

Question 17

common operations you might do with lists

Answer 17

access, update, insert, search, and delete

Question 18

linked list

Answer 18

Like an array, but not necessarily contiguous. Uses pointers to refer to other list items. Doesn’t have to use contiguous locations in memory but can link to any memory slot. Just need a memory address, or rather the next pointer. You just indicate what is next and use that to sort your list.

Question 19

Array class in Java

Answer 19

ArrayList class

Question 20

Linked list class in Java

Answer 20

LinkedList class

Question 21

Stack

Answer 21

An ordered series of objects. You can only add or remove items from the top. You push objects onto a stack and pop objects off of it. Think of a stack of pancakes. You remove from the top. You add a pancake by placing it on top of the stack. Stacks follow a last in, first out (LIFO) policy. The first item pushed onto the stack will be the last item popped off.

Question 22

Pop

Answer 22

Removing an item is called popping the item off. To get an item further down the stack, you have to pop off the upper items.

Question 23

When to use stacks

Answer 23

great for reversing actions. also for keeping track of state.

Question 24

Queue

Answer 24

A list with front and back. Designed to have a front and back. Queues follow a first in, first out policy (FIFO)

Question 25

Enque

Answer 25

the process of adding an item to the queue.

Question 26

Dequeue

Answer 26

the process of removing an item from the queue

Question 27

What are queues good for

Answer 27

Queues are good for storing the order of things that need to happen. often used to share system resources. For example, everyone sending a job to the printer. They keep track of waiting which tasks need to be performed.

Question 28

Shift

Answer 28

moves all elements down by one

Question 29

LIFO

Answer 29

last in, first out (refers to stacks)

Question 30

FIFO

Answer 30

first in, first out (refers to queues)

Question 31

difference between stacks and queues

Answer 31

In one word, the difference between Stack and Queue comes in how they consume elements, In Stack, we remove the most recently added element, while in Queue we remove least recently added element.

Question 32

Poll

Answer 32

removing the top element (first item) in a queue

Question 33

Priority queue

Answer 33

Items with higher priority can be moved to the top of the list.

Question 34

DEQUEK

Answer 34

items can be removed from either end of the queue. But you can’t do anything with items in the middle

Question 35

Peek

Answer 35

see what's at the top of the list

Question 36

are stacks and queues good data structures for pulling information from the middle of the list?

Answer 36

no, if you’re pulling lots of items from the middle of the queue, then they are not the right data structure.

Question 37

associative array

Answer 37

a collection of key-value pairs. example, Sacramento: California. Each key-value pair always stays together. The keys must always be unique in associative arrays.

Question 38

Dictionaries

Answer 38

Python term for hashes. A dictionary is a key-value pair. Internally, this is stored as an array with a hash function on the keys.

Question 39

Hashing

Answer 39

taking raw data and taking it together to create some simplified form. Like making hashbrowns. Different ingredients combined to form some final. The raw data goes through a hashing function (cooking) to arrive at the final value. Basically, you start with some text, and the hash algorithm creates some scrambled form of that original.

Question 40

differences between hashing and encryption

Answer 40

Hash functions are not reversible. One way. You can’t feed the function into some reverse algorithm to get the original values. Just like you can’t get the original ingredients to the hash browns. encryption, on the other hand, is reversible

Question 41

Collision

Answer 41

when two keys have same hash value.

Question 42

Purpose of hashing

Answer 42

let you store a value at a certain location in a secure way.

Question 43

Hash table

Answer 43

A hash table is a way to implement an associative array. A “bucket” is each place for a key-value pair to be stored in the hash table. Key will go through hash function, and then an integer will pop out.

Question 44

hashCode

Answer 44

hashes the value you pass it

Question 45

Set

Answer 45

A collection of unique items. Order doesn’t matter, but none of the elements are duplicated. Grouped with a common property. No key, no index to look up value. You only care about the set as a whole. You’re testing to see if the test has a given number, character, or string.

Question 46

Tree data structure

Answer 46

Unlike with linked lists that just have links to next items, the tree data structure can link to multiple different nodes. In a tree structure, there’s a root node. You can have parent and child nodes down the tree. A node can be a parent and child at the same time. Child nodes with the same parent are siblings.

Question 47

Binary tree

Answer 47

A special type of tree. Each node has two child nodes (left and right nodes). The left child node and right child node could be null, both have values. BST = Binary Search Tree. In the BST, you keep track of order to keep track of left, right, etc. this data structure naturally stays sorted. Binary search trees often store key-value pairs. If you get a match, you remove any need to keep going down the tree. A recursive data structure where each node can have 2 children at most. a common type of binary tree is a binary search tree, in which every node has a value that is greater than or equal to the node values in the left sub-tree, and less than or equal to the node values in the right sub-tree The basic idea is that by sorting the values, when you want to retrieve a particular value, it’s a lot easier to do so because you can eliminate whole branches of the tree.

Question 48

TreeMap

Answer 48

Java class for binary trees

Question 49

Heap

Answer 49

two meanings. area of memory where you allocate objects. in reference to data structures, a heap is a data structure implemented as a binary tree. A heap is a collection of objects. As you add items to the heap, they are always added top to bottom, left to right. We care about min and max values. The heap swap nodes to keep itself organized. Nodes get swapped around so that the parent nodes are smaller than child nodes. Every child must be less than its parent, so you always bubble up the larger values to the top. The max value will always be on top. Order doesn’t matter. Instead, it’s more like a size sorting. Used for priority queues and certain sorting algorithms.

Question 50

when to use a binary tree

Answer 50

One reason to use trees might be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer: