Arrays/Linked Lists

Question 1

What is array data structure? What are the applications of arrays?

Question 2

What is a linked list data structure? What are the applications for the Linked list?

Question 3

https://medium.com/javarevisited/20-array-coding-problems-and-questions-from-programming-interviews-869b475b9121

https://medium.com/techie-delight/linked-list-interview-questions-and-practice-problems-55f75302d613

https://medium.com/javarevisited/top-20-linked-list-coding-problems-from-technical-interviews-90b64d2df093

Question 4

Elaborate on different types of Linked List data structures?

Answer 4

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.

Question 5

Difference between Array and Linked List.

Question 6

Are linked lists considered non-linear or linear data structures?

Answer 6

linear

Question 7

What is a doubly-linked list used for?

Answer 7

Some of the real-time applications where doubly-linked lists used are navigation systems and browsers (when both back and front navigation is required).

Question 8

Can you change the size of the array once created?

Answer 8

no

Question 9

Can you store String in an array of Integer in Java? compile-time error or runtime exception?

Answer 9

This is a tricky question. The answer is both yes and no. You cannot store a string in an array of primitive int, it will result in a compile-time error as shown below, but if you create an array of Object and assign String[] to it and then try to store Integer object on it.

The compiler won’t be able to detect that and it will throw ArrayStoreExcpetion at runtime.

Question 10

Can you use Generics with an array?

Answer 10

no

Question 11

Where does an array stored in memory?

Answer 11

An array is created in the heap space of JVM memory. Since an array is an object in Java, even if you create an array locally inside a method or block, an object is always allocated memory from the heap

Question 12

How do you insert an element at the beginning of an array? What is the efficiency of this operation?

Insertion in middle? At end?

Deletion beginnng?middle? end?

Answer 12

O(N)

1. Create new array of size N+1, where N is size of original array.
2. Copy from originalArray[i] to newArray[i+1], where i = 0 to N-1
   Add new element at newArray[0]

Question 13

How do you search an element from an array? What is the efficiency of this operation?

write the code…

Answer 13

Binary Search - O(log N)
Linear Search - O(N)

Question 14

What are all the search algorithms?

Answer 14

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Shellsort
5. Quicksort
6. Radixsort

Question 15

How do you sort the elements in an array using Bubble Sort algorithm?

Answer 15

Approach
1. Start from the left of the array, i.e. index position 0.
2. Compare with the value at the next position, i.e. index 1. If the value at index 0 is greater than the value at index 1, then swap them.
3. Repeat step 2 for all adjacent pairs of values until the end of array is reached. At this point the last index of the array contains the highest value.
4. Repeat steps 1, 2, 3 until the whole array is sorted.

Performance - The time efficiency of Bubble sort operation in Big-O notation is O(N*2).

Question 16

How do you sort the elements in an array using Selection Sort algorithm?

Answer 16

1. Start from the left of the array, i.e. index position 0, and pass through all elements and select the smallest number. Swap the smallest number with number at position 0.
2. Start from the next position of the array, i.e. index position 1, and pass through all subsequent elements and select the smallest number. Swap the smallest number with number at position 1.

Repeat for all remaining elements, i.e. elements at index positions 2,3,4… until the last element of the array.

Performance - The time efficiency of Selection sort operation in Big-O notation is O(N*2).

Question 17

How do you sort the elements in an array of numbers using Insertion Sort algorithm?

Answer 17

1. Start by selecting one of the elements, usually an element in the middle of the array, as a marker element.
2. Sort all the elements to the left of the marker element.
3. Insert the marker element at appropriate position in the sorted array such that the sort order is maintained. Shift all elements with a value greater than the marker element one position to the right to make way for the marker element.
4. Repeat step 3 for each of the elements to the right of the marker element.

Performance - - The time efficiency of Insertion sort operation in Big-O notation is O(N*2).

Question 18

How do you sort the elements in an array of numbers using Quick Sort algorithm

Answer 18

Approach
1. Partition the array into left and right subarrays.
2. Call recursively to sort the left subarray
3. Call recursively to sort the right subarray.

Performance - - The time efficiency of Insertion sort operation in Big-O notation is O(N*logN)

Question 19

How do you insert an element at the beginning of a singly-linked linkedlist? What is the efficiency of this operation?

Insertion in middle? At end?

Deletion beginnng?middle? end?

Question 20

How do you insert an element at the beginning of a doubly-linked linkedlist? What is the efficiency of this operation?

Insertion in middle? At end?

Deletion beginnng?middle? end?