5 + Interview Questions in Array Coding Interview Questions in Array Interview Questions

1.	Find out smallest and largest number in a given Array?
Answer» Approach: For storing the largest and smallest numbers create two variables named smallest and largest. Assign Integer.MAX_VALUE to the variable smallest Assign Integer.MIN_VALUE to the variable largest In each traversal of for loop, we will compare the current element with the largest and smallest number and update the value accordingly. If a number is larger than the largest, then it can not be smaller than the smallest, therefore, we can skip if the first condition holds. import java.util.;public class InterviewBit{ public static VOID main(String args[]) { int[] inputArray = {10,20, 22, 30, 77}; int largest = inputArray[0]; int smallest = inputArray[0]; for( int number : inputArray ) { if(number > largest) { largest = number; } else if (smallest > number) { smallest = number; } } System.out.println("Largest and Smallest numbers are " + largest +" "+smallest); }} Output :* Largest and Smallest numbers are 77 10Conclusion In this article, we have covered the most IMPORTANT and commonly asked interview questions based on arrays. To make the most of all the knowledge AVAILABLE, it is absolutely necessary to practice data structures and algorithms as much as POSSIBLE. You should keep in mind certain properties of array data structures, for example, array index starts at 0, the elements of an array are stored in contiguous MEMORY locations, etc. Additional Interview Resources: Data Structure Interview Questions Algorithm Interview Questions DSA Tutorial

1.

Find out smallest and largest number in a given Array?

Answer»

Approach:

For storing the largest and smallest numbers create two variables named smallest and largest.
Assign Integer.MAX_VALUE to the variable smallest
Assign Integer.MIN_VALUE to the variable largest
In each traversal of for loop, we will compare the current element with the largest and smallest number and update the value accordingly.
If a number is larger than the largest, then it can not be smaller than the smallest, therefore, we can skip if the first condition holds.

import java.util.*;public class InterviewBit{ public static VOID main(String args[]) { int[] inputArray = {10,20, 22, 30, 77}; int largest = inputArray[0]; int smallest = inputArray[0]; for( int number : inputArray ) { if(number > largest) { largest = number; } else if (smallest > number) { smallest = number; } } System.out.println("Largest and Smallest numbers are " + largest +" "+smallest); }}

Output :

Largest and Smallest numbers are 77 10Conclusion

In this article, we have covered the most IMPORTANT and commonly asked interview questions based on arrays. To make the most of all the knowledge AVAILABLE, it is absolutely necessary to practice data structures and algorithms as much as POSSIBLE. You should keep in mind certain properties of array data structures, for example, array index starts at 0, the elements of an array are stored in contiguous MEMORY locations, etc.

Additional Interview Resources:

Data Structure Interview Questions
Algorithm Interview Questions
DSA Tutorial

Discussion

2.	Check for balanced parenthesis in an expression using constant space.
Answer» You will be GIVEN string str containing characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, your task is to determine whether the brackets are balanced or not. These conditions should satisfy for balanced brackets: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Approach: To keep track of two brackets to be compared keep two variables i and j. Maintain a count variable and increment its VALUE on encountering an opening bracket and DECREMENTS on encountering a closing bracket. Assign values of j and i as- j = i, i = i + 1 and counter++ when opening brackets are encountered. When Closing brackets are encountered do count– i,e decrement its value and compare brackets at i and j, If brackets at i and j match, then SUBSTITUTE ‘#’ in the string at ith and jth position. Increment i and decrement j until non ‘#’ value is encountered or j ≥ 0. If brackets at i and j do not match, return false. If count != 0, return false. import java.util.*; class InterviewBit{ static String str = "[[]][]()"; static int Count = 0; static int i = 0; static int j = -1; static int helperFunc(char compare) { Count--; char temp = str.charAt(j); if (j > -1 &AMP;& temp == compare) { str = str.replace(str.charAt(i),'#'); str = str.replace(str.charAt(j),'#'); temp = str.charAt(j); while (j >= 0 && temp == '#') j--; i++; return 1; } else return 0; } static boolean isValid() { if (str.length() == 0) return true; else { int result; while (i < str.length()) { char temp = str.charAt(i); if(temp=='}') { result = helperFunc('{'); if (result == 0) { return false; } } else if(temp == ')') { result = helperFunc('('); if (result == 0) { return false; } } else if(temp == ']') { result = helperFunc('['); if (result == 0) { return false; } } else { j = i; i++; Count++; } } if (count != 0) return false; return true; } } public static void main(String args[]) { if (isValid()) System.out.println("No"); else System.out.println("Yes"); }}

2.

Check for balanced parenthesis in an expression using constant space.

Answer»

You will be GIVEN string str containing characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, your task is to determine whether the brackets are balanced or not.
These conditions should satisfy for balanced brackets:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.

Approach:

To keep track of two brackets to be compared keep two variables i and j.
Maintain a count variable and increment its VALUE on encountering an opening bracket and DECREMENTS on encountering a closing bracket.
Assign values of j and i as- j = i, i = i + 1 and counter++ when opening brackets are encountered.
When Closing brackets are encountered do count– i,e decrement its value and compare brackets at i and j,
- If brackets at i and j match, then SUBSTITUTE ‘#’ in the string at ith and jth position. Increment i and decrement j until non ‘#’ value is encountered or j ≥ 0.
- If brackets at i and j do not match, return false.
If count != 0, return false.

import java.util.*; class InterviewBit{ static String str = "[[]][]()"; static int Count = 0; static int i = 0; static int j = -1; static int helperFunc(char compare) { Count--; char temp = str.charAt(j); if (j > -1 &AMP;& temp == compare) { str = str.replace(str.charAt(i),'#'); str = str.replace(str.charAt(j),'#'); temp = str.charAt(j); while (j >= 0 && temp == '#') j--; i++; return 1; } else return 0; } static boolean isValid() { if (str.length() == 0) return true; else { int result; while (i < str.length()) { char temp = str.charAt(i); if(temp=='}') { result = helperFunc('{'); if (result == 0) { return false; } } else if(temp == ')') { result = helperFunc('('); if (result == 0) { return false; } } else if(temp == ']') { result = helperFunc('['); if (result == 0) { return false; } } else { j = i; i++; Count++; } } if (count != 0) return false; return true; } } public static void main(String args[]) { if (isValid()) System.out.println("No"); else System.out.println("Yes"); }}

Discussion

3.	Two sum of an array: In this question you will be given an array arr and a target. You have to return the indices of the two numbers such that they add up to target.
Answer» In this question, you will be given an array arr and a target. You have to return the indices of the two NUMBERS such that they add up to the target. Approach: So the easiest and most efficient solution is using a HashMap. We have to iterate through all the elements of the array and if (target-num) is present in the array then return {lower index, higher index} else PUSH the value at arr[i] and the index i in the hashmap. public class InterviewBit { public int[] twoSum(int[] arr, int target) { HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>(); for(int i = 0; i <arr.length; i++){ Integer diff = (Integer)(target - arr[i]); if(hash.containsKey(diff)){ int TORETURN[] = {hash.get(diff)+1, i+1}; return toReturn; } hash.put(arr[i], i); } return NULL; }} The time Complexity for this approach will be O(n).

3.

Two sum of an array: In this question you will be given an array arr and a target. You have to return the indices of the two numbers such that they add up to target.

Answer»

In this question, you will be given an array arr and a target. You have to return the indices of the two NUMBERS such that they add up to the target.

Approach:

So the easiest and most efficient solution is using a HashMap. We have to iterate through all the elements of the array and if (target-num) is present in the array then return {lower index, higher index} else PUSH the value at arr[i] and the index i in the hashmap.

public class InterviewBit { public int[] twoSum(int[] arr, int target) { HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>(); for(int i = 0; i <arr.length; i++){ Integer diff = (Integer)(target - arr[i]); if(hash.containsKey(diff)){ int TORETURN[] = {hash.get(diff)+1, i+1}; return toReturn; } hash.put(arr[i], i); } return NULL; }}

The time Complexity for this approach will be O(n).

Discussion

4.	How do you rotate an array?
Answer» You will be given an input number N and N numbers following it as the input. You are ALSO given an integer K which represents how many times you have to rotate the array. Rotate the array K values to the right if K is positive and K values to the left if K is negative. If K=0, do not rotate the array. The figure shows how the rotating array will look if k=2. Approach: If the value of K is positive then do K=K%N where N is the LENGTH of the input array for eg: if k =10 and N=3 then k will become 1 which means rotating the array 10 times is EQUIVALENT to rotating the array 1 time. Similarly, If the value of K is negative, K=K%N + N. Reverse the first part of the array i.e. from 0 to N-K-1 and the second part from N-K to N-1 separately. Reverse the entire array i.e. from 0 to N-1. K determines how the array will be rotated. Code: import java.io.;import java.util.;public class Main { public static void display(int[] arr) { StringBuilder sb = new StringBuilder();for (int val : arr) { sb.append(val + " "); } System.out.println(sb); } public static void reverse(int[] arr, int li, int ri) { while (li < ri) { int t = arr[li]; arr[li] = arr[ri]; arr[ri] = t; li++; ri--; } } public static void rotate(int[] arr, int k) { k = k % arr.length; if (k < 0) { k += arr.length; } reverse(arr, 0, arr.length - k - 1); reverse(arr, arr.length - k, arr.length - 1); reverse(arr, 0, arr.length - 1); } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(br.readLine()); } int k = Integer.parseInt(br.readLine()); rotate(arr, k); display(arr); }

4.

How do you rotate an array?

Answer»

You will be given an input number N and N numbers following it as the input. You are ALSO given an integer K which represents how many times you have to rotate the array. Rotate the array K values to the right if K is positive and K values to the left if K is negative. If K=0, do not rotate the array.

The figure shows how the rotating array will look if k=2.

Approach:

If the value of K is positive then do K=K%N where N is the LENGTH of the input array for eg: if k =10 and N=3 then k will become 1 which means rotating the array 10 times is EQUIVALENT to rotating the array 1 time.
Similarly, If the value of K is negative, K=K%N + N.
Reverse the first part of the array i.e. from 0 to N-K-1 and the second part from N-K to N-1 separately.
Reverse the entire array i.e. from 0 to N-1. K determines how the array will be rotated.

Code:

import java.io.*;import java.util.*;public class Main { public static void display(int[] arr) { StringBuilder sb = new StringBuilder();for (int val : arr) { sb.append(val + " "); } System.out.println(sb); } public static void reverse(int[] arr, int li, int ri) { while (li < ri) { int t = arr[li]; arr[li] = arr[ri]; arr[ri] = t; li++; ri--; } } public static void rotate(int[] arr, int k) { k = k % arr.length; if (k < 0) { k += arr.length; } reverse(arr, 0, arr.length - k - 1); reverse(arr, arr.length - k, arr.length - 1); reverse(arr, 0, arr.length - 1); } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(br.readLine()); } int k = Integer.parseInt(br.readLine()); rotate(arr, k); display(arr); }

Discussion

5.	How do you sort an array of 0 and 1?
Answer» You are given an array of 0s and 1s in random order and you have to sort this array i.e Segregate 0s on the left side and 1s on the right side of the array. Approach: MAINTAIN two INDEXES and INITIALIZE the first index as 0 and second index n-1. Now follow the following algorithm until left < right a) Keep incrementing left index while there are 0s at it B) Keep decrementing index right while there are 1s at it c) Whenever left < right, exchange arr[left] and arr[right] class InterviewBit{VOID segregatearray(int arr[], int size){ int left = 0, right = size - 1; while (left < right) { while (arr[left] == 0 && left < right) left++; while (arr[right] == 1 && left < right) right--; if (left < right) { arr[left] = 0; arr[right] = 1; left++; right--; } }}public static void main(String[] args){ Segregate seg = new Segregate(); int arr[] = new int[]{0, 1, 0, 1, 1, 1}; int i, arr_size = arr.length; seg.segregatearray(arr, arr_size); System.out.print("Array after segregation is "); for (i = 0; i < 6; i++) System.out.print(arr[i] + " ");}} Time Complexity : O(n)

5.

How do you sort an array of 0 and 1?

Answer»

You are given an array of 0s and 1s in random order and you have to sort this array i.e Segregate 0s on the left side and 1s on the right side of the array.

Approach:

MAINTAIN two INDEXES and INITIALIZE the first index as 0 and second index n-1.
Now follow the following algorithm until left < right
a) Keep incrementing left index while there are 0s at it
B) Keep decrementing index right while there are 1s at it
c) Whenever left < right, exchange arr[left] and arr[right]

class InterviewBit{VOID segregatearray(int arr[], int size){ int left = 0, right = size - 1; while (left < right) { while (arr[left] == 0 && left < right) left++; while (arr[right] == 1 && left < right) right--; if (left < right) { arr[left] = 0; arr[right] = 1; left++; right--; } }}public static void main(String[] args){ Segregate seg = new Segregate(); int arr[] = new int[]{0, 1, 0, 1, 1, 1}; int i, arr_size = arr.length; seg.segregatearray(arr, arr_size); System.out.print("Array after segregation is "); for (i = 0; i < 6; i++) System.out.print(arr[i] + " ");}}

Time Complexity : O(n)

Discussion

Explore topic-wise InterviewSolutions in Current Affairs.

Find out smallest and largest number in a given Array?

Check for balanced parenthesis in an expression using constant space.

Two sum of an array: In this question you will be given an array arr and a target. You have to return the indices of the two numbers such that they add up to target.

How do you rotate an array?

How do you sort an array of 0 and 1?