Geico interview question prep.
Sample Medium-Level Coding Problems:
- Pathfinding/DP: "Minimum
Path Sum" (grid traversal), often with constraints on moves
(right/down).
- Strings/Sliding
Window: "Longest Substring Without Repeating
Characters," "First Unique Character," "String to
Integer (atoi)".
- Linked
Lists: "Detect Cycle in Linked List," "Merge Two
Sorted Lists," "Reverse Linked List" (use dummy
nodes/two-pointers).
- Heaps/Priority
Queues: Finding the top K elements, or complex sorting
scenarios.
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at
any point in time.
Example 1:
Simpler form;
int m = grid.length; int n =
grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++)
dp[i][0] =
dp[i-1][0] + grid[i][0];
for (int j = 1; j < n; j++)
dp[0][j] =
dp[0][j-1] + grid[0][j];
for (int i = 1; i < m; i++) {
for (int j =
1; j < n; j++) {
dp[i][j] =
grid[i][j] +
Math.min(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m-1][n-1];
A little bit complex style:
int m = grid.length; int n = grid[0].length;
int[] dp = new int[n];
dp[0] = grid[0][0];
// First row
for (int j = 1; j < n; j++) {
dp[j] = dp[j - 1]
+ grid[0][j];
}
// Remaining rows
for (int i = 1; i < m; i++) {
dp[0] +=
grid[i][0]; // first column
for (int j = 1; j
< n; j++) {
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
}
}
return dp[n - 1];
Longest Substring Without Repeating Characters - LeetCode
1st attempt, I tried this way:
✅ Optimal Approach: Sliding Window (O(n))
Idea (simple):
Use two pointers: left and right
Maintain a HashSet of characters in the current window
Expand right
If duplicate found → shrink from left
Track max window size
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> set = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}
Detect Cycle in Linked List,
Linked
List Cycle - LeetCode
linked list has a cycle in it.
the list that can be reached again by continuously following the next pointer.
Internally, pos is used to denote the index of the node
that tail's next pointer is connected to.
where the tail connects to the 1st node (0-indexed).
Given head, the head of a linked list, determine if the
There is a cycle in a linked list if there is some node in
Return true if there is a cycle in the linked
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list,
Solution: DetectCycle in Linked List - GeeksforGeeks
class GfG {
static boolean detectLoop(Node head) {
Node slow =head; Node fast = head;
// Loop that runs while fast and slow pointer are not null and not equal
while (slow !=null && fast != null && fast.next != null) {
slow =slow.next;
fast =fast.next.next;
// If fast and slow pointer points to the same node, // then the cycle is detected
if (slow== fast) {
return true;
}
}
return false;
}
[Expected Approach] Using Floyd's Cycle-Finding Algorithm
This idea is to use Floyd'sCycle-Finding Algorithm to find a loop in a linked list. It uses two pointers slow and fast,
fast pointer move two steps ahead and slow will move one step ahead at a time.
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list.
The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode finalNode=null;
// Dummy node to simplify logic
ListNode dummy = new ListNode(-1);
ListNode finallist = dummy;
while (list1 != null && list2 != null) {
if (list1.val<= list2.val) {
finallist.next= list1;
list1 = list1.next;
} else {
finallist.next= list2;
list2 = list2.next;
}
finallist = finallist.next;
}
// Attach remaining nodes
if (list1 != null) {
finallist.next =list1;
} else {
finallist.next =list2;
}
return dummy.next;
}
}
Reverse
Linked List - LeetCode
Given the head of a singly linked list, reverse
the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Solution 1: using stack:class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
Stack<ListNode> stack = new Stack<>();
ListNode curr = head;
while (curr != null) {
stack.push(curr);
curr = curr.next;
}
ListNode newHead = stack.pop();
curr = newHead;
while (!stack.isEmpty()) {
curr.next = stack.pop();
curr = curr.next;
}
curr.next = null; // important to avoid cycle
return newHead;
}
}Solution 2: using temp variable:
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp= curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}
Max pathhole.
Problem Description (Common Version)
You are given a string road consisting of:
• '.' → smooth road
• 'x' → pothole
You can fix potholes using one repair operation, which:
• Fixes exactly one pothole
• Cannot be applied to adjacent potholes
Goal
Return the maximum number of potholes that can be fixed.
Example
Input
road = "x..xx...xxx"
Breakdown
Segment Length Fixable
x 1 1
xx 2 1
xxx 3 2
Output
4
public class Solution {
public int maximumPotholes(String road) {
int count = 0;
int i = 0;
while (i <road.length()) {
if(road.charAt(i) == 'x') {
count++; // fix this pothole
i +=2; // skip next to avoid adjacency
} else {
i++;
}
}
return count;
}
}
Why This Works 🧠
road = "xxx..xx"
Walkthrough:
i=0 → 'x' → fix → count=1 → i=2
i=2 → 'x' → fix → count=2 → i=4
i=4 → '.' → skip → i=5
i=5 → 'x' → fix → count=3 → i=7 (end)
Integer to roman
✅ Corrected Version (Minimal Change to Your Code)
class Solution {
public String intToRoman(int num) {
int[] value = {
1000, 900, 500, 400,
100, 90, 50, 40,
10, 9, 5, 4, 1
};
String[] symbol = {
"M", "CM", "D", "CD",
"C", "XC", "L", "XL",
"X", "IX", "V", "IV", "I"
};
StringBuilder b = new StringBuilder();
for (int j = 0; j < value.length; j++) {
while (num >= value[j]) {
num -= value[j];
b.append(symbol[j]);
}
}
return b.toString();
}
}
Time Complexity
Key Observation
• The value array has a constant size (13).
• Each iteration of while reduces num.
• Maximum Roman numeral length for 3999 is 15 characters (MMMCMXCIX).
Analysis
• Outer loop → 13 iterations (constant)
• Inner loop → runs at most 15 times total
✅ Time Complexity = O(1) (constant time)
Even though there is a nested loop, the total number of operations is bounded by a constant, not by input size.
________________________________________
💾 Space Complexity
Extra Space Used
• StringBuilder → max ~15 characters
• value[] and symbol[] → fixed size
✅ Space Complexity = O(1) (constant space)
455. Assign Cookies
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Example 1:
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int child = 0, cookie = 0;
while (child < g.length && cookie < s.length) {
if (s[cookie] >= g[child]) {
child++; // child is content
}
cookie++; // move to next cookie
}
return child;
}
Why this is simpler
Uses two pointers (child, cookie)
No extra variables
Greedy logic is clear: give the smallest sufficient cookie to the least greedy child
⏱ Time: O(n log n + m log m)
📦 Space: O(1) (ignoring sort)
Valid parenthesis
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
if ((c == ')' && stack.peek() == '(') ||
(c == '}' && stack.peek() == '{') ||
(c == ']' && stack.peek() == '[')) {
stack.pop();
} else {
return false;
}
}
}
return stack.isEmpty();
}
}
678. Valid Parenthesis String
Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.
The following rules define a valid string:
• Any left parenthesis '(' must have a corresponding right parenthesis ')'.
• Any right parenthesis ')' must have a corresponding left parenthesis '('.
• Left parenthesis '(' must go before the corresponding right parenthesis ')'.
• '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".
class Solution {
public boolean checkValidString(String s) {
Stack<Integer> openStack = new Stack<>();
Stack<Integer> starStack = new Stack<>();
// First pass
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
openStack.push(i);
} else if (c == '*') {
starStack.push(i);
} else { // c == ')'
if (!openStack.isEmpty()) {
openStack.pop();
} else if (!starStack.isEmpty()) {
starStack.pop();
} else {
return false;
}
}
}
// Match remaining '(' with '*'
while (!openStack.isEmpty() && !starStack.isEmpty()) {
if (openStack.peek() > starStack.peek()) {
return false;
}
openStack.pop();
starStack.pop();
}
return openStack.isEmpty();
}
}
🔍 Example Walkthrough
Input:
"(*)"
• ( → push index to openStack
• * → push index to starStack
• ) → pop from openStack
✅ Valid
________________________________________
Input:
"(*))"
• ( → openStack
• * → starStack
• ) → match (
• ) → match *
✅ Valid
Two pointer problem
Two Pointers
Technique - GeeksforGeeks
Two-Pointer Technique - O(n) time and O(1) space
The idea of this technique is to begin with two corners of the given array. We use two index variables left and right to traverse from both corners.
Initialize: left = 0, right = n - 1
Run a loop while left < right, do the following inside the loop
• Compute current sum, sum = arr[left] + arr[right]
• If the sum equals the target, we’ve found the pair.
• If the sum is less than the target, move the left pointer to the right to increase the sum.
• If the sum is greater than the target, move the right pointer to the left to decrease the sum.
class GfG {
// Function to check whether any pair exists
// whose sum is equal to the given target value
static boolean twoSum(int[] arr, int target){
// Sort the array
int left = 0, right = arr.length - 1;
// Iterate while left pointer is less than right
while (left < right) {
int sum = arr[left] + arr[right];
// Check if the sum matches the target
if (sum == target)
return true;
else if (sum < target)
left++; // Move left pointer to the right
else
right--; // Move right pointer to the left
}
// If no pair is found
return false;
}
public static void main(String[] args){
int[] arr = {-3, -1, 0, 1, 2 };
int target = -2;
// Call the twoSum function and print the result
if (twoSum(arr, target)) {
System.out.println("true");
}
else {
System.out.println("false");
}
}
}
Example Problem - Maximum Sum of a Subarray with K Elements
Given an array arr[] and an integer k, we need to calculate the maximum sum of a subarray having size exactly k.
Input : arr[] = [5, 2, -1, 0, 3], k = 3
Output : 6
Explanation : We get maximum sum by considering the subarray [5, 2 , -1]
Input : arr[] = [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4
Output : 39
Explanation : We get maximum sum by adding subarray [4, 2, 10, 23] of size 4.
Using the Sliding Window Technique - O(n) Time and O(1) Space
• We compute the sum of the first k elements out of n terms using a linear loop and store the sum in variable window_sum.
• Then we will traverse linearly over the array till it reaches the end and simultaneously keep track of the maximum sum.
• To get the current sum of a block of k elements just subtract the first element from the previous block and add the last element of the current block.
class Solution {
public int maxSumSubarray(int[] nums, int k) {
int n = nums.length;
if (n < k) return 0;
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
int maxSum = windowSum;
for (int i = k; i < n; i++) {
windowSum += nums[i]; // add next element
windowSum -= nums[i - k]; // remove left element
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
}
Prefix Sum Array - Implementation - GeeksforGeeks
Given an array arr[], Find the prefix sum of the array. A prefix sum array is another array prefixSum[] of the same size, such that prefixSum[i] is arr[0] + arr[1] + arr[2] . . . arr[i].
Examples:
Input: arr[] = [10, 20, 10, 5, 15]
Output: [10, 30, 40, 45, 60]
Explanation: For each index i, add all the elements from 0 to i:
prefixSum[0] = 10,
prefixSum[1] = 10 + 20 = 30,
prefixSum[2] = 10 + 20 + 10 = 40 and so on.
// function to find the prefix sum array
function prefSum(arr) {
let n = arr.length;
// to store the prefix sum
let prefixSum = new Array(n);
// initialize the first element
prefixSum[0] = arr[0];
// Adding present element with previous element
for (let i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] + arr[i];
return prefixSum;
}
// Driver Code
let arr = [10, 20, 10, 5, 15];
let prefixSum = prefSum(arr);
for (let i of prefixSum) {
process.stdout.write(i + " ");
}
Comments
Post a Comment