Google Interview Question
Software Engineer / DevelopersCountry: United States
If you cannot use a simple array like
String[] or Object[] or E[]
then the question would be more like create an array implementation on the JVM an not in JAVA.
In Java there is a class called Arrays, which is a utility class to deal with regular arrays ( sorting, copying, etc etc etc)
The only thing you can do ( as far as I can think ) is to implement any Data Structure such as Vector, ArrayList, Stack, Queue even a tree using a regular array ( Object[] )
Another thing to point out is that, in java we cannot extends from Object[] even if arrays are treat like Objects. This is not allow. so that is not the way to go.
The last resource we have instead would be using native methods and try to implement something in C on a DDL or something. But I am running out of ideas.
Anybody?
Maybe you should implement linked list based on something like that:
class Node {
Node prev;
Node next;
Object value;
I think the interviewer wanted you to understand that an array must be contiguous and not a linked list. That is, you must have capacity, which is the amount of memory allocated, and size, which is the actual size of the array. So, when the user resizes the array with size > capacity, you must reallocate memory and copy the values from the old to the new array.
- Dídac Pérez December 08, 2013