Coding Questions with Solutions and Explanations
Coding Questions with Solutions and Explanations
1. Chain of Beads
Problem:
Find the maximum sum among all continuous subarrays.
Approach:
Use Kadane’s Algorithm to keep track of:
- current maximum subarray sum
- overall maximum sum
Java Solution:
(imported exactly as provided)
------------------------------------------------------------
2. Equal Numbers
Problem:
Find minimum operations required to make all numbers equal.
Approach:
Sort the array and choose the median.
The median minimizes total absolute difference.
Java Solution:
(imported exactly as provided)
------------------------------------------------------------
3. Sort the URLs
Problem:
Sort URLs based on popularity.
If frequencies are same, sort lexicographically.
Approach:
- Use HashMap for counting frequency
- Sort entries using custom comparator
Java Solution:
(imported exactly as provided)
------------------------------------------------------------
4. PK's World Tour
Problem:
Find minimum travel cost without using same transport consecutively.
Approach:
Dynamic Programming:
dp[i][j] stores minimum cost to reach country i using transport j.
Java Solution:
(imported exactly as provided)
------------------------------------------------------------
5. Good Array
Problem:
Remove consecutive duplicate characters.
Approach:
Use StringBuilder and append only non-duplicate consecutive characters.
Java Solution:
(imported exactly as provided)
1. Chain of Beads
import [Link].*;
import [Link].*;
class Main {
public static void main(String args[]) {
Scanner sc = new Scanner([Link]);
if (![Link]()) {
return;
}
int n = [Link]();
long maxSoFar = Long.MIN_VALUE;
long currentMax = 0;
for (int i = 0; i < n; i++) {
long val = [Link]();
if (i == 0) {
maxSoFar = val;
currentMax = val;
} else {
currentMax = [Link](val, currentMax + val);
maxSoFar = [Link](maxSoFar, currentMax);
}
}
[Link](maxSoFar);
[Link]();
}
}
2. Equal Numbers
import [Link].*;
class Main {
public static void main(String args[]) {
Scanner sc = new Scanner([Link]);
if (![Link]()) return;
int t = [Link]();
for (int i = 0; i < t; i++) {
int n = [Link]();
long[] a = new long[n];
for (int j = 0; j < n; j++) {
a[j] = [Link]();
}
[Link](a);
long median = a[n / 2];
long cost = 0;
for (int j = 0; j < n; j++) {
cost += [Link](a[j] - median);
}
[Link](cost);
}
[Link]();
}
}
3. Sort the URLs
import [Link].*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
if (![Link]()) return;
int n = [Link]();
Map<String, Integer> freqMap = new HashMap<>();
for (int i = 0; i < n; i++) {
String url = [Link]();
[Link](url, [Link](url, 0) + 1);
}
List<[Link]<String, Integer>> list =
new ArrayList<>([Link]());
[Link]((a, b) -> {
int countCmp = [Link]().compareTo([Link]());
if (countCmp != 0) {
return countCmp;
}
return [Link]().compareTo([Link]());
});
[Link]([Link]());
for ([Link]<String, Integer> entry : list) {
[Link]([Link]());
}
[Link]();
}
}
4. PK's World Tour
import [Link].*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
if (![Link]()) return;
int n = [Link]();
long[][] dp = new long[n][3];
for (int i = 0; i < n; i++) {
long cost0 = [Link]();
long cost1 = [Link]();
long cost2 = [Link]();
if (i == 0) {
dp[i][0] = cost0;
dp[i][1] = cost1;
dp[i][2] = cost2;
} else {
dp[i][0] =
cost0 + [Link](dp[i - 1][1], dp[i - 1][2]);
dp[i][1] =
cost1 + [Link](dp[i - 1][0], dp[i - 1][2]);
dp[i][2] =
cost2 + [Link](dp[i - 1][0], dp[i - 1][1]);
}
}
long minCost =
[Link](dp[n - 1][0],
[Link](dp[n - 1][1], dp[n - 1][2]));
[Link](minCost);
[Link]();
}
}
5. Good Array
import [Link].*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
if (![Link]()) return;
int t = [Link]();
for (int i = 0; i < t; i++) {
String s = [Link]();
StringBuilder res = new StringBuilder();
[Link]([Link](0));
for (int j = 1; j < [Link](); j++) {
if ([Link](j) != [Link](j - 1)) {
[Link]([Link](j));
}
}
[Link]([Link]());
}
[Link]();
}
}