Write an algorithm to find N’th smallest element in an Unsorted Array.

Problem statement:
Given an array of positive and negative unsorted integer. Can you write an algorithm to find out the nth smallest element in the array.

1. public class NthSmallestElement {
2. public static void main(String[] args) {
3. int a[] = { 3, 4, 1, 105, 10, -10 };
4.   int thirdSmallest = 3;
5. int min= nthSmallestElement(a, thirdSmallest );
6. System.out.println(min);
7. }
8. public static int nthSmallestElement(int a[], int n) {
9. // Sort the given array
10. Arrays.sort(a);
11. // Return n'th element in the sorted array
12. return a[n - 1];
13. }
14. }

Output:

3

Write an algorithm to find N’th largest element in an Unsorted Array.

Problem statement:
Given an array of positive and negative unsorted integer. Can you write an algorithm to find out the nth largest element in the array.

1. public class NthLargestElement {
2. public static void main(String[] args) {
3. int a[] = { 3, 4, 1, 105, 10, -10 };
4.                 int thirdLargest = 3;
5. int max = nthLargestElement(a, thirdLargest);
6. System.out.println(max);
7. }
8. public static int nthLargestElement(int a[], int n) {
9. // Sort the given array
10. Arrays.sort(a);
11. // Return n'th element in the sorted array
12. return a[a.length - n];
13. }
14. }

Output:

4

Write an algorithm to find out the second smallest element in an array.

Problem statement:
Given an array of positive and negative unsorted integer. Can you write an algorithm to find out the second smallest element in the array.

1. public class SecondMinElement {
2. public static void main(String[] args) {
3. int a[] = { 3, 4, 1, 105, 10, -10 };
4. int firstMin = Integer.MAX_VALUE;
5. int secondMin = Integer.MAX_VALUE;
6. for (int i = 0; i < a.length; i++) {
7. if (a[i] < firstMin) {
8. secondMin = firstMin;
9. firstMin = a[i];
10. } else if (a[i] < secondMin) {
11. secondMin = a[i];
12. }
13. }
14. System.out.println("Second min element: " + secondMin);
15. }
16. }

Output:

Second min element: 1

Write an algorithm to find out the second largest element in an array.

Problem statement:
Given an array of positive and negative unsorted integer. Can you write an algorithm to find out the second largest element in the array.

1. public class SecondMaxElement {
2. public static void main(String[] args) {
3. int a[] = { 3, 4, 1, 105, 10, -10 };
4. int firstMax = Integer.MIN_VALUE, // large -ve value
5.   int secondMax = Integer.MIN_VALUE; // large -ve value
6. for (int i = 0; i < a.length; i++) {
7. if (a[i] > firstMax) {
8. secondMax = firstMax;
9. firstMax = a[i]; // a[0] becomes first max
10. } else if (a[i] > secondMax) {
11. secondMax = a[i];
12. }
13. }
14. System.out.println(secondMax);
15. }
16. }

Output:

10

How do you sort an array based on count of occurrences in ascending order

Problem statement:
Given an array of integer, you have to sort based on count of occurrences in ascending order?

1. import java.util.*;
2. public class SortArrayInDesc {
3.     public static void main(String[] args) {
4.         int a[] = {2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 1, 1, 1};
5.         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
6.         for (int i = 0; i < a.length; i++) {
7.             if (map.containsKey(a[i])) {
8.               map.put(a[i], map.get(a[i]) + 1);
9.             } else {
10.                 map.put(a[i], 1);
11.             }
12.         }
13.         ValueComparator<Integer, Integer> comparator = new ValueComparator<Integer, Integer>(map);
14.         TreeMap<Integer, Integer> sortedMap = new TreeMap<Integer, Integer>(comparator);
15.         sortedMap.putAll(map);
16.         ArrayList<Integer> lists = new ArrayList<Integer>();
17.         for (Integer i : sortedMap.keySet()) {
18.             for (int c = 0; c < sortedMap.get(i); c++) {
19.                 lists.add(i);
20.             }
21.         }
22.         System.out.println(lists.toString());
23.     }
24. }

1. import java.util.Comparator;
2. import java.util.Map;
3. public class ValueComparator<T1, T2 extends Comparable<T2>> implements Comparator<T1> {
4.     Map<T1, T2> map;
5.     public ValueComparator(Map<T1, T2> map) {
6.         this.map = map;
7.     }
8.     @Override
9.     public int compare(T1 k1, T1 k2) {
10.         T2 val1 = map.get(k1);
11.         T2 val2 = map.get(k2);
12. 
    
13.         return val1.compareTo(val2);
14.     }
15. }

Output:

[5, 1, 1, 1, 2, 2, 2, 2, 6, 6, 6, 6, 6, 4, 4, 4, 4, 4, 4]

How do you declare, instantiate, initialize and traverse an array?

Problem statement: How will you declare, initialize & traverse an array?

1. class TestArray {
2. public static void main(String args[]) {
3. int a[] = new int[5];// declaration and instantiation.
4. a[0] = 10;// initialization.
5. a[1] = 20;
6. a[2] = 70;
7. a[3] = 40;
8. a[4] = 50;
9. }
10. }

Find two pair of index or two sum of index in a list

Problem statement: Given an array of integers, return indices of two numbers such that they add up to a specific target.
e.g. - arr[] = { 4, 6, 5, -10, 8, 5, 20 };
target = 10
Output: [4,6] , [5,5], [-10,20]

Note: You may assume that each input would have exactly one solution, and you may not use the same element twice.

1. import java.util.HashMap;
2. import java.util.Map;
3. 
   
4. public class IndexOfTwoPair{
5. 
   
6. public static void main(String[] args) {
7. int a[] = { 4, 6, 5, -10, 8, 5, 20 };
8. int n = 10;
9. int idx[] = indexOfTwoSum(a, n);
10. for (int i : idx) {
11. System.out.print(i + " ");
12. }
13. }
14. public static int[] indexOfTwoSum(int nums[], int target) {
15. // array to return the result
16. int arr[] = new int[2];
17. 
    
18. // map for num and index pair
19. Map<Integer, Integer> map = new HashMap<Integer, Integer>();
20. 
    
21. // scan the array element
22. for (int i = 0; i < nums.length; i++) {
23. // check if map has an element which is equal to difference
24. // between target and current element
25. Integer val = map.get(target - nums[i]);
26. if (val == null) {
27. // no match found, add current element & index to map
28. map.put(nums[i], i);
29. } else {
30. // match found, update the index values
31. arr[0] = val;
32. arr[1] = i;
33. }
34. }
35. return arr;
36. }
37. }

Output:

3 6

Find Two Sum / Pair of Sum in list

Problem statement: Given an array of integers, return two numbers such that they add up to a specific target.
e.g. - arr[] = { 4, 6, 5, -10, 8, 5, 20 };
target = 10
Output: [4,6] , [5,5], [-10,20]

Note: You may assume that each input would have exactly one solution, and you may not use the same element twice.

// Method -I:

1. import java.util.HashMap;
2. import java.util.Map;
3. public class PairOfSumByMap {
4. public static void main(String[] args) {
5. int arr[] = { 4, 6, 5, -10, 8, 5, 20 };
6. int num = 10;
7. pairOfSum(arr, num);
8. }
9. public static void pairOfSum(int arr[], int num) {
10. Map<Integer, Integer> map = new HashMap<>();
11. for (int i = 0; i < arr.length; i++) {
12. if (map.containsKey(num - arr[i])) {
13. System.out.println("pair of num: [" + (num - arr[i]) + ", " + arr[i] + "]");
14. } else
15. map.put(arr[i], 0);
16. }
17. }
18. }

Time complexity: O(n) | reason - the array is traversed only once. so the time complexity is directly proportional to the size of the array i.e. O(n)

Space complexity: O(n) | reason -  O(1) + O(n) = O(n).O(1) for the variable and O(n) for the hashmap. for hashmap, with the increase of the number of entries, the hashmap's space will increase linearly. so space complexity of hashmap is O(n).

Output:
pair of num: [4, 6]
pair of num: [5, 5]
pair of num: [-10, 20]

// Method-II: it works only for SORTED arrays

1. import java.util.Arrays;
2. public class PairOfArraySum {
3. static int arr[] = { 4, 6, 5, -10, 8, 5, 20 };
4. public static void main(String[] args) {
5. Arrays.sort(arr); 
6. int i = 0;  // first index
7. int j = arr.length - 1;  // last index
8. while (i < j) {
9. // if arr[i]+arr[j] = num
10. if (arr[i] + arr[j] == 10) {
11. // then print the pair
12. System.out.println("Pair of elements are: (" + arr[i] + "," + arr[j] + ")");
13. i++;  // increment i
14. j--;  // decrement j
15. }
16. // if arr[i]+arr[j]<num
17. else if (arr[i] + arr[j] < 10) {
18. i++;   // then increment i
19. }
20. // if arr[i] + arr[j] >num
21. else if (arr[i] + arr[j] > 10) {
22. j--;  // then decrement j
23. }
24. }
25. }
26. }

Output:

Pair of elements are: (-10,20)

Pair of elements are: (4,6)

Pair of elements are: (5,5)

// Method-III:

1. public class PairOfSumByBruteForce {
2. static int arr[] = { 4, 6, 5, -10, 8, 5, 20 };
3. public static void main(String[] args) {
4. int sum = 10;
5. // brute force
6. for (int i = 0; i < arr.length; i++) {
7. for (int j = i + 1; j < arr.length; j++) {
8. if (arr[i] + arr[j] == sum)
9. System.out.println("Pair of elements are: (" + arr[i] + ", " + arr[j] + ")");
10. }
11. }
12. }
13. }

Output:

Pair of elements are: (4, 6)

Pair of elements are: (5, 5)

Pair of elements are: (-10, 20)

Time complexity: O(n^n)

Find the largest product of any two numbers in a list

Problem statement: Find the largest product of any two numbers in a list
Input - a list of numbers
Output - the largest product of any 2 numbers in the list
e.g. - [1 7 3 4 2 6 5]  => 42

1. public class ProductOfLargestNum {
2. public static void main(String[] args) {
3. 
   
4. int a[] = { 1, 7, 3, 4, 2, 6, 5 };
5. int temp;
6. /*
7. * logic is to sort the list first then get last and last but one
8. * element and do the product
9. */
10.    // bubble sort algorithm
11. for (int i = 0; i < a.length; i++) {
12. for (int j = 0; j < a.length - 1; j++) {
13. if (a[j] > a[j + 1]) {
14. temp = a[j];
15. a[j] = a[j + 1];
16. a[j + 1] = temp;
17. }
18. }
19. }
20. System.out.println("list after sorting");
21. for (int i : a) {
22. System.out.print(i + " ");
23. }
24. int last = a[a.length - 1];
25. int lastButOne = a[a.length - 2];
26. System.out.println();
27. System.out.println(last * lastButOne);
28. }
29. }

Output:

list after sorting

1 2 3 4 5 6 7 

42

Reverse a string array !!

Problem statement: Reverse a string array in java !
Using for Loop:

1. public class ReverseStringArrayExe1 {
2. public static void main(String[] args) {
3. 
   
4. String a[] = { "apples", "tomatoes", "bananas", "guavas", "pineapples" };
5. for (int i = 0; i < a.length / 2; i++) {
6. Object temp = a[i];
7. a[i] = a[a.length - 1 - i];
8. a[a.length - 1 - i] = (String) temp;
9. 
   
10. }
11. for (String s : a) {
12. System.out.print(s + " ");
13. 
    
14. }
15. }
16. }

Output: 
pineapples guavas bananas tomatoes apples
Time complexity: O(n/2)

Using while Loop:

1. public class ReverseStringArray {
2. public static void main(String[] args) {
3. String a[] = { "apples", "tomatoes", "bananas", "guavas", "pineapples" };
4. int end = a.length - 1;
5. int start = 0;
6. String temp;
7. while (start < end) {
8. temp = a[start];
9. a[start] = a[end];
10. a[end] = temp;
11. start++;
12. end--;
13. }
14. for (String i : a) {
15. System.out.print(i + " ");
16. }
17. }
18. }

Output:

pineapples guavas bananas tomatoes apples

Time complexity: O(n/2)

Using Java 8 Stream API:

1. import java.util.stream.IntStream;
2. 
   
3. public class ReverseArrayUsingStream {
4. public static void main(String[] args) {
5. String a[] = { "apples", "tomatoes", "bananas", "guavas", "pineapples" };
6. reverseUsingStream(a);
7. }
8. 
   
9. static void reverseUsingStream(Object a[]) {
10. 
    
11. Object rev[] =IntStream.rangeClosed(1, a.length).mapToObj(i -> a[a.length - i]).toArray();
12. for (Object s : rev) {
13. System.out.print(s + " ");
14. }
15. }
16. }

Output:

pineapples guavas bananas tomatoes apples 

Using Collections.reverse() :

1. import java.util.List;
2. import java.util.Arrays;
3. import java.util.Collections;
4. 
   
5. public class ReverseArrayCollections {
6. public static void main(String[] args) {
7. String a[] = { "apples", "tomatoes", "bananas", "guavas", "pineapples" };
8. reverseUsingCollectionsUtils(a);
9. }
10. static void reverseUsingCollectionsUtils(Object[] array) {
11. List<Object> list = Arrays.asList(array);
12. Collections.reverse(list);
13. for (Object i : list) {
14. System.out.print(i + " ");
15. }
16. }
17. }

Output:

pineapples guavas bananas tomatoes apples

Reverse an integer array !!

Problem statement:  Reverse an integer array in java !
Using  for Loop:

1. public class ReverseNumberArray {
2. public static void main(String[] args) {
3. int a[] = { 2, 4, 6, 7, 3, 56, 34 };
4. for (int i = 0; i < a.length / 2; i++) {
5. int temp = a[i];
6. a[i] = a[a.length - 1 - i];
7. a[a.length - 1 - i] = temp;
8. }
9. for (int i : a) {
10. System.out.print(i + " ");
11. }
12. }
13. }

Output: 

34 56 3 7 6 4 2 

Time complexity: O(n/2)

Using while Loop:

1. public class ReverseNumberArray {
2. 
   
3. public static void main(String[] args) {
4. int a[] = { 2, 4, 6, 7, 3, 56, 34 };
5. 
   
6. int end = a.length - 1;
7. int start = 0;
8. Object temp;
9. while (start < end) {
10. temp = a[start];
11. a[start] = a[end];
12. a[end] = (int) temp;
13. start++;
14. end--;
15. }
16. for (int i : a) {
17. System.out.print(i + " ");
18. }
19. }
20. }

Output: 

34 56 3 7 6 4 2 

Time complexity: O(n/2)

Using Java 8 Stream API:

1. import java.util.stream.IntStream;
2. 
   
3. public class ReverseArrayUsingStream {
4. public static void main(String[] args) {
5. Integer a[] = { 2, 4, 6, 7, 3, 56, 34 };
6. reverseUsingStream(a);
7. }
8. 
   
9. static void reverseUsingStream(Object a[]) {
10. 
    
11. Object rev[] = IntStream.rangeClosed(1, a.length).mapToObj(i -> a[a.length - i]).toArray();
12. for (Object s : rev) {
13. System.out.print(s + " ");
14. }
15. }
16. }

Using Collections.reverse():

1. import java.util.List;
2. import java.util.Arrays;
3. import java.util.Collections;
4. 
   
5. public class ReverseArrayCollections {
6. public static void main(String[] args) {
7. 
   
8. Object a[] = { 2, 4, 6, 7, 3, 56, 34 };
9. reverseUsingCollectionsUtils(a);
10. }
11. static void reverseUsingCollectionsUtils(Object[] array) {
12. List<Object> list = Arrays.asList(array);
13. Collections.reverse(list);
14. for (Object i : list) {
15. System.out.print(i + " ");
16. }
17. }
18. }

Output:
34 56 3 7 6 4 2 

Count the repeated character in a string !!

1. public class CountOfCharacter {
2. public static void main(String[] args) {
3. String s = "abcabcabc";
4. countOfRepeatedCharacter(s);
5. }
6. public static void countOfRepeatedCharacter(String s) {
7. char c[] = s.toCharArray();
8. Map<Character, Integer> map = new HashMap<Character, Integer>();
9. for (int i = 0; i < c.length; i++) {
10. if (map.containsKey(c[i])) {
11. map.put(c[i], map.get(c[i]) + 1);
12. } else {
13. map.put(c[i], 1);
14. }
15. }
16. System.out.println(map);
17. }
18. }

Output: 

{a=3, b=3, c=3}

Write a program to print square grid pattern !!

// Method-I:

1. /**
2.  * 
3.  * @author ishaan_sharma
4.  *
5.  */
6. public class PrintGridPatternAlgorithm {
7. public static void main(String[] args) {
8. printPatten(10);
9. }
10. 
    
11. /**
12.  * n accepts as an input argument to print rows and columns
13.  * @param n
14.  */
15. public static void printPatten(int n) {
16. for (int i = 0; i < n; i++) {
17. for (int j = n; j > 0; j--) {
18. System.out.print("* ");
19. }
20. System.out.println();
21. }
22. }
23. }

Output: 

* * * * * * * * * * 

* * * * * * * * * * 

* * * * * * * * * * 

* * * * * * * * * * 

* * * * * * * * * * 

* * * * * * * * * * 

* * * * * * * * * * 

* * * * * * * * * * 

* * * * * * * * * * 

* * * * * * * * * * 

// Method-II:

1. /**
2.  * 
3.  * @author ishaan_sharma
4.  *
5.  */
6. public class PrintPatternBy2DArrayAlgorithm {
7. 
   
8. public static void main(String[] args) {
9. int a[][] = new int[10][10];
10. printPattern(a);
11. }
12. 
    
13. /**
14.  * a takes 2D array value
15.  * @param a
16.  */
17. public static void printPattern(int a[][]) {
18. for (int i = 0; i < 10; i++) {
19. for (int j = 0; j < 10; j++) {
20. System.out.print(a[i][j] + " ");
21. }
22. System.out.println();
23. }
24. }
25. }

Output: 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

Write a program to sum values of an array !!

// Method-I:

1. public class SumValueOfArrayAlgorithm {
2. public static void main(String[] args) {
3. int a[] = { 1, 3, 4, 5, 56, 4 };
4. int sum = 0;
5. for (int i : a) {
6. sum = sum + i;
7. }
8. System.out.println(sum);
9. }
10. }

Output: 73

// Method-II:

1. public class SumValueOfArrayAlgorithm {
2. public static void main(String[] args) {
3. int a[] = { 1, 3, 4, 5, 56, 4 };
4. int sum = 0;
5. for (int i = 0; i < a.length; i++) {
6. sum = sum + a[i];
7. }
8. System.out.println(sum);
9. }
10. }

Output: 73

Write a program to sort a string array !!

// Method-I: (Using our own algorithm)

1. public class SortStringArrayByOwnAlgorithm {
2. public static void main(String[] args) {
3. String s[] = { "Java", "C++", "Python", "ruby", "Perl", "ishaan" };
4. String temp;
5. for (int i = 0; i < s.length; i++) {
6. for (int j = 0; j < s.length-1; j++) {
7. if (s[j].compareTo(s[j+1]) > 0) {
8. temp = s[j];
9. s[j] = s[j+1];
10. s[j+1] = temp;
11. }
12. }
13. }
14. for (String str : s) {
15. System.out.print(str + " ");
16. }
17. }
18. }

Output: C++ Java Perl Python ishaan ruby


// Mehod-II: (Using our own algorithm)

1. public class SortStringArrayByOwnAlgorithm {
2. public static void main(String[] args) {
3. String s[] = { "Java", "C++", "Python", "ruby", "Perl", "ishaan" };
4. String temp;
5. for (int i = 0; i < s.length; i++) {
6. for (int j = i + 1; j < s.length; j++) {
7. if (s[i].compareTo(s[j]) < 0) {
8. temp = s[i];
9. s[i] = s[j];
10. s[j] = temp;
11. }
12. }
13. }
14. for (String str : s) {
15. System.out.print(str + " ");
16. }
17. }
18. }

Output: ruby ishaan Python Perl Java C++

// Mehod-III: (Using pre-defined API)

1. public class SortStringArrayAlgorithmExe {
2. public static void main(String[] args) {
3. String s[] = { "Java", "C++", "Python", "ruby", "Perl", "ishaan" };
4. Arrays.sort(s);
5. for (String str : s) {
6. System.out.print(str + " ");
7. }
8. }
9. }

Output: C++ Java Perl Python ishaan ruby 

Write a program to sort numeric array !!

// Method-I:

1. public class SortIntegerArrayAlgorithm {
2. public static void main(String[] args) {
3. int a[] = { 2, 3, 4, 5, 22, 13, 5, 3 };
4. int temp;
5. for (int i = 0; i < a.length; i++) {
6. for (int j = 0; j < a.length - 1; j++) {
7. if (a[j] > a[j + 1]) {
8. temp = a[j];
9. a[j] = a[j + 1];
10. a[j + 1] = temp;
11. }
12. }
13. }
14. for (int i : a) {
15. System.out.print(i + " ");
16. }
17. }
18. }

Output: 2 3 3 4 5 5 13 22
Note: This is also called Bubble sort algorithm.

// Method-II:

1. public class SortIntArrayAlgorithm {
2. 
   
3. public static void main(String[] args) {
4. int a[] = { 1, 43, 4, 43, 33, 2, 2, 5, 5, 5, 5, 33, 777 };
5. Arrays.sort(a);
6. for (int i : a) {
7. System.out.print(i + " ");
8. }
9. }
10. }

Output: 1 2 2 4 5 5 5 5 33 33 43 43 777 

Note: Sorting has been done using pre-defined method not our own algorithm.