JetBrains Academy: Dynamic array in Java

Simple list:

There is a linear list. The following commands are given:

add value – add an element with the value ‘value’ at the end of the list;
remove – remove the last element;
size – return the number of elements in the array.

Input: In the first line N is the total number of commands. 0 ≤ N ≤ 100. In the following N are aforementioned commands. -1000 ≤ value ≤ 1000. It is guaranteed that remove command will not be called for an empty array.

Output: for each size command on new lines print the answer.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) {
        final int lines;
        String commandLine;

        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            lines = Integer.parseInt(reader.readLine());
            DynamicArray<String> array = new DynamicArray<>();

            for (int i = 0; i < lines; i++) {
                commandLine = reader.readLine();
                InputUtils.run(commandLine, array);
            }


        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static class InputUtils {
        private static Command analyze(String command) {
            if ("add".equals(command)) {
                return Command.ADD;
            } else if ("remove".equals(command)) {
                return Command.REMOVE;
            } else if ("size".equals(command)) {
                return Command.SIZE;
            } else {
                throw new AssertionError("Unsupported operation: " + command + ", provide: put / get / remove");
            }
        }

        public static <T> void run(String inputLine, DynamicArray<T> array) {
            String[] entry = inputLine.split("\\s+");
            String command = entry[0];
            T value = (T) (entry.length > 1 ? entry[1] : "");

            Command cmd = analyze(command);
            cmd.apply(value, array);
        }
    }

    private enum Command {
        ADD {
            @Override
            public <T> void apply(T value, DynamicArray<T> array) {
                array.add(value);
            }
        }, REMOVE {
            @Override
            public <T> void apply(T value, DynamicArray<T> array) {
                array.remove();
            }
        }, SIZE {
            @Override
            public <T> void apply(T value, DynamicArray<T> array) {
                System.out.println(array.size());
            }
        };

        public abstract <T> void apply(T value, DynamicArray<T> array);
    }

    public static class DynamicArray<E> {
        private Object[] arr;
        private int arraySize;

        private static final int DEFAULT_CAPACITY = 10;
        private static final double SCALING_FACTOR = 1.5;

        public DynamicArray() {
            this.arr = new Object[DEFAULT_CAPACITY];
            this.arraySize = 0;
        }

        private void ensureCapacity() {
            if (arr.length == arraySize) {
                arr = Arrays.copyOf(arr, (int) (arr.length * SCALING_FACTOR));
            }
        }

        public void add(E value) {
            ensureCapacity();
            arr[arraySize++] = value;
        }

        public void remove() {
            arr[--arraySize] = null;
        }

        public int size() {
            return arraySize;
        }
    }
}

Advanced list:

There is a linear list. The following commands are given:

add value – add an element with value ‘value’ at the end of the list;
remove idx – remove the element with index ‘idx’;
size – return the number of elements in the array;
isempty – determine whether the list is empty or not. Print «true» or «false»;
contains value – determine if there is at least one element with value ‘value’ in the array. Print «true» or «false»;
indexof value – print the index of the first instance of an element with value ‘value’, '-1' otherwise;
clear – clear the array.

Input: In the first line N is the total number of commands. 0 ≤ N ≤ 100. In the following N are the aforementioned commands. -1000 ≤ value ≤ 1000. It is guaranteed that remove command will not be called for a non-existing index.

Output: For each command size, isempty, contains and indexof print the answer on a separate line.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) {
        final int lines;
        String commandLine;

        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            lines = Integer.parseInt(reader.readLine());
            DynamicArray<Integer> array = new DynamicArray<>();

            for (int i = 0; i < lines; i++) {
                commandLine = reader.readLine();
                InputUtils.run(commandLine, array);
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    
    private static class InputUtils {
        /**
        * Method analyzes input line provided by the user.
        * 
        * @param command - String provided by user
        * @return enum for command
        */
        private static Command analyze(String command) {
            if ("add".equals(command)) {
                return Command.ADD;
            } else if ("remove".equals(command)) {
                return Command.REMOVE;
            } else if ("size".equals(command)) {
                return Command.SIZE;
            } else if ("isempty".equals(command)) {
                return Command.IS_EMPTY;
            } else if ("contains".equals(command)) {
                return Command.CONTAINS;
            } else if ("indexof".equals(command)) {
                return Command.INDEX_OF;
            } else if ("clear".equals(command)) {
                return Command.CLEAR;
            } else {
                throw new AssertionError("Unsupported operation: " + command +
                    "\n Please provide following: add E/ remove / size / isempty / contains E/ indexof E/ clear");
            }
        }

        /**
        * Method calls the desired enum command on the array based on provided inputLine
        * 
        * @param inputLine - command line with possible parameters
        * @param array - array that method refer to
        * @param <T> - elements of the array
        */
        public static <T extends Comparable<T>> void run(String inputLine, DynamicArray<T> array) {
            String[] entry = inputLine.split("\\s+");
            String command = entry[0];
            T value = (T) (entry.length > 1 ? entry[1] : "");

            Command cmd = analyze(command);
            cmd.apply(value, array);
        }
    }
    
    private enum Command {
        ADD {
            @Override
            public <T extends Comparable<T>> void apply(T value, DynamicArray<T> array) {
                array.add(value);
            }
        }, REMOVE {
            @Override
            public <T extends Comparable<T>> void apply(T value, DynamicArray<T> array) {
                array.removeLast();
            }
        }, SIZE {
            @Override
            public <T extends Comparable<T>> void apply(T value, DynamicArray<T> array) {
                System.out.println(array.getSize());
            }
        }, IS_EMPTY {
            @Override
            public <T extends Comparable<T>> void apply(T value, DynamicArray<T> array) {
                System.out.println(array.isEmpty());
            }
        }, CONTAINS {
            @Override
            public <T extends Comparable<T>> void apply(T value, DynamicArray<T> array) {
                System.out.println(array.contains(value));
            }
        }, INDEX_OF {
            @Override
            public <T extends Comparable<T>> void apply(T value, DynamicArray<T> array) {
                System.out.println(array.indexOf(value));
            }
        }, CLEAR {
            @Override
            public <T extends Comparable<T>> void apply(T value, DynamicArray<T> array) {
                array.clear();
            }
        };
        
        /**
        * Method calls the provided command from parameter value on the array.
        * 
        * @param value - command to be executed
        * @param array - array for the command to be executed on
        * @param <T> - type of elements of the array
        */
        public abstract <T extends Comparable<T>> void apply(T value, DynamicArray<T> array);
    }
    
    public static class DynamicArray<E extends Comparable<E>> {
        private Object[] arr;
        private int size;

        private static final int DEFAULT_CAPACITY = 10;
        private static final double SCALING_FACTOR = 1.5;

        public DynamicArray() {
            this.arr = new Object[DEFAULT_CAPACITY];
            this.size = 0;
        }

        /** ADDITION methods **/
        public void add(E value) {
            ensureCapacity();
            arr[size++] = value;
        }
    
        private void ensureCapacity() {
            if (arr.length == size) {
                arr = Arrays.copyOf(arr, (int) (arr.length * SCALING_FACTOR));
            }
        }

        /** REMOVAL methods **/
        public void removeLast() {
            arr[--size] = null;
        }

        public void clear() {
            for (int i = 0; i < size; i++) {
                arr[i] = null;
            }
            size = 0;
        }

        /** RETRIEVAL methods **/
        public boolean isEmpty() {
            return size == 0;
        }

        /**
        *
        * @return <<true>> if array contains given element, <<false>> otherwise
        */
        public boolean contains(E value) {
            return indexOf(value) >= 0;
        }

        /**
        * Method allows to find first index of element in unsorted array using linear search algorithm.
        * 
        * @param value
        * @return value of the first appearance of element in the list or '-1' if there is no such element
        */
        public int indexOf(E value) {
            for (int i = 0; i < size; i++) {
                if (arr[i].equals(value)) {
                    return i;
                }
            }
            return -1;
        }

        /**
        * 
        * @return actual used size of the array
        */
        public int getSize() {
            return size;
        }
    }
}

Sorted list:

There is a linear list. The following commands are given:

add value adds an element ‘value’ to the list so that it remains sorted;
remove idx removes an element with an index 'idx';
size returns the number of elements in the array;
indexOf value prints the index of the first instance of an element with the value ‘value’, '-1' otherwise.

Input: In the first line N is the total number of commands, where 0 ≤ N ≤ 100. In the following N lines are the aforementioned commands (-1000 ≤ value ≤ 1000). It is guaranteed that remove command will not be called for a non-existing index.

Output: For each command size or indexof print the answer on a separate line.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) {
        final int lines;
        String commandLine;

        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            lines = Integer.parseInt(reader.readLine());
            DynamicArray<Integer> array = new DynamicArray<>();

            for (int i = 0; i < lines; i++) {
                commandLine = reader.readLine();
                InputUtils.run(commandLine, array);
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static class InputUtils {
        private static Command analyze(String command) {
            if ("add".equals(command)) {
                return Command.ADD;
            } else if ("remove".equals(command)) {
                return Command.REMOVE;
            } else if ("indexof".equals(command)) {
                return Command.INDEX_OF;
            } else if ("size".equals(command)) {
                return Command.SIZE;
            } else {
                throw new AssertionError("Unsupported operation: " + command + ", provide: add/remove/indexof/size");
            }
        }

        public static <T extends Comparable<T>> void run(String inputLine, DynamicArray<T> array) {
            String[] entry = inputLine.split("\\s+");
            String command = entry[0];
            String argument = entry.length > 1 ? entry[1] : "";

            Command cmd = analyze(command);
            cmd.apply(argument, array);
        }
    }

    private enum Command {
        ADD {
            @Override
            public <T extends Comparable<T>> void apply(String argument, DynamicArray<T> array) {
                array.add(argument);
            }
        }, REMOVE {
            @Override
            public <T extends Comparable<T>> void apply(String argument, DynamicArray<T> array) {
                int index = Integer.parseInt(argument);
                array.remove(index);
            }
        }, INDEX_OF {
            @Override
            public <T extends Comparable<T>> void apply(String argument, DynamicArray<T> array) {
                System.out.println(array.indexOf((T) argument));
            }
        }, SIZE {
            @Override
            public <T extends Comparable<T>> void apply(String argument, DynamicArray<T> array) {
                System.out.println(array.size());
            }
        };

        public abstract <T extends Comparable<T>> void apply(String argument, DynamicArray<T> array);
    }

    public static class DynamicArray<E extends Comparable<E>> {
        private Object[] arr;
        private int arraySize;

        private static final int DEFAULT_CAPACITY = 10;
        private static final double SCALING_FACTOR = 1.5;

        public DynamicArray() {
            this.arr = new Object[DEFAULT_CAPACITY];
            this.arraySize = 0;
        }

        private void ensureCapacity() {
            if (arr.length == arraySize) {
                arr = Arrays.copyOf(arr, (int) (arr.length * SCALING_FACTOR));
            }
        }

        public void add(String element) {
            ensureCapacity();
            int value = Integer.parseInt(element);
            int index = findPlace(value);     // index of the first element that is bigger than provided 'element'
            System.arraycopy(arr, index, arr, index + 1, arraySize - index);
            arr[index] = element;
            arraySize++;
        }

        public void remove(int index) {
            if (index < 0 || index >= arraySize) {
                throw new IndexOutOfBoundsException();
            }
            int moveCount = arraySize - index - 1;
            if (moveCount > 0) {
                System.arraycopy(arr, index + 1, arr, index, moveCount);
            }
            arr[--arraySize] = null;
        }

        /**
         *
         * Method allows to find index of element in sorted array using Binary Search algorithm.
         * @param element
         * @return value of the first appearance of element in the list or '-1' if there is no such element
         */
        public int indexOf(E element) {
            for (int i = 0; i < arraySize; i++) {
                if (element.equals(arr[i])) {
                    return i;
                }
            }
            return -1;
        }

        /**
         *
         * Method allows to find index of element in sorted array using Binary Search algorithm.
         * @param element
         * @return value of the first appearance of value that is bigger than provided element
         */
        private int findPlace(Integer element) {
            int left = 0;
            int right = arraySize - 1;
            int index = 0;

            while (left <= right) {
                int mid = left + (right - left) / 2;

                if (element.compareTo(Integer.parseInt((String) arr[mid])) >= 0) {
                    left = mid + 1;
                    index = mid + 1;
                } else if (element.compareTo(Integer.parseInt((String) arr[mid])) < 0) {
                    right = mid - 1;
                }
            }
            return index;
        }

        public int size() {
            return arraySize;
        }
    }
}

Allocated memory:

Assume that in addition to the scaling factor, there is a factor responsible for deallocating unnecessary memory after removing elements from the list. You will be given two factors: one for increasing and one for reducing the allocated memory. Following that will be queries for abstract addition and removal of clusters of elements.

Your task is to return the allocated memory for each 'count' query at that moment. Multiplication on a fraction is rounded up, division by a fraction is rounded down. The initially allocated memory is 2.

Input: In the first line there's a number of queries and both the scaling (≥ 1.1) and down-scaling (≥ 1.1) factors. Following that are queries of these types:

add count;
remove count;
count.

Output: For every 'count' query, write down the amount of allocated memory at the moment.

import java.io.*;

class Main {
    public static void main(String[] args) {
        final int lines;
        double allocateFactor;
        double deallocateFactor;
        String[] parameters;
        String commandLine;

        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            parameters = reader.readLine().split("\\s+");
            lines = Integer.parseInt(parameters[0]);
            allocateFactor = Double.parseDouble(parameters[1]);
            deallocateFactor = Double.parseDouble(parameters[2]);

            MemoryProcessor dynamicArrayMemory = new MemoryProcessor();
            dynamicArrayMemory.setAllocateFactor(allocateFactor);
            dynamicArrayMemory.setDeallocateFactor(deallocateFactor);

            for (int i = 0; i < lines; i++) {
                commandLine = reader.readLine();
                InputUtils.run(commandLine, dynamicArrayMemory);
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static class InputUtils {
        private static Command analyze(String command) {
            if ("add".equals(command)) {
                return Command.ADD;
            } else if ("delete".equals(command)) {
                return Command.DELETE;
            } else if ("count".equals(command)) {
                return Command.COUNT;
            } else {
                throw new AssertionError("Unsupported operation: " + command + ", provide: add / remove / count");
            }
        }

        public static void run(String inputLine, MemoryProcessor array) {
            String[] entry = inputLine.split("\\s+");
            String command = entry[0];
            int count = entry.length > 1 ? Integer.parseInt(entry[1]) : 1;

            Command cmd = analyze(command);
            cmd.apply(count, array);
        }
    }

    private enum Command {
        ADD {
            @Override
            public void apply(int count, MemoryProcessor array) {
                array.add(count);
            }
        }, DELETE {
            @Override
            public void apply(int count, MemoryProcessor array) {
                array.remove(count);
            }
        }, COUNT {
            @Override
            public void apply(int count, MemoryProcessor array) {
                System.out.println(array.getCapacity());
            }
        };

        public abstract void apply(int count, MemoryProcessor array);
    }

    public static class MemoryProcessor {
        private static final int DEFAULT_CAPACITY = 2;
        private double availableMemory;
        private double size;
        private double allocateFactor;
        private double deallocateFactor;

        public void setAllocateFactor(double allocateFactor) {
            this.allocateFactor = allocateFactor;
        }

        public void setDeallocateFactor(double deallocateFactor) {
            this.deallocateFactor = deallocateFactor;
        }

        public MemoryProcessor() {
            size = 0.0;
            availableMemory = DEFAULT_CAPACITY;
        }

        private void ensureCapacity() {
            while (availableMemory <= size) {
                availableMemory *= allocateFactor;
            }
            availableMemory = Math.floor(availableMemory);
        }

        private void decreaseCapacity() {
            while (availableMemory / deallocateFactor > size) {
                availableMemory /= deallocateFactor;
            }
            availableMemory = Math.floor(availableMemory);
        }

        public void add(int count) {
            size += count;
            ensureCapacity();
        }

        public void remove(int count) {
            size -= count;
            decreaseCapacity();
        }

        public int getCapacity() {
            return (int) Math.floor(availableMemory);
        }
    }
}

JetBrains Academy: Dynamic array in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki

JetBrains Academy: Dynamic array in Java

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️