Interview-prep

Best source -> https://github.com/bsikander/getting-a-gig

Linked List:

Data structure to hold data of any type and size

Advantages:
1- Access is O(n)
2- Insertion in O(1).

Insertion consists of two functions Find + insert. Insert is always O(1) but find always makes the difference. If we have the pointer then find is O(1) otherwise find will be O(n) which makes the overall time of insert to be O(n). <– Good implementations will always keep the pointer to the last node

Disadvantages
1- Memory waste for extra pointers
2- Can navigate in single direction

Operations
1- Insertion
2- Deletion
3- Traversing

Double LinkedList:

Advantages:

1- Can navigate in both directions

2-

Disadvantages:

1- Each node requires an extra pointer

2- Take a little bit of more time because of extra pointer assignment operations

 

Concepts:

Constant Time: “Constant time” has the same meaning as “O(1)”, which doesn’t mean that an algorithm runs in a fixed amount of time, it just means that it isn’t proportional to the length/size/magnitude of the input. i.e., for any input, it can be computed in the same amount of time (even if that amount of time is really long).

Linear + Constant Time description

 

How to Solve a problem:

1- Solve on paper
2- Write unit test
3- Handle corner cases