Time Complexity of ArrayList Insertion
Then calculate the average time complexity of inserting n new items into an empty brand new ArrayList.
Problem Statement
Explain how an ArrayList works in Java. Then calculate the average time complexity of inserting n new items into an empty brand new ArrayList.
Evaluation
- The explanation of how an ArrayList allocates memory (25%)
- The expanded mathematical calculation of the cost of insertion over time (25%)
- Mathematical and order notation simplification (25%)
- Correctness of the final O notation and the grand conclusion (25%)
References
Vlad, a software architect at Lionside, a Bay Area gaming startup, asked me this during an interview
Recommended reading
-
Return true if input is a Prime number
You are given n, a positive integer. Return true if n is a prime number, and false if it's not.
-
Find the middle node of a Linked List
Given a Singly Linked List, write an algorithm to find the middle node. You may not use more than one loop of any kind.
-
Graph Cycle Detection
You have a directed connected graph. Write an algorithm that detects any cycle, if one exists, and returns a list of its nodes.
-
Is the given String a repeated sub-pattern?
Given a string, return whether it is made of a perfectly repeated string pattern.
- Author
- Amin Ariana
- Published
- September 2010