Last Updated on March 12, 2022 by Ria Pathak
1. Write a program to swap two numbers in Java.
Ans. Two ways to do this -with third variable and without third variable.
public static void swapNumberswithtemp(int a, int b) { //using 3rd variable
int temp = a;
a = b;
b = temp;
}
public static void swapNumberswithouttemp(int a, int b) {//without using 3rd variable
b = b + a;
a = b - a;
b = b - a;
}
public static void main(String[] args) {
int a = 10;
int b = 20;
swapNumbers(a, b);
System.out.printf("%d %d", a, b);
}2. Given an array of integers, return indices of the two numbers such that they add up to a specific target.
Ans. This is a very popular questions for various interviews. The idea is to use two pointers technique after sorting the array.
public static int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length < 2) return new int[0];
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
return new int[]{map.get(nums[i]), i};
} else {
map.put(target - nums[i], i);
}
}
return new int[0];
}3. Write a function that reverse a string. Do not use any extra space for the solution.
Ans. The idea to swap the corresponding element from the right side for every element in left of the middle.
public void reverseString(char[] s) {
int i= 0;
int j= s.length-1;
while (i<= j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
I +=1;
J -=1;
}
}4. Write a function to check whether a number is prime or not.
Ans. The algorithm is to check for all the numbers below it if any such number divides the given number then false else true.
public static boolean isPrime(int n) {
if (n == 0 || n == 1) {
return false;
}
if (n == 2) {
return true;
}
for (int i = 2; i <= n / 2; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int n;
Scanner sc =new Scanner(System.in);
n = sc.nextInt();
System.out.println(isPrime(n));
}-
Check If a number is palindrome or not.
Ans. A number is palindrome if the reverse of the number is equal to the given number.boolean checkPalindromeString(String input) { boolean result = true; int length = input.length(); for(int i=0; i < length/2; i++) { if(input.charAt(i) != input.charAt(length-i-1)) { result = false; break; } } return result; }6. Can you Implement a Binary Search Algorithm?
Ans. Binary Search is the most popular and efficient searching algorithm when the data is sorted. The idea is after sorting we start our pointers from two ends, and calculate the mid element, if our mid element if greater than the searching element then surely the element lies in the left half otherwise it lies in the right half and accordingly, we will change our low=mid+1 or high=mid-1.public static int binarySearch(int arr[], int low, int high, int key) { int mid = (low + high) / 2; while (low <= high) { if (arr[mid] < key) { low = mid + 1; } else if (arr[mid] == key) { return mid; } else { high = mid - 1; } mid = (low + high) / 2; } if (low > high) { return -1; } return -1; }7. Do you know how to find GCD of two numbers?
Ans.public static void main(String args[]) { Scanner in = new Scanner(System.in); BigInteger a = in.nextBigInteger(); BigInteger b = in.nextBigInteger(); in.close(); System.out.println(finDGCD(a, b)); } public static BigInteger findGCD(BigInteger a, BigInteger b) { //if(a==0)return b; //else return findGCD(b,a%b); return a.compareTo(BigInteger.ZERO) == 0 ? b : b.compareTo(BigInteger.ZERO) == 0 ? a : findGCD(b, a.mod(b)); }8. Suppose you are given an array of characters, write a program to remove duplicates from it.
Ans. The idea is to sort the array and remove every duplicate elements as then they will be side by side.public static void main(String[] args) { Object[] arr = { 'a', 'a', 'd', 'c', 'b', 'c', 'e', 'd' }; System.out.println( Arrays.toString(removeDuplicates(arr))); } public static Object[] removeDuplicates(Object[] arr) { Arrays.sort(arr); Object[] result = new Object[arr.length]; Object previous = arr[0]; result[0] = previous; for (int i = 1; i < arr.length; i++) { Object ch = arr[i]; if (previous != ch) { result[i] = ch; } previous = ch; } return result; }9. Given an array of n integers, are there elements a, b, c in array such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Ans. This is a little modification of 2 sum problem, and we just need an extra loop for the new target which can be considered as a+b= -c, -c becomes our new target.public static List<List<Integer>> threeSum(int[] nums) { if (nums == null || nums.length < 3) return new ArrayList<>(); Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); int lo, hi, target; for (int i = 0; i < nums.length - 2; i++) { if (nums[i] > 0) break; if (i == 0 || nums[i] != nums[i - 1]) { lo = i + 1; hi = nums.length - 1; target = 0 - nums[i]; while (lo < hi) { if (nums[lo] + nums[hi] < target) { lo++; } else if (nums[lo] + nums[hi] > target) { hi--; } else { res.add(Arrays.asList(nums[i], nums[lo], nums[hi])); while (lo < hi && nums[lo] == nums[lo + 1]) lo++; while (lo < hi && nums[hi] == nums[hi - 1]) hi--; lo++; hi--; } } } } return res; }10. Do you know about Merge Sort? Implement the Merge Sort Algorithm and also describe its time complexity.
Ans. Merge Sort is basically a divide and conquer algorithm in which we divide the array into two parts and call the recursive function to return us the sorted parts and finally we merge these two sorted parts to get our final sorted array. This is not a in place algorithm although it is a stable algorithm.private int arrSize; private int [] arrAux; private int [] arrInput; public MergeSort(int [] arrInput){ this.arrInput = arrInput; arrSize = arrInput.length; arrAux = new int [arrSize]; } public int[] mergeSorting(){ sort(0,arrSize-1); return arrInput; } public void sort(int low, int high){ if(low<high){ int mid = low+((high-low))/2; sort(low,mid); sort(mid+1,high); merge(low, mid, high); } } public void merge(int low, int mid, int high){ //copy the entire array in the Auxilary array for(int i=low;i<=high;i++){ arrAux[i] = arrInput[i]; } int i = low; int j = mid+1; int k = low; while(i<=mid && j<=high){ if(arrAux[i]<=arrAux[j]){ arrInput[k]=arrAux[i]; i++; } else{ arrInput[k]=arrAux[j]; j++; } k++; } while(i<=mid){ arrInput[k]=arrAux[i]; i++; k++; } while(j<=high){ arrInput[k]=arrAux[j]; j++; k++; } } public void displayArray(int [] b){ for(int i=0;i<b.length;i++){ System.out.print(" " + b[i]); } } public static void main(String[] args){ int [] a = {2,1,6,3,9,4,5,10}; MergeSort m = new MergeSort(a); int [] b = m.mergeSorting(); m.displayArray(b); }Time Complexity:O(nlogn)
Space Complexity:O(n)