basic 2

Question 1

Write a program to check if a given string of parentheses is balanced.

Answer 1

import java.util.Stack;

public class BalancedParentheses {

public static boolean isBalanced(String str) {
    Stack<Character> stack = new Stack<>();

    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.pop();
            if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

public static void main(String[] args) {
    String input1 = "([])(){}";
    String input2 = "([)]";
    
    System.out.println("Is '" + input1 + "' balanced? " + isBalanced(input1));
    System.out.println("Is '" + input2 + "' balanced? " + isBalanced(input2));
} }

Question 2

Binary Search:
Write a program to implement binary search on a sorted array.

Answer 2

public class BinarySearch {

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        // Check if target is present at mid
        if (arr[mid] == target)
            return mid;

        // If target greater, ignore left half
        if (arr[mid] < target)
            left = mid + 1;

        // If target is smaller, ignore right half
        else
            right = mid - 1;
    }

    // If the target is not present in the array
    return -1;
}

public static void main(String[] args) {
    int[] arr = { 2, 3, 4, 10, 40 };
    int target = 10;
    int result = binarySearch(arr, target);
    if (result == -1)
        System.out.println("Element not present");
    else
        System.out.println("Element found at index " + result);
} }

If the value at the middle index is less than the target value, it means the target value lies in the right half of the array. So, it updates the left pointer to mid + 1.

If the value at the middle index is greater than the target value, it means the target value lies in the left half of the array. So, it updates the right pointer to mid - 1.

O(logn)

Question 3

Find Duplicates in Array:
Write a program to find duplicate elements in an array.

Answer 3

import java.util.*;

public class FindDuplicates {

public static List<Integer> findDuplicates(int[] nums) {
    List<Integer> duplicates = new ArrayList<>();
    Set<Integer> set = new HashSet<>();

    for (int num : nums) {
        if (!set.add(num)) { // If the number already exists in the set, it's a duplicate
            duplicates.add(num);
        }
    }

    return duplicates;
}

public static void main(String[] args) {
    int[] nums = {1, 2, 3, 4, 5, 2, 6, 7, 8, 9, 4};
    List<Integer> duplicateElements = findDuplicates(nums);
    
    if (duplicateElements.isEmpty()) {
        System.out.println("No duplicates found.");
    } else {
        System.out.println("Duplicate elements in the array: " + duplicateElements);
    }
} }