DEV Community: Dolly Sharma

Three different ways to combine data in Pandas — concat, merge, and join.

Dolly Sharma — Thu, 26 Mar 2026 12:02:09 +0000

🔹 1. `pd.concat()` → Stack or attach data

👉 Used when you want to combine DataFrames along rows or columns

📌 Row-wise (axis=0)

combined = pd.concat([df1, df2], axis=0)

Stacks df2 below df1
Columns should be same (ideally)

🧠 Think: “append rows”

📌 Column-wise (axis=1)

combined = pd.concat([df1, df2], axis=1)

Adds df2 as new columns
Works based on index alignment

🧠 Think: “side-by-side”

🔹 2. `pd.merge()` → Database-style join

👉 Used when you want to combine based on a common column (key)

📌 Default (inner join)

merged = pd.merge(df1, df2, on="common_column")

Only keeps matching values

📌 Left join

merged = pd.merge(df1, df2, how="left", on="common_column")

Keeps all rows of df1
Matches from df2 (NaN if no match)

📌 Inner join

merged = pd.merge(df1, df2, how="inner", on="common_column")

Same as default
Only common rows

🧠 Think: “SQL JOIN using a column”

🔹 3. `df.join()` → Index-based join

joined = df1.join(df2, how="inner")

👉 Combines using index (not columns)

Faster for index-based operations
Equivalent to merge but simpler syntax

🧠 Think: “merge on index”

🔥 Quick Difference Table

Method	Based On	Use Case
concat	index/axis	stacking data
merge	column (key)	SQL-style joins
join	index	quick index-based combine

✅ When to use what?

Use concat → when data is already aligned
Use merge → when you have a common column
Use join → when index is important

Queue using Stack(s)

Dolly Sharma — Tue, 24 Mar 2026 00:34:54 +0000

🧠 Approach 1: Using TWO Stacks (Efficient)

📌 Idea

Use:

s1 → for push
s2 → for pop / front

✅ Operations

🔹 Push (O(1))

Push into s1

🔹 Pop / Front (Amortized O(1))

If s2 is empty:
- Move all elements from s1 → s2
Then pop from s2

✅ Code (C++)

#include <iostream>
#include <stack>
using namespace std;

class Queue {
    stack<int> s1, s2;

public:
    void push(int x) {
        s1.push(x);
    }

    int pop() {
        if (s1.empty() && s2.empty()) {
            cout << "Queue is empty\n";
            return -1;
        }

        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }

        int val = s2.top();
        s2.pop();
        return val;
    }

    int front() {
        if (s1.empty() && s2.empty()) {
            cout << "Queue is empty\n";
            return -1;
        }

        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }

        return s2.top();
    }

    bool empty() {
        return s1.empty() && s2.empty();
    }
};

int main() {
    Queue q;
    q.push(1);
    q.push(2);
    q.push(3);

    cout << q.front() << endl; // 1
    cout << q.pop() << endl;   // 1
    cout << q.front() << endl; // 2
}

⚡ Complexity

Operation	Time
push	O(1)
pop	Amortized O(1)
front	Amortized O(1)

🔥 Approach 2: Using ONE Stack (Recursive)

📌 Idea

Push normally
For pop → recursively reach bottom element

❗ Drawback

Pop becomes O(n)

✅ Code

#include <iostream>
#include <stack>
using namespace std;

class Queue {
    stack<int> s;

public:
    void push(int x) {
        s.push(x);
    }

    int pop() {
        if (s.empty()) {
            cout << "Queue is empty\n";
            return -1;
        }

        int x = s.top();
        s.pop();

        if (s.empty()) {
            return x;
        }

        int res = pop();
        s.push(x);
        return res;
    }
};

🔍 Key Insight

👉 Stack = LIFO
👉 Queue = FIFO

So we reverse order twice using two stacks to simulate FIFO.

🎯 Interview One-Liner

“Use two stacks: one for input and one for output; transfer elements only when needed to achieve amortized O(1) operations.”

C++ Object Creation & Memory

Dolly Sharma — Tue, 24 Mar 2026 00:07:32 +0000

🔹 1. Object Creation in C++ vs Java

✅ C++

Objects can be created in two ways:

1. Stack Allocation

queue q;

Stored in stack memory
Automatically destroyed when out of scope
Faster and preferred

2. Heap Allocation

queue* q = new queue();
delete q;

Stored in heap memory
Must manually free using delete

✅ Java

Queue q = new Queue();

Objects are created only on heap
new is mandatory
Memory handled by Garbage Collector

🎯 Key Difference

C++ supports both stack & heap allocation → new is optional
Java supports only heap allocation → new is mandatory

🔹 2. Stack Memory

📌 Definition

Memory used for:

Local variables
Function calls
Static allocation

⚙️ Properties

✅ Automatic memory management
⚡ Very fast
📦 Limited size
🔁 Follows LIFO (Last In First Out)
⏳ Lifetime = function/block scope

✅ Example

int x = 10;
queue q;

❌ Problem: Stack Overflow

int arr[10000000]; // too large → crash

🔹 3. Heap Memory

📌 Definition

Memory used for:

Dynamic allocation at runtime

⚙️ Properties

❗ Manual memory management (new / delete)
🐢 Slower than stack
📦 Large memory
⏳ Lifetime = until deleted
🔀 No fixed order

✅ Example

queue* q = new queue();
delete q;

❌ Problem: Memory Leak

queue* q = new queue();
// forgot delete → memory leak

🔹 4. Stack vs Heap (Comparison Table)

Feature	Stack	Heap
Allocation	Automatic	Manual (`new/delete`)
Speed	Fast	Slower
Size	Limited	Large
Lifetime	Scope-based	Until deleted
Access	Direct	Pointer-based
Management	Compiler	Programmer
Risk	Stack overflow	Memory leak

🔹 5. Circular Queue Insight (From Your Code)

📌 Concept

You implemented a circular queue using modulo:

rear = (rear + 1) % 10;
front = (front + 1) % 10;

✅ Why?

Prevents wasted space
Reuses freed indices
Makes array behave like a circle

⚙️ Time Complexity

push() → O(1)
pop() → O(1)
top() → O(1)

🔹 6. When to Use What?

✅ Use Stack When:

Small data
Short lifetime
High performance needed

✅ Use Heap When:

Large data
Dynamic size
Data must persist outside function
Trees, graphs, linked lists

🔹 7. Best Practices (Important 🚀)

✅ Prefer Stack

queue q;

⚠️ Use Heap Carefully

queue* q = new queue();
delete q;

✅ Modern C++ (Recommended)

Use Smart Pointers instead of raw new:

#include <memory>
auto q = make_unique<queue>();

✔ Prevents memory leaks automatically

🔹 8. Common Interview Questions

❓ Why is stack faster than heap?

👉 No overhead of allocation/deallocation (handled by compiler)

❓ Why avoid excessive `new`?

👉 Can cause:

Memory leaks
Fragmentation
Slower performance

❓ What is RAII?

👉 Resource Acquisition Is Initialization

Objects manage their own lifetime automatically

🎯 Final One-Liner Summary

Stack is fast, automatic, and scope-based, while heap is flexible, dynamic, and manually managed.

📘 Minimum Insertions and Deletions to Convert String A -B

Dolly Sharma — Sun, 22 Mar 2026 10:46:41 +0000

🔹 Problem

Given two strings:

s1 → convert into → s2

👉 Find:

Minimum deletions
Minimum insertions

🔥 Key Idea (VERY IMPORTANT)

👉 Use Longest Common Subsequence (LCS)

Let L = LCS(s1, s2)

🔹 Formula

Deletions = n - L
Insertions = m - L

Where:

n = length of s1
m = length of s2

🧠 Why this works?

LCS = part already common → no need to change
Remove extra from s1 → deletions
Add missing for s2 → insertions

🔹 Example

s1 = "heap"
s2 = "pea"

👉 LCS = "ea" → length = 2

Deletions = 4 - 2 = 2
Insertions = 3 - 2 = 1

🔹 Code (C++)

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    vector<int> prev(m+1, 0), curr(m+1, 0);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                curr[j] = 1 + prev[j-1];
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        prev = curr;
    }

    return prev[m];
}

pair<int,int> minInsertDelete(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    int L = lcs(s1, s2);

    int deletions = n - L;
    int insertions = m - L;

    return {deletions, insertions};
}

🔹 Total Operations

If asked:

Minimum operations = deletions + insertions
                  = n + m - 2*LCS

🔹 Important Variants

✅ Only deletions:

n - LCS

✅ Only insertions:

m - LCS

🔥 Interview Pattern

👉 If you see:

“Convert string A → B”
“Insert/Delete operations only”

➡️ Think:

Use LCS

⚡ Quick Summary

L = LCS(s1, s2)

Delete = n - L
Insert = m - L
Total = n + m - 2L

🧠 Intuition Shortcut

Keep common part (LCS)
Remove rest from s1
Add rest from s2

If you want next 🚀
I can show:
✅ Edit Distance (insert + delete + replace)
✅ Print actual operations
✅ Hard problems based on this

Just tell me 👍

📘 Minimum Insertions to Make a String Palindrome

Dolly Sharma — Sun, 22 Mar 2026 10:37:20 +0000

🔹 Key Idea (MOST IMPORTANT)

👉 Use Longest Palindromic Subsequence (LPS)

Minimum Insertions = n - LPS

🔹 Why this works?

LPS = longest part already palindrome
Remaining characters must be inserted to fix symmetry

👉 So:

Total characters − already palindrome part = insertions needed

🔹 Convert to LCS

LPS(s) = LCS(s, reverse(s))

🔥 Final Formula

Min Insertions = n - LCS(s, reverse(s))

🔹 Example

s = "abcaa"

Reverse:

"aacba"

👉 LCS = "aca" → length = 3

Min Insertions = 5 - 3 = 2

🔹 Code (C++)

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[n][m];
}

int minInsertions(string s) {
    string t = s;
    reverse(t.begin(), t.end());

    int lps = lcs(s, t);
    return s.size() - lps;
}

🔹 Space Optimized 🚀

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<int> prev(m+1, 0), curr(m+1, 0);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                curr[j] = 1 + prev[j-1];
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        prev = curr;
    }
    return prev[m];
}

🔹 Alternative DP (Direct without LCS)

👉 Define:

dp[i][j] = min insertions to make s[i..j] palindrome

Transition:

If match:

dp[i][j] = dp[i+1][j-1]

If not:

dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])

🔹 Code (Direct DP)

int minInsertions(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for(int len = 2; len <= n; len++){
        for(int i = 0; i + len - 1 < n; i++){
            int j = i + len - 1;

            if(s[i] == s[j])
                dp[i][j] = dp[i+1][j-1];
            else
                dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]);
        }
    }

    return dp[0][n-1];
}

🔹 Complexity

Approach	Time	Space
LCS-based	O(n²)	O(n²) / O(n)
Direct DP	O(n²)	O(n²)

🧠 Key Pattern

👉 Whenever you see:

“Make palindrome”
“Minimum insert/delete”

➡️ Think:

Use LPS (LCS with reverse)

🔥 Interview Tip

If asked:

“Minimum insertions to make palindrome?”

👉 Answer:

“We compute LPS using LCS with reverse string, then subtract from length.”

⚡ Summary

Convert → LPS
LPS → LCS(s, reverse(s))
Answer → n - LPS

📘 Best Optimized Approach

(From Dynamic Programming)

🔹 Final Optimized Idea

We use:

Min Insertions = n - LCS(s, reverse(s))

👉 Optimize LCS to O(n) space

🔥 Fully Optimized Code (O(n²) time, O(n) space)

int minInsertions(string s) {
    int n = s.size();

    string t = s;
    reverse(t.begin(), t.end());

    vector<int> prev(n+1, 0), curr(n+1, 0);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(s[i-1] == t[j-1])
                curr[j] = 1 + prev[j-1];
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        prev = curr;
    }

    int lps = prev[n];
    return n - lps;
}

🔹 Space Complexity

Approach	Space
Normal DP	O(n²)
Optimized (above)	✅ O(n)

🔥 Can we optimize more?

👉 ❌ NO (for general case)

Why?

You must compare all pairs → needs O(n²) time
LCS inherently requires quadratic time

🔹 Alternative (Direct DP optimized?)

👉 Direct DP:

dp[i][j] = min insertions

❌ Cannot reduce to O(n) easily
👉 Because it depends on:

dp[i+1][j]
dp[i][j-1]
dp[i+1][j-1]

🧠 Final Takeaway

👉 Best you can do:

Metric	Optimal
Time	O(n²)
Space	✅ O(n)

⚡ Interview Answer (Perfect 🔥)

If asked:

“Can you optimize space?”

👉 Say:

“Yes, by computing LCS with a 1D DP array, reducing space to O(n) while keeping time O(n²). Further optimization isn’t possible due to dependency structure.”

🚀 Extra Insight (Advanced)

👉 If asked harder:

You can use Hirschberg’s Algorithm
Space → O(n)
Still O(n²) time
Can reconstruct palindrome too

If you want next 🚀
I can show:
✅ Build the actual palindrome string (very important)
✅ Minimum deletions version
✅ Hard interview problems

Just tell me 👍

📘 Longest Palindromic Subsequence (LPS)

Dolly Sharma — Sun, 22 Mar 2026 09:59:14 +0000

🔹 Key Idea (VERY IMPORTANT 🔥)

👉 Convert LPS → LCS

LPS(s) = LCS(s, reverse(s))

🔹 Why does this work?

Palindrome = same forward & backward
So if we reverse string and find LCS → we get longest palindrome subsequence

🔹 Your Code Explained

string t = s;
reverse(t.begin(), t.end());
return lcs(s, t);

👉 Steps:

Copy string → t
Reverse it
Find LCS between s and t

🔹 Example

s = "bbabcbcab"

Reverse:

t = "bacbcbabb"

👉 LCS = "babcbab" (length = 7)

🔥 Full Code (Clean)

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[n][m];
}

int longestPalindromeSubsequence(string s) {
    string t = s;
    reverse(t.begin(), t.end());
    return lcs(s, t);
}

🔹 Space Optimized Version 🚀

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<int> prev(m+1, 0), curr(m+1, 0);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                curr[j] = 1 + prev[j-1];
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        prev = curr;
    }
    return prev[m];
}

🔥 Print Longest Palindromic Subsequence

👉 Just print LCS of s and reverse(s)

string printLPS(string s) {
    string t = s;
    reverse(t.begin(), t.end());

    int n = s.size();
    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(s[i-1]==t[j-1])
                dp[i][j]=1+dp[i-1][j-1];
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }

    // backtrack
    string ans="";
    int i=n,j=n;
    while(i>0 && j>0){
        if(s[i-1]==t[j-1]){
            ans+=s[i-1];
            i--; j--;
        }
        else if(dp[i-1][j]>dp[i][j-1]) i--;
        else j--;
    }

    reverse(ans.begin(), ans.end());
    return ans;
}

🔹 Complexity

Metric	Value
Time	O(n²)
Space	O(n²) → optimized to O(n)

🧠 Important Observations

LPS is a subsequence, not substring
Works even if characters are not continuous
Always think:

“Reverse + LCS”

🔥 Related Problems

Minimum insertions to make palindrome:

n - LPS

Minimum deletions:

n - LPS

⚡ Interview Tip

If asked:

“Longest palindromic subsequence?”

👉 Say instantly:

“We can solve it using LCS between string and its reverse.”

If you want next 🚀
I can show:
✅ Direct DP without LCS trick
✅ Palindromic substring (different problem ⚠️)
✅ Hard variations

Just tell me 👍

Longest Common Substring

Dolly Sharma — Sun, 22 Mar 2026 09:41:46 +0000

🔹 Definition

👉 Longest substring that is:

Present in both strings
Continuous (no skipping allowed) ❗

🔹 Difference from LCS

Feature	Subsequence	Substring
Continuous	❌	✅
DP reset	❌	✅ (important)

🔥 Core Idea

If characters match:

dp[i][j] = 1 + dp[i-1][j-1]

If NOT match:

dp[i][j] = 0   // 🔥 RESET (this is key difference)

🔹 Code (Correct & Clean C++)

int longestCommonSubstring(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    int ans = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1]){
                dp[i][j] = 1 + dp[i-1][j-1];
                ans = max(ans, dp[i][j]);
            }
            else{
                dp[i][j] = 0;  // 🔥 important
            }
        }
    }

    return ans;
}

🔹 Optimized Space (O(m)) 🚀

int longestCommonSubstring(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    vector<int> prev(m+1, 0), curr(m+1, 0);
    int ans = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1]){
                curr[j] = 1 + prev[j-1];
                ans = max(ans, curr[j]);
            }
            else{
                curr[j] = 0; // reset
            }
        }
        prev = curr;
    }

    return ans;
}

🔥 Print Longest Common Substring

👉 Trick:

Track ending index
Extract substring

🔹 Code (Print substring)

string printLCSubstring(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    int maxLen = 0;
    int endIndex = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1]){
                dp[i][j] = 1 + dp[i-1][j-1];

                if(dp[i][j] > maxLen){
                    maxLen = dp[i][j];
                    endIndex = i; // track end
                }
            }
        }
    }

    return s1.substr(endIndex - maxLen, maxLen);
}

🔹 Example

s1 = "abcde"
s2 = "abfce"

👉 Output:

"ab"

🧠 Key Intuition

Match → extend substring
Not match → break (reset to 0)

⚠️ Common Mistake

❌ Writing:

dp[i][j] = max(...)

👉 That is LCS (wrong problem)

🔥 Interview Tip

If interviewer says:

“Longest common substring”

👉 Immediately think:

“Reset DP to 0 when mismatch”

🚀 Summary

Substring = continuous → reset DP
Use diagonal only
Track max length

If you want next level:
✅ Difference table (LCS vs substring vs subsequence problems)
✅ Hard problems based on this
✅ Visual DP table like your image

Just tell me 👍

📘 Print Longest Common Subsequence (LCS)

Dolly Sharma — Sun, 22 Mar 2026 00:25:45 +0000

🔹 Approach (2 Steps)

✅ Step 1: Build DP Table

Same as LCS length

✅ Step 2: Backtrack

Start from (n, m)
Move:
- Diagonal → if characters match (take char)
- Up / Left → based on max value

🔹 Full Code (C++)

string longestCommonSubsequence(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    // Step 1: DP table
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // Step 2: Backtracking
    int i = n, j = m;
    string ans = "";

    while(i > 0 && j > 0){
        if(s1[i-1] == s2[j-1]){
            ans.push_back(s1[i-1]);
            i--;
            j--;
        }
        else if(dp[i-1][j] > dp[i][j-1]){
            i--;  // move up
        }
        else{
            j--;  // move left
        }
    }

    // reverse because we built it backwards
    reverse(ans.begin(), ans.end());
    return ans;
}

🔹 Example

👉 Input:

s1 = "AGGTAB"
s2 = "GXTXAYB"

👉 Output:

GTAB

🔹 Key Intuition 🧠

Matching characters → part of LCS
Otherwise → follow the path that gave max value

👉 Rule:

Match → take & go diagonal
Not match → go where value is larger

🔹 Complexity

Time: O(n × m)
Space: O(n × m)

🔹 Important Notes ⚠️

Always reverse the answer
This gives one valid LCS, not necessarily all
Works for strings, arrays, etc.

🔥 Interview Tip

If asked:

“Print LCS”

Say confidently:

Build DP table
Backtrack from (n, m)

📘 Hirschberg’s Algorithm (LCS with O(m) space)

🔹 Why do we need it?

Normal LCS:

Time: O(n*m)
Space: O(n*m) ❌ (too large for big strings)

👉 Hirschberg reduces:

Space → O(m) ✅
Still prints LCS!

🔥 Core Idea (Divide & Conquer)

Instead of storing full DP table:

👉 Split string s1 into two halves:

s1 = left_half + right_half

Then:

Compute LCS length of left_half with all prefixes of s2
Compute LCS length of right_half (reversed) with all suffixes of s2
Find best split point k in s2
Recursively solve:

(left_half, s2[0..k])
(right_half, s2[k..m])

🧠 Visualization

s1 = ABC | DEF
s2 = GHIJKL

→ Find split k in s2
→ Solve:
   LCS(ABC, s2[0..k])
   +
   LCS(DEF, s2[k..end])

🔹 Key Trick

We only compute one row at a time → saves space

🔹 Helper Function (1D DP)

vector<int> lcsLength(string a, string b) {
    int n = a.size(), m = b.size();
    vector<int> prev(m+1, 0), curr(m+1, 0);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i-1] == b[j-1])
                curr[j] = 1 + prev[j-1];
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        prev = curr;
    }
    return prev;
}

🔹 Main Hirschberg Function

string hirschberg(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    // base cases
    if(n == 0) return "";
    if(n == 1) {
        for(char c : s2) {
            if(c == s1[0]) return string(1, c);
        }
        return "";
    }

    int mid = n / 2;

    string left = s1.substr(0, mid);
    string right = s1.substr(mid);

    // forward LCS
    vector<int> L1 = lcsLength(left, s2);

    // reverse LCS
    reverse(right.begin(), right.end());
    string rev_s2 = s2;
    reverse(rev_s2.begin(), rev_s2.end());

    vector<int> L2 = lcsLength(right, rev_s2);

    // find partition k
    int k = 0, maxVal = 0;
    for(int j = 0; j <= m; j++){
        int val = L1[j] + L2[m - j];
        if(val > maxVal){
            maxVal = val;
            k = j;
        }
    }

    // divide and conquer
    string lcs_left = hirschberg(left, s2.substr(0, k));
    string lcs_right = hirschberg(s1.substr(mid), s2.substr(k));

    return lcs_left + lcs_right;
}

🔹 Complexity

Metric	Value
Time	O(n × m)
Space	O(m) ✅

🔥 Why it Works

Avoids storing full DP table
Uses only two rows at a time
Reconstructs answer via recursion

⚠️ When to Use

👉 Use Hirschberg when:

Strings are very large
Memory is limited
Interviewer asks “optimize space for printing LCS”

🧠 Interview Answer (Perfect 🔥)

If asked:

“Can you print LCS in O(m) space?”

Say:

“Yes, using Hirschberg’s Algorithm — a divide & conquer approach that computes LCS using 1D DP and reconstructs the sequence recursively.”

⚡ Final Intuition

Split → Solve → Combine
Use forward + reverse DP to find split point

If you want 🚀 next:

Step-by-step dry run of Hirschberg
Compare with normal DP visually
Convert this into interview-ready explanation

Just tell me 👍

DP lecture-25 Longest Common Subsequence (LCS) — Complete Notes

Dolly Sharma — Sat, 21 Mar 2026 23:53:23 +0000

🔹 1. Definition

The Longest Common Subsequence (LCS) of two strings is the longest sequence that appears in both strings in the same order, but not necessarily contiguous.

👉 Example:

s1 = "abcde"
s2 = "ace"
✅ LCS = "ace" (length = 3)

🔹 2. Subsequence vs Substring

Type	Meaning
Subsequence	Can skip characters
Substring	Must be continuous

👉 Example:

"ace" is subsequence of "abcde" ✅
"aec" is NOT ❌ (order changed)

🔹 3. Recursive Thinking (Brute Force)

Case 1: Characters match

f(i, j) = 1 + f(i-1, j-1)

Case 2: Not match

f(i, j) = max(f(i-1, j), f(i, j-1))

Base Case

if i < 0 or j < 0 → return 0

🔹 4. DP Formulation (Tabulation)

Let:

dp[i][j] = LCS length of first i chars of s1 and first j chars of s2

🔹 5. Transition

If match:

dp[i][j] = 1 + dp[i-1][j-1]

If not match:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

🔹 6. Base Case

dp[0][j] = 0
dp[i][0] = 0

🔹 7. DP Table Visualization

For s1 = "abc" and s2 = "ac":

      ""  a  c
   ----------------
"" |  0  0  0
a  |  0  1  1
b  |  0  1  1
c  |  0  1  2

🔹 8. Code (C++ Tabulation)

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[n][m];
}

🔹 9. Space Optimization (Important 🔥)

Use only 2 rows:

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<int> prev(m+1, 0), curr(m+1, 0);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                curr[j] = 1 + prev[j-1];
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        prev = curr;
    }
    return prev[m];
}

🔹 10. Printing the LCS String

string printLCS(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    // build dp
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s1[i-1]==s2[j-1])
                dp[i][j]=1+dp[i-1][j-1];
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }

    // backtrack
    string ans="";
    int i=n, j=m;
    while(i>0 && j>0){
        if(s1[i-1]==s2[j-1]){
            ans += s1[i-1];
            i--; j--;
        }
        else if(dp[i-1][j] > dp[i][j-1]) i--;
        else j--;
    }

    reverse(ans.begin(), ans.end());
    return ans;
}

🔹 11. Time & Space Complexity

Approach	Time	Space
Recursion	Exponential	O(n+m)
DP	O(n*m)	O(n*m)
Optimized	O(n*m)	O(m)

🔥 12. Important Variations (VERY IMPORTANT)

✅ 1. Longest Common Substring

Must be continuous

if match → dp[i][j] = 1 + dp[i-1][j-1]
else → 0

✅ 2. Print Shortest Common Supersequence

Formula:

SCS length = n + m - LCS

✅ 3. Minimum Insertions/Deletions to Convert String

Operations = (n - LCS) + (m - LCS)

✅ 4. Longest Palindromic Subsequence

👉 Trick:

LPS(s) = LCS(s, reverse(s))

✅ 5. Minimum Insertions to Make Palindrome

n - LPS

✅ 6. Distinct Subsequences (Related DP)

Different concept but similar DP structure.

🧠 13. Key Patterns (Must Remember)

👉 If you see:

Two strings
“common”
“subsequence”
“insert/delete”

➡️ Think LCS immediately

⚡ 14. Interview Tips

Always start with recursion → convert to DP
Watch indices (i-1, j-1) carefully
Practice printing LCS (commonly asked)
Space optimization is a bonus point

🎯 15. Summary

LCS is a 2D DP problem
Core idea:

Match → diagonal +1
Not match → max(top, left)

Subset Sum Equal to K — All Approaches (C++)

Dolly Sharma — Mon, 16 Mar 2026 04:05:29 +0000

Subset Sum Equal to K — All Approaches (C++)

Subset Sum is a classic Dynamic Programming problem.

Problem

Given an array arr of n positive integers and a number k, determine whether there exists a subset whose sum equals k.

Example:

arr = [1,2,3,4]
k = 5

Possible subset:

1 + 4 = 5

Answer → true

1️⃣ Recursive Approach (Brute Force)

Idea:
For every element we have two choices:

Take the element
Do not take the element

Recurrence

f(index, target)

Base Cases

if target == 0 → true
if index == 0 → arr[0] == target

Code

bool f(int ind, int target, vector<int>& arr){

    if(target == 0) return true;

    if(ind == 0)
        return arr[0] == target;

    bool notTake = f(ind-1, target, arr);

    bool take = false;
    if(arr[ind] <= target)
        take = f(ind-1, target-arr[ind], arr);

    return take || notTake;
}

bool subsetSumToK(int n, int k, vector<int>& arr){
    return f(n-1, k, arr);
}

Complexity

Time  : O(2^n)
Space : O(n)

Very slow for large n.

2️⃣ Memoization (Top-Down DP)

Avoid recomputing the same states.

DP State

dp[index][target]

Code

bool f(int ind, int target, vector<int>& arr, vector<vector<int>>& dp){

    if(target == 0) return true;

    if(ind == 0)
        return arr[0] == target;

    if(dp[ind][target] != -1)
        return dp[ind][target];

    bool notTake = f(ind-1, target, arr, dp);

    bool take = false;
    if(arr[ind] <= target)
        take = f(ind-1, target-arr[ind], arr, dp);

    return dp[ind][target] = take || notTake;
}

bool subsetSumToK(int n, int k, vector<int>& arr){

    vector<vector<int>> dp(n, vector<int>(k+1, -1));

    return f(n-1, k, arr, dp);
}

Complexity

Time  : O(n × k)
Space : O(n × k) + recursion stack

3️⃣ Tabulation (Bottom-Up DP)

Build DP table iteratively.

DP Table

dp[i][target]

Meaning:

Using elements 0..i, can we form target?

Code

bool subsetSumToK(int n, int k, vector<int>& arr){

    vector<vector<bool>> dp(n, vector<bool>(k+1,false));

    for(int i=0;i<n;i++)
        dp[i][0] = true;

    if(arr[0] <= k)
        dp[0][arr[0]] = true;

    for(int ind=1; ind<n; ind++){

        for(int target=1; target<=k; target++){

            bool notTake = dp[ind-1][target];

            bool take = false;
            if(arr[ind] <= target)
                take = dp[ind-1][target-arr[ind]];

            dp[ind][target] = take || notTake;
        }
    }

    return dp[n-1][k];
}

Complexity

Time  : O(n × k)
Space : O(n × k)

4️⃣ Space Optimized DP

Observation:

Each row only depends on the previous row.

So we can reduce space to O(k).

Code

bool subsetSumToK(int n, int k, vector<int>& arr){

    vector<bool> prev(k+1,false);

    prev[0] = true;

    if(arr[0] <= k)
        prev[arr[0]] = true;

    for(int ind=1; ind<n; ind++){

        vector<bool> cur(k+1,false);
        cur[0] = true;

        for(int target=1; target<=k; target++){

            bool notTake = prev[target];

            bool take = false;
            if(arr[ind] <= target)
                take = prev[target-arr[ind]];

            cur[target] = take || notTake;
        }

        prev = cur;
    }

    return prev[k];
}

Complexity

Time  : O(n × k)
Space : O(k)

Key DP Pattern

This pattern is used in many problems:

Problem	Concept
Partition Equal Subset Sum	Subset Sum
Target Sum	Subset Count
Minimum Subset Difference	Partition DP
Count Subsets with Sum K	Variation

Summary

Approach	Time	Space
Recursion	O(2^n)	O(n)
Memoization	O(n×k)	O(n×k)
Tabulation	O(n×k)	O(n×k)
Space Optimized	O(n×k)	O(k)

stack me operation

Dolly Sharma — Mon, 16 Mar 2026 01:26:30 +0000

C++ Code

#include <stack>
using namespace std;

void insert(stack<int>& st, int x){
    if(st.empty() || st.top() <= x){
        st.push(x);
        return;
    }

    int temp = st.top();
    st.pop();

    insert(st, x);

    st.push(temp);
}

void sortStack(stack<int>& st){
    if(st.empty()) return;

    int x = st.top();
    st.pop();

    sortStack(st);

    insert(st, x);
}

Idea in Simple Words

Remove the top element.
Sort the remaining stack recursively.
Insert the removed element in the correct position.

Example

Initial stack (top → bottom)

Sorted stack

(bottom → top → 1 2 3 4)

Complexity

Time: O(n²)
Space: O(n) recursion stack

1. Reverse a Stack using Recursion

Idea

Pop the top element.
Reverse the remaining stack.
Insert the popped element at the bottom.

Code (C++)

#include <stack>
using namespace std;

void insertBottom(stack<int>& st, int x){
    if(st.empty()){
        st.push(x);
        return;
    }

    int temp = st.top();
    st.pop();

    insertBottom(st, x);

    st.push(temp);
}

void reverseStack(stack<int>& st){
    if(st.empty()) return;

    int x = st.top();
    st.pop();

    reverseStack(st);

    insertBottom(st, x);
}

2. Delete Middle Element of Stack

Idea

Find the middle index k = size/2.
Recursively pop elements.
Skip pushing the middle element back.

Code

#include <stack>
using namespace std;

void solve(stack<int>& st, int k){
    if(k == 1){
        st.pop();
        return;
    }

    int temp = st.top();
    st.pop();

    solve(st, k-1);

    st.push(temp);
}

void deleteMiddle(stack<int>& st){
    int k = st.size()/2 + 1;
    solve(st, k);
}

3. Sort a Stack using Recursion

Idea

Pop element.
Sort remaining stack.
Insert element in sorted position.

void insert(stack<int>& st, int x){
    if(st.empty() || st.top() <= x){
        st.push(x);
        return;
    }

    int temp = st.top();
    st.pop();

    insert(st, x);

    st.push(temp);
}

void sortStack(stack<int>& st){
    if(st.empty()) return;

    int x = st.top();
    st.pop();

    sortStack(st);

    insert(st, x);
}

Key Pattern (Important for Interviews)

All these follow the same recursion template:

1 Remove element
2 Solve smaller problem recursively
3 Insert element back correctly

Ninja's Training

Dolly Sharma — Tue, 10 Mar 2026 06:01:36 +0000

Ninja Training Problem – Complete DP Guide (Recursion → Memoization → Tabulation → Space Optimization)

Dynamic Programming is one of the most important topics in DSA interviews and coding tests.
The Ninja Training problem is a classic example that helps you understand several DP techniques step by step.

In this guide we will cover:

Problem intuition
Why greedy fails
Recursion approach
Memoization (Top-Down DP)
Tabulation (Bottom-Up DP)
Space optimization
Dry run example

Problem Intuition

Ninja is planning a training schedule for N days.

Each day he can perform one of three activities:

Activity	Meaning
0	Running
1	Fighting
2	Learning

Rule

You cannot perform the same activity on two consecutive days.

Goal

Maximize the total merit points.

Example

points =
[1 2 5]
[3 1 1]
[3 3 3]

Optimal schedule:

Day 1 → Learning (5)
Day 2 → Running (3)
Day 3 → Fighting (3)

Total = 11

Why Greedy Fails

Consider this example:

10 50 1
5 100 11

Greedy Approach

Day1 → 50
Day2 → cannot choose 100 (same activity)
choose 11

Total = 61

Optimal Solution

Day1 → 10
Day2 → 100

Total = 110

Greedy fails because the best local choice does not guarantee global optimum.

Therefore we must explore all possibilities → Dynamic Programming.

DP State Idea

We define a state:

dp[day][last]

Meaning:

Maximum points earned until "day"
if the last activity performed was "last"

Where:

last = 0 → Running
last = 1 → Fighting
last = 2 → Learning
last = 3 → No activity yet

Recursion Idea

Define a function:

solve(day, last)

Meaning:

Maximum points obtainable from day 0 → day if the previous activity was last.

Recurrence

solve(day,last) =
max(points[day][task] + solve(day-1,task))
for all task ≠ last

Recursion Code (C++)

int solve(int day, int last, vector<vector<int>> &points)
{
    if(day == 0)
    {
        int maxi = 0;
        for(int task=0; task<3; task++)
        {
            if(task != last)
                maxi = max(maxi, points[0][task]);
        }
        return maxi;
    }

    int maxi = 0;

    for(int task=0; task<3; task++)
    {
        if(task != last)
        {
            int point = points[day][task] + solve(day-1, task, points);
            maxi = max(maxi, point);
        }
    }

    return maxi;
}

int ninjaTraining(int n, vector<vector<int>> &points)
{
    return solve(n-1,3,points);
}

Recursion Complexity

Time Complexity = O(3^N)

Because many states repeat.

Example repeated calls:

solve(2,3)
solve(1,0)
solve(1,1)
solve(1,2)

Each again calls:

solve(0, ...)

This creates overlapping subproblems.

Memoization (Top-Down DP)

To avoid recomputation we store results in a DP table.

dp[day][last]

If a state is already solved, we return it directly.

Memoization Code

int solve(int day,int last,vector<vector<int>> &points,vector<vector<int>> &dp)
{
    if(day==0)
    {
        int maxi=0;
        for(int task=0;task<3;task++)
        {
            if(task!=last)
                maxi=max(maxi,points[0][task]);
        }
        return dp[day][last]=maxi;
    }

    if(dp[day][last]!=-1)
        return dp[day][last];

    int maxi=0;

    for(int task=0;task<3;task++)
    {
        if(task!=last)
        {
            int point=points[day][task]+solve(day-1,task,points,dp);
            maxi=max(maxi,point);
        }
    }

    return dp[day][last]=maxi;
}

int ninjaTraining(int n,vector<vector<int>> &points)
{
    vector<vector<int>> dp(n,vector<int>(4,-1));
    return solve(n-1,3,points,dp);
}

Memoization Complexity

States = n × 4
Transitions = 3

Time Complexity = O(n × 4 × 3)
Space Complexity = O(n × 4) + recursion stack

Tabulation (Bottom-Up DP)

Instead of recursion, we build the solution iteratively from day 0 to day n-1.

Base Case (Day 0)

dp[0][0] = max(points[0][1], points[0][2])
dp[0][1] = max(points[0][0], points[0][2])
dp[0][2] = max(points[0][0], points[0][1])
dp[0][3] = max(points[0][0],points[0][1],points[0][2])

Explanation:

If last activity was 0, we cannot do 0 today, so choose the best of 1 or 2.

Tabulation Code

int ninjaTraining(int n, vector<vector<int>> &points)
{
    vector<vector<int>> dp(n,vector<int>(4,0));

    dp[0][0]=max(points[0][1],points[0][2]);
    dp[0][1]=max(points[0][0],points[0][2]);
    dp[0][2]=max(points[0][0],points[0][1]);
    dp[0][3]=max({points[0][0],points[0][1],points[0][2]});

    for(int day=1;day<n;day++)
    {
        for(int last=0;last<4;last++)
        {
            dp[day][last]=0;

            for(int task=0;task<3;task++)
            {
                if(task!=last)
                {
                    int point=points[day][task]+dp[day-1][task];
                    dp[day][last]=max(dp[day][last],point);
                }
            }
        }
    }

    return dp[n-1][3];
}

Tabulation Complexity

Time Complexity = O(n × 4 × 3)
Space Complexity = O(n × 4)

Space Optimized Version

Observation:

dp[day] depends only on dp[day-1]

So instead of storing n × 4, we store only one previous row.

Space Optimized Code

int ninjaTraining(int n, vector<vector<int>> &points)
{
    vector<int> prev(4,0);

    prev[0]=max(points[0][1],points[0][2]);
    prev[1]=max(points[0][0],points[0][2]);
    prev[2]=max(points[0][0],points[0][1]);
    prev[3]=max({points[0][0],points[0][1],points[0][2]});

    for(int day=1;day<n;day++)
    {
        vector<int> cur(4,0);

        for(int last=0;last<4;last++)
        {
            for(int task=0;task<3;task++)
            {
                if(task!=last)
                {
                    cur[last]=max(cur[last],
                    points[day][task]+prev[task]);
                }
            }
        }

        prev=cur;
    }

    return prev[3];
}

Space Optimized Complexity

Time Complexity = O(n × 4 × 3)
Space Complexity = O(4)

This is the most optimal solution.

Dry Run Example

Input:

points =
[1 2 5]
[3 1 1]
[3 3 3]

Day 0

prev[0] = max(2,5) = 5
prev[1] = max(1,5) = 5
prev[2] = max(1,2) = 2
prev[3] = max(1,2,5) = 5

prev = [5,5,2,5]

Day 1

cur = [6,8,8,8]

Day 2

Final result:

prev[3] = 11

Answer:

Key DP Pattern

Whenever you see problems with:

Days / Steps
Multiple choices
Restriction on previous choice

Think:

dp[day][last]

Problems With Same Pattern

Paint House
Vacation Problem (AtCoder DP)
Task Scheduling Problems
Activity Selection With Restrictions

If you'd like, I can also show the 7 most important Dynamic Programming patterns used in FAANG interviews, which cover almost 70% of DP problems.

1️⃣ The 3 Questions Trick for Identifying DP

Whenever you see a problem, ask these 3 questions:

**Question 1

Does the problem ask for MAX / MIN / COUNT / WAYS?**

Examples:

Maximum profit

Minimum cost

Number of ways

Maximum points

Ninja Training:

Maximum merit points

So ✔ DP candidate

Question 2

Does the problem have stages or steps?

Common stages:

Days

Index

Position in array

Grid cell

Number of items

In Ninja Training:

Days = stages
Question 3

Does the decision depend on the previous step?

If the current choice depends on previous choice, then DP is very likely.

Example:

Cannot do same activity on consecutive days

So today's choice depends on yesterday's activity.

That means the state must store previous activity.

2️⃣ How Interviewers Expect You to Think

The correct thinking pattern:

Step 1 → Identify state

dp[day][lastActivity]

Step 2 → Identify choices

3 activities

Step 3 → Identify restriction

task != lastActivity

Step 4 → Write transition

dp[day][last] =
max(points[day][task] + dp[day-1][task])
3️⃣ Visual State Diagram

For each day:

Running
Fighting
Learning

But if yesterday was Running, today you can choose only:

Fighting
Learning

So transitions look like this:

Running -> Fighting
Running -> Learning

Fighting -> Running
Fighting -> Learning

Learning -> Running
Learning -> Fighting

This forms a state graph, which is why DP works perfectly.

4️⃣ The Universal DP Template

Many DP problems follow this template:

State:
dp[index][previousChoice]

Transition:
dp[index][prev] =
max/min/ways of
(value[index] + dp[index-1][choice])
5️⃣ Problems With Same Pattern

These are almost identical to Ninja Training.

1️⃣ Paint House
2️⃣ Vacation Problem (AtCoder DP C)
3️⃣ Maximum Points with Restrictions
4️⃣ Activity Selection with Restrictions
5️⃣ Task Scheduling Problems

6️⃣ Another Super Important Interview Trick

If you see:

Day / Index
Choice from K options
Restriction on previous choice

Then DP dimension =

dp[n][k+1]

Example:

Ninja Training:

n days
3 tasks
+1 for "no previous task"

dp[n][4]
7️⃣ One More Advanced Trick (Used in Google Interviews)

If the constraint is large:

N ≤ 100000

Then recursion alone is impossible.

Interviewers expect:

DP with space optimization

Which reduces memory:

O(N*4) → O(4)
8️⃣ The Fast Interview Answer

If an interviewer asks how you recognized DP, answer like this:

The problem has stages (days), choices (3 activities), and a restriction based on the previous choice. Since the current decision depends on the previous state and we need to maximize total points, it forms overlapping subproblems, so dynamic programming is appropriate.

This answer sounds very strong in interviews.

DEV Community: Dolly Sharma

Three different ways to combine data in Pandas — concat, merge, and join.

🔹 1. pd.concat() → Stack or attach data

📌 Row-wise (axis=0)

📌 Column-wise (axis=1)

🔹 2. pd.merge() → Database-style join

📌 Default (inner join)

📌 Left join

📌 Inner join

🔹 3. df.join() → Index-based join

🔥 Quick Difference Table

✅ When to use what?

Queue using Stack(s)

🧠 Approach 1: Using TWO Stacks (Efficient)

📌 Idea

✅ Operations

🔹 Push (O(1))

🔹 Pop / Front (Amortized O(1))

✅ Code (C++)

⚡ Complexity

🔥 Approach 2: Using ONE Stack (Recursive)

📌 Idea

❗ Drawback

✅ Code

🔍 Key Insight

🎯 Interview One-Liner

C++ Object Creation & Memory

🔹 1. Object Creation in C++ vs Java

✅ C++

1. Stack Allocation

2. Heap Allocation

✅ Java

🎯 Key Difference

🔹 2. Stack Memory

📌 Definition

⚙️ Properties

✅ Example

❌ Problem: Stack Overflow

🔹 3. Heap Memory

📌 Definition

⚙️ Properties

✅ Example

❌ Problem: Memory Leak

🔹 4. Stack vs Heap (Comparison Table)

🔹 5. Circular Queue Insight (From Your Code)

📌 Concept

✅ Why?

⚙️ Time Complexity

🔹 6. When to Use What?

✅ Use Stack When:

✅ Use Heap When:

🔹 7. Best Practices (Important 🚀)

✅ Prefer Stack

⚠️ Use Heap Carefully

✅ Modern C++ (Recommended)

🔹 8. Common Interview Questions

❓ Why is stack faster than heap?

❓ Why avoid excessive new?

❓ What is RAII?

🎯 Final One-Liner Summary

📘 Minimum Insertions and Deletions to Convert String A -B

🔹 Problem

🔥 Key Idea (VERY IMPORTANT)

🔹 Formula

🧠 Why this works?

🔹 Example

🔹 Code (C++)

🔹 Total Operations

🔹 Important Variants

✅ Only deletions:

✅ Only insertions:

🔥 Interview Pattern

⚡ Quick Summary

🧠 Intuition Shortcut

📘 Minimum Insertions to Make a String Palindrome

🔹 Key Idea (MOST IMPORTANT)

🔹 Why this works?

🔹 Convert to LCS

🔥 Final Formula

🔹 Example

🔹 1. `pd.concat()` → Stack or attach data

🔹 2. `pd.merge()` → Database-style join

🔹 3. `df.join()` → Index-based join

❓ Why avoid excessive `new`?