YuWebdesign



Data Structures and Algorythms Interview Questions and Answers

By YuwebDesign


JVM Model Architecture: Java Memory Management

JVM is an abstract machine.
It is a specification
that provides a run-time environment
in which Java bytecode can be executed.

  1. JVM loads the code
  2. verifies the code
  3. executes the code
  4. manages memory

JVM follows three notations:

  1. Specification
  2. Implementation
  3. Runtime Instance

Java Memory Model, JVM architecture, Stack vs. Heap

Once we load the JVM,
the operating system allocates the memory for the process.

The memory allocated to that process includes:

  1. Heap
  2. Thread Stacks
  3. Meta Space
  4. JIT code cache
  5. shared libraries

JVM divides memory into stack and heap memory.

Whenever we declare a new variable/ object, or call a new method,
JVM allocates memory to these operations
either from Heap Space or from Stack Memory.

Stack Memory in Java

Stack Memory in Java is used for static memory allocation and the execution of a thread.

  1. Stack is automatically allocated when a new method is called.
  2. Access to this memory is in Last-In-First-Out (LIFO) order.
  3. Stack contains method specific values
    A new block on top of the stack stores values for this method: local primitive variables and reference variables to objects in heap space.
  4. Method specific values are short-lived.
    Variables inside stack exist only as long as the method that created them is running.
  5. Stack is automatically deallocated when method finishes execution
    After method execution is finished, it’s stack frame is flushed, the flow goes back to the calling method
    and space becomes available for the next method.
  6. If stack memory is full, Java throws java.lang.StackOverFlowError
  7. Stack memory is threadsafe as each thread operates in its own stack
Heap Space in Java

Heap space in Java
is used for dynamic memory allocation
for Java objects and JRE classes
at the runtime.

Whenever a new object is created,
it’s always stored in the Heap space
and stack memory contains the reference to it.

Any object created in the heap space
has global access
and can be referenced from anywhere of the application.

Heap Space memory model is further broken into smaller parts called generations:

  1. Young Generation
    where all new objects are allocated and aged.

    Eden
    is a part of Young Generation.
    Whenever a new object is created, it goes to Eden.

    Minor Garbage Collection

    Minor GC is performed to free the heap memory
    used by objects that don’t have any reference.

    Young Generation (Eden -> S0 -> S1) -> Old Generation

    When Eden Space is filled with objects,
    Minor GC is performed to clean up the Young Generation.

    Also, Minor GC checks the survivor objects
    to move them through the survivor space levels:

    1. from Eden to the Survivor Space S0
    2. and from S0 to S1.

    So at a time, one of the survivor spaces is always empty.

    When objects are stored in the Young Generation,
    a threshold for the object’s age is set
    and when that threshold is reached,
    the object becomes eligible to promote
    to be moved to the Old Generation.

  2. Old or Tenured Generation
    contains long surviving objects (survived many cycles of Minor GC).

    Major Garbage Collection (Major GC) is performed
    when Old Generation is full.
    Major GC takes a longer time.

    Old Memory
    is a part of Old Generation

  3. Permanent Generation
    also called “Perm Gen” or Meta Space

    Permanent Generation is NOT a part of Heap Memory

    Perm Generation contains application metadata:
    JVM metadata for the runtime classes and application methods

    Perm Generation is populated by JVM at the runtime
    based on the classes used by the application.

    It also contains Java system (SE) libraries, classes, and methods.

    Perm Generation Objects are cleaned up by Full Garbage Collection (Full GC).

    OutofmemoryError is related to the Perm Generation overfill.

Stack vs Heap
  1. Because of simplicity in memory allocation (LIFO), access to stack memory is faster than to the heap memory.
  2. Stack memory size is much smaller than that of the Heap memory.
  3. Heap memory is used by all the parts of the application.
    Stack memory is used only by one thread of execution.
  4. Whenever a new object is created, it’s always stored in the Heap space and stack memory contains only the reference to it.
  5. Objects stored in the heap are globally accessible whereas stack memory can’t be accessed by other threads.
  6. Memory management in stack is done in LIFO manner whereas it’s more complex in Heap memory because it’s used globally. Heap memory is divided into Generations and cleaned by Java Garbage Collection.
  7. Stack memory is short-lived whereas heap memory lives from the start till the end of application execution.
Stack Heap
Used only by one thread of execution. Used by all the parts of the application.
Can’t be accessed by other threads. Globally accessible.
Follows LIFO manner to free memory. Memory management is based on the generation associated with each object.
Exists until the end of execution of the thread. Lives from the start till the end of application execution.
Contains only local primitive and reference variables to objects in heap space. Whenever an object is created, it’s always stored in the Heap space.

Watch more:

  1. level: easy
  2. level: easy
  3. level: low intermediate
  4. level: intermediate
  5. level: intermediate
  6. level: advanced

Java doesn’t use pointers because they are unsafe and increases the complexity of the program.
Since Java is known for its simplicity of code, adding the concept of pointers will be contradicting.

Moreover, since JVM is responsible for implicit memory allocation,
thus in order to avoid direct access to memory by the user, pointers are discouraged in Java.

In Java, all objects are dynamically allocated on Heap.

This is different from C++ where objects can be allocated memory either on Stack or on Heap.
In C++, when using “new()” keyword, the object is allocated on Heap, otherwise on Stack if not global or static.

In Java, when we only declare a variable of a class type,
only a reference is created (memory is not allocated for the object).
To allocate memory to an object, we must use new().

  1. Garbage collection in Java is a program which helps in implicit memory management.
  2. Using the new keyword, you can create objects dynamically.
    Once created, they will consume some memory.
  3. Once the job is done and there are no more references left to the object, Java using garbage collection destroys the object and relieves the memory occupied by it.

Java provides four types of Garbage Collectors:

  1. Serial Garbage Collector
  2. Parallel Garbage Collector
  3. CMS Garbage Collector
  4. G1 Garbage Collector

All Java Objects are stored on the Heap,
so ArrayList Object will be created on the Heap
with a reference on the Stack that points to this Object on the Heap.

Watch this

Data Structures

A data structure
is a particular way
of organizing data in a computer
so that it can be used effectively.

E.g., we can store a list of items
having the same data-type
using the array data structure.

Strings in Java

In computer science, string interning
is a method of storing only one copy of each distinct string value,
which must be immutable.

String Pool Java

Interning strings makes some string processing tasks
more time- or space-efficient
at the cost of requiring more time
when the string is created or interned.

Global Intern Pool

The distinct values are stored in a string intern pool.

The single copy of each string is called its intern
and is typically looked up by a method of the string class,
e.g., String.intern() in Java.

All compile-time constant strings in Java
are automatically interned using this method.

Source: wikipedia

In heap memory, JVM allocates some memory specially meant for string literals. This part of the heap memory is called String Constant Pool.

Whenever you create a string object using string literal, that object is stored in the string constant pool and whenever you create a string object using new keyword, such object is stored in the heap memory.

String pool space is allocated to an object depending upon it’s content.
There will be no two objects in the string pool having the same content.
But there can be two string objects with the same content in the heap memory.

Whenever a String object is created,
String pool first checks whether the object whether same content is already present in the pool.
If present, no new object is created, and same reference gets returned,
otherwise new object will be created in the String Pool and the respective reference will be returned.

However, when you create string objects using new keyword, a new object is created whether the content is same or not.

Once the string reference changes the old value that exists in the “constant string pool”, it cannot be erased.

E.g., String name = “book”;

Constant string pool:
constant string pool in Java

E.g., If name value has changed from “book” to “pen”,
the older value retains in the constant string pool.

Constant string pool:
changed string value in constant string pool in Java

  1. In Java, string objects are immutable in nature which simply means once the String object is created its state cannot be modified.
  2. Whenever you try to update the value of that object instead of updating the values of that particular object, Java creates a new string object.
  3. Java String objects are immutable as String objects are generally cached in the String pool.
  4. Since String literals are usually shared between multiple clients, action from one client might affect the rest.
  5. Immutability enhances security, caching, synchronization, and performance of the application.

String String Builder String Buffer
Storage Constant String Pool (Heap) Heap Heap
Mutability Immutable Mutable
(If the values are changed then the new value replaces the older value.)
Mutable
(E.g., String Buffer name =”book”;
Once the name value has been changed to “pen” then the “book” is erased in the stack.)
Thread Safety Yes Yes
(synchronized which is thread-safe)
No
(not synchronized)
Performance Fast Slow Fast

Array in Java

An array
is a collection of items
stored at contiguous memory locations.

Each element can be uniquely identified by their index in the array.
Arrays in Java

The idea is to store multiple items
of the same type together.

Array Memory Location

This makes it easier
to calculate the position of each element
by simply adding an offset to a base value,
i.e., the memory location of the first element of the array
(generally denoted by the name of the array).

Location of next index depends on the data type we use.

For simplicity, we can think of an array
as a fleet of stairs
where on each step is placed a value (let’s say one of your friends).

Here, you can identify the location of any of your friends
by simply knowing the count of the step they are on.

Read more about arrays: oracle tutorials, geeksforgeeks

Array Data types

Array can contains primitives data types
as well as objects of a class
depending on the definition of array.

  1. In case of primitives data types,
    the actual values are stored in contiguous memory locations.
  2. In case of objects of a class,
    the actual objects are stored in heap segment.

***Stack memory is used to store local variables
which get memory at the time of declaration.

***Heap memory stores those
which get memory at run time like objects.

Arrays in Java
  1. In Java all arrays are dynamically allocated.

    Obtaining an array is a two-step process:

    1. First, you must declare a variable of the desired array type.
    2. Second, you must allocate the memory that will hold the array, using new,
      and assign it to the array variable.

    Thus, in Java all arrays are dynamically allocated.

  2. Java Arrays are first class objects.
    The direct superclass of an array type is Object.

    Since arrays are objects in Java,
    size of array is accessed using length
    which is a member of arr[] object.

    public class JavaArrayExample { 
        public static void main(String args[]) { 
           //character array
           char arr1[] = {'g', 'e', 'e', 'k', 's'};
    
           //integer array
           int arr[] = {10, 20, 30, 40, 50}; 
           for(int i=0; i < arr.length; i++) 
           { 
                 System.out.print(" " + arr[i]);               
           } 
        } 
    } 
    // Output: 10 20 30 40 50
    
  3. The size of an array must be specified by
    an int value
    short value (as the java does implicit casting from short to int)
    but not long
  4. A Java array variable can also be declared
    like other variables with [] after the data type.
  5. Variables in the array are ordered
  6. Java arrays are 0-based (index begins from 0.)
  7. Java array can be also be used as
    • a static field,
    • a local variable
    • or a method parameter.
  8. Every array type implements the interfaces Cloneable and java.io.Serializable.

Types of indexing in array

:

  1. 0 (zero-based indexing):
    The first element of the array is indexed by subscript of 0
  2. 1 (one-based indexing):
    The first element of the array is indexed by subscript of 1
  3. n (n-based indexing):
    The base index of an array can be freely chosen.

    Usually programming languages allowing n-based indexing
    also allow negative index values
    and other scalar data types like enumerations,
    or characters may be used as an array index.

Java Arrays are zero-based.

Accessing Java Array Elements
  1. using for Loop
    for (int i=0; i
    
  2. using for-each loop
    for (type var : array) 
    { 
        statements using var;
    }
    

Array Declaration

An array declaration has two components: the type and the name:

type var-name[];
OR
type[] var-name;
  1. var-name is a name of an array variable that is linked to the array
  2. type: Array can hold elements of
    primitive data types (int, char, float, double, etc.)
    or user defined data type (objects of a class).

Example:

//both are valid declarations
int intArray[]; 
int[] intArray;

//Object Array
Object[]  ao,  
 
// array of Collection of unknown type     
Collection[] ca;  
Instantiating an Array in Java

When an array is declared, only a reference of an array is created.

Declaring an integer array establishes the fact
that intArray is an array variable,
no array actually exists.

It simply tells to the compiler
that this(intArray) variable will hold an array of the integer type.

To link intArray with an actual, physical array of integers,
you must allocate an Array using new and assign it to intArray.

To actually create and give memory to an array,
you need to specify the type and number of elements to allocate:

var-name = new type [size];
  1. type
    specifies the type of data being allocated,
  2. size
    specifies the number of elements in the array,
  3. var-name
    is the name of array variable that is linked to the array.

Example:

int intArray[];    //declaring array
intArray = new int[20];  // allocating memory to array for 20 integers

or

int[] intArray = new int[20]; // combining both statements in one
Default Array Values in Java

The elements in the array allocated by new
will automatically be initialized to

  1. zero (for numeric types),
  2. false (for boolean),
  3. null (for reference types).

<5>Array Literal

If Array size and variables are already known,
array literals can be used.

 int[] intArray = new int[]{ 1,2,3,4,5,6,7,8,9,10 }; 
 // Declaring array literal
  1. The length of this array determines the length of the created array.
  2. There is no need to write the new int[] part in the latest versions of Java

Multidimensional arrays
are arrays of arrays
with each element of the array
holding the reference of the other array.

A multidimensional array is created by appending one set of square brackets ([]) per dimension:

int[][] intArray = new int[10][20]; //a 2D array or matrix
int[][][] intArray = new int[10][20][10]; //a 3D array
column 1 column 2 column 3 column 4 column 5
row 1 arr[0][0] arr[0][1] arr[0][2] arr[0][3] arr[0][4]
row 2 arr[1][0] arr[1][1] arr[1][2] arr[1][3] arr[1][4]
row 3 arr[2][0] arr[2][1] arr[2][2] arr[2][3] arr[2][4]
class multiDimensional { public static void main(String args[]) { // declaring and initializing 2D array int arr[][] = { {2,7,9},{3,6,1},{7,4,2} }; // printing 2D array for (int i=0; i< 3 ; i++) { for (int j=0; j < 3 ; j++) System.out.print(arr[i][j] + " "); System.out.println(); } } }

Output:

2 7 9 
3 6 1 
7 4 2

Jagged array
is a multidimensional array (array of arrays)
where member arrays can be of different sizes.

E.g., we can create a 2-D array
with variable number of columns in each row.

Example of a 2-D Jugged Array:

class MultidimensionalJuggedArrayDemo 
{ 
    public static void main(String[] args) 
    { 
        // Declaring 2-D array with 2 rows 
        int arr[][] = new int[2][]; 
  
        // Making the above array Jagged 
  
        // First row has 3 columns 
        arr[0] = new int[3]; 
  
        // Second row has 2 columns 
        arr[1] = new int[2]; 
  
        // Initializing array 
        int count = 0; 
        for (int i=0; i < arr.length; i++) 
            for(int j=0; j < arr[i].length; j++) 
                arr[i][j] = count++; 
  
        // Displaying the values of 2D Jagged array 
        System.out.println("Contents of 2D Jagged Array"); 
        for (int i=0; i < arr.length; i++) 
        { 
            for (int j=0; j < arr[i].length; j++) 
                System.out.print(arr[i][j] + " "); 
            System.out.println(); 
        } 
    } 
} 

Output:

Contents of 2D Jagged Array
0 1 2 
3 4

Example of a 2-D Jugged Array where i’th row has i columns:

// 2-D Jugged Array 
//where first row has 1 element,  
// second row has two elements and so on. 

class TwoDimensionalJuggedArray 
{ 
    public static void main(String[] args) 
    { 
        int r = 5; 
  
        // Declaring 2-D array with 5 rows 
        int arr[][] = new int[r][]; 
  
        // Creating a 2D array such that first row 
        // has 1 element, second row has two  
        // elements and so on. 
        for (int i=0; i < arr.length; i++) 
            arr[i] = new int[i+1]; 
  
        // Initializing array 
        int count = 0; 
        for (int i=0; i < arr.length; i++) 
            for(int j=0; j < arr[i].length; j++) 
                arr[i][j] = count++; 
  
        // Displaying the values of 2D Jagged array 
        System.out.println("Contents of 2D Jagged Array"); 
        for (int i=0; i < arr.length; i++) 
        { 
            for (int j=0; j < arr[i].length; j++) 
                System.out.print(arr[i][j] + " "); 
            System.out.println(); 
        } 
    } 
} 

Output:

Contents of 2D Jagged Array
0 
1 2 
3 4 5 
6 7 8 9 
10 11 12 13 14 

Source: geeksforgeeks

JVM throws ArrayIndexOutOfBoundsException
to indicate that array
has been accessed with an illegal index.

The index is either

  1. negative
  2. or greater than
  3. or equal to size of array
class GFG 
{ 
    public static void main (String[] args) 
    { 
        int[] arr = new int[2]; 
        arr[0] = 10; 
        arr[1] = 20; 
  
        for (int i = 0; i <= arr.length; i++) 
            System.out.println(arr[i]); 
    } 
}

Runtime error

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2
    at GFG.main(File.java:12)

Output:

10
20

Advantages of Using Arrays
  1. Arrays allow random access of elements.
    This makes accessing elements by position faster.
  2. Arrays have better cache locality
    that can make a pretty big difference in performance.

Passing Arrays to Methods

Like variables, we can also pass arrays to methods.

// pass array to method sum 
//for calculating sum of array’s values.
  
class PassArrayToMethod 
{     
    // Driver method 
    public static void main(String args[])  
    { 
        int arr[] = {3, 1, 2, 5, 4}; 
          
        // passing array to method m1 
        sum(arr); 
    } 
  
    public static void sum(int[] arr)  
    { 
        // getting sum of array values 
        int sum = 0; 
          
        for (int i = 0; i < arr.length; i++) 
            sum+=arr[i]; 
          
        System.out.println("sum of array values : " + sum); 
    } 
} 

Output :

sum of array values : 15

Returning Arrays from Methods

A method can also return an array.

// Returns an array from method 
  
class ReturnArrayFromMethod 
{     
    // Driver method 
    public static void main(String args[])  
    { 
        int arr[] = m1(); 
          
        for (int i = 0; i < arr.length; i++) 
            System.out.print(arr[i]+" "); 
    } 
  
    public static int[] m1()  
    { 
        // returning  array 
        return new int[]{1,2,3}; 
    } 
} 

Output:

1 2 3

Every array has an associated Class object,
shared with all other arrays
with the same component type.

// Class Objects for Arrays 
  
class ClassObjectsForArrays 
{  
    public static void main(String args[])  
    { 
        int intArray[] = new int[3]; 
        byte byteArray[] = new byte[3]; 
        short shortsArray[] = new short[3]; 
          
        // array of Strings 
        String[] strArray = new String[3]; 
          
        System.out.println(intArray.getClass()); 
        System.out.println(intArray.getClass().getSuperclass()); 
        System.out.println(byteArray.getClass()); 
        System.out.println(shortsArray.getClass()); 
        System.out.println(strArray.getClass()); 
    } 
}

Output:

class [I
class java.lang.Object
class [B
class [S
class [Ljava.lang.String;

Explanation:

  1. The string “[I”
    is the run-time type signature for the class object “array with component type int“.
  2. The only direct superclass of any array type is java.lang.Object.
  3. The string “[B”
    is the run-time type signature for the class object “array with component type byte“.
  4. The string “[S”
    is the run-time type signature for the class object “array with component type short“.
  5. The string “[L”
    is the run-time type signature for the class object “array with component type of a Class”. The Class name is then followed.

Arrays are object of a class
and direct superclass of arrays is class Object.

The members of an Array type are:

  1. All the members are inherited from class Object;
    the only method of Object that is not inherited is its clone method.
  2. Public final field length
    contains the number of components of the array.
    Length may be positive or zero.
  3. Public method clone()
    overrides clone method in class Object
    and throws no checked exceptions.

Cloning a Single-Dimensional Array

When cloning a single-dimensional array (e.g.Object[])
a “deep copy” is performed.

The new array contains copies of the original array’s elements
as opposed to references.

// cloning of one-dimensional arrays
class CloningOneDimensionalArray 
{     
    public static void main(String args[])  
    { 
        int intArray[] = {1,2,3}; 
          
        int cloneArray[] = intArray.clone(); 
          
        // will print false as deep copy is created 
        // for one-dimensional array 
        System.out.println(intArray == cloneArray); 
          
        for (int i = 0; i < cloneArray.length; i++) { 
            System.out.print(cloneArray[i]+" "); 
        } 
    } 
} 

Output:

false
1 2 3

Cloning a Multidimensional Array

A clone of a multidimensional array (like Object[][]) is a “shallow copy” however, which is to say that it creates only a single new array with each element array a reference to an original element array but subarrays are shared.

// Cloning multi-dimensional array 
  
class CloningMultiDimensionalArray 
{     
    public static void main(String args[])  
    { 
        int intArray[][] = {{1,2,3},{4,5}}; 
          
        int cloneArray[][] = intArray.clone(); 
          
        // will print false 
        System.out.println(intArray == cloneArray); 
          
        // will print true as shallow copy is created 
        // i.e. sub-arrays are shared 
        System.out.println(intArray[0] == cloneArray[0]); 
        System.out.println(intArray[1] == cloneArray[1]); 
    } 
}

Output:

false
true
true

      

Java Collection

  1. A group of objects is known as a collection.
  2. In Java, Collection is a framework that acts as an architecture for storing and manipulating a group of objects.
  3. All the classes and interfaces for collecting are available in java.util package.
  4. Collections are used to perform the following operations:
    1. Searching
    2. Sorting
    3. Manipulation
    4. Insertion
    5. Deletion
  5. Java Collection framework includes:
    1. Interfaces
    2. Classes
    3. Methods

Interfaces
  1. Collection
  2. List
  3. Set
  4. Map
  5. Sorted Set
  6. Sorted Map
  7. Queue
Classes
Lists Sets Maps Queue
  1. Array List
  2. Vector
  3. Linked List
  1. Hash set
  2. Linked Hash Set
  3. Tree Set
  1. Hash Map
  2. Hash Table
  3. Tree Map
  4. Linked Hashed Map
Priority Queue
Java Collection Framework Architecture Hierarchy

Java Collection Framework Architecture Hierarchy

Ordered

It means the values that are stored in a collection is based on the values that are added to the collection. So we can iterate the values from the collection in a specific order.

Sorted

Sorting mechanism can be applied internally or externally so that the group of objects sorted in a particular collection is based on properties of the objects.

In Java, Map is an interface of Util package.
It maps a unique key to a specific value as a key/value pair.
We can search a value, based on the key.

Like Set, Map also uses “equals ( )” method to determine whether two keys are same or different.

The Map interface is not a subset of the main Collection interface
and thus it behaves little different from the other collection types.

Characteristics of Map interface:

  1. Map doesn’t contain duplicate keys.
  2. Each key can map at max one value.
Hash Map
  1. Doesn’t maintain any insertion order
  2. Unordered and unsorted map.
  3. Hashmap is a good choice when we don’t care about the order.
  4. It allows one null key and multiple null values.
  5. Duplicate keys are not allowed in Map.
Hash Table
  1. Like vector key, methods of the class are synchronized.
  2. Thread safety and therefore slows the performance.
  3. Doesn’t allow anything that is null.
  4. Duplicate keys are not allowed.
Linked Hash Map
  1. Maintains insertion order.
  2. Slower than Hash map.
  3. Can expect a faster iteration.
  4. Duplicate keys are not allowed.
TreeMap
  1. Sorted Map.
  2. Like Tree set, we can construct a sort order with the constructor.
  3. It is sorted in ascending order based on the key. Duplicate keys are not allowed.

Methods are not synchronized Key methods are synchronized
Not thread safety Thread safety
Iterator is used to iterate the values Enumerator is used to iterate the values
Allows one null key and multiple null values Doesn’t allow anything that is null
Performance is higher than of HashTable Performance is slow

Set cares about uniqueness. It doesn’t allow duplications. Here “equals ( )” method is used to determine whether two objects are identical or not.

Hash Set
  1. Unordered and unsorted.
  2. Doesn’t follow any insertion order.
  3. Uses the hash code of the object to insert the values.
  4. Duplicates are not allowed.
  5. Use this when the requirement is “no duplicates and don’t care about the order”.
Linked Hash set
  1. An ordered version of the hash set is known as Linked Hash Set.
  2. Maintains a doubly-Linked list of all the elements.
  3. Maintains the insertion order in which they have been added to the Set.
  4. Use this when the iteration order is required.
  5. Duplicates are not allowed.
Tree Set
  1. It is one of the two sorted collections.
  2. TreeSet sorts the elements in an ascending order.
  3. Uses “Read-Black” tree structure and guarantees that the elements will be in an ascending order.
  4. We can construct a tree set with the constructor by using comparable (or) comparator.

HashSet TreeSet
Inserted elements are in random order Maintains the elements in the sorted order
Can store null objects Cannot store null objects
Performance is fast Performance is slow

Values added to the list is based on the index position and it is ordered by index position. Duplicates are allowed.

Array List
  1. Fast iteration and fast Random Access.
  2. It is an ordered collection (by index) and not sorted.
  3. It implements Random Access Interface.
  4. Array List maintains the insertion order and it accepts the duplicates. But not sorted.
Vector

It is same as Array List.

  1. Vector methods are synchronized.
  2. Thread safety.
  3. It also implements the Random Access.
  4. Thread safety usually causes a performance hit.
  5. Vector also maintains the insertion order and accepts the duplicates.
Linked List
  1. Elements are doubly linked to one another.
  2. Performance is slow than Array list.
  3. Good choice for insertion and deletion.
  4. In Java 5.0 it supports common queue methods peek( ), Pool ( ), Offer ( ) etc.
  5. Maintains the insertion order and accepts the duplicates.

Array Array List
Size Should be given at the time of array declaration.

String[] name = new String[2]

Not required. It changes the size dynamically.

ArrayList name = new ArrayList

Index requirement while adding element Index should be specified.

name[1] = “book”

No index required.

name.add(“book”)

Type parameterization Array is not type parameterized ArrayList in java 5.0 are parameterized.
ArrayLists are a type.

Eg: a list of String.

Data types Arrays can contain primitive data types as well as objects Arraylists can contain only objects, no primitive data types are allowed.

Array List Vector
not synchronized. synchronized.
fast (as it’s non-synchronized). slow (as it is thread safe).
If an element is inserted into the Array List, it increases its Array size by 50%. Vector defaults to doubling size of its array.
does not define the increment size. defines the increment size.
only Iterator can be used for traversing an Array List. both Enumeration and Iterator can be used for traversing Vector.

Classification of Algorithms

Profiling

To decide which algorythm is better for a particular application, one approach is to try them both and see how long they take.

This approach, which is called “profiling”, has a few problems:

  1. Before you can compare the algorithms,
    you have to implement them both.
  2. The results might depend on what kind of computer you use.

    One algorithm might be better on one machine;
    the other might be better on a different machine.

  3. The results might depend on the size of the problem
    or the data provided as input.

Algorithm Analysis

We can address some of these problems using Analysis of Algorithms.

Algorithm Analysis makes it possible to compare algorithms without
having to implement them.


But we have to make some assumptions:

  1. To avoid dealing with the details of computer hardware,
    we usually identify the basic operations that make up an algorithm —
    like addition, multiplication, and comparison of numbers —
    and count the number of operations each algorithm requires.
  2. To avoid dealing with the details of the input data,
    the best option is to analyze the average performance
    for the inputs we expect.

    If that’s not possible, a common alternative is to analyze the worst case scenario.

  3. Finally, we have to deal with the possibility
    that one algorithm works best for small problems
    and another for big ones.

    In that case, we usually focus on the big ones,
    because for small problems the difference probably doesn’t matter,
    but for big problems the difference can be huge.

This kind of analysis lends itself to simple classification of algorithms.

E.g., if we know that the run time of Algorithm A
tends to be proportional to the size of the input, n,
and Algorithm B tends to be proportional to n2,
we expect A to be faster than B, at least for large values of n.

Most simple algorithms fall into just a few categories:

  • Constant time:
    An algorithm is “constant time”
    if the run time does not depend on the size of the input.

    E.g, if you have an array of n elements
    and you use the bracket operator ([]) to access one of the elements,
    this operation takes the same number of operations
    regardless of how big the array is.

  • ˆ

  • Linear:
    An algorithm is “linear”
    if the run time is proportional to the size of the input.

    E.g., if you add up the elements of an array,
    you have to access n elements and perform n − 1 additions.
    The total number of operations (element accesses and additions)
    is 2n − 1, which is proportional to n.

  • ˆ

  • Quadratic:

    An algorithm is “quadratic”
    if the run time is proportional to n2.

    E.g., suppose you want to check whether any element in a list appears more than once.
    A simple algorithm is to compare each element to all of the others.
    If there are n elements and each is compared to n − 1 others,
    the total number of comparisons is n2 − n,
    which is proportional to n2 as n grows.


Sources:

  1. geeksforgeeks.org,
  2. free course by William Fiset - Software Engineer at Google,
  3. Data Structure course by Log(n) Academy,
  4. data structures course by University of California San Diego & National Research University Higher School of Economics,
  5. Data Structures and Performance by University of California San Diego,
  6. Algorithms, Part I by Princeton University


Leave a Reply or Comment

Your email address will not be published. Required fields are marked *