Explore topic-wise InterviewSolutions in Current Affairs.

The time complexity is O(1) assuming that the hash function used in the hash map distributes elements uniformly among the buckets.

• The java.util.HashMap class in Java uses the approach of chaining to handle collisions. In chaining, if the new values with the same key are attempted to be pushed, then these values are stored in a linked list stored in a bucket of the key as a chain along with the existing value.


• In the worst-case scenario, it can happen that all keys might have the same hashcode, which will result in the hash table turning into a linked list. In this case, searching a value will take O(n) complexity as opposed to O(1) time due to the nature of the linked list. Hence, care has to be taken while selecting hashing algorithm.

• The key or value object that gets used in the hashmap must implement equals() and hashcode() method.


• The hash code is used when inserting the key object into the map and the equals method is used when trying to retrieve a value from the map.

Hashmap is a data structure that uses an implementation of a hash table data structure which allows access to data in constant time (O(1)) complexity if you have the key.

Asymptotic analysis of an algorithm defines the run-time performance as per its mathematical boundations. Asymptotic analysis helps us articulate the best case(Omega Notation, Ω), average case(Theta Notation, θ), and worst case(Big Oh Notation, Ο) performance of an algorithm.

Following are different types of linked lists:

1. Singly Linked List: A singly linked list is a data structure that is used to store multiple items. The items are linked together using the key. The key is used to identify the item and is usually a unique identifier. In a singly linked list, each item is stored in a separate node. The node can be a single object or it can be a collection of objects. When an item is added to the list, the node is updated and the new item is added to the end of the list. When an item is removed from the list, the node that contains the removed item is deleted and its place is taken by another node. The key of a singly linked list can be any type of data structure that can be used to identify an object. For example, it could be an integer, a string, or even another singly linked list. Singly-linked lists are useful for storing many different types of data. For example, they are commonly used to store lists of items such as grocery lists or patient records. They are also useful for storing data that is time sensitive such as stock market prices or flight schedules.

2. Doubly Linked List: A doubly linked list is a data structure that allows for two-way data access such that each node in the list points to the next node in the list and also points back to its previous node. In a doubly linked list, each node can be accessed by its address, and the contents of the node can be accessed by its index. It's ideal for applications that need to access large amounts of data in a fast manner. A disadvantage of a doubly linked list is that it is more difficult to maintain than a single-linked list. In addition, it is more difficult to add and remove nodes than in a single-linked list.

3. Circular Linked List: A circular linked list is a unidirectional linked list where each node points to its next node and the last node points back to the first node, which makes it circular.

4. Doubly Circular Linked List: A doubly circular linked list is a linked list where each node points to its next node and its previous node and the last node points back to the first node and first node’s previous points to the last node.

5. Header List: A list that contains the header node at the beginning of the list, is called the header-linked list. This is helpful in calculating some repetitive operations like the number of elements in the list etc.

A linked list can be thought of as a series of linked nodes (or items) that are connected by links (or paths). Each link represents an entry into the linked list, and each entry points to the next node in the sequence. The order in which nodes are added to the list is determined by the order in which they are created.

Following are some applications of linked list data structure:

• Stack, Queue, binary trees, and graphs are implemented using linked lists.


• Dynamic management for Operating System memory.


• Round robin scheduling for operating system tasks.


• Forward and backward operation in the browser.

There are several different types of arrays:

• 
  One-dimensional array: A one-dimensional array stores its elements in contiguous memory locations, accessing them using a single index value. It is a linear data structure holding all the elements in a sequence.

• 
  Two-dimensional array: A two-dimensional array is a tabular array that includes rows and columns and stores data. An M × N two-dimensional array is created by grouping M rows and N columns into N columns and rows.

• 
  Three-dimensional array: A three-dimensional array is a grid that has rows, columns, and depth as a third dimension. It comprises a cube with rows, columns, and depth as a third dimension. The three-dimensional array has three subscripts for a position in a particular row, column, and depth. Depth (dimension or layer) is the first index, row index is the second index, and column index is the third index.

An array data structure is a data structure that is used to store data in a way that is efficient and easy to access. It is similar to a list in that it stores data in a sequence. However, an array data structure differs from a list in that it can hold much more data than a list can. An array data structure is created by combining several arrays together. Each array is then given a unique identifier, and each array’s data is stored in the order in which they are created.

Array data structures are commonly used in databases and other computer systems to store large amounts of data efficiently. They are also useful for storing information that is frequently accessed, such as large amounts of text or images.

• A stack can be implemented using two queues. We know that a queue supports enqueue and dequeue operations. Using these operations, we need to develop push, pop operations.


• Let stack be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Then, stack ‘s’ can be implemented in two ways:

1. By making push operation costly:

• This method ensures that the newly entered element is always at the front of ‘q1’ so that pop operation just dequeues from ‘q1’.


• ‘q2’ is used as auxillary queue to put every new element in front of ‘q1’ while ensuring pop happens in O(1) complexity.


• 
  Pseudocode:
  • Push element to stack s: Here push takes O(n) time complexity.
  
  

• Pop element from stack s: Takes O(1) time complexity.

2. By making pop operation costly:

• In push operation, the element is enqueued to q1.


• In pop operation, all the elements from q1 except the last remaining element, are pushed to q2 if it is empty. That last element remaining of q1 is dequeued and returned.


• 
  Pseudocode:
  • Push element to stack s: Here push takes O(1) time complexity.
  
  

• Pop element from stack s: Takes O(n) time complexity.

A queue can be implemented using two stacks. Let q be the queue andstack1 and stack2 be the 2 stacks for implementing q. We know that stack supports push, pop, and peek operations and using these operations, we need to emulate the operations of the queue - enqueue and dequeue. Hence, queue q can be implemented in two methods (Both the methods use auxillary space complexity of O(n)):

1. By making enqueue operation costly:

• Here, the oldest element is always at the top of stack1 which ensures dequeue operation occurs in O(1) time complexity.


• To place the element at top of stack1, stack2 is used.


• 
  Pseudocode:
  • 
    Enqueue: Here time complexity will be O(n)
  
  

• 
  Dequeue: Here time complexity will be O(1)

2. By making the dequeue operation costly:

• Here, for enqueue operation, the new element is pushed at the top of stack1. Here, the enqueue operation time complexity is O(1).


• In dequeue, if stack2 is empty, all elements from stack1 are moved to stack2 and top of stack2 is the result. Basically, reversing the list by pushing to a stack and returning the first enqueued element. This operation of pushing all elements to a new stack takes O(n) complexity.


• 
  Pseudocode:
  • 
    Enqueue: Time complexity: O(1)
  
  

• 
  Dequeue: Time complexity: O(n)

• 
  enqueue: This adds an element to the rear end of the queue.  Overflow conditions occur if the queue is full.


• 
  dequeue: This removes an element from the front end of the queue. Underflow conditions occur if the queue is empty.


• 
  isEmpty: This returns true if the queue is empty or else false.


• 
  rear: This returns the rear end element without removing it.


• 
  front: This returns the front-end element without removing it.


• 
  size: This returns the size of the queue.

A queue is a linear data structure that allows users to store items in a list in a systematic manner. The items are added to the queue at the rear end until they are full, at which point they are removed from the queue from the front. Queues are commonly used in situations where the users want to hold items for a long period of time, such as during a checkout process. A good example of a queue is any queue of customers for a resource where the first consumer is served first.

Following are some applications of queue data structure:

• Breadth-first search algorithm in graphs


• Operating system: job scheduling operations, Disk scheduling, CPU scheduling etc.


• Call management in call centres

Some of the main operations provided in the stack data structure are: 

• 
  push: This adds an item to the top of the stack. The overflow condition occurs if the stack is full.


• 
  pop: This removes the top item of the stack. Underflow condition occurs if the stack is empty.


• 
  top: This returns the top item from the stack.


• 
  isEmpty: This returns true if the stack is empty else false.


• 
  size:  This returns the size of the stack.

A stack is a data structure that is used to represent the state of an application at a particular point in time. The stack consists of a series of items that are added to the top of the stack and then removed from the top. It is a linear data structure that follows a particular order in which operations are performed. LIFO (Last In First Out) or FILO (First In Last Out) are two possible orders. A stack consists of a sequence of items. The element that's added last will come out first, a real-life example might be a stack of clothes on top of each other. When we remove the cloth that was previously on top, we can say that the cloth that was added last comes out first.

Following are some applications for stack data structure:

• It acts as temporary storage during recursive operations


• Redo and Undo operations in doc editors


• Reversing a string


• Parenthesis matching


• Postfix to Infix Expressions


• Function calls order

• 
  Linear Data Structure: A data structure that includes data elements arranged sequentially or linearly, where each element is connected to its previous and next nearest elements, is referred to as a linear data structure. Arrays and linked lists are two examples of linear data structures.


• 
  Non-Linear Data Structure: Non-linear data structures are data structures in which data elements are not arranged linearly or sequentially. We cannot walk through all elements in one pass in a non-linear data structure, as in a linear data structure. Trees and graphs are two examples of non-linear data structures.

• 
  File Structure: Representation of data into secondary or auxiliary memory say any device such as a hard disk or pen drives that stores data which remains intact until manually deleted is known as a file structure representation.


• 
  Storage Structure: In this type, data is stored in the main memory i.e RAM, and is deleted once the function that uses this data gets completely executed.

The difference is that the storage structure has data stored in the memory of the computer system, whereas the file structure has the data stored in the auxiliary memory.

• A variable is stored in memory based on the amount of memory that is needed. Following are the steps followed to store a variable:
  
  
  • The required amount of memory is assigned first.
  
  
  • Then, it is stored based on the data structure being used.
  
  
  
  


• Using concepts like dynamic allocation ensures high efficiency and that the storage units can be accessed based on requirements in real-time.

Following are some real-time applications of data structures:

• Decision Making


• Genetics


• Image Processing


• Blockchain


• Numerical and Statistical Analysis


• Compiler Design


• Database Design and many more

Data structures serve a number of important functions in a program. They ensure that each line of code performs its function correctly and efficiently, they help the programmer identify and fix problems with his/her code, and they help to create a clear and organized code base.

A data structure is a mechanical or logical way that data is organized within a program. The organization of data is what determines how a program performs. There are many types of data structures, each with its own uses. When designing code, we need to pay particular attention to the way data is structured. If data isn't stored efficiently or correctly structured, then the overall performance of the code will be reduced.