Contractor Kartavya’s Conundrum / Ekalavya’s Excursions

 I’ve gone through your uploaded handwritten notes (the “Contractor Kartavya’s Conundrum / Ekalavya’s Excursions” material) and distilled them into two clean outputs:

1. Structured study notes (crisp, exam/learning-friendly)

2. A conceptual blog post (story-driven, intuitive, readable)

Both are derived directly from the content in the PDF, especially pages 1–5 and the later linear algebra sections on functions, matrices, inverses, and transformations .

---

1. Clean Notes (Structured)

Theme 1: Contractor Kartavya’s Conundrum

Problem statement

• Kartavya wants to determine the optimal statewise distribution of workers to maximize productivity.

• Parameters:

  • ( k = 120 ) months

  • ( n = 30 ) states

• Productivity over time is modeled using a system of linear equations:
  [
  \begin{aligned}
  a_{11}s_1 + a_{12}s_2 + \dots + a_{1n}s_n &= P_1 \
  a_{21}s_1 + a_{22}s_2 + \dots + a_{2n}s_n &= P_2 \
  \vdots \
  a_{k1}s_1 + a_{k2}s_2 + \dots + a_{kn}s_n &= P_k
  \end{aligned}
  ]

Key idea

• This is a system-level optimization problem

• Best strategy: Outsource decision-making to a “game” or algorithmic process

• Introduces the idea of learning via error minimization

---

Theme 2: Outsourcing as Optimization

How Kartavya outsources

1. Defines an error function

2. Uses an iterative method metaphorically called
   “Blind man’s walk down the hill”

   • Intuition for gradient descent

   • Move step-by-step in the direction that reduces error

Insight

• Even without deep math, arithmetic + iteration can converge to good solutions

---

Theme 3: Functions and Inverses (Ekalavya’s Excursions)

Scalar Functions

• Example:
  [
  f(x) = x^2 \Rightarrow f^{-1}(y) = \sqrt{y}
  ]

• Understanding a function deeply allows construction of its inverse

---

Theme 4: Matrices as Functions

A matrix behaves like a function mapping vectors to vectors.

Example:
[
f:
\begin{pmatrix}
x \ y
\end{pmatrix}
\mapsto
\begin{pmatrix}
2x + y \
x + 3y
\end{pmatrix}
]

• This is a function ( f: \mathbb{R}^2 \to \mathbb{R}^2 )

• Question: Is it invertible?

---

Theme 5: Finding the Inverse (Hook or Crook)

Solve:
[
\begin{cases}
2\alpha + \beta = a \
\alpha + 3\beta = b
\end{cases}
]

Solution:
[
\begin{pmatrix}
\alpha \
\beta
\end{pmatrix}

\begin{pmatrix}
\frac{3a-b}{5} \
\frac{2b-a}{5}
\end{pmatrix}
]

Matrix inverse:
[
\begin{pmatrix}
2 & 1 \
1 & 3
\end{pmatrix}^{-1}

\begin{pmatrix}
\frac{3}{5} & -\frac{1}{5} \
-\frac{1}{5} & \frac{2}{5}
\end{pmatrix}
]

---

Theme 6: Linear Combinations & Span

• Any point in the plane can be written as:
  [
  \alpha u + \beta v
  ]

• If vectors (u, v) are linearly independent → mapping is 1–1 and onto

---

Theme 7: Composition of Linear Maps

If:
[
f(x,y) = (2x+y,\ x+3y)
]
[
g(a,b) = (a+b,\ 4a+5b)
]

Then:
[
g(f(x,y)) = (3x+4y,\ 13x+19y)
]

➡️ Composition corresponds to matrix multiplication

---

Theme 8: Geometric Transformations

• Rotation by 90° clockwise:
  [
  \begin{pmatrix}
  0 & 1 \
  -1 & 0
  \end{pmatrix}
  ]

• Reflections and rotations are also linear transformations

• Geometry ↔ algebra via matrices

---

2. Blog Post (Conceptual & Story-Driven)

From Blind Walks to Brilliant Solutions: How Linear Algebra Explains Learning

Kartavya isn’t a mathematician. He’s a contractor with a problem.

He has workers scattered across 30 states and productivity data spanning 120 months. The question haunting him is deceptively simple:

How should I distribute my workers so productivity is maximized?

Behind the scenes, this is a massive system of equations—far too complex to solve by hand. So Kartavya does something radical.

He outsources thinking itself.

---

Learning Without Knowing the Math

Kartavya defines an error—how far reality is from what he wants. Then he lets the town try random steps, keeping only those that reduce the error.

It’s like a blindfolded person walking downhill, step by step.

You already know this idea by another name: gradient descent.

Learning, it turns out, doesn’t require genius—just feedback and direction.

---

Ekalavya’s Real Lesson

Ekalavya asks a deeper question: What does it mean to reverse a process?

If squaring turns 3 into 9, what turns 9 back into 3?

This curiosity leads us from simple functions to matrices—objects that don’t just compute numbers, but move space itself.

---

Matrices Are Functions in Disguise

A matrix isn’t just numbers in a box. It’s a function:

• It takes a point

• Moves it

• Stretches it

• Rotates it

• Or flips it

And sometimes—if you’re lucky—you can undo it perfectly.

That’s what an inverse really is:
A guarantee that no information was lost.

---

Why This Matters

• Machine learning is just Kartavya’s outsourcing, scaled up

• Neural networks are stacked matrix functions

• Invertibility is about reversibility and trust

• Geometry, algebra, and optimization are the same story told differently

---

Final Thought

Math isn’t about symbols.

It’s about control:

• Can you predict?

• Can you reverse?

• Can you improve step by step?

Kartavya didn’t learn linear algebra.

Linear algebra learned Kartavya.

---

If you want, I can:

• Turn this into LaTeX notes

• Simplify it for high-school / JEE / undergrad

• Convert the blog into Medium / Substack style

• Add visual explanations or diagrams

Just tell me how you want to use it.

Finding Top-K Frequent Elements in Java: From Interview Solution to Production-Ready Code

Finding the top-K most frequent elements is a classic interview problem that looks simple—but is often used to evaluate how well a candidate understands time complexity, space optimization, and scalability trade-offs.

In this post, we’ll start with a common interview solution, analyze its shortcomings, and progressively evolve it into optimal and scalable approaches suitable for real-world systems.

---

Problem Statement

Given a list of strings, return the top K most frequent strings.

Example:

Input: ["def","abc","def","abc","def","ghi"]
K = 3
Output: def, abc, ghi

---

Baseline Interview Solution (Max Heap)

A very common approach is:

1. Count frequencies using a HashMap

2. Push all unique keys into a max-heap

3. Poll k elements

Code

Map<String, Integer> map = new HashMap<>();
for (String s : list) {
    map.put(s, map.getOrDefault(s, 0) + 1);
}

PriorityQueue<String> pq =
    new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));

pq.addAll(map.keySet());

for (int i = 0; i < k; i++) {
    System.out.println(pq.poll());
}

---

Complexity Analysis (Corrected)

Let:

• N = total number of elements

• U = number of unique elements

Step	Complexity
Frequency count	O(N)
Heap build	O(U log U)
Extract top K	O(k log U)
Space	O(U)

What Interviewers Notice

• Heap size grows to all unique elements

• Comparator uses subtraction → integer overflow risk

• Inefficient when k is small and U is large

---

Improvement #1: Fix Comparator Overflow

This line is dangerous:

(a, b) -> map.get(b) - map.get(a)

If counts are large, subtraction can overflow.

Safer Version

(a, b) -> Integer.compare(map.get(b), map.get(a))

This is a frequent interview pitfall.

---

Improvement #2: Use a Min-Heap of Size K (Optimal)

Instead of storing all unique elements, we only keep the top K seen so far.

Key Idea

• Use a min-heap

• Remove smallest frequency whenever size exceeds k

Optimized Code

Map<String, Integer> freq = new HashMap<>();
for (String s : list) {
    freq.put(s, freq.getOrDefault(s, 0) + 1);
}

PriorityQueue<String> pq =
    new PriorityQueue<>((a, b) ->
        Integer.compare(freq.get(a), freq.get(b))
    );

for (String key : freq.keySet()) {
    pq.offer(key);
    if (pq.size() > k) {
        pq.poll();
    }
}

while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}

Complexity

Metric	Value
Time	O(N + U log K)
Space	O(U + K)

This is the preferred interview solution.

---

Improvement #3: Avoid Repeated Map Lookups

A more efficient and cleaner approach is to store Map.Entry objects directly.

PriorityQueue<Map.Entry<String, Integer>> pq =
    new PriorityQueue<>(
        (a, b) -> Integer.compare(a.getValue(), b.getValue())
    );

for (Map.Entry<String, Integer> entry : freq.entrySet()) {
    pq.offer(entry);
    if (pq.size() > k) {
        pq.poll();
    }
}

while (!pq.isEmpty()) {
    System.out.println(pq.poll().getKey());
}

This reduces repeated hash lookups and improves readability.

---

Improvement #4: Bucket Sort (When Counts Are Bounded)

If frequencies are bounded by N, we can eliminate heap usage entirely.

Idea

• Create buckets where index = frequency

• Traverse from highest frequency down

Complexity

• Time: O(N + U)

• Space: O(N)

This is usually mentioned verbally in interviews to demonstrate algorithmic range.

---

Handling Massive Data (1B+ Records)

For very large datasets:

• Holding all strings in memory is not feasible

• HashMap alone can exhaust heap

Real-World Approach

• Stream data from files / Kafka

• Aggregate in chunks

• Use distributed systems (MapReduce / Spark)

• Use approximate algorithms (Count-Min Sketch)

Mentioning this shows system design awareness, not just coding skill.

---

Key Interview Takeaways

What this problem really tests:

• Correct complexity analysis

• Heap optimization strategies

• Comparator correctness

• Scalability thinking

• Ability to trade memory for speed

---

Final Thoughts

A solution that works is not the same as a solution that scales.

If you can:

• Start with the basic heap

• Optimize to O(U log K)

• Discuss bucket sort and streaming

You’ll stand out as someone who writes production-grade code, not just interview code.

---

If you want, I can:

• Add Java Streams version (and explain why it’s often worse)

• Convert this into a LeetCode-style explanation

• Tailor it for FAANG / Staff-level interviews

Just say the word.

Finding Engaged Users From Interaction Logs: What I Learned Building It in Java 7, 8, and 17

When you’re given raw interaction events like:

Timestamp,UserId,PostId

…and asked to derive a meaningful cohort (in this case, “engaged users”), the challenge is rarely the syntax. The challenge is choosing the right data structures, keeping the logic correct, and writing code that’s easy to explain in an interview.

This post walks through the core idea, common mistakes, and clean implementations in Java 7, Java 8, and Java 17.

---

The Problem

You have two days of interaction logs. A user is considered engaged if:

1. They have at least one interaction on both days, and

2. Across both days combined, they interacted with at least two unique posts.

Important detail: multiple interactions with the same post count only once toward “unique posts”.

---

The Core Insight

This is a “group-by user” problem with two checks:

• Presence on day 1 and day 2

• Unique post count across both days

The simplest and most reliable approach is:

• Use a Map keyed by userId.

• Store post IDs in Sets (because uniqueness is built-in).

Why sets are the right tool

If you store post IDs in a list, you’ll need extra de-dup logic. With sets:

• Add is O(1) average

• Uniqueness is automatic

---

A Simple Data Model

For two days, a lightweight per-user structure is enough:

• Set<String> day1Posts

• Set<String> day2Posts

A user qualifies if both sets are non-empty and the union size is ≥ 2.

---

Common Mistakes (The Ones That Usually Show Up in Interviews)

1) Using counts instead of presence

You only need to know whether the user appeared that day (at least one event). Counting events adds complexity with no benefit unless the requirements change.

2) Mixing mutation inside filtering predicates

Using removeIf(...) or stream filter(...) to also mutate sets is a readability and correctness trap.

Predicates should return a boolean and avoid side effects.

3) Java version mismatch

• Java 8 streams do not have .toList(). Use collect(Collectors.toList()).

• Java 17 streams do have .toList().

4) Splitting each log line multiple times

Calling log.split(",") repeatedly creates garbage and slows things down. Parse once per line.

---

Example Input Used Throughout

// Day 1
"2026-01-01T10:05:12Z,U1,P101"
"2026-01-01T10:07:45Z,U2,P102"
"2026-01-01T10:10:30Z,U1,P103"
"2026-01-01T10:15:00Z,U3,P104"

// Day 2
"2026-01-02T09:00:10Z,U1,P101"
"2026-01-02T09:05:20Z,U2,P105"
"2026-01-02T09:10:55Z,U4,P106"
"2026-01-02T09:12:00Z,U2,P102"

Expected engaged users: [U1, U2] (order doesn’t matter)

---

Java 7 Implementation (Imperative, Clear, Interview-Friendly)

Java 7 has no streams/lambdas, so we use plain loops.

import java.util.*;

public class EngagedUsersFinderJava7 {

    private static final List<String> DAY1_LOGS = Arrays.asList(
        "2026-01-01T10:05:12Z,U1,P101",
        "2026-01-01T10:07:45Z,U2,P102",
        "2026-01-01T10:10:30Z,U1,P103",
        "2026-01-01T10:15:00Z,U3,P104"
    );

    private static final List<String> DAY2_LOGS = Arrays.asList(
        "2026-01-02T09:00:10Z,U1,P101",
        "2026-01-02T09:05:20Z,U2,P105",
        "2026-01-02T09:10:55Z,U4,P106",
        "2026-01-02T09:12:00Z,U2,P102"
    );

    static class Engage {
        final String userId;
        final Set<String> day1Posts = new HashSet<String>();
        final Set<String> day2Posts = new HashSet<String>();

        Engage(String userId) {
            this.userId = userId;
        }
    }

    public static List<String> findEngagedUsers() {
        Map<String, Engage> userMap = new HashMap<String, Engage>();

        // Day 1
        for (String log : DAY1_LOGS) {
            String[] parts = log.split(",");
            String userId = parts[1];
            String postId = parts[2];

            Engage e = userMap.get(userId);
            if (e == null) {
                e = new Engage(userId);
                userMap.put(userId, e);
            }
            e.day1Posts.add(postId);
        }

        // Day 2
        for (String log : DAY2_LOGS) {
            String[] parts = log.split(",");
            String userId = parts[1];
            String postId = parts[2];

            Engage e = userMap.get(userId);
            if (e == null) {
                e = new Engage(userId);
                userMap.put(userId, e);
            }
            e.day2Posts.add(postId);
        }

        // Filter engaged
        List<String> result = new ArrayList<String>();
        for (Engage e : userMap.values()) {
            if (!e.day1Posts.isEmpty() && !e.day2Posts.isEmpty()) {
                Set<String> union = new HashSet<String>(e.day1Posts);
                union.addAll(e.day2Posts);
                if (union.size() >= 2) {
                    result.add(e.userId);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(findEngagedUsers());
    }
}

---

Java 8 Implementation (Streams for Filtering)

Java 8 adds streams and lambdas, which can make the filtering phase more declarative.

Important: use collect(Collectors.toList()) in Java 8.

import java.util.*;
import java.util.stream.Collectors;

public class EngagedUsersFinderJava8 {

    private static final List<String> DAY1_LOGS = Arrays.asList(
        "2026-01-01T10:05:12Z,U1,P101",
        "2026-01-01T10:07:45Z,U2,P102",
        "2026-01-01T10:10:30Z,U1,P103",
        "2026-01-01T10:15:00Z,U3,P104"
    );

    private static final List<String> DAY2_LOGS = Arrays.asList(
        "2026-01-02T09:00:10Z,U1,P101",
        "2026-01-02T09:05:20Z,U2,P105",
        "2026-01-02T09:10:55Z,U4,P106",
        "2026-01-02T09:12:00Z,U2,P102"
    );

    static class Engage {
        final String userId;
        final Set<String> day1Posts = new HashSet<>();
        final Set<String> day2Posts = new HashSet<>();

        Engage(String userId) {
            this.userId = userId;
        }
    }

    public static List<String> findEngagedUsers() {
        Map<String, Engage> userMap = new HashMap<>();

        for (String log : DAY1_LOGS) {
            String[] parts = log.split(",");
            String userId = parts[1];
            String postId = parts[2];

            Engage e = userMap.get(userId);
            if (e == null) {
                e = new Engage(userId);
                userMap.put(userId, e);
            }
            e.day1Posts.add(postId);
        }

        for (String log : DAY2_LOGS) {
            String[] parts = log.split(",");
            String userId = parts[1];
            String postId = parts[2];

            Engage e = userMap.get(userId);
            if (e == null) {
                e = new Engage(userId);
                userMap.put(userId, e);
            }
            e.day2Posts.add(postId);
        }

        return userMap.values().stream()
            .filter(e -> !e.day1Posts.isEmpty() && !e.day2Posts.isEmpty())
            .filter(e -> {
                Set<String> union = new HashSet<>(e.day1Posts);
                union.addAll(e.day2Posts);
                return union.size() >= 2;
            })
            .map(e -> e.userId)
            .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        System.out.println(findEngagedUsers());
    }
}

---

Java 17 Implementation (Records + Modern Conveniences)

Java 17 lets you write concise, expressive code:

• record for modeling

• List.of(...) for input lists

• Stream.toList() for collection

import java.util.*;
import java.util.stream.Stream;

public class EngagedUsersFinderJava17 {

    private static final List<String> DAY1_LOGS = List.of(
        "2026-01-01T10:05:12Z,U1,P101",
        "2026-01-01T10:07:45Z,U2,P102",
        "2026-01-01T10:10:30Z,U1,P103",
        "2026-01-01T10:15:00Z,U3,P104"
    );

    private static final List<String> DAY2_LOGS = List.of(
        "2026-01-02T09:00:10Z,U1,P101",
        "2026-01-02T09:05:20Z,U2,P105",
        "2026-01-02T09:10:55Z,U4,P106",
        "2026-01-02T09:12:00Z,U2,P102"
    );

    record Engage(String userId, Set<String> day1Posts, Set<String> day2Posts) {
        Engage(String userId) {
            this(userId, new HashSet<>(), new HashSet<>());
        }
    }

    public static List<String> findEngagedUsers() {
        Map<String, Engage> userMap = new HashMap<>();

        DAY1_LOGS.forEach(log -> {
            var parts = log.split(",");
            userMap.computeIfAbsent(parts[1], Engage::new).day1Posts().add(parts[2]);
        });

        DAY2_LOGS.forEach(log -> {
            var parts = log.split(",");
            userMap.computeIfAbsent(parts[1], Engage::new).day2Posts().add(parts[2]);
        });

        return userMap.values().stream()
            .filter(e -> !e.day1Posts().isEmpty() && !e.day2Posts().isEmpty())
            .filter(e ->
                Stream.concat(e.day1Posts().stream(), e.day2Posts().stream())
                      .distinct()
                      .count() >= 2
            )
            .map(Engage::userId)
            .toList();
    }

    public static void main(String[] args) {
        System.out.println(findEngagedUsers());
    }
}

A quick note: the record holds mutable sets here. That’s fine for a coding exercise, but in production you’d typically prefer immutability (or keep it as a normal class with encapsulation).

---

Complexity (What You Should Say Out Loud)

Let:

• N = number of events on day 1

• M = number of events on day 2

Time Complexity: O(N + M)
Space Complexity: O(U + P)
(where U is number of users and P is total unique user-post relationships)

---

How to Explain the Approach in an Interview (A Strong Script)

Here’s a concise explanation that typically lands well:

“I group events by user. For each user I track unique post IDs for each day using sets.
Then I filter users who appear on both days and whose union of post IDs across the two days contains at least two unique posts.
Sets give me uniqueness for free, and the solution is linear in the size of the logs.”

---

Extensions That Make Great Follow-Ups

1) More than two days

Replace day-specific fields with:

• Set<LocalDate> activeDays, or

• BitSet / bitmask if the day count is bounded, or

• Map<Day, Set<Post>> if you want to keep per-day post sets

2) Huge log files

Process logs line-by-line with BufferedReader, avoid loading everything in memory. The same data structures still work.

3) Malformed lines

Add validation around split length and skip/record bad lines.

---

Final Takeaways

• Sets are the simplest way to enforce uniqueness.

• Separate aggregation from filtering.

• Be mindful of Java version APIs (toList() vs Collectors.toList()).

• Clean naming (day1Posts, not day1Users) makes your reasoning easier to follow.

• The best interview solutions are not the “cleverest”—they’re the clearest.

If you want, I can turn this into a “publish-ready” Medium-style post (with headings, diagrams, and a “what the interviewer is looking for” rubric) or add a JUnit test section for each Java version.