Java Data Structure Interview Questions

What Is A Linked List And What Are The Various Types

In a linked list, each element is a distinct object. Like arrays, linked lists are a linear type of data structure. In addition to data, every element of a linked list has a reference to the next element. The various types of linked lists are:

• Singly linked list: Each node stores the address or reference of the next node in the linked list, except for the last node that stores NULL.
• Doubly linked list: Each node keeps two references. One point to the next node and the other points to the previous node.
• Circular linked list: In this type of linked list, all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can either be a single circular linked list or a double circular linked list.

What Can I Achieve From The Purdue Postgraduate Data Science Program

You will receive the following as part of this PG in Data Science, which is offered in conjunction with IBM:

Q3 Explain The Difference Between Linkedlist And Arraylist

ArrayList is an implementation of the List interface that is based on an array. ArrayList internally handles resizing of this array when the elements are added or removed. You can access its elements in constant time by their index in the array. However, inserting or removing an element infers shifting all consequent elements which may be slow if the array is huge and the inserted or removed element is close to the beginning of the list.

LinkedList is a doubly-linked list: single elements are put into Node objects that have references to previous and next Node. This implementation may appear more efficient than ArrayList if you have lots of insertions or deletions in different parts of the list, especially if the list is large.

In most cases, however, ArrayList outperforms LinkedList. Even elements shifting in ArrayList, while being an O operation, is implemented as a very fast System.arraycopy call. It can even appear faster than the LinkedLists O insertion which requires instantiating a Node object and updating multiple references under the hood. LinkedList also can have a large memory overhead due to a creation of multiple small Node objects.

You May Like: Java Crash Course For Interview

Question 3: Stock Buy Sell To Maximize Profit

Given an array of integers representing stock price on single day, find max profit that can be earned by 1 transaction.So you need to find pair where buyDay < = sellDay and it should maximise the profit.For example :

Solution :

Question : How To Find Duplicate Characters In String In Java

Solution: Here is a solution to find duplicate characters in String.

Don’t Miss: How To Answer Project Management Interview Questions

List The Types Of Trees

• The General Tree

A tree is referred to as a generic tree if its hierarchy is not constrained. In the General Tree, each node can have an endless number of offspring, and all other trees are subsets of the tree.

• The Binary Tree

The binary tree is a type of tree in which each parent has at least two offspring. The children are referred to as the left and right youngsters. This tree is more popular than most others. When specific limitations and features are given to a Binary tree, various trees such as AVL tree, BST , RBT tree, and so on are also utilized.

• Tree of Binary Search

Binary Search Tree is a binary tree extension that includes numerous optional constraints. In BST, a node’s left child value should be less than or equal to the parent value, while the correct child value should always be higher than or equal to the parent’s value.

• The AVL Tree

The AVL tree is a self-balancing binary search tree. The term AVL is given in honor of the inventors Adelson-Velshi and Landis. This was the first tree to achieve dynamic equilibrium. Each node in the AVL tree is assigned a balancing factor based on whether the tree is balanced or not. The node kids have a maximum height of one AVL vine.

• Red and Black Tree

• The N-ary Tree

In this sort of tree with a node, N is the maximum number of children. A binary tree is a two-year tree since each binary tree node has no more than two offspring. A full N-ary tree is one in which the children of each node are either 0 or N.

Right Rotate The Array By One Index

Problem Statement

Create the method void rotateArray which takes an array of integers and rotates the position of each element one to the right. The right-most element will rotate to become the left-most element.

Solution and Explanation:

class CheckRotateArray    arr = lastElement   } //end of rotateArray  public static void main      System.out.print     for     System.out.println     rotateArray     System.out.print     for   }} 

If the list is empty, the situation is exactly like insertion at the head.

Otherwise, we can use a loop to reach the tail of the list and set our new node as the nextNode of the last node.

Read Also: What Kind Of Questions Are Asked In A Job Interview

What Are The Applications Of Data Structures

Some practical applications of data structures are:

• Storing data in a tabular form. For example, the contact details of an individual can be stored in arrays.
• Arrays are widely used in image processing and speech processing.
• Music players and image sliders use linked lists to switch between items.
• A queue is used for job scheduling – the arrangement of data packets for communication.
• A tree is used by the decision tree algorithm in machine learning.
• Technologies like blockchain and cryptography are based on hashing algorithms.
• Matrices are widely used to represent data and plot graphs, and perform statistical analysis.

What Is The Difference Between File Structure And Storage Structure

Difference between file structure and storage structure:

The main difference between file structure and storage structure is based on memory area that is being accessed.

Storage structure: It is the representation of the data structure in the computer memory.

File structure: It is the representation of the storage structure in the auxiliary memory.

Recommended Reading: What Should I Say In An Exit Interview

The Best Data Structures And Algorithms Interview Questions And Answers In Java

Q. What do you understand by Data Structure?Answer:

A data structure can be considered as a way of organizing the data for efficient utilization.For example, Binary trees are particularly suited for database implementation, while compiler implementations are usually done using hash tables to look up identifiers.

Q. What are linear and non-linear types of data Structures? Also, How is an Array different from Linked List?

Answer:Linear: A data structure is called as linear if its elements form a sequence or a linear list such as Array, Linked List, Stacks, and Queues.Non-Linear: A data structure is called as non-linear if traversal of nodes is of nonlinear nature such as Graphs and Trees.Difference between array and linked list are the following:

• The size of the arrays is fixed always, Linked Lists size is not fixed.
• Insert and delete in an array is an expensive process, whereas the same can be easily done in Linked Lists.
• Accessing an element randomly is not possible in case of Linked Listed, but possible in an array.
• Extra memory space for a pointer is needed with each element of the Linked list, arrays dont have pointers.
• Arrays have better cache locality mechanism that can make a big difference in performance.

Q. Why do we need to do algorithm analysis?Answer:

A problem can be solved in more than one way. So, many solution algorithms can be derived for a given problem. We analyze available algorithms to find and implement the best suitable algorithm.

Answer:

Answer:

Data Structures In Java Part I

Basic algorithms and data structures: AVL tree, binary search tree, array, linked list, stack, queue and hashmapsWhat youll learn

• grasp the fundamentals of algorithms and data structures
• develop your own algorithms that best fit to the personal need
• detect non-optimal code snippets
• get to know basic complexity related definitions
• get to know linked lists
• get to know arrays
• get to know balanced trees: AVL trees and red-black trees
• get to know hash tables

Requirements

• Eclipse or other IDE

Descriptiondata structures and algorithmsJava14 hoursSection 1:

• data structures and abstract data types
• what are arrays and linked lists
• arrays and linked list related interview questions

Section 2:

• what are stacks and queues
• heap memory and stack memory

Section 3:

• balanced search trees: AVL trees and red-black trees
• splay trees
• B-trees and their applications in memory

• what are hashing and hashtables
• what are hash-functions
• how to achieve O running time complexity

Section 5 :

• Fenwick trees
• binary indexed tree implementation

Eclipselets get startedWho this course is for:

• This course is meant for everyone from scientists to software developers who want to get closer to algorithmic thinking in the main

• Learn all features of Angular

Don’t Miss: How To Study For A Job Interview

Question 3: Largest Sum Contiguous Subarray

Largest sum contiguous subarray is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.For example :

Solution :

Top 100+ Java Coding Interview Questions

I have been posting data structure and coding interview questions on various topics such as Array, Queue, Stack, Binary tree, LinkedList, String, Number, ArrayList, etc. So I am consolidating a list of java coding interview questions to create an index post. I will keep adding links to this post whenever I will add new java coding interview question.

These are frequently asked java coding interview questions.

If you want to practice and improve data structure and algorithm programs, this post will be very helpful to you. I will recommend you to try it yourself first and then check the solution.

Recommended Reading: When To Email After Interview

Data Structures And Algorithms Interview Questions In Java

Q: What Are The Types Of Algorithm Ans:

A step-by-step technique for solving a problem is known as an algorithm. In terms of both time and space, a good algorithm should be optimized. Different types of problems have different algorithms to be tackled in the most efficient manner.

Although there are various kinds of algorithms, the following are the most significant and fundamental:

• Recursive Algorithm

Also Check: How To Ace A Nursing Interview

Calculate The Address Of A Random Element Present In A 2d Array Given Base Address As Ba

Row-Major Order: If array is declared as a where m is the number of rows while n is the number of columns, then address of an element a of the array stored in row major order is calculated as,

Address = B. A. + * size

Column-Major Order: If array is declared as a where m is the number of rows while n is the number of columns, then address of an element a of the array stored in column major order is calculated as

Address = +i)*Size + BA.

What Is A Doubly

A doubly linked list is one of the complex types of the linked list, where a node contains a pointer to the previous and the next node in the sequence. It consists of three parts: node data, a pointer to the next node in sequence , a pointer to the previous node

The below diagram depicts the working of doubly linked list:

Some of the real-time applications where doubly-linked lists used are navigation systems and browsers .

Also Check: How To Prepare For A Customer Service Representative Interview

What Are Asymptotic Notations

Asymptotic Notation represents an algorithm’s running time – how long an algorithm takes with a given input, n. Big O, large Theta , and big Omega are the three distinct notations. When the running time is the same in all circumstances, big- is used, big-O for the worst-case running time, and big- for the best case running time.

Binary Tree Coding Interview Questions

So far, we have looked at only the linear data structure, but all information in the real world cannot be represented in a linear fashion, and thats where tree data structure helps.

The tree data structure is a data structure that allows you to store your data in a hierarchical fashion. Depending on how you store data, there are different types of trees, such as a binary tree, where each node has, at most, two child nodes.

Along with its close cousin binary search tree, its also one of the most popular tree data structures. Therefore, you will find a lot of questions based on them, such as how to traverse them, count nodes, find depth, and check if they are balanced or not.

A key point to solving binary tree questions is a strong knowledge of theory, e.g. what is the size or depth of the binary tree, what is a leaf, and what is a node, as well as an understanding of the popular traversing algorithms, e.g. pre-, post-, and in-order traversal.

Here is a list of popular binary tree-based coding questions from software engineer or developer job interviews:

Read Also: How To Interview A Therapist

What Operations Can Be Performed On Queues

• enqueue adds an element to the end of the queue
• dequeue removes an element from the front of the queue
• init is used for initializing the queue
• isEmpty tests for whether or not the queue is empty
• The front is used to get the value of the first data item but does not remove it
• The rear is used to get the last item from a queue

Data Science with Python

List A Few Queue Data Structure Applications

As the name suggests, the queue is used whenever you need to manage a group of objects in the order FIFO. A few of the queue data structure applications are listed below:

• Serving requests on a single shared resource, like CPU task scheduling, printer, etc.
• Handling interruptions in real-time systems.
• Buffers in apps like CD player and MP3 media players
• In maintaining a playlist in media players, like adding or removing songs.

Don’t Miss: What Motivates You Interview Question

Write A Recursive C Function To Calculate The Height Of A Binary Tree

To find the height using recursion, we find the maximum of the height of subtrees on the left and right sides and then add it with the root.

staticint counter = 0 intcountnodesreturn counter }

28. How is memory affected by signed and unsigned numbers?

For signed numbers, the first bit is reserved for indicating whether the number is positive or negative. Hence, it has one bit less for storing the value. Unlike signed numbers, unsigned numbers have all the bits available for storing the number.

The effect of the aforementioned can be seen in the value range available to signed and unsigned numbers. While an unsigned 8-bit number can have a range of 0 to 255, an 8-bit signed number has a range varying from -128 to 127.

Java Data Structures Interview Questions On Linked Lists

You May Like: What Are Questions You Get Asked At A Job Interview