Arrays

Question 1

how to insert an element in a array ?

Answer 1

there are two ways to insert an element in a array.
1. add an element ‘element’ at k position. In this case you have to first check if the index k is smaller than the length of the array. then you can easily add the element at arr[k] = element; after shifting all the elements to the right.
2. add an element at the end of the array: In this case, first check if the postion at which you want to add the element is not greater than the length of the array. then just add the element at arr[pos] = element;

Question 2

How to rotate an array. Explain the approach using temp array.

Answer 2

1. first, make a temp array of size equal to the original array.
2. Then, copy all the elements from the d(the index from which to rotate the array) to n-1 in the temp array and also keep an variable k to keep track of the last index in the temp array.
3. Now only d elements are left in the original array. copy all the leftout elements to the temp array from the index 0 to d. add elements from the index k to the end of the original array.
4. copy the elements from temp array to original array if you want or just return the temp array.

time: O(n)
space: O(n)

Question 3

how to rotate an array by rotating elements one by one ?

Answer 3

1. In this approach, first you have to keep an variable to track the first element in the array and then left shift all the elements of the array.
2. Then, simply add the variable to the last of the array.
3. Repeat this whole process for d times.
4. it will take two nested loops to work. Outer loop will keep the track of d and inner loop is for the shifting.

time: O(n*d)
space: O(1)

Question 4

how to rotate an array using the juggling algorithm ?

Answer 4

1. Make a reverse method that can reverse the elements of an array. This method takes three arguments:
   
   • the array on which the reverse operation to be performed
   • The starting index
   • The ending index
2. Now, first reverse the elements starting from 0 to d-1.
3. Then, reverse the elements from d to n-1.
4. Lastly, reverse the whole array i.e, from 0 to n-1.
   The final array is the result after rotating the array by d elements.

time: O(n)
space: O(1)

Question 5

how to reverse an array iteratively ?

Answer 5

1) Initialize start and end indexes as
start = 0, end = N-1
2) In a loop, swap arr[start] with arr[end]
and change start and end as follows :
start = start + 1,
end = end – 1

time: O(N)
space: constant

Question 6

how to reverse an array recursively ?

Answer 6

1) Initialize start and end indexes as
start = 0, end = n-1
2) Swap arr[start] with arr[end]
3) Recursively call reverse for rest of the array. for eg.
return reverse(arr, start + 1, end - 1)

time: O(N)
space: constant

Question 7

what is the purpose of using sliding window technique ? or in which situation we use this technique ?

Answer 7

This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.

Question 8

how sliding window technique works ?

Answer 8

This technique works in 3 simple steps:
I am demostrating this technique by solving an max sum for k consecutive elements in a array problem.
In this problem, k is the length of sub array for which we have to calculate the sum of elements.
The following steps demostrate the sliding window technique-
1. first, we will calculate the sum of first k elements for which we will iterate from 0 to k and store the sum of elements in window_sum.
2. Then, we will make an element maxSum for tracking the max sum of elements in the array. Now, we will remove the last element after shifting the window to the left and add the latest element to the sum. The current sum would look something like this
currentSum += arr[i] + arr[i -k]
3. Lastly, we will compare the current sum with the max sum that we were keeping for checking the max sum of consecutive elements in an array.

time: O(n)
space: constant

Question 9

How to find the second largest element in an array ?

Answer 9

Firstly, we should find the largest element in the array and then find the second largest element by just excluding the largest element. we can find the largest and second largest in the same traversal of the array.

The condition to find the second largest is:
if (inputArray[index] != largest)

Question 10

How to move zeros to the end in an array ?

Answer 10

To move zeros to the end in an array, we can use two pointer approach
* First pointer will keep track of the non zero elements present in the array and increment only when it encounters a non zero element.
* Second pointer will simply traverse the array and will help in overriding the zero elements to the non zero elements.
* After the whole traversal, the first pointer will become the 1st index for the zero elements present in the array, so we will simply override all the remaining elements by zero.

time: O(N)
space: constant

Question 11

how to insert an element in the middle of an array ?

Answer 11

To insert an element in the middle of an array, first you have to move all the elements to the right(only if the capacity is not full otherwise just return the original array)

for moving the elements to the right, traverse the array in reverse direction and override the right element to the left element and stop the iteration at the position on which the new element will be inserted

inserting at the end, time: 1
inserting at the begining, time: n
in general insertion time: n

Question 12

what is the time complexity of insert at the end for a dynamic sized array ?

Answer 12

In general, it is O(1)

Question 13

time complexity for inserting in an array ?

Answer 13

O(N)

Question 14

time complexity for searching in an unsorted array ?

Answer 14

O(N)

Question 15

Time complexity for searching in an sorted array ?

Answer 15

O(logn)

Question 16

time complexity for deletion in an array ?

Answer 16

O(N)

Question 17

time complexity to get and update an ith element in an array ?

Answer 17

O(1)

Question 18

time complexity for insertion and deletion from the end in an array ?

Answer 18

O(1)

Question 19

how to find immediate greater element than x in an array ?

Answer 19

1. first, we make a variable called currentImmediateGreater and set a large value to it.
2. Then we will iterate the whole array and check whether currentImmediateGreater is greater that ith element as well as x(the element to check). The condition will look something like this:

if (inputArray[i] > x 
&& currentImmediateGreater > inputArray[i])

After checking this condition, we will simple re initialize the currentImmediateGreater with inputArray[i] found.

Question 20

find the majoritGiven an array arr[] of size N and two elements x and y, use counter variables to find which element appears most in the array. If both elements have the same frequency, then return the smaller element.
Note: We need to return the element, not its count.y between two elements x and y

Answer 20

1. First, make a counter variable to count the number of occurances for both the elements in the array
2. if x is encountered then increament the counter and if y is encountered then decreament the counter.
3. if counter is positive then, it means x occured more than y and vice versa.
4. if counter is zero then, it means both the elements have same occurance and we will return the smallest among them

Question 21

how to find max and min element in a array ?

Answer 21

1. first, assume arr[0] as the max or min element
2. traverse the array and compare the current element with the max element, if the current element is greater than maxElement then, assign maxElement with the current element
3. do the same for minElement

Question 22

how to reverse an array without using temporary array?

Answer 22

1. for this we will first make a temporary variable temp and use it swap the elements in the array
2. we will traverse the array to it’s half size and keep swapping the elements until we reach the half the length

Question 23

how to check if a char array is palindrome or not using recursion ?

Answer 23

There would be three conditions to check whether the array is palindrome or not.

1. check if there is only one character in the array, it means it is palindrome
2. check if the first and last character matches or not, if not then it is not palindrome
3. check the substring or subarray by calling the method recusively as
   ~~~
   checkPalindrome(string[], start + 1, end - 1)
   ~~~