Master HashMaps, Stacks, Queues & Array Patterns with Java

Introduction

Welcome to Part 2 of the Top 50 Coding Interview Questions for QA/SDET series.

In Part 1, we covered the fundamentals of Strings and Arrays, including reversing strings, palindrome checking, anagrams, duplicate characters, and array manipulation.

In this part, we'll explore another set of interview favorites that frequently appear in coding rounds for QA Automation Engineers and SDETs. These problems assess your ability to use Java Collections efficiently, optimize algorithms, and solve real-world automation challenges.

By the end of this article, you'll be comfortable with:

Using HashMap and HashSet effectively
Stack-based interview questions
Queue concepts
Array frequency problems
Sliding window basics
Parentheses validation
Majority element
Missing number problems

Let's begin!

Question 11: Find the Missing Number in an Array

Problem Statement

Given an array containing numbers from 1 to N, one number is missing.

Find the missing number.

Example

Input

{1,2,4,5,6}

Output

Why Interviewers Ask This

This question evaluates:

Mathematical thinking
Loop optimization
Alternative problem-solving approaches

Approach 1 – Sum Formula

The expected sum of numbers from 1 to N is:

N × (N + 1) / 2

Subtract the actual array sum from the expected sum.

Java Solution

public class MissingNumber {

    public static void main(String[] args) {

        int[] arr = {1,2,4,5,6};

        int n = arr.length + 1;

        int expectedSum = n * (n + 1) / 2;

        int actualSum = 0;

        for(int num : arr)
            actualSum += num;

        System.out.println("Missing Number = " + (expectedSum - actualSum));
    }
}

Complexity

Time: O(n)

Space: O(1)

Follow-up Questions

What if numbers don't start from 1?
What if two numbers are missing?
Can you solve using XOR?

Question 12: Find the Majority Element

Problem Statement

Find the element appearing more than n/2 times.

Example

Input

{2,2,1,2,3,2,2}

Output

Approach 1 – HashMap

Count frequencies and identify the element whose count exceeds n/2.

Java Solution

import java.util.HashMap;
import java.util.Map;

public class MajorityElement {

    public static void main(String[] args) {

        int[] arr = {2,2,1,2,3,2,2};

        Map<Integer,Integer> map = new HashMap<>();

        for(int num : arr)
            map.put(num, map.getOrDefault(num,0)+1);

        for(Map.Entry<Integer,Integer> entry : map.entrySet()){

            if(entry.getValue() > arr.length/2){

                System.out.println(entry.getKey());
                break;
            }
        }
    }
}

Optimized Approach

Use Moore's Voting Algorithm.

Time Complexity: O(n)

Space Complexity: O(1)

Interviewers often ask candidates to explain why Moore's Voting Algorithm works, so it's worth studying after mastering the HashMap solution.

Question 13: Valid Parentheses

Problem Statement

Determine whether the given parentheses string is valid.

Examples

()
(())

{}[]

{[()]}

Invalid examples

(]

([)]

(((

Why Stack?

The last opening bracket must match the first closing bracket.

This follows the Last In, First Out (LIFO) principle.

Java Solution

import java.util.Stack;

public class ValidParentheses {

    public static boolean isValid(String str){

        Stack<Character> stack = new Stack<>();

        for(char ch : str.toCharArray()){

            if(ch=='(' || ch=='{' || ch=='[')
                stack.push(ch);

            else{

                if(stack.isEmpty())
                    return false;

                char top = stack.pop();

                if(ch==')' && top!='(')
                    return false;

                if(ch=='}' && top!='{')
                    return false;

                if(ch==']' && top!='[')
                    return false;
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args){

        System.out.println(isValid("{[()]}"));
    }
}

Complexity

Time: O(n)

Space: O(n)

Interview Variations

Balanced HTML tags
XML validation
Expression validation

Question 14: Find Intersection of Two Arrays

Problem Statement

Find common elements between two arrays.

Input

Array1 = {1,2,3,4,5}

Array2 = {3,4,5,6}

Output

3 4 5

Approach

Use a HashSet for efficient lookup.

Java Solution

import java.util.HashSet;

public class ArrayIntersection {

    public static void main(String[] args){

        int[] arr1={1,2,3,4,5};
        int[] arr2={3,4,5,6};

        HashSet<Integer> set=new HashSet<>();

        for(int num:arr1)
            set.add(num);

        for(int num:arr2){

            if(set.contains(num))
                System.out.print(num+" ");
        }
    }
}

Complexity

Time: O(n + m)

Space: O(n)

Real QA Use Case

Comparing:

Expected API response IDs
Actual response IDs
Database records
UI records

Question 15: Find Union of Two Arrays

Problem Statement

Return all unique elements from two arrays.

Input

{1,2,3}

{3,4,5}

Output

1 2 3 4 5

Java Solution

import java.util.HashSet;

public class UnionArray {

    public static void main(String[] args){

        int[] arr1={1,2,3};
        int[] arr2={3,4,5};

        HashSet<Integer> set=new HashSet<>();

        for(int num:arr1)
            set.add(num);

        for(int num:arr2)
            set.add(num);

        System.out.println(set);
    }
}

Complexity

Time: O(n + m)

Space: O(n + m)

Question 16: Count Frequency of Elements in an Array

Problem Statement

Input

{1,2,2,3,1,4,2}

Output

1 -> 2

2 -> 3

3 -> 1

4 -> 1

Java Solution

import java.util.HashMap;

public class FrequencyCount {

    public static void main(String[] args){

        int[] arr={1,2,2,3,1,4,2};

        HashMap<Integer,Integer> map=new HashMap<>();

        for(int num:arr){

            map.put(num,map.getOrDefault(num,0)+1);
        }

        System.out.println(map);
    }
}

Complexity

Time: O(n)

Space: O(n)

Interview Follow-up

Print elements in sorted order using TreeMap.

Question 17: Remove Duplicates from an Array

Problem Statement

Input

{1,2,2,3,3,4}

Output

1 2 3 4

Approach

Use LinkedHashSet to preserve insertion order.

Java Solution

import java.util.LinkedHashSet;

public class RemoveDuplicateArray {

    public static void main(String[] args){

        int[] arr={1,2,2,3,3,4};

        LinkedHashSet<Integer> set=new LinkedHashSet<>();

        for(int num:arr)
            set.add(num);

        System.out.println(set);
    }
}

Complexity

Time: O(n)

Space: O(n)

Question 18: Longest Common Prefix

Problem Statement

Input

flower

flow

flight

Output

fl

Approach

Sort the array.

Compare the first and last strings.

The common prefix between these two will also be the common prefix for the entire array.

Java Solution

import java.util.Arrays;

public class LongestPrefix {

    public static void main(String[] args){

        String[] words={"flower","flow","flight"};

        Arrays.sort(words);

        String first=words[0];
        String last=words[words.length-1];

        int i=0;

        while(i<first.length() &&
              i<last.length() &&
              first.charAt(i)==last.charAt(i)){

            i++;
        }

        System.out.println(first.substring(0,i));
    }
}

Complexity

Sorting: O(n log n)

Comparison: O(m)

where m is the length of the shortest string.

Question 19: String Compression

Problem Statement

Compress repeated characters.

Input

aaabbccccdd

Output

a3b2c4d2

Approach

Track the current character and its count while traversing the string.

Java Solution

public class StringCompression {

    public static void main(String[] args){

        String str="aaabbccccdd";

        StringBuilder result=new StringBuilder();

        int count=1;

        for(int i=1;i<=str.length();i++){

            if(i<str.length() &&
                    str.charAt(i)==str.charAt(i-1)){

                count++;

            }else{

                result.append(str.charAt(i-1));
                result.append(count);

                count=1;
            }
        }

        System.out.println(result);
    }
}

Complexity

Time: O(n)

Space: O(n)

Real QA Use Cases

Log compression
Report generation
Result summarization

Question 20: First Unique Character in an Array of Characters

Problem Statement

Given an array of characters, find the first non-repeating character.

Input

{'a','b','c','a','b','d'}

Output

Approach

Use a LinkedHashMap to preserve insertion order while counting occurrences.

Java Solution

import java.util.LinkedHashMap;
import java.util.Map;

public class FirstUnique {

    public static void main(String[] args){

        char[] arr={'a','b','c','a','b','d'};

        LinkedHashMap<Character,Integer> map=new LinkedHashMap<>();

        for(char ch:arr)
            map.put(ch,map.getOrDefault(ch,0)+1);

        for(Map.Entry<Character,Integer> entry:map.entrySet()){

            if(entry.getValue()==1){

                System.out.println(entry.getKey());
                break;
            }
        }
    }
}

Complexity

Time: O(n)

Space: O(n)

Coding Patterns Covered in Part 2

Congratulations! You have now completed another ten frequently asked QA/SDET coding interview questions.

The problems in this chapter introduce several important patterns that appear repeatedly in coding interviews:

Pattern	Questions
HashMap	12, 16, 20
HashSet	14, 15, 17
Stack	13
Mathematical Formula	11
String Traversal	19
Sorting	18
Frequency Counting	12, 16, 20

Interview Tips

Before moving to Part 3, make sure you can:

Explain why you selected a particular data structure.
Analyze the time and space complexity before writing code.
Handle edge cases such as empty arrays, null inputs, duplicate values, and negative numbers.
Discuss an optimized solution after presenting a straightforward approach.
Write clean, readable Java code with meaningful variable names.

Interviewers often value a well-explained solution more than simply arriving at the correct answer.

What's Next?

In Part 3, we'll tackle more advanced coding problems that commonly appear in SDET interviews, including:

Two Sum
Best Time to Buy and Sell Stock
Merge Two Sorted Arrays
Binary Search
Rotate Array
Product of Array Except Self
Kadane's Algorithm (Maximum Subarray)
Sliding Window Maximum
Merge Intervals
Search in a Rotated Sorted Array

These questions introduce optimization techniques such as two pointers, binary search, greedy algorithms, prefix/suffix arrays, and interval merging—patterns that are highly valued in product-based company interviews.

Playwright Tutorial

Java Tutorial

Selenium Tutorial

Rest Assured Tutorial

SQL Tutorial

Git Tutorial

CI / CD Tutorial

Interview Questions

Top 50 Coding Interview Questions for QA/SDET – Part 2 (Questions 11–20)

Master HashMaps, Stacks, Queues & Array Patterns with Java

Introduction

Question 11: Find the Missing Number in an Array

Problem Statement

Example

Why Interviewers Ask This

Approach 1 – Sum Formula

Java Solution

Complexity

Follow-up Questions

Question 12: Find the Majority Element

Problem Statement

Example

Approach 1 – HashMap

Java Solution

Optimized Approach

Question 13: Valid Parentheses

Problem Statement

Why Stack?

Java Solution

Complexity

Interview Variations

Question 14: Find Intersection of Two Arrays

Problem Statement

Approach

Java Solution

Complexity

Real QA Use Case

Question 15: Find Union of Two Arrays

Problem Statement

Java Solution

Complexity

Question 16: Count Frequency of Elements in an Array

Problem Statement

Java Solution

Complexity

Interview Follow-up

Question 17: Remove Duplicates from an Array

Problem Statement

Approach

Java Solution

Complexity

Question 18: Longest Common Prefix

Problem Statement

Approach

Java Solution

Complexity

Question 19: String Compression

Problem Statement

Approach

Java Solution

Complexity

Real QA Use Cases

Question 20: First Unique Character in an Array of Characters

Problem Statement

Approach

Java Solution

Complexity

Coding Patterns Covered in Part 2

Interview Tips

What's Next?