Flat Preloader Icon

Interview Programs

1.Array rotation

  • Problem: Rotate an array to the right by k steps.
  • Solution: Use a temporary array to store elements and shift them to their new positions.
				
					import java.util.Arrays;

public class ArrayRotation {
    // Function to rotate array to the 
    right by k steps
    public static void rotateArray(int[] nums, int k) 
    {
        if (nums == null || nums.length == 0 || k == 0) 
        {
            return;
        }
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    // Function to reverse the array within the
    given range
    public static void reverse(int[] nums,
    int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    // Main method to test the rotation function
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;
        System.out.println("Original Array: " 
        + Arrays.toString(nums));
        rotateArray(nums, k);
        System.out.println("Array rotated by "
        + k + " steps: " + Arrays.toString(nums));
    }
}

				
			

2.Find the missing number in a given integer array of 1 to 100

  • Problem: Find the missing number in a sequence of integers from 1 to 100.
  • Solution: Calculate the sum of the sequence and find the missing number by subtracting the sum of the given array from the sum of the sequence.
				
					public class FindMissingNumber {
    public static void main(String[] args) {
        // Given array with one missing number
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
        11, 12, 13, 14, 15, 16, 17, 18, 20, 
        21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 
        31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 
        41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 
        51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
        61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 
        71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 
        81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
        91, 92, 93, 94, 95, 96, 97, 98, 99, 100};
        
        int missingNumber = findMissingNumber(array);
        
        System.out.println("The missing number is: "
        + missingNumber);
    }

    // Function to find the missing number in 
    the given array
    public static int findMissingNumber(int[] array) {
        int n = array.length + 1;
        int totalSum = n * (n + 1) / 2;
        int arraySum = 0;
        
        for (int num : array) {
            arraySum += num;
        }
        
        return totalSum - arraySum;
    }
}

				
			

3.Sort an array of 0s, 1s, and 2s

  • Problem: Sort an array containing only 0s, 1s, and 2s without using any sorting algorithm.
  • Solution: Use the Dutch National Flag algorithm to partition the array into three sections.
				
					public class SortArrayOfZeroOneTwo {
    public static void sortArray(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        int mid = 0, temp = 0;
        while (mid <= high) {
            switch (nums[mid]) {
                case 0: {
                    temp = nums[low];
                    nums[low] = nums[mid];
                    nums[mid] = temp;
                    low++;
                    mid++;
                    break;
                }
                case 1:
                    mid++;
                    break;
                case 2: {
                    temp = nums[mid];
                    nums[mid] = nums[high];
                    nums[high] = temp;
                    high--;
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 2, 1, 0, 2, 1, 0, 2, 0, 1};
        System.out.println("Original Array: " 
        + java.util.Arrays.toString(nums));
        sortArray(nums);
        System.out.println("Sorted Array: " 
        + java.util.Arrays.toString(nums));
    }
}

				
			

4.Reverse an array

  • Problem: Reverse an array of integers.
  • Solution: Use two pointers to swap elements from the beginning and end of the array.
				
					import java.util.Arrays;

public class ReverseArray {
    public static void reverseArray(int[] arr) {
        int start = 0;
        int end = arr.length - 1;
        int temp;
        while (start < end) {
            temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        System.out.println("Original Array: " 
        + Arrays.toString(array));
        reverseArray(array);
        System.out.println("Reversed Array: "
        + Arrays.toString(array));
    }
}

				
			

5.Implement a stack using an array

  • Problem: Implement a stack data structure using an array.
  • Solution: Use an array and keep track of the top element.
				
					public class Stack {
    private int maxSize;
    private int[] stackArray;
    private int top;

    public Stack(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1;
    }

    public void push(int value) {
        if (top < maxSize - 1) {
            stackArray[++top] = value;
            System.out.println("Pushed element: 
            " + value);
        } else {
            System.out.println
            ("Stack is full. Cannot push " + value);
        }
    }

    public int pop() {
        if (top >= 0) {
            int value = stackArray[top--];
            System.out.println
            ("Popped element: " + value);
            return value;
        } else {
            System.out.println
            ("Stack is empty. Cannot pop");
            return -1;
        }
    }

    public int peek() {
        if (top >= 0) {
            return stackArray[top];
        } else {
            System.out.println
            ("Stack is empty. No element to peek");
            return -1;
        }
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (top == maxSize - 1);
    }

    public static void main(String[] args) {
        Stack stack = new Stack(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.pop();
        System.out.println("Top element: " 
        + stack.peek());
        System.out.println("Is the stack empty? " 
        + stack.isEmpty());
        System.out.println("Is the stack full? "
        + stack.isFull());
    }
}

				
			

6.Implement a queue using an array

  • Problem: Implement a queue data structure using an array.
  • Solution: Use an array and maintain pointers for the front and rear elements.
				
					public class Queue {
    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int currentSize;

    public Queue(int size) {
        maxSize = size;
        queueArray = new int[maxSize];
        front = 0;
        rear = -1;
        currentSize = 0;
    }

    public void enqueue(int value) {
        if (!isFull()) {
            rear = (rear + 1) % maxSize;
            queueArray[rear] = value;
            currentSize++;
            System.out.println("Enqueued element:
            " + value);
        } else {
            System.out.println
            ("Queue is full. Cannot enqueue " + value);
        }
    }

    public int dequeue() {
        if (!isEmpty()) {
            int temp = queueArray[front];
            front = (front + 1) % maxSize;
            currentSize--;
            System.out.println
            ("Dequeued element: " + temp);
            return temp;
        } else {
            System.out.println
            ("Queue is empty. Cannot dequeue");
            return -1;
        }
    }

    public int peek() {
        if (!isEmpty()) {
            return queueArray[front];
        } else {
            System.out.println
            ("Queue is empty. No element to peek");
            return -1;
        }
    }

    public boolean isEmpty() {
        return (currentSize == 0);
    }

    public boolean isFull() {
        return (currentSize == maxSize);
    }

    public static void main(String[] args) {
        Queue queue = new Queue(5);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.dequeue();
        System.out.println
        ("Front element: " + queue.peek());
        System.out.println
        ("Is the queue empty? " + queue.isEmpty());
        System.out.println
        ("Is the queue full? " + queue.isFull());
    }
}

				
			

7.Find the intersection point of two linked lists

  • Problem: Find the node at which two linked lists intersect.
  • Solution: Find the lengths of the two lists, align the starting points, and then iterate to find the intersection.
				
					// Node class for the linked list
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class IntersectionLinkedLists {
    // Function to find the
    intersection point of two linked lists
    public static Node getIntersectionNode
    (Node headA, Node headB) {
        if (headA == null || headB == null) {
            return null;
        }

        Node a = headA;
        Node b = headB;

        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }

        return a;
    }

    public static void main(String[] args) {
        // Creating the first linked list
        Node node1 = new Node(3);
        Node node2 = new Node(6);
        Node node3 = new Node(9);
        Node node4 = new Node(15);
        Node node5 = new Node(30);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        // Creating the second linked list
        Node node6 = new Node(10);
        node6.next = node4;

        Node intersectionNode = getIntersectionNode
        (node1, node6);
        if 
        (intersectionNode != null) {
            System.out.println
            ("Intersection point of the two 
            linked lists is: " + intersectionNode.data);
        } else {
            System.out.println
            ("No intersection point found.");
        }
    }
}

				
			

8.Reverse a linked list

  • Problem: Reverse a singly linked list.
  • Solution: Traverse the list, reversing the links between nodes.
				
					// Node class for the linked list
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class ReverseLinkedList {
    // Function to reverse the linked list
    public static Node reverseList(Node head) {
        Node prev = null;
        Node current = head;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

    // Function to print the linked list
    public static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Creating a sample linked list
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        Node fourth = new Node(4);

        head.next = second;
        second.next = third;
        third.next = fourth;

        System.out.println("Original linked list:");
        printList(head);

        Node reversedHead = reverseList(head);

        System.out.println("Reversed linked list:");
        printList(reversedHead);
    }
}

				
			

9.Detect a cycle in a linked list

  • Problem: Determine if a linked list has a cycle.
  • Solution: Use the slow and fast pointer approach to detect a cycle in the linked list.
				
					// Node class for the linked list
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class DetectCycleLinkedList {
    // Function to detect a cycle in a linked list
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(0);
        ListNode node3 = new ListNode(-4);

        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node1; // creating a cycle

        boolean hasCycle = hasCycle(head);
        if (hasCycle) {
            System.out.println
            ("The linked list has a cycle.");
        } else {
            System.out.println
            ("The linked list does not have a cycle.");
        }
    }
}

				
			

10.Find the nth node from the end in a linked list

  • Problem: Find the nth node from the end of a singly linked list.
  • Solution: Use two pointers with a distance of n between them.
				
					// Node class for the linked list
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class NthNodeFromEndLinkedList {
    // Function to find the nth node from the end 
    of a linked list
    public static ListNode findNthFromEnd
    (ListNode head, int n) {
        if (head == null || n <= 0) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        for (int i = 0; i < n; i++) {
            if (fast == null) {
                return null;
            }
            fast = fast.next;
        }

        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(5);

        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        int n = 2; // Find the 2nd node from the end
        ListNode nthNode = findNthFromEnd(head, n);

        if (nthNode != null) {
            System.out.println("The " + n 
            + "th node from the end is: " + nthNode.val);
        } else {
            System.out.println("The list is too 
            short or n is not valid.");
        }
    }
}