Java Interview Programming Problems 100 Essentials

====================================================

By: ChatGPT
Contents: 100 common interview problems with concise Java solutions.

Sections: Strings & Arrays, Math, Arrays & Matrices, Linked Lists, Stacks & Queues,
Trees & Graphs, Dynamic Programming, Java-Specific, Miscellaneous, Advanced.

Tip: Copy code snippets into your IDE and run with your own tests.
Problems 1 4
============

1. Reverse a String
```java
public static String reverse(String s) {
char[] a = s.toCharArray();
int i = 0, j = a.length - 1;
while (i < j) {
char t = a[i]; a[i] = a[j]; a[j] = t;
i++; j--;
}
return new String(a);
}
```

2. Check Palindrome String

```java
public static boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
return true;
}
```

3. First Non-Repeating Character

```java
public static int firstUniqueChar(String s) {
int[] cnt = new int[256];
for (char c : s.toCharArray()) cnt[c]++;
for (int i = 0; i < s.length(); i++) if (cnt[s.charAt(i)] == 1) return i;
return -1;
}
```

4. Character Frequency Map

```java
public static Map<Character,Integer> freq(String s) {
Map<Character,Integer> map = new LinkedHashMap<>();
for (char c : s.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);
return map;
}
```
Problems 5 8
============

5. Anagram Check
```java
public static boolean isAnagram(String a, String b) {
if (a.length() != b.length()) return false;
int[] cnt = new int[256];
for (char c : a.toCharArray()) cnt[c]++;
for (char c : b.toCharArray()) if (--cnt[c] < 0) return false;
return true;
}
```

6. All Permutations of a String (Backtracking)

```java
public static List<String> perms(String s) {
List<String> out = new ArrayList<>();
char[] a = s.toCharArray();
backtrack(a, 0, out);
return out;
}
private static void backtrack(char[] a, int i, List<String> out) {
if (i == a.length) { out.add(new String(a)); return; }
for (int j = i; j < a.length; j++) {
swap(a, i, j); backtrack(a, i+1, out); swap(a, i, j);
}
}
private static void swap(char[] a, int i, int j) { char t=a[i]; a[i]=a[j]; a[j]=t; }
```

7. Remove Duplicate Characters (Preserve Order)

```java
public static String removeDup(String s) {
boolean[] seen = new boolean[256];
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) if (!seen[c]) { seen[c] = true; sb.append(c); }
return sb.toString();
}
```

8. Reverse Words in a Sentence

```java
public static String reverseWords(String s) {
String[] parts = s.trim().split("\\s+");
Collections.reverse(Arrays.asList(parts));
return String.join(" ", parts);
}
```
Problems 9 12
=============

9. Substring Search (KMP)

```java
public static int indexOf(String hay, String needle) {
if (needle.isEmpty()) return 0;
int m = needle.length(), n = hay.length();
int[] lps = new int[m];
for (int i=1, len=0; i<m; ) {
if (needle.charAt(i)==needle.charAt(len)) lps[i++]=++len;
else if (len>0) len=lps[len-1];
else lps[i++]=0;
}
for (int i=0, j=0; i<n; ) {
if (hay.charAt(i)==needle.charAt(j)) { i++; j++; if (j==m) return i-j; }
else if (j>0) j=lps[j-1]; else i++;
}
return -1;
}
```

10. Longest Substring Without Repeating Characters (Sliding Window)

```java
public static int lengthOfLongestSubstring(String s) {
int[] idx = new int[256];
Arrays.fill(idx, -1);
int best=0, start=0;
for (int i=0;i<s.length();i++) {
char c=s.charAt(i);
if (idx[c]>=start) start=idx[c]+1;
idx[c]=i;
best=Math.max(best,i-start+1);
}
return best;
}
```

11. Prime Check

```java
public static boolean isPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
for (int i=3; i*i<=n; i+=2) if (n % i == 0) return false;
return true;
}
```

12. Factorial (Iterative & Recursive)

```java
public static long factIter(int n){ long f=1; for(int i=2;i<=n;i++) f*=i; return f; }
public static long factRec(int n){ return n<=1?1:n*factRec(n-1); }
```
Problems 13 16
==============

13. Fibonacci (Iterative)

```java
public static long fib(int n) {
if (n<=1) return n;
long a=0,b=1;
for(int i=2;i<=n;i++){ long c=a+b; a=b; b=c; }
return b;
}
```

14. Armstrong Number

```java
public static boolean isArmstrong(int n) {
int x=n, sum=0, d=(int)Math.log10(n)+1;
while (x>0){ int r=x%10; sum+=Math.pow(r,d); x/=10; }
return sum==n;
}
```

15. GCD & LCM

```java
public static int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
public static long lcm(int a,int b){ return (long)a/gcd(a,b)*b; }
```

16. Swap Without Temp

```java
public static void swap(int[] a, int i, int j){
if(i==j) return;
a[i]^=a[j]; a[j]^=a[i]; a[i]^=a[j];
}
```
Problems 17 20
==============

17. Reverse Integer

```java
public static int reverseInt(int x){
long res=0;
while (x!=0){ res = res*10 + x%10; x/=10; if (res>Integer.MAX_VALUE || res<Integer.MIN_VALUE)
return 0; }
return (int)res;
}
```

18. Missing Number 1..n

```java
public static int missing(int[] a){
long n=a.length+1;
long sum=n*(n+1)/2;
for(int v:a) sum-=v;
return (int)sum;
}
```

19. Find Duplicates in Array (Floyd's)

```java
public static int findDuplicate(int[] nums){
int slow=nums[0], fast=nums[nums[0]];
while (slow!=fast){ slow=nums[slow]; fast=nums[nums[fast]]; }
fast=0;
while (slow!=fast){ slow=nums[slow]; fast=nums[fast]; }
return slow;
}
```

20. Power of Two

```java
public static boolean isPowerOfTwo(int n){
return n>0 && (n & (n-1)) == 0;
}
```
Problems 21 24
==============

21. Min & Max in Array

```java
public static int[] minMax(int[] a){
int min=a[0], max=a[0];
for(int v:a){ if(v<min) min=v; if(v>max) max=v; }
return new int[]{min,max};
}
```

22. Second Largest Element

```java
public static Integer secondLargest(int[] a){
Integer first=null, second=null;
for(int v:a){
if(first==null || v>first){ second=first; first=v; }
else if(v!=first && (second==null || v>second)){ second=v; }
}
return second;
}
```

23. Sort Array (QuickSort)

```java
public static void quickSort(int[] a){ qs(a,0,a.length-1); }
private static void qs(int[] a,int l,int r){
if(l>=r) return;
int i=l, j=r, pivot=a[(l+r)/2];
while(i<=j){
while(a[i]<pivot) i++;
while(a[j]>pivot) j--;
if(i<=j){ int t=a[i]; a[i]=a[j]; a[j]=t; i++; j--; }
}
if(l<j) qs(a,l,j);
if(i<r) qs(a,i,r);
}
```

24. Merge Two Sorted Arrays

```java
public static int[] merge(int[] a, int[] b){
int i=0,j=0,k=0; int[] c=new int[a.length+b.length];
while(i<a.length && j<b.length) c[k++]= a[i]<=b[j]?a[i++]:b[j++];
while(i<a.length) c[k++]=a[i++];
while(j<b.length) c[k++]=b[j++];
return c;
}
```
Problems 25 28
==============

25. Rotate Array by k

```java
public static void rotate(int[] a, int k){
int n=a.length; k%=n;
rev(a,0,n-1); rev(a,0,k-1); rev(a,k,n-1);
}
private static void rev(int[] a,int l,int r){ while(l<r){ int t=a[l]; a[l]=a[r]; a[r]=t; l++; r--; }
}
```

26. Move Zeros to End

```java
public static void moveZeros(int[] a){
int i=0;
for(int v:a) if(v!=0) a[i++]=v;
while(i<a.length) a[i++]=0;
}
```

27. Max Subarray Sum (Kadane)

```java
public static int maxSubArray(int[] a){
int best=a[0], cur=a[0];
for(int i=1;i<a.length;i++){
cur=Math.max(a[i],cur+a[i]);
best=Math.max(best,cur);
}
return best;
}
```

28. Intersection of Two Arrays

```java
public static int[] intersect(int[] a, int[] b){
Map<Integer,Integer> m=new HashMap<>();
for(int v:a) m.put(v,m.getOrDefault(v,0)+1);
List<Integer> res=new ArrayList<>();
for(int v:b){ Integer c=m.get(v); if(c!=null && c>0){ res.add(v); m.put(v,c-1); } }
return res.stream().mapToInt(x->x).toArray();
}
```
Problems 29 32
==============

29. Spiral Order of Matrix

```java
public static List<Integer> spiral(int[][] m){
List<Integer> out=new ArrayList<>();
int top=0, left=0, bottom=m.length-1, right=m[0].length-1;
while(top<=bottom && left<=right){
for(int j=left;j<=right;j++) out.add(m[top][j]); top++;
for(int i=top;i<=bottom;i++) out.add(m[i][right]); right--;
if(top<=bottom){ for(int j=right;j>=left;j--) out.add(m[bottom][j]); bottom--; }
if(left<=right){ for(int i=bottom;i>=top;i--) out.add(m[i][left]); left++; }
}
return out;
}
```

30. Transpose Matrix

```java
public static int[][] transpose(int[][] m){
int r=m.length, c=m[0].length; int[][] t=new int[c][r];
for(int i=0;i<r;i++) for(int j=0;j<c;j++) t[j][i]=m[i][j];
return t;
}
```

31. Reverse Linked List (Iterative)

```java
static class ListNode{ int val; ListNode next; ListNode(int v){val=v;} }
public static ListNode reverseList(ListNode head){
ListNode prev=null, cur=head;
while(cur!=null){ ListNode nxt=cur.next; cur.next=prev; prev=cur; cur=nxt; }
return prev;
}
```

32. Detect Cycle (Floyd)

```java
public static boolean hasCycle(ListNode head){
ListNode slow=head, fast=head;
while(fast!=null && fast.next!=null){
slow=slow.next; fast=fast.next.next;
if(slow==fast) return true;
}
return false;
}
```
Problems 33 36
==============

33. Middle of Linked List

```java
public static ListNode middle(ListNode head){
ListNode slow=head, fast=head;
while(fast!=null && fast.next!=null){ slow=slow.next; fast=fast.next.next; }
return slow;
}
```

34. Merge Two Sorted Lists

```java
public static ListNode mergeTwo(ListNode a, ListNode b){
ListNode dummy=new ListNode(0), cur=dummy;
while(a!=null && b!=null){
if(a.val<=b.val){ cur.next=a; a=a.next; }
else { cur.next=b; b=b.next; }
cur=cur.next;
}
cur.next = (a!=null)?a:b;
return dummy.next;
}
```

35. Remove Duplicates (Sorted List)

```java
public static ListNode removeDupSorted(ListNode head){
ListNode cur=head;
while(cur!=null && cur.next!=null){
if(cur.val==cur.next.val) cur.next=cur.next.next;
else cur=cur.next;
}
return head;
}
```

36. Nth from End

```java
public static ListNode nthFromEnd(ListNode head, int n){
ListNode fast=head, slow=head;
for(int i=0;i<n;i++) fast=fast.next;
while(fast!=null){ fast=fast.next; slow=slow.next; }
return slow;
}
```
Problems 37 40
==============

37. Palindrome Linked List

```java
public static boolean isPalindrome(ListNode head){
if(head==null||head.next==null) return true;
ListNode slow=head, fast=head;
while(fast!=null && fast.next!=null){ slow=slow.next; fast=fast.next.next; }
ListNode second=reverseList(slow), p1=head, p2=second;
boolean ok=true;
while(p2!=null){ if(p1.val!=p2.val){ ok=false; break; } p1=p1.next; p2=p2.next; }
// optional: restore list
return ok;
}
```

38. Flatten Linked List (K Sorted Lists via Min-Heap idea)

```java
// If nodes have 'down' pointers representing sorted lists
static class Node { int val; Node right, down; Node(int v){val=v;} }
public static Node mergeDown(Node a, Node b){
Node dummy=new Node(0), cur=dummy;
while(a!=null && b!=null){
if(a.val<=b.val){ cur.down=a; a=a.down; }
else { cur.down=b; b=b.down; }
cur=cur.down;
}
cur.down = (a!=null)?a:b;
return dummy.down;
}
public static Node flatten(Node head){
if(head==null || head.right==null) return head;
return mergeDown(head, flatten(head.right));
}
```

39. Delete Node Without Head Reference

```java
public static void deleteNode(ListNode node){
if(node==null || node.next==null) return;
node.val = node.next.val;
node.next = node.next.next;
}
```

40. Sort Linked List (Merge Sort)

```java
public static ListNode sortList(ListNode head){
if(head==null||head.next==null) return head;
ListNode slow=head, fast=head, prev=null;
while(fast!=null && fast.next!=null){ prev=slow; slow=slow.next; fast=fast.next.next; }
prev.next=null;
 ListNode l=sortList(head), r=sortList(slow);
return mergeTwo(l,r);
}
```
Problems 41 44
==============

41. Implement Stack (ArrayList)

```java
static class MyStack {
private ArrayList<Integer> a = new ArrayList<>();
public void push(int x){ a.add(x); }
public int pop(){ return a.remove(a.size()-1); }
public int peek(){ return a.get(a.size()-1); }
public boolean isEmpty(){ return a.isEmpty(); }
}
```

42. Queue Using Two Stacks

```java
static class MyQueue {
Deque<Integer> in=new ArrayDeque<>(), out=new ArrayDeque<>();
public void enqueue(int x){ in.push(x); }
public int dequeue(){ if(out.isEmpty()) move(); return out.pop(); }
public int peek(){ if(out.isEmpty()) move(); return out.peek(); }
private void move(){ while(!in.isEmpty()) out.push(in.pop()); }
public boolean isEmpty(){ return in.isEmpty() && out.isEmpty(); }
}
```

43. Evaluate Postfix

```java
public static int evalPostfix(String[] tokens){
Deque<Integer> st=new ArrayDeque<>();
for(String t:tokens){
switch(t){
case "+": st.push(st.pop()+st.pop()); break;
case "-": {int b=st.pop(), a=st.pop(); st.push(a-b);} break;
case "*": st.push(st.pop()*st.pop()); break;
case "/": {int b=st.pop(), a=st.pop(); st.push(a/b);} break;
default: st.push(Integer.parseInt(t));
}
}
return st.pop();
}
```

44. Min Stack

```java
static class MinStack {
Deque<Integer> st=new ArrayDeque<>(), min=new ArrayDeque<>();
public void push(int x){ st.push(x); min.push(min.isEmpty()?x:Math.min(x,min.peek())); }
public int pop(){ min.pop(); return st.pop(); }
public int top(){ return st.peek(); }
public int getMin(){ return min.peek(); }
}
```
Problems 45 48
==============

45. Next Greater Element

```java
public static int[] nextGreater(int[] a){
int n=a.length; int[] res=new int[n]; Arrays.fill(res,-1);
Deque<Integer> st=new ArrayDeque<>();
for(int i=0;i<n;i++){
while(!st.isEmpty() && a[i]>a[st.peek()]) res[st.pop()]=a[i];
st.push(i);
}
return res;
}
```

46. Circular Queue

```java
static class CircularQueue{
int[] q; int head=0, size=0;
CircularQueue(int k){ q=new int[k]; }
public boolean enq(int x){ if(size==q.length) return false; q[(head+size)%q.length]=x; size++;
return true; }
public Integer deq(){ if(size==0) return null; int v=q[head]; head=(head+1)%q.length; size--;
return v; }
}
```

47. Balanced Parentheses

```java
public static boolean isValid(String s){
Deque<Character> st=new ArrayDeque<>();
for(char c:s.toCharArray()){
if(c=='('||c=='{'||c=='[') st.push(c);
else {
if(st.isEmpty()) return false;
char o=st.pop();
if((o=='('&&c!=')')||(o=='{'&&c!='}')||(o=='['&&c!=']')) return false;
}
}
return st.isEmpty();
}
```

48. LRU Cache (LinkedHashMap)

```java
static class LRU<K,V> extends LinkedHashMap<K,V>{
private final int cap;
LRU(int cap){ super(cap,0.75f,true); this.cap=cap; }
protected boolean removeEldestEntry(Map.Entry<K,V> e){ return size()>cap; }
}
```
Problems 49 52
==============

49. Reverse a Stack using Recursion

```java
public static void reverseStack(Deque<Integer> st){
if(st.isEmpty()) return;
int x=st.pop();
reverseStack(st);
insertBottom(st,x);
}
private static void insertBottom(Deque<Integer> st,int x){
if(st.isEmpty()){ st.push(x); return; }
int y=st.pop(); insertBottom(st,x); st.push(y);
}
```

50. Priority Queue (K Largest)

```java
public static List<Integer> kLargest(int[] a, int k){
PriorityQueue<Integer> pq=new PriorityQueue<>();
for(int v:a){ pq.offer(v); if(pq.size()>k) pq.poll(); }
ArrayList<Integer> res=new ArrayList<>(pq);
Collections.sort(res, Collections.reverseOrder());
return res;
}
```

51. Binary Tree Traversals

```java
static class TreeNode{ int val; TreeNode left,right; TreeNode(int v){val=v;} }
public static void inorder(TreeNode r, List<Integer> out){ if(r==null) return; inorder(r.left,out);
out.add(r.val); inorder(r.right,out); }
public static void preorder(TreeNode r, List<Integer> out){ if(r==null) return; out.add(r.val);
preorder(r.left,out); preorder(r.right,out); }
public static void postorder(TreeNode r, List<Integer> out){ if(r==null) return;
postorder(r.left,out); postorder(r.right,out); out.add(r.val); }
```

52. Level Order (BFS)

```java
public static List<List<Integer>> levelOrder(TreeNode root){
List<List<Integer>> res=new ArrayList<>(); if(root==null) return res;
Deque<TreeNode> q=new ArrayDeque<>(); q.offer(root);
while(!q.isEmpty()){
int sz=q.size(); List<Integer> level=new ArrayList<>(sz);
for(int i=0;i<sz;i++){ TreeNode n=q.poll(); level.add(n.val);
if(n.left!=null) q.offer(n.left); if(n.right!=null) q.offer(n.right);
}
res.add(level);
}
return res;
}
```
Problems 53 56
==============

53. Check Balanced Binary Tree

```java
public static boolean isBalanced(TreeNode r){ return height(r)!=-1; }
private static int height(TreeNode n){
if(n==null) return 0;
int lh=height(n.left); if(lh==-1) return -1;
int rh=height(n.right); if(rh==-1) return -1;
if(Math.abs(lh-rh)>1) return -1;
return Math.max(lh,rh)+1;
}
```

54. Height of Tree

```java
public static int heightTree(TreeNode n){
return n==null?0:1+Math.max(heightTree(n.left),heightTree(n.right));
}
```

55. Lowest Common Ancestor (BST)

```java
public static TreeNode lcaBST(TreeNode r, int p, int q){
while(r!=null){
if(p<r.val && q<r.val) r=r.left;
else if(p>r.val && q>r.val) r=r.right;
else return r;
}
return null;
}
```

56. Serialize/Deserialize Binary Tree (Preorder '#')

```java
public static String serialize(TreeNode r){
StringBuilder sb=new StringBuilder(); ser(r,sb); return sb.toString();
}
private static void ser(TreeNode n,StringBuilder sb){
if(n==null){ sb.append("#,"); return; }
sb.append(n.val).append(",");
ser(n.left,sb); ser(n.right,sb);
}
public static TreeNode deserialize(String s){
Deque<String> q=new ArrayDeque<>(Arrays.asList(s.split(",")));
return des(q);
}
private static TreeNode des(Deque<String> q){
String t=q.poll(); if(t.equals("#")) return null;
TreeNode n=new TreeNode(Integer.parseInt(t));
n.left=des(q); n.right=des(q); return n;
}
```
Problems 57 60
==============

57. Diameter of Binary Tree

```java
public static int diameter(TreeNode root){
int[] best=new int[1];
depth(root,best);
return best[0];
}
private static int depth(TreeNode n, int[] best){
if(n==null) return 0;
int l=depth(n.left,best), r=depth(n.right,best);
best[0]=Math.max(best[0], l+r);
return 1+Math.max(l,r);
}
```

58. Check Identical Trees

```java
public static boolean same(TreeNode a, TreeNode b){
if(a==null||b==null) return a==b;
return a.val==b.val && same(a.left,b.left) && same(a.right,b.right);
}
```

59. Detect Cycle in Graph (DFS)

```java
public static boolean hasCycleUndirected(int n, List<int[]> edges){
List<List<Integer>> g=new ArrayList<>();
for(int i=0;i<n;i++) g.add(new ArrayList<>());
for(int[] e:edges){ g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
boolean[] vis=new boolean[n];
for(int i=0;i<n;i++) if(!vis[i] && dfs(i,-1,g,vis)) return true;
return false;
}
private static boolean dfs(int u,int p,List<List<Integer>> g,boolean[] vis){
vis[u]=true;
for(int v:g.get(u)){
if(v==p) continue;
if(vis[v] || dfs(v,u,g,vis)) return true;
}
return false;
}
```

60. Dijkstra's Algorithm

```java
static class Edge{ int v,w; Edge(int v,int w){this.v=v;this.w=w;} }
public static int[] dijkstra(int n, List<List<Edge>> g, int src){
int[] dist=new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src]=0;
PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(a->a[1]));
pq.offer(new int[]{src,0});
 boolean[] vis=new boolean[n];
while(!pq.isEmpty()){
int[] cur=pq.poll(); int u=cur[0]; if(vis[u]) continue; vis[u]=true;
for(Edge e:g.get(u)){
if(dist[u]!=Integer.MAX_VALUE && dist[u]+e.w < dist[e.v]){
dist[e.v]=dist[u]+e.w; pq.offer(new int[]{e.v, dist[e.v]});
}
}
}
return dist;
}
```
Problems 61 64
==============

61. Longest Common Subsequence

```java
public static int lcs(String a, String b){
int n=a.length(), m=b.length(); int[][] dp=new int[n+1][m+1];
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
dp[i][j]= a.charAt(i-1)==b.charAt(j-1) ? 1+dp[i-1][j-1] : Math.max(dp[i-1][j],dp[i][j-1]);
return dp[n][m];
}
```

62. Longest Increasing Subsequence (n log n)

```java
public static int lis(int[] a){
int[] tails=new int[a.length]; int len=0;
for(int x:a){
int i=Arrays.binarySearch(tails,0,len,x);
if(i<0) i=-(i+1);
tails[i]=x;
if(i==len) len++;
}
return len;
}
```

63. Coin Change (Min Coins)

```java
public static int coinChange(int[] coins,int amount){
int INF=1_000_000, dp[]=new int[amount+1];
Arrays.fill(dp, INF); dp[0]=1;
for(int c:coins) for(int s=c; s<=amount; s++) dp[s]=Math.min(dp[s], dp[s-c]==INF?INF:dp[s-c]+1);
return dp[amount]==INF?-1:dp[amount]-1;
}
```

64. Edit Distance

```java
public static int editDistance(String a,String b){
int n=a.length(), m=b.length(); int[][] dp=new int[n+1][m+1];
for(int i=0;i<=n;i++) dp[i][0]=i;
for(int j=0;j<=m;j++) dp[0][j]=j;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
if(a.charAt(i-1)==b.charAt(j-1)) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=1+Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
}
return dp[n][m];
}
```
Problems 65 68
==============

65. 0/1 Knapsack

```java
public static int knapsack(int[] wt,int[] val,int W){
int n=wt.length; int[][] dp=new int[n+1][W+1];
for(int i=1;i<=n;i++) for(int w=0;w<=W;w++){
dp[i][w]=dp[i-1][w];
if(wt[i-1]<=w) dp[i][w]=Math.max(dp[i][w], val[i-1]+dp[i-1][w-wt[i-1]]);
}
return dp[n][W];
}
```

66. Matrix Chain Multiplication

```java
public static int mcm(int[] p){
int n=p.length-1; int[][] dp=new int[n][n];
for(int len=2; len<=n; len++){
for(int i=0;i+len-1<n;i++){
int j=i+len-1; dp[i][j]=Integer.MAX_VALUE;
for(int k=i;k<j;k++) dp[i][j]=Math.min(dp[i][j],
dp[i][k]+dp[k+1][j]+p[i]*p[k+1]*p[j+1]);
}
}
return dp[0][n-1];
}
```

67. Word Break

```java
public static boolean wordBreak(String s, Set<String> dict){
boolean[] dp=new boolean[s.length()+1]; dp[0]=true;
for(int i=1;i<=s.length();i++){
for(int j=0;j<i;j++){
if(dp[j] && dict.contains(s.substring(j,i))){ dp[i]=true; break; }
}
}
return dp[s.length()];
}
```

68. Maximum Product Subarray

```java
public static int maxProduct(int[] a){
int max=a[0], min=a[0], ans=a[0];
for(int i=1;i<a.length;i++){
if(a[i]<0){ int t=max; max=min; min=t; }
max=Math.max(a[i], max*a[i]);
min=Math.min(a[i], min*a[i]);
ans=Math.max(ans, max);
}
 return ans;
}
```
Problems 69 72
==============

69. Unique Paths in Grid

```java
public static int uniquePaths(int m,int n){
int[] dp=new int[n]; Arrays.fill(dp,1);
for(int i=1;i<m;i++) for(int j=1;j<n;j++) dp[j]+=dp[j-1];
return dp[n-1];
}
```

70. Minimum Path Sum in Grid

```java
public static int minPathSum(int[][] g){
int m=g.length, n=g[0].length;
int[] dp=new int[n]; dp[0]=g[0][0];
for(int j=1;j<n;j++) dp[j]=dp[j-1]+g[0][j];
for(int i=1;i<m;i++){
dp[0]+=g[i][0];
for(int j=1;j<n;j++) dp[j]=Math.min(dp[j], dp[j-1]) + g[i][j];
}
return dp[n-1];
}
```

71. Singleton Pattern (Thread-Safe, Lazy)

```java
public class Singleton {
private static volatile Singleton INSTANCE;
private Singleton(){}
public static Singleton getInstance(){
if (INSTANCE == null) {
synchronized (Singleton.class) {
if (INSTANCE == null) INSTANCE = new Singleton();
}
}
return INSTANCE;
}
}
```

72. == vs equals()
```java
// == compares references for objects; equals() compares logical equality (may be overridden).
// Example:
String a = new String("hi"), b = new String("hi");
boolean refEqual = (a==b); // false
boolean logicalEqual = a.equals(b); // true
```
Problems 73 76
==============

73. Word Frequency with HashMap

```java
public static Map<String,Integer> wordFreq(String text){
Map<String,Integer> m=new HashMap<>();
for(String w : text.toLowerCase().split("\\W+"))
if(!w.isEmpty()) m.put(w, m.getOrDefault(w,0)+1);
return m;
}
```

74. Detect Concurrent Modification

```java
// Use ConcurrentHashMap or fail-fast iterator example:
public static void failFast(List<Integer> list){
for(Integer x : list){
// list.add(1); // would throw ConcurrentModificationException
System.out.println(x);
}
}
```

75. Custom Exception

```java
class InvalidAgeException extends Exception{
public InvalidAgeException(String msg){ super(msg); }
}
```

76. Threads: Runnable & Thread

```java
class MyTask implements Runnable {
public void run(){ System.out.println("Hello from thread!"); }
}
public static void startThread(){
Thread t = new Thread(new MyTask());
t.start();
}
```
Problems 77 80
==============

77. Producer-Consumer with wait/notify

```java
static class BQ {
private final Deque<Integer> q=new ArrayDeque<>(); private final int cap=5;
public synchronized void put(int x) throws InterruptedException {
while(q.size()==cap) wait();
q.addLast(x); notifyAll();
}
public synchronized int take() throws InterruptedException {
while(q.isEmpty()) wait();
int v=q.removeFirst(); notifyAll(); return v;
}
}
```

78. Deadlock Example & Avoidance

```java
final Object A=new Object(), B=new Object();
Thread t1=new Thread(()->{ synchronized(A){ try{Thread.sleep(10);}catch(Exception e){}
synchronized(B){} } });
Thread t2=new Thread(()->{ synchronized(B){ synchronized(A){} } });
// Avoid by ordering locks A then B in all places.
```

79. Java Streams: Filter & Sort

```java
public static List<String> filterSort(List<String> names){
return names.stream().filter(s->s.length()>3).sorted().toList();
}
```

80. HashMap vs LinkedHashMap vs TreeMap

```java
// HashMap: O(1) avg ops, no order.
// LinkedHashMap: maintains insertion order (or access order if configured).
// TreeMap: Red-Black tree, keys sorted, O(log n) ops.
```
Problems 81 84
==============

81. Binary Search

```java
public static int binarySearch(int[] a,int key){
int l=0,r=a.length-1;
while(l<=r){
int m=(l+r)>>>1;
if(a[m]==key) return m;
if(a[m]<key) l=m+1; else r=m-1;
}
return -1;
}
```

82. Quicksort (in-place)

```java
// See #23 for quicksort implementation.
```

83. Mergesort (Top-Down)

```java
public static void mergeSort(int[] a){
int[] tmp=new int[a.length];
ms(a,0,a.length-1,tmp);
}
private static void ms(int[] a,int l,int r,int[] t){
if(l>=r) return;
int m=(l+r)/2;
ms(a,l,m,t); ms(a,m+1,r,t);
int i=l,j=m+1,k=l;
while(i<=m && j<=r) t[k++]= a[i]<=a[j]?a[i++]:a[j++];
while(i<=m) t[k++]=a[i++];
while(j<=r) t[k++]=a[j++];
for(i=l;i<=r;i++) a[i]=t[i];
}
```

84. Top K Frequent Elements

```java
public static int[] topKFrequent(int[] a, int k){
Map<Integer,Integer> cnt=new HashMap<>();
for(int v:a) cnt.put(v,cnt.getOrDefault(v,0)+1);
PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(x->x[1]));
for(var e:cnt.entrySet()){ pq.offer(new int[]{e.getKey(),e.getValue()}); if(pq.size()>k)
pq.poll(); }
int[] res=new int[pq.size()]; int i=0;
while(!pq.isEmpty()) res[i++]=pq.poll()[0];
return res;
}
```
Problems 85 88
==============

85. Cache with LinkedHashMap

```java
// See #48 LRU cache; use accessOrder=true.
```

86. Shortest Word Distance

```java
public static int shortestDistance(String[] words,String a,String b){
int i1=-1,i2=-1,ans=Integer.MAX_VALUE;
for(int i=0;i<words.length;i++){
if(words[i].equals(a)) i1=i;
if(words[i].equals(b)) i2=i;
if(i1!=-1 && i2!=-1) ans=Math.min(ans, Math.abs(i1-i2));
}
return ans;
}
```

87. Tic Tac Toe Winner Check

```java
public static char checkWinner(char[][] b){
for(int i=0;i<3;i++){
if(b[i][0]!=' '&&b[i][0]==b[i][1]&&b[i][1]==b[i][2]) return b[i][0];
if(b[0][i]!=' '&&b[0][i]==b[1][i]&&b[1][i]==b[2][i]) return b[0][i];
}
if(b[0][0]!=' '&&b[0][0]==b[1][1]&&b[1][1]==b[2][2]) return b[0][0];
if(b[0][2]!=' '&&b[0][2]==b[1][1]&&b[1][1]==b[2][0]) return b[0][2];
return ' '; // no winner or draw
}
```

88. Design URL Shortener (Outline)

```java
// Use base62 encoding, mapping from id->url in DB, cache hot entries, REST endpoints:
// POST /shorten {url}, GET /{code} redirect.
// Consider rate limiting, custom aliases, analytics.
```
Problems 89 92
==============

89. Design Parking Lot (OO Design Skeleton)

```java
abstract class Vehicle{ String plate; }
class Car extends Vehicle{} class Bike extends Vehicle{}
class Slot{ int id; boolean covered; Vehicle v; }
class ParkingLot{
Map<Integer,Slot> slots = new HashMap<>();
public boolean park(Vehicle v){ /* find free, assign */ return true; }
public boolean leave(int slotId){ /* free slot */ return true; }
}
```

90. Rate Limiter (Token Bucket Skeleton)

```java
class TokenBucket{
final long capacity, refillPerSec; double tokens; long lastRefill;
TokenBucket(long cap,long rps){ capacity=cap; refillPerSec=rps; tokens=cap;
lastRefill=System.nanoTime(); }
synchronized boolean allow(){
long now=System.nanoTime();
double add = (now-lastRefill)/1e9*refillPerSec;
tokens=Math.min(capacity, tokens+add); lastRefill=now;
if(tokens>=1){ tokens-=1; return true; }
return false;
}
}
```

91. Double-Checked Locking Singleton

```java
// See #71 Singleton implementation (uses volatile + double-checked locking).
```

92. volatile Keyword Demo

```java
class Flag { volatile boolean running = true; }
```
Problems 93 96
==============

93. Callable & Future

```java
ExecutorService es=Executors.newSingleThreadExecutor();
Future<Integer> f = es.submit(()-> 42);
int ans = f.get();
es.shutdown();
```

94. Blocking Queue (Custom, lock/cond)

```java
class BlockingQueueX<T>{
private final Deque<T> q=new ArrayDeque<>(); private final int cap;
public BlockingQueueX(int cap){ this.cap=cap; }
public synchronized void put(T x) throws InterruptedException {
while(q.size()==cap) wait();
q.addLast(x); notifyAll();
}
public synchronized T take() throws InterruptedException {
while(q.isEmpty()) wait();
T v=q.removeFirst(); notifyAll(); return v;
}
}
```

95. Observer Pattern (Minimal)

```java
interface Observer{ void update(String msg); }
interface Subject{ void add(Observer o); void remove(Observer o); void notifyAll(String m); }
class Topic implements Subject{
List<Observer> list=new ArrayList<>();
public void add(Observer o){ list.add(o); }
public void remove(Observer o){ list.remove(o); }
public void notifyAll(String m){ for(Observer o:list) o.update(m); }
}
```

96. BlockingQueue with java.util.concurrent

```java
BlockingQueue<Integer> q=new ArrayBlockingQueue<>(5);
new Thread(()->{ try{ for(int i=0;i<10;i++){ q.put(i); } }catch(Exception e){} }).start();
new Thread(()->{ try{ while(true){ Integer x=q.take(); } }catch(Exception e){} }).start();
```
Problems 97 100
===============

97. Immutability Example

```java
final class Point{
private final int x,y;
public Point(int x,int y){ this.x=x; this.y=y; }
public int x(){ return x; } public int y(){ return y; }
}
```

98. CompletableFuture Async

```java
CompletableFuture<Integer> cf = CompletableFuture.supplyAsync(()-> 21)
.thenApply(x->x*2);
int v = cf.join();
```

99. In-Memory Key-Value Store (Thread-Safe)

```java
class KV{
private final ConcurrentHashMap<String,String> m=new ConcurrentHashMap<>();
public void put(String k,String v){ m.put(k,v); }
public String get(String k){ return m.get(k); }
}
```

100. GC Demo (WeakReference)

```java
Object o = new Object();
WeakReference<Object> w = new WeakReference<>(o);
o = null; System.gc();
// After some time, w.get() may become null.
```