Master Two Pointers, Binary Search, Sliding Window & Greedy Algorithms with Java
Introduction
Welcome to Part 3 of the Top 50 Coding Interview Questions for QA/SDET series.
In Part 1, we focused on Strings and Arrays, building a strong foundation with basic data manipulation problems.
In Part 2, we explored HashMaps, HashSets, Stacks, Queues, and frequency-based problems that commonly appear in QA Automation and SDET interviews.
Now it's time to move to intermediate-level coding questions. These questions are frequently asked during interviews at companies such as Amazon, Microsoft, Walmart, ServiceNow, Adobe, Oracle, Salesforce, and many other product-based organizations.
The coding patterns covered in this chapter are among the most important for technical interviews because they help solve complex problems efficiently.
After completing this article, you'll be comfortable with:
Two Pointer Technique
Binary Search
Sliding Window
Greedy Algorithms
Prefix & Suffix Arrays
Interval Merging
Array Rotation
Optimized Searching
Let's dive in.
Question 21: Two Sum
Problem Statement
Given an integer array and a target value, return the indices of two numbers whose sum equals the target.
Example
Input
nums = [2,7,11,15]
target = 9
Output
[0,1]
Why Interviewers Ask This
This problem evaluates:
HashMap usage
Lookup optimization
Problem-solving ability
Brute Force Approach
Compare every pair.
Time Complexity:
O(n²)
Optimized Approach
Store previously seen numbers inside a HashMap.
For every number:
Calculate target − current number.
Check if it already exists.
If yes, return both indices.
Java Solution
import java.util.*;
public class TwoSum {
public static void main(String[] args) {
int[] nums = {2,7,11,15};
int target = 9;
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
int diff = target - nums[i];
if(map.containsKey(diff)){
System.out.println(map.get(diff)+" "+i);
return;
}
map.put(nums[i],i);
}
}
}
Dry Run
Array
2 7 11 15
Target
9
Iteration
| Current | Need | HashMap |
|---|---|---|
| 2 | 7 | {2} |
| 7 | 2 | Found |
Answer
0 1
Complexity
Time
O(n)
Space
O(n)
Common Mistakes
Returning values instead of indices.
Forgetting duplicate numbers.
Updating HashMap before checking complement.
Question 22: Best Time to Buy and Sell Stock
Problem Statement
Find the maximum profit from one buy and one sell.
Input
[7,1,5,3,6,4]
Output
5
Approach
Track:
Minimum price seen so far.
Maximum profit.
Java Solution
public class BuySellStock {
public static void main(String[] args){
int[] prices={7,1,5,3,6,4};
int min=prices[0];
int profit=0;
for(int i=1;i<prices.length;i++){
if(prices[i]<min)
min=prices[i];
profit=Math.max(profit,prices[i]-min);
}
System.out.println(profit);
}
}
Complexity
Time
O(n)
Space
O(1)
Interview Follow-up
Multiple transactions.
Cooldown period.
Transaction fee.
Question 23: Merge Two Sorted Arrays
Problem Statement
Merge two sorted arrays into one sorted array.
Input
1 3 5
2 4 6
Output
1 2 3 4 5 6
Approach
Maintain two pointers.
Compare both arrays.
Insert the smaller element.
Java Solution
public class MergeArrays {
public static void main(String[] args){
int[] a={1,3,5};
int[] b={2,4,6};
int[] result=new int[a.length+b.length];
int i=0,j=0,k=0;
while(i<a.length && j<b.length){
if(a[i]<b[j])
result[k++]=a[i++];
else
result[k++]=b[j++];
}
while(i<a.length)
result[k++]=a[i++];
while(j<b.length)
result[k++]=b[j++];
for(int num:result)
System.out.print(num+" ");
}
}
Complexity
Time
O(n+m)
Space
O(n+m)
QA Use Case
Frequently used while merging:
Test reports
API responses
Log files
Database results
Question 24: Binary Search
Problem Statement
Search a number in a sorted array.
Input
Array = [2,5,8,10,15]
Target = 10
Output
Found at index 3
Why Binary Search?
Instead of checking every element,
Divide the search space into half.
Java Solution
public class BinarySearch {
public static void main(String[] args){
int[] arr={2,5,8,10,15};
int target=10;
int left=0;
int right=arr.length-1;
while(left<=right){
int mid=(left+right)/2;
if(arr[mid]==target){
System.out.println(mid);
return;
}
if(arr[mid]<target)
left=mid+1;
else
right=mid-1;
}
System.out.println("Not Found");
}
}
Complexity
Time
O(log n)
Space
O(1)
Interview Follow-up
First occurrence
Last occurrence
Search insert position
Question 25: Rotate Array by K Positions
Problem Statement
Input
1 2 3 4 5 6 7
k=3
Output
5 6 7 1 2 3 4
Efficient Approach
Reverse:
Entire array
First K elements
Remaining elements
Java Solution
public class RotateArray {
static void reverse(int[] arr,int start,int end){
while(start<end){
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
}
public static void main(String[] args){
int[] arr={1,2,3,4,5,6,7};
int k=3;
reverse(arr,0,arr.length-1);
reverse(arr,0,k-1);
reverse(arr,k,arr.length-1);
for(int num:arr)
System.out.print(num+" ");
}
}
Complexity
Time
O(n)
Space
O(1)
Question 26: Product of Array Except Self
Problem Statement
Input
[1,2,3,4]
Output
[24,12,8,6]
Why This Question?
Interviewers want to see if you can solve it without division.
Approach
Build:
Prefix product array
Suffix product array
Multiply both.
Java Solution
public class ProductArray {
public static void main(String[] args){
int[] nums={1,2,3,4};
int n=nums.length;
int[] result=new int[n];
result[0]=1;
for(int i=1;i<n;i++)
result[i]=result[i-1]*nums[i-1];
int suffix=1;
for(int i=n-1;i>=0;i--){
result[i]*=suffix;
suffix*=nums[i];
}
for(int num:result)
System.out.print(num+" ");
}
}
Complexity
Time
O(n)
Space
O(1) (excluding output array)
Question 27: Maximum Subarray Sum (Kadane's Algorithm)
Problem Statement
Input
[-2,1,-3,4,-1,2,1,-5,4]
Output
6
Subarray
4,-1,2,1
Why Interviewers Love This Question
Tests optimization thinking.
Brute force takes O(n²).
Kadane solves it in O(n).
Java Solution
public class Kadane {
public static void main(String[] args){
int[] arr={-2,1,-3,4,-1,2,1,-5,4};
int max=arr[0];
int current=arr[0];
for(int i=1;i<arr.length;i++){
current=Math.max(arr[i],current+arr[i]);
max=Math.max(max,current);
}
System.out.println(max);
}
}
Complexity
Time
O(n)
Space
O(1)
Question 28: Sliding Window Maximum (Simplified)
Problem Statement
Find the maximum sum of every window of size K.
Input
Array = [2,1,5,1,3,2]
k = 3
Output
8
9
9
6
Approach
Maintain the current window sum.
Subtract the outgoing element.
Add the incoming element.
Java Solution
public class SlidingWindow {
public static void main(String[] args){
int[] arr={2,1,5,1,3,2};
int k=3;
int sum=0;
for(int i=0;i<k;i++)
sum+=arr[i];
System.out.println(sum);
for(int i=k;i<arr.length;i++){
sum+=arr[i]-arr[i-k];
System.out.println(sum);
}
}
}
Complexity
Time
O(n)
Space
O(1)
QA Example
Useful while analyzing:
Moving average response time
CPU usage
API latency
Performance metrics
Question 29: Merge Intervals
Problem Statement
Input
[1,3]
[2,6]
[8,10]
[15,18]
Output
[1,6]
[8,10]
[15,18]
Approach
Sort intervals.
Compare current interval with previous.
Merge overlapping intervals.
Java Solution
import java.util.*;
public class MergeIntervals {
public static void main(String[] args){
int[][] intervals={{1,3},{2,6},{8,10},{15,18}};
Arrays.sort(intervals,(a,b)->a[0]-b[0]);
List<int[]> result=new ArrayList<>();
for(int[] interval:intervals){
if(result.isEmpty() ||
result.get(result.size()-1)[1]<interval[0]){
result.add(interval);
}else{
result.get(result.size()-1)[1]=Math.max(
result.get(result.size()-1)[1],
interval[1]);
}
}
for(int[] i:result)
System.out.println(i[0]+" "+i[1]);
}
}
Complexity
Time
O(n log n)
Space
O(n)
Question 30: Search in Rotated Sorted Array
Problem Statement
Input
Array = [4,5,6,7,0,1,2]
Target = 0
Output
4
Approach
Modified Binary Search.
At every step:
One half is sorted.
Decide which half contains the target.
Java Solution
public class RotatedSearch {
public static void main(String[] args){
int[] nums={4,5,6,7,0,1,2};
int target=0;
int left=0,right=nums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]==target){
System.out.println(mid);
return;
}
if(nums[left]<=nums[mid]){
if(target>=nums[left] &&
target<nums[mid])
right=mid-1;
else
left=mid+1;
}else{
if(target>nums[mid] &&
target<=nums[right])
left=mid+1;
else
right=mid-1;
}
}
System.out.println(-1);
}
}
Complexity
Time
O(log n)
Space
O(1)
Coding Patterns Covered in Part 3
| Pattern | Questions |
|---|---|
| HashMap | 21 |
| Greedy | 22 |
| Two Pointers | 23 |
| Binary Search | 24, 30 |
| Array Reversal | 25 |
| Prefix & Suffix Arrays | 26 |
| Dynamic Programming (Kadane's) | 27 |
| Sliding Window | 28 |
| Interval Merging | 29 |
Common Interview Tips
Before attempting these problems in an interview:
Clearly explain the brute-force solution before jumping to the optimized one.
State the expected time and space complexity.
Consider edge cases such as empty arrays, duplicate values, negative numbers, and integer overflow.
Use descriptive variable names and modular methods where appropriate.
Verify your solution with a small dry run before concluding.
These practices demonstrate not only coding ability but also strong communication and problem-solving skills.
What's Next?
In Part 4, we'll cover ten more interview questions focused on Linked Lists, Trees, Recursion, and Backtracking, including:
Reverse a Linked List
Detect a Cycle in a Linked List
Merge Two Sorted Linked Lists
Find the Middle of a Linked List
Binary Tree Traversals
Maximum Depth of a Binary Tree
Lowest Common Ancestor
Fibonacci Using Recursion and Dynamic Programming
Generate All Permutations
Generate Valid Parentheses
These questions are commonly asked in advanced QA/SDET interviews and assess your understanding of data structures, recursion, and algorithmic thinking.