Master Advanced Data Structures, Graphs & Design Problems with Java

Introduction

Congratulations! You've reached the final part of the Top 50 Coding Interview Questions for QA/SDET series.

Throughout this series, we've covered the most frequently asked coding questions in QA Automation and SDET interviews:

Part 1: Strings and Arrays
Part 2: HashMaps, HashSets, Stacks, Queues, and Collection Problems
Part 3: Binary Search, Two Pointers, Sliding Window, Greedy Algorithms, and Dynamic Programming
Part 4: Linked Lists, Trees, Recursion, and Backtracking

In this final part, we'll tackle advanced problems that are commonly asked during interviews for Senior QA Automation Engineers and SDETs at companies such as Amazon, Microsoft, Google, Adobe, Oracle, Salesforce, Walmart, Atlassian, and ServiceNow.

These questions test:

Design skills
Advanced data structures
Graph algorithms
Priority Queues
Trie
BFS & DFS
Real-world problem-solving

Let's get started.

Question 41: Design an LRU Cache

Problem Statement

Design a cache that supports the following operations in O(1) time:

get(key)
put(key, value)

When the cache reaches capacity, remove the Least Recently Used (LRU) item.

Why Interviewers Ask This

This question evaluates your understanding of:

HashMap
Doubly Linked List
Cache Design
Object-Oriented Design

Approach

Use:

HashMap → O(1) lookup
Doubly Linked List → O(1) insertion and deletion

The most recently used item stays at the head, while the least recently used item remains near the tail.

Java Solution (Using LinkedHashMap)

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");

        cache.get(1);
        cache.put(4, "D");

        System.out.println(cache);
    }
}

Complexity

Operation	Complexity
get	O(1)
put	O(1)

Interview Follow-up

Implement the cache without using LinkedHashMap, using a HashMap and a custom Doubly Linked List.

Question 42: Design a Min Stack

Problem Statement

Implement a stack that supports:

push()
pop()
top()
getMin()

All operations must run in O(1) time.

Approach

Maintain two stacks:

Main Stack
Minimum Stack

The second stack stores the minimum value seen so far.

Java Solution

import java.util.Stack;

public class MinStack {

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public void push(int val) {

        stack.push(val);

        if (minStack.isEmpty() || val <= minStack.peek())
            minStack.push(val);
    }

    public void pop() {

        if (stack.pop().equals(minStack.peek()))
            minStack.pop();
    }

    public int getMin() {
        return minStack.peek();
    }
}

Complexity

Operation	Complexity
push	O(1)
pop	O(1)
getMin	O(1)

Question 43: Top K Frequent Elements

Problem Statement

Find the K most frequent elements in an array.

Example

Input

[1,1,1,2,2,3]

k = 2

Output

[1,2]

Approach

Count frequencies using a HashMap.
Store entries in a Max Heap (PriorityQueue).
Remove the top K elements.

Java Solution

import java.util.*;

public class TopKFrequent {

    public static void main(String[] args) {

        int[] nums = {1,1,1,2,2,3};
        int k = 2;

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

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

        PriorityQueue<Integer> pq =
                new PriorityQueue<>(
                        (a,b)->map.get(b)-map.get(a));

        pq.addAll(map.keySet());

        while(k-- > 0)
            System.out.println(pq.poll());
    }
}

Complexity

Time: O(n log n)

Space: O(n)

QA Use Case

Useful for:

Most common test failures
Frequently occurring exceptions
API error analysis
Log analytics

Question 44: Kth Largest Element in an Array

Problem Statement

Find the Kth largest element.

Input

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

k = 2

Output

Approach

Maintain a Min Heap of size K.

Java Solution

import java.util.PriorityQueue;

public class KthLargest {

    public static void main(String[] args){

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

        int k=2;

        PriorityQueue<Integer> pq=new PriorityQueue<>();

        for(int num:nums){

            pq.offer(num);

            if(pq.size()>k)
                pq.poll();
        }

        System.out.println(pq.peek());
    }
}

Complexity

Time: O(n log k)

Space: O(k)

Question 45: Implement a Trie (Prefix Tree)

Problem Statement

Implement a Trie supporting:

insert()
search()
startsWith()

Why It's Asked

Tries enable efficient prefix-based searches, making them valuable for autocomplete, spell checking, and dictionary applications.

Java Solution

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord;
}

public class Trie {

    TrieNode root = new TrieNode();

    public void insert(String word) {

        TrieNode node = root;

        for(char c : word.toCharArray()){

            int index = c - 'a';

            if(node.children[index] == null)
                node.children[index] = new TrieNode();

            node = node.children[index];
        }

        node.isWord = true;
    }
}

Complexity

Operation	Complexity
Insert	O(n)
Search	O(n)
Prefix	O(n)

Question 46: Word Search

Problem Statement

Given a 2D board and a word, determine if the word exists in the grid.

Characters can be connected horizontally or vertically.

Approach

Use Depth-First Search (DFS) with Backtracking.

Mark a cell as visited before exploring neighbors and restore it after backtracking.

Java DFS Signature

boolean dfs(char[][] board,
            String word,
            int row,
            int col,
            int index)

Complexity

Time: O(m × n × 4^L)

Space: O(L)

where L is the length of the word.

Interview Tip

Explain why each cell cannot be reused in the same search path.

Question 47: Number of Islands

Problem Statement

Given a grid of '1's (land) and '0's (water), count the number of islands.

Example

Output

Approach

Traverse the grid.

Whenever land is found:

Increment island count.
Perform DFS or BFS to mark all connected land as visited.

Java DFS

void dfs(char[][] grid,int i,int j){

    if(i<0 || j<0 ||
       i>=grid.length ||
       j>=grid[0].length ||
       grid[i][j]=='0')
        return;

    grid[i][j]='0';

    dfs(grid,i+1,j);
    dfs(grid,i-1,j);
    dfs(grid,i,j+1);
    dfs(grid,i,j-1);
}

Complexity

Time: O(m × n)

Space: O(m × n) in the worst case due to recursion.

Question 48: Longest Consecutive Sequence

Problem Statement

Find the length of the longest consecutive sequence.

Input

[100,4,200,1,3,2]

Output

Sequence

1 2 3 4

Approach

Use a HashSet.

Start counting only if the current number has no predecessor (num - 1).

Java Solution

import java.util.HashSet;

public class LongestSequence {

    public static void main(String[] args){

        int[] nums={100,4,200,1,3,2};

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

        for(int n:nums)
            set.add(n);

        int longest=0;

        for(int n:set){

            if(!set.contains(n-1)){

                int current=n;
                int length=1;

                while(set.contains(current+1)){
                    current++;
                    length++;
                }

                longest=Math.max(longest,length);
            }
        }

        System.out.println(longest);
    }
}

Complexity

Time: O(n)

Space: O(n)

Question 49: Meeting Rooms

Problem Statement

Determine whether a person can attend all meetings.

Input

[0,30]

[5,10]

[15,20]

Output

False

Approach

Sort meetings by start time.

If the next meeting starts before the previous one ends, there is an overlap.

Java Solution

import java.util.Arrays;

public class MeetingRooms {

    public static void main(String[] args){

        int[][] meetings={{0,30},{5,10},{15,20}};

        Arrays.sort(meetings,(a,b)->a[0]-b[0]);

        boolean possible=true;

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

            if(meetings[i][0]<meetings[i-1][1]){

                possible=false;
                break;
            }
        }

        System.out.println(possible);
    }
}

Complexity

Time: O(n log n)

Space: O(1)

QA Use Case

Scheduling:

Test execution
CI/CD pipelines
Parallel automation jobs

Question 50: Alien Dictionary (Topological Sort)

Problem Statement

Given a sorted dictionary of words from an alien language, determine the order of characters.

Example

Input

wrt

wrf

er

ett

rftt

Output

wertf

Approach

Build a graph representing character precedence.
Calculate the in-degree of each character.
Perform Topological Sorting using BFS (Kahn's Algorithm).

Key Java Components

Map<Character, List<Character>> graph = new HashMap<>();

Map<Character, Integer> indegree = new HashMap<>();

Queue<Character> queue = new LinkedList<>();

Complexity

Time: O(V + E)

Space: O(V + E)

where:

V = Number of unique characters
E = Number of ordering relationships

Interview Follow-up

Detect cycles in the graph.
Handle invalid dictionary inputs.
Return all valid character orders.

Coding Patterns Covered in Part 5

Pattern	Questions
Design	41, 42
Heap (Priority Queue)	43, 44
Trie	45
DFS	46, 47
BFS	47, 50
HashSet	48
Sorting	49
Graph	50
Topological Sort	50

Final Interview Preparation Checklist

Congratulations! You've completed all 50 coding interview questions in this series.

Before your interview, ensure you can:

Explain your approach before writing code.
Discuss brute-force and optimized solutions.
Analyze time and space complexity.
Identify edge cases such as empty inputs, duplicate values, and null references.
Select the most appropriate data structure for each problem.
Perform a dry run to validate your logic.
Write clean, modular, and readable Java code.

Remember, interviewers evaluate not only the correctness of your solution but also your communication, reasoning, and ability to optimize.

Complete Series Summary

Part	Topics Covered
Part 1	Strings and Arrays
Part 2	HashMaps, HashSets, Stacks, Queues
Part 3	Binary Search, Sliding Window, Dynamic Programming, Greedy Algorithms
Part 4	Linked Lists, Trees, Recursion, Backtracking
Part 5	Advanced Data Structures, Graphs, Design Problems, BFS, DFS, Heaps, Trie

Final Thoughts

Coding interviews for QA Automation Engineers and SDETs have evolved significantly over the past few years. Modern interviews assess not only your expertise in automation tools such as Selenium, Playwright, Cypress, or API testing frameworks but also your ability to solve algorithmic problems efficiently.

Consistent practice is the key to success. Focus on understanding the underlying patterns instead of memorizing solutions. Once you recognize common techniques such as HashMaps, Two Pointers, Sliding Window, Binary Search, Dynamic Programming, DFS, BFS, and Backtracking, you'll be able to solve a wide range of interview questions with confidence.

Keep practicing, write code every day, and challenge yourself with variations of these problems. The more you practice, the more naturally these patterns will come to you during interviews.

Happy Coding, and best of luck with your next QA/SDET interview!

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 5 (Questions 41–50)

Master Advanced Data Structures, Graphs & Design Problems with Java

Introduction

Question 41: Design an LRU Cache

Problem Statement

Why Interviewers Ask This

Approach

Java Solution (Using LinkedHashMap)

Complexity

Interview Follow-up

Question 42: Design a Min Stack

Problem Statement

Approach

Java Solution

Complexity

Question 43: Top K Frequent Elements

Problem Statement

Example

Approach

Java Solution

Complexity

QA Use Case

Question 44: Kth Largest Element in an Array

Problem Statement

Approach

Java Solution

Complexity

Question 45: Implement a Trie (Prefix Tree)

Problem Statement

Why It's Asked

Java Solution

Complexity

Question 46: Word Search

Problem Statement

Approach

Java DFS Signature

Complexity

Interview Tip

Question 47: Number of Islands

Problem Statement

Example

Approach

Java DFS

Complexity

Question 48: Longest Consecutive Sequence

Problem Statement

Approach

Java Solution

Complexity

Question 49: Meeting Rooms

Problem Statement

Approach

Java Solution

Complexity

QA Use Case

Question 50: Alien Dictionary (Topological Sort)

Problem Statement

Example

Approach

Key Java Components

Complexity

Interview Follow-up

Coding Patterns Covered in Part 5

Final Interview Preparation Checklist

Complete Series Summary

Final Thoughts