Data Structures and Algorythms Flashcards
What is a datascructure?
Something that organises and stores data. Like Arrays.
They differ in the way that they organize and store data. Trees for example are abstract with hierarchy with parents and children where array is a sequential slot based array.
What is an algorithm and how is it different from an implementation?
It describes steps that should be followed to perform a repeatable task. Like a recipe.
An implementation is the actual code you write to perform the algorithm.
Why do we use BigO notation and what else is it called?
It has to do with the running time of algorithms. Because of things like hardware and other non constant things, you cant just time an algorithms’ performance. You need something to express its complexity and performance. BigO is the time complexity.
Remember that for BigO we always use the worst case. Sometimes if you are lucky an algorythm is solved quickly, but that is not always the case you must plan for worst case.
There is time complexity and memory complexity. These days memory complexity is not important because memory is cheap. Time complexity is important.
Time Complexity tells us how well an algorithm will scale. How will time increase as input repeats?
How is BigO calculated for the tea recipe? There are two steps that are constant and two that are repeated every time you add more sugar.
- Number of desired sugars = n
- Total number of steps = 2n+2
- As n grows the number of steps grows.
- The 2 in 2n and the +2 remain constant so they don’t factor into the time complexity. The value of n determines the growth rate.
- Time complexity is O(n)
- Linear time complexity.
How is BigO calculated for the tea recipe? There are two steps that are constant and two that are repeated every time you add more sugar.
- Number of desired sugars = n
- Total number of steps = 2n+2
- As n grows the number of steps grows.
- The 2 in 2n and the +2 remain constant so they don’t factor into the time complexity. The value of n determines the growth rate.
- Time complexity is O(n)
- Linear time complexity.
What are the different time complexities? and describe what they look like on a graph?
O(1) - Constant
O(Logn) - Logmaritmic - Log base 2 not log base 10…
O(n) - Linear
O(nlogn) - n Log-start n
O(n^2) - Quadratic
Linear is a constant increase. As input increases there is a linear increase.
https://en.wikipedia.org/wiki/Big_O_notation#/media/File:Comparison_computational_complexity.svg
What is important for the Amazon interview process?
* Knowing the combination of BigO and data structures.
* Arrays, HashTables, LinkedList and Graphs (Some people ask graphs).
* Sorting algorithms, not really…
* Knowing that quick-sort and the other’s BigO notation. Knowing the tradeoffs is more important.
* No one will ask you to implement a sort…
* LRU cache with 50 elements. Evict the old element. You need two data structures to make it work. you need the hash-table and something to take care of the oldest like an array, heap or linkList
What are the key attributes of an array and define an Array in Java
Arrays are heterogenous.
Arrays have a constant length.
Arrays need to be initialized with a length
The indexes are 0 based.
String[] myArray = new String[100];
myArray = [“test”,”best”,”west”]
How do you loop through an Array?
for(int x = 0; x < myArray.length, x++){
System.out.println(myArray[i]);
}
How are Arrays stored in memory? Take into account strings, objects and ints for example.
They are stored as one continuous block. Which means they arent scattered around in memory. All the elements are grouped together.
So if an array starts at a specific memory address and it is 100 bytes long it will take the following number of bytes required.
This is why you need to allocated the size when initializing. The JVM needs to know how much memory to allocated to the array.
If you could resize an Array it would mean that not work.
Every value in the array occupies the same size in memory.
What if I create an array of objects? Like a string array with different lengths? Its important to remember that only references to objects are stored in an array. Its not a primitive type. Sop you are storing a reference to the string instances.
All of this is why its easy to find a specific element based on the index.
When and why are arrays efficient data structures?
When you know the index of the value you want to retrieve.
They also dont store additional metadata in memory. Some of the other datastructures require this.
How do you find the memory address for the element you are looking for in an Array? Assume were using and int array that starts at address 12.
1) Multiply the size of the element by its index.
2) Get the start address of the array.
3) Add the start address to the result of the multiplication.
So for an int array, assume element starts at address 12. Each int is 4 bytes.
To get intArray[0] = 12+0*4 = 12
intArray[3] = 12+3*4=24.
What and why is the time complexity of an array access?
So for every element in the array it takes 3 steps. Does not matter how many elements, its always 3 steps.
This means its O(1). The number of steps is constant time complexity. The algorythm is always the same. Its the best time. This is one of the advantages of arrays.
Because it takes constant steps to access an item of an array via its index, or add/remove an item at the end of an array, the complexity for accessing, pushing or popping a value in an array is O(1). Whereas, linearly searching through an array via its index, as seen before, has a complexity of O(n).
What are some of the disadvantages of using an array?
When we dont know what the index is we need to iterate through all of the indexes until we find it.
Worst case we need to loop through the whole array. In this case we need do loop through the whole array. This looks like linear time complexity.
O(n).
If we know the index its O(1) if we dont know it its O(n)
What are the time complexities of the different operation on an array?
* Retrieve with an Index
* Retrieve without index
* Adding an element to a full array
* Add an element to the end of an array that has space
* Insert or updated an element at a specific index
* Delete an element by setting it to null or something else
* Delete and element by shifting it
Retrieve with an Index - O(1) - Constant time because it always takes the same three steps to calculate the address.
Retrieve without index - O(n) - Linear - They are the same steps, but the number of times you need to do the calculation changes depending on the length.. so it takes longer for each element.
Adding an element to a full array - O(n) - Linear - A full array means you need to create a new array. The steps to create the array are simple, but depending on the array you will need to loop and assign the new values to each index in the new array.
Add an element to the end of an array that has space. O(1) - the steps dont depend on the number of elements.
Insert or updated an element at a specific index O(1).
Delete an element by setting it to null or something else. Assuming we know the index. O(1).
Delete and element by shifting it - O(n) - because we want to shift all the elements down. This means you shift everything behind the one you want down.
Essentially - if you loop you need to do linear.
Explain the theory of a bubble sort for the following array of length 7.
- Bubble Sort is commonly used but not great as it degrades with the length of an array.
- Its called a Bubble Sort because the values bubble up or down. There are variations where the array is sorted from left to right etc..
- Pretty common with sorting algorythms is that it creates sorted or unsorted partitions. Its a logical partition. With bubble sort we dont have a new array, we partition it logically.
- So you create a field with unsorted partition index. When you start the unsorted index is the last index of the array.
- So you start at comparing the element at index 0 with the element at index 1. If the value is smaller you dont swap it. then you increment your counter to the next index.
- Compare the element at the next position with the and swapt if you needed.
- Repeat this pattern untill you reach the last index.
- Basically this allows you to move the largest value to the end of the array so you are finished sorting the last index in the array.
- Decrease the index value for sorted position.
- Start over untill you have got to the completed sorting
What is the time complexity of a Bubble Sort algorythm?
- It is an in-place algorithm - we are using the array in place instead of creating a new algorythm. In terms of memory we call something in-place if you dont need to increase the memory as the length increases as the number if items increases.
- This is O(n2) algorthm - it wil take 100 steps to sort 10 items, 10000 to sort 100 etc. It degrades quickly.
*
