Scribd
Upload
14 views3 pages

Coding Round Solutions Array DP String

The document presents solutions for three coding problems in Java: finding leaders in an array, counting ways to cover a distance using steps of 1, 2, or 3, and finding the longest substring without repeating characters. Each problem includes a brief description, approach, Java code implementation, and an explanation of the solution. The solutions utilize techniques such as dynamic programming and sliding window with HashMap.

Uploaded by

jatinvalechatab
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views3 pages

Coding Round Solutions Array DP String

The document presents solutions for three coding problems in Java: finding leaders in an array, counting ways to cover a distance using steps of 1, 2, or 3, and finding the longest substring without repeating characters. Each problem includes a brief description, approach, Java code implementation, and an explanation of the solution. The solutions utilize techniques such as dynamic programming and sliding window with HashMap.

Uploaded by

jatinvalechatab
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Coding Round Solutions - Java (Array, DP, String)

1. Leaders in an Array

[OK] Problem:
An element is a leader if it is greater than or equal to all elements to its right.

[Idea] Approach:
- Traverse from right to left.
- Keep track of max so far.

[Code] Java Code:


import java.util.*;
public class LeadersInArray {
public static void findLeaders(int[] arr) {
int n = arr.length;
List<Integer> leaders = new ArrayList<>();
int maxRight = arr[n - 1];
leaders.add(maxRight);
for (int i = n - 2; i >= 0; i--) {
if (arr[i] >= maxRight) {
maxRight = arr[i];
leaders.add(maxRight);
}
}
Collections.reverse(leaders);
System.out.println("Leaders: " + leaders);
}
public static void main(String[] args) {
int[] arr = {16, 17, 4, 3, 5, 2};
findLeaders(arr);
}
}

[Explain] Explanation:
From the end, compare with maxRight. Result: [17, 5, 2]

2. Count Ways to Cover Distance (DP)

[OK] Problem:
Count the number of ways to cover distance n using steps of 1, 2, or 3.
Coding Round Solutions - Java (Array, DP, String)

[Idea] Approach:
Dynamic Programming: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

[Code] Java Code:


public class WaysToCoverDistance {
public static int countWays(int dist) {
int[] dp = new int[dist + 1];
dp[0] = 1;
for (int i = 1; i <= dist; i++) {
dp[i] = 0;
if (i >= 1) dp[i] += dp[i - 1];
if (i >= 2) dp[i] += dp[i - 2];
if (i >= 3) dp[i] += dp[i - 3];
}
return dp[dist];
}
public static void main(String[] args) {
int dist = 4;
System.out.println("Ways to cover distance " + dist + " = " + countWays(dist));
}
}

[Explain] Explanation:
dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7

3. Longest Substring Without Repeating Characters

[OK] Problem:
Find the longest substring without repeating characters.

[Idea] Approach:
Use sliding window with HashMap to track characters.

[Code] Java Code:


import java.util.*;
public class LongestUniqueSubstring {
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int maxLen = 0, left = 0;
Coding Round Solutions - Java (Array, DP, String)

for (int right = 0; right < s.length(); right++) {


char c = s.charAt(right);
if (map.containsKey(c)) {
left = Math.max(left, map.get(c) + 1);
}
map.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
public static void main(String[] args) {
String input = "abcabcbb";
System.out.println("Length of Longest Unique Substring: " +
lengthOfLongestSubstring(input));
}
}

[Explain] Explanation:
Sliding window resizes on repeat. Final length = 3 ("abc")

You might also like