<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Zaid on Medium]]></title>
        <description><![CDATA[Stories by Zaid on Medium]]></description>
        <link>https://medium.com/@zaid03?source=rss-3cd7af860162------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*xWvgCX6p7KIBCEPfcAVumw.png</url>
            <title>Stories by Zaid on Medium</title>
            <link>https://medium.com/@zaid03?source=rss-3cd7af860162------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 23:15:21 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@zaid03/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[My Zomato FDE Interview Experience]]></title>
            <link>https://medium.com/@zaid03/my-zomato-fde-interview-experience-ee99a141ef7b?source=rss-3cd7af860162------2</link>
            <guid isPermaLink="false">https://medium.com/p/ee99a141ef7b</guid>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Zaid]]></dc:creator>
            <pubDate>Wed, 18 Feb 2026 03:32:48 GMT</pubDate>
            <atom:updated>2026-02-18T03:32:48.555Z</atom:updated>
            <content:encoded><![CDATA[<p>The interview was with respect to the AI team of Zomato-Forward Deployed Engineer.</p><p>Questions asked:</p><p>1.Difference between Reasoning and Non reasoning llms and their prompt engineering techniques with detailed understanding expected.</p><p>2.How does tool calling happens internally in llm.</p><p>3.Show the flow for above.</p><p>4.How in intra workflow ,agent is taken back to previous step based on a prompt.</p><p>5.How in parallel agent workflows context switching is handled along with false positive handling leading to out of scope issues.</p><p>6.Show flow for each of them.</p><p>7.Optimized and accurate workflow is expected,has to be scalable.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ee99a141ef7b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Optimal Account Balancing — From Naive Thinking to Backtracking Brilliance]]></title>
            <link>https://medium.com/@zaid03/optimal-account-balancing-from-naive-thinking-to-backtracking-brilliance-79717fc125ba?source=rss-3cd7af860162------2</link>
            <guid isPermaLink="false">https://medium.com/p/79717fc125ba</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[cpp]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Zaid]]></dc:creator>
            <pubDate>Sat, 10 Jan 2026 15:34:17 GMT</pubDate>
            <atom:updated>2026-01-10T15:34:18.936Z</atom:updated>
            <content:encoded><![CDATA[<p>When I first encountered the Optimal Account Balancing problem, my instinct was…<br>“Okay, this looks like a simple bookkeeping task.”<br>Turns out — it absolutely isn’t 😄.<br>This problem is a classic example of how greedy intuition fails, and why controlled backtracking with pruning is sometimes the only clean solution.<br>Let’s walk through the journey.</p><p>🧠 Problem Statement (In Simple Terms)<br>You’re given a list of transactions:</p><p>[from, to, amount]</p><p>Each transaction means:<br>from pays amount<br>to receives amount<br>Your task is to determine the minimum number of transactions required to settle all balances — i.e., make everyone’s net balance zero.</p><p>Example<br>Input</p><p>2<br>0 1 10<br>2 0 5</p><p>Explanation<br>Person 0 gives 10 to person 1 → balance = -10<br>Person 2 gives 5 to person 0 → balance = +5<br>Final balances:</p><p>0 → -5<br>1 → +10<br>2 → -5</p><p>Minimum transactions required: 2</p><p>🚫 My First Thought: “Let’s Do It Iteratively”<br>My first instinct was:<br>“Why not keep matching debtors and creditors greedily?”<br>Something like:<br>Take the first negative balance<br>Match it with the first positive balance<br>Settle as much as possible<br>Repeat<br>Sounds reasonable… until you realize:<br>❌ Greedy pairing doesn’t guarantee a minimum count<br>❌ Local optimal choices can lead to suboptimal global results<br>This is similar to why greedy fails in many partition and matching problems.<br>💡 Key Insight That Changed Everything<br>Only the final balances matter — not the original transactions.<br>So instead of thinking in terms of who paid whom, we reduce the problem to:<br>Some people owe money (negative balance)<br>Some people are owed money (positive balance)<br>We need to cancel them out using the fewest transfers<br>This reframing is critical.<br>🧩 Strategy: Backtracking with Pruning<br>At this point, the problem screams:<br>“Try all valid ways — but smartly.”<br>Core Idea<br>Pick the first non-zero balance<br>Try settling it with every opposite-signed balance<br>Recurse<br>Track the minimum transactions used<br>Why Backtracking Works Here<br>Number of non-zero balances is small<br>We aggressively prune useless paths<br>We skip redundant and symmetric cases<br>🔥 The Algorithm in Action<br>Step 1: Compute Net Balances</p><p>vector&lt;int&gt; balances(12, 0);</p><p>for(int i = 0; i &lt; n; i++) {<br> balances[transactions[i][0]] -= transactions[i][2];<br> balances[transactions[i][1]] += transactions[i][2];<br>}</p><p>Now we only care about who owes and who is owed.<br>Step 2: Recursive Backtracking Function</p><p>void optimalaccountbalancing(<br> vector&lt;int&gt;&amp; balances,<br> int idx,<br> int count,<br> int&amp; mintrans<br>) {<br> while(idx &lt; balances.size() &amp;&amp; balances[idx] == 0) {<br> idx++;<br> }</p><p>if(idx == balances.size()) {<br> mintrans = min(mintrans, count);<br> return;<br> }</p><p>if(count &gt;= mintrans) {<br> return;<br> }</p><p>int curr = balances[idx];</p><p>for(int i = idx + 1; i &lt; balances.size(); i++) {<br> if(balances[i] == 0) continue;<br> if(balances[i] * curr &gt; 0) continue;</p><p>balances[i] += curr;<br> balances[idx] = 0;</p><p>optimalaccountbalancing(balances, idx + 1, count + 1, mintrans);</p><p>balances[idx] = curr;<br> balances[i] -= curr;<br> }<br>}</p><p>🧠 What’s Going On Inside the Mind of This Code?<br>Let’s decode the thinking, not just the syntax.<br>✔ Skip Zero Balances</p><p>while(idx &lt; balances.size() &amp;&amp; balances[idx] == 0)</p><p>Why waste time on settled accounts?<br>✔ Stop Early (Pruning)</p><p>If we already used more transactions than the best solution so far — abort immediately.<br>✔ Only Opposite Signs Can Cancel</p><p>if(balances[i] * curr &gt; 0) continue;</p><p>Two debtors or two creditors cannot settle each other.<br>✔ Try Every Valid Pairing<br>Each recursive call explores:<br>“What if person idx settles with person i?”<br>This exhaustive exploration ensures optimality.</p><p>🧪 Full Working Code</p><p>#include &lt;bits/stdc++.h&gt;<br>using namespace std;</p><p>void optimalaccountbalancing(<br> vector&lt;int&gt;&amp; balances,<br> int idx,<br> int count,<br> int&amp; mintrans<br>) {<br> while(idx &lt; balances.size() &amp;&amp; balances[idx] == 0) {<br> idx++;<br> }</p><p>if(idx == balances.size()) {<br> mintrans = min(mintrans, count);<br> return;<br> }</p><p>if(count &gt;= mintrans) return;</p><p>int curr = balances[idx];</p><p>for(int i = idx + 1; i &lt; balances.size(); i++) {<br> if(balances[i] == 0) continue;<br> if(balances[i] * curr &gt; 0) continue;</p><p>balances[i] += curr;<br> balances[idx] = 0;</p><p>optimalaccountbalancing(balances, idx + 1, count + 1, mintrans);</p><p>balances[idx] = curr;<br> balances[i] -= curr;<br> }<br>}</p><p>int main() {<br> int n;<br> cin &gt;&gt; n;</p><p>vector&lt;vector&lt;int&gt;&gt; transactions(n, vector&lt;int&gt;(3));<br> for(int i = 0; i &lt; n; i++) {<br> cin &gt;&gt; transactions[i][0]<br> &gt;&gt; transactions[i][1]<br> &gt;&gt; transactions[i][2];<br> }</p><p>vector&lt;int&gt; balances(12, 0);</p><p>for(int i = 0; i &lt; n; i++) {<br> balances[transactions[i][0]] -= transactions[i][2];<br> balances[transactions[i][1]] += transactions[i][2];<br> }</p><p>int mintrans = INT_MAX;<br> optimalaccountbalancing(balances, 0, 0, mintrans);</p><p>cout &lt;&lt; (mintrans == INT_MAX ? 0 : mintrans);<br>}</p><p>⏱ Time Complexity (Practical Reality)<br>Worst-case: Exponential<br>But in practice:<br>Zero balances are skipped<br>Same-sign balances are skipped<br>Early pruning cuts most branches<br>Which makes it fast enough for real inputs.<br>🎯 Final Takeaway<br>This problem taught me a valuable lesson:<br>Sometimes the cleanest solution isn’t greedy or iterative —<br>it’s structured exploration with intelligent pruning.<br>If you enjoyed this breakdown, feel free to clap 👏 or share —<br>and if you’re preparing for interviews, this pattern appears everywhere.<br>Happy coding 🚀</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=79717fc125ba" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to analytically write on an issue?]]></title>
            <link>https://medium.com/@zaid03/how-to-analytically-write-on-an-issue-39ab0b12964c?source=rss-3cd7af860162------2</link>
            <guid isPermaLink="false">https://medium.com/p/39ab0b12964c</guid>
            <dc:creator><![CDATA[Zaid]]></dc:creator>
            <pubDate>Sat, 29 Nov 2025 15:45:38 GMT</pubDate>
            <atom:updated>2025-11-29T15:45:38.881Z</atom:updated>
            <content:encoded><![CDATA[<p>I — INTRODUCTION:</p><p>1.Hook:Explain context with one example</p><p>2.Bridge:Opposing context in 2–3 lines</p><p>3.Thesis:Your position with the main supporting reasons</p><p>II-BODY PARAGRAPHS(2 paragraphs):</p><p>Strongest reason/point should be in the first body paragraph</p><p>Body Paragraph 1:</p><p>Topic-sentence:introduce your reason for your standpoint</p><p>then a strong Example/evidence-incident from the news/fragments from history/own real-life situations/incidents.</p><p>Explanation:explain how your example connects back to your reason and to your thesis</p><p>Same for body paragraph 2.</p><p>III-CONCESSION PARAGRAPH</p><p>In this we will Address the opposing viewpoints</p><p>Topic Sentence-introduce a reason why the opposite viewpoint is also valid.</p><p>With an example that supports this</p><p>and an Explanation how the example connects back to the opposing viewpoint</p><p>Rebuttal-acknowledge then refuse the opposing viewpoint</p><p>IV-CONCLUSION(Least time important)</p><ol><li>Restate your thesis</li><li>Summarize your main points</li><li>Finish up with a closing statement</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=39ab0b12964c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Union Find Data Structure explained in 1 shot]]></title>
            <link>https://medium.com/@zaid03/union-find-data-structure-explained-in-1-shot-a7a284901cea?source=rss-3cd7af860162------2</link>
            <guid isPermaLink="false">https://medium.com/p/a7a284901cea</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[faang]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <dc:creator><![CDATA[Zaid]]></dc:creator>
            <pubDate>Wed, 22 Oct 2025 08:00:03 GMT</pubDate>
            <atom:updated>2025-10-22T08:11:59.181Z</atom:updated>
            <content:encoded><![CDATA[<h3>Why do we use Union-Find?</h3><p>The Union-Find (also called Disjoint Set Union or DSU) is used to <strong>efficiently determine if two nodes are in the same connected component</strong> in a dynamic graph.</p><ul><li><strong>Typical applications:</strong></li><li>Find cycles in a graph</li><li>Dynamic connectivity (like in Kruskal’s MST)</li><li>Percolation, network connectivity, image processing, etc.</li></ul><p>Traditional DFS/BFS checks for connectivity take <strong>O(N+E)</strong> time per query, but Union-Find achieves nearly <strong>constant time</strong> per operation using two core techniques: <strong>path compression</strong> and <strong>union by rank/size</strong>.</p><h3>How to implement it:<br>Both start with individual nodes and dynamically creating the graph</h3><p>Initialize three vectors<br>1.Parent vector where each node’s parent is stored and we keep updating it with the final ultimate parent,also it is initialized as parent of itself i.</p><p>2.Rank vector stores rank of each node intialized with 0 but actually stores the distance between the node and the farthest leaf node</p><p>3.Size vector stores size of each node ,initialized with 1 but actually stores the current node+neighbouring/adjacent nodes .</p><p>findultp: returns the ultimate parent.</p><p>find:returns whether the two nodes are part of the same component or not.</p><p>unionbyRank:Joins components based on rank</p><p>unionbySize:Joins compononents based on size</p><p>Method 1:Union by rank<br>Method 2:Union by size</p><blockquote>class DisjointSet {<br>public:<br>vector&lt;int&gt;parent;<br>vector&lt;int&gt;rank1;<br>vector&lt;int&gt;size1;<br> DisjointSet(int n) {<br> parent.resize(n);<br> for(int i=0;i&lt;parent.size();i++)<br> {<br> parent[i]=i;<br> }<br> rank1.resize(n,0);<br> size1.resize(n,1);<br> }<br> int findultp(int u)<br> {<br> if(parent[u]==u)<br> {return u;}<br> return parent[u]=findultp(parent[u]);<br> }<br> bool find(int u, int v) {<br> int rootu=findultp(u);<br> int rootv=findultp(v);<br> if(rootu==rootv)<br> {return true;<br> }<br> else<br> {return false;}</blockquote><blockquote>}</blockquote><blockquote>void unionByRank(int u, int v) {<br> int rootu=findultp(u);<br> int rootv=findultp(v);<br> if(rootu==rootv)<br> {return ;<br> }<br> int ranku=rank1[rootu];<br> int rankv=rank1[rootv];<br> if(ranku&gt;rankv)<br> {parent[rootv]=rootu;}<br> else if(ranku&lt;rankv)<br> {parent[rootu]=rootv;}<br> else<br> {parent[rootv]=rootu;<br> rank1[rootu]++;}</blockquote><blockquote>}</blockquote><blockquote>void unionBySize(int u, int v) {<br> int rootu=findultp(u);<br> int rootv=findultp(v);<br> if(rootu==rootv)<br> {return ;<br> }<br> int sizeu=size1[rootu];<br> int sizev=size1[rootv];<br> if(sizeu&lt;sizev)<br> {parent[rootu]=rootv;<br> size1[rootv]+=size1[rootu];}<br> else<br> { parent[rootv]=rootu;<br> size1[rootu]+=size1[rootv];}</blockquote><blockquote>}<br>};</blockquote><h3>When to Use Union-Find?</h3><ul><li><strong>Dynamic connectivity:</strong> When you need to know if two nodes are connected as the graph changes.</li><li><strong>Cycle detection:</strong> Checking if adding an edge creates a cycle in an undirected graph.</li><li><strong>Kruskal’s MST algorithm:</strong> Fast connectivity checks during edge selection</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a7a284901cea" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Exploring the optimization of Djikstra’s Algorithm]]></title>
            <link>https://medium.com/@zaid03/exploring-the-optimization-of-djikstras-algorithm-b38f33e71c27?source=rss-3cd7af860162------2</link>
            <guid isPermaLink="false">https://medium.com/p/b38f33e71c27</guid>
            <dc:creator><![CDATA[Zaid]]></dc:creator>
            <pubDate>Wed, 03 Sep 2025 20:05:57 GMT</pubDate>
            <atom:updated>2025-10-20T05:40:42.681Z</atom:updated>
            <content:encoded><![CDATA[<p>Solving the problem <a href="https://leetcode.com/problems/path-with-maximum-probability/">1514. Path with Maximum Probability</a></p><p><strong>For Time Complexity O(n²)</strong></p><blockquote>class Solution {<br> public:<br> double maxProbability(int n, vector&lt;vector&lt;int&gt;&gt;&amp; edges,<br> vector&lt;double&gt;&amp; succProb, int start_node,<br> int end_node) {<br> vector&lt;double&gt; dist(n, 0);<br> vector&lt;vector&lt;pair&lt;int, double&gt;&gt;&gt; adj(n);<br> for (int i = 0; i &lt; edges.size(); i++) {<br> adj[edges[i][0]].push_back({edges[i][1], succProb[i]});<br> adj[edges[i][1]].push_back({edges[i][0], succProb[i]});<br> }</blockquote><blockquote>vector&lt;int&gt; visited(n, 0);<br> dist[start_node] = 1;</blockquote><blockquote>for (int count = 0; count &lt; n; count++) {<br> double maxdist = -1;<br> int curr = -1;<br> // find the max distance neighbouring node<br> for (int i = 0; i &lt; n; i++) {<br> if (!visited[i] &amp;&amp; maxdist &lt; dist[i]) {<br> maxdist = dist[i];<br> curr = i;<br> }<br> }<br> if (curr == -1 || maxdist == 0) break;<br> if (curr == end_node) return maxdist;<br> visited[curr] = 1;<br> // update all other distances<br> for (auto nbr : adj[curr]) {<br> int v = nbr.first;<br> double prob1 = nbr.second;<br> if (visited[v]) continue;<br> if (dist[v] &lt; dist[curr] * prob1) {<br> dist[v] = dist[curr] * prob1;<br> }<br> }<br> }<br> return dist[end_node];<br> }<br>};</blockquote><p>Algorithm:</p><p>Create a visited array ,a distance array and an adjacent matrix with cost paired.</p><p>Loop n times inside that find curr nodes max near neighbour</p><p>if curr==-1 or maxdist==0 exit</p><p>if curr==endnode return maxdist</p><p>Update the neighbour distances of above max near neighbour</p><p><strong>For Time Complexity O(n+nlogn)</strong></p><blockquote>class Solution {<br> public: double maxProbability(int n, vector &lt; vector &lt; int &gt;&gt; &amp; edges, vector &lt; double &gt; &amp; succProb, int start_node, int end_node) {<br> vector &lt; double &gt; dist(n, 0);<br> vector &lt; vector &lt; pair &lt; int, double &gt;&gt;&gt; adj(n);<br> for (int i = 0; i &lt; edges.size(); i++) {<br> adj[edges[i][0]].push_back({<br> edges[i][1],<br> succProb[i]<br> });<br> adj[edges[i][1]].push_back({<br> edges[i][0],<br> succProb[i]<br> });<br> }</blockquote><blockquote>priority_queue &lt; pair &lt; double, int &gt;&gt; pq;<br> pq.push({<br> 1.0,<br> start_node<br> });<br> while (!pq.empty()) {<br> auto[prob, node] = pq.top();<br> pq.pop();<br> if (node == end_node) return prob;<br> for (auto &amp; [neighbour, edgeprob]: adj[node]) {<br> double newprob = prob * edgeprob;<br> if (newprob &gt; dist[neighbour]) {<br> dist[neighbour] = newprob;<br> pq.push({<br> newprob,<br> neighbour<br> });<br> }<br> }<br> }<br> return 0;<br> }<br>};</blockquote><p><strong>For Time Complexity O(m(logn)^(2/3))</strong></p><p>You can use the new shortest path algorithm</p><p><strong>Step 1:Frontier shrinking</strong></p><p><strong>Step 2:Divide and conquer</strong></p><p><strong>Step 3:Bounded relaxation</strong></p><p>This method does not use global sorting,it moves over layers of nodes rather than just one node at a time.This method has recursive partitioning.</p><p>Space complexity may increase because of recursive stack.</p><p><strong>Step-by-Step Algorithm of the New Shortest Path Approach</strong></p><p>The new shortest path algorithm is a breakthrough improvement over the classical Dijkstra and Bellman-Ford algorithms, introducing novel concepts such as frontier shrinking, divide and conquer, and bounded relaxation. Here’s how it works step-by-step:</p><p><strong>1. Initialization</strong><br>- Start from the source node ( S ). Set the initial distances from ( S ) to itself as 0, and to all other nodes as infinity.<br>- Define a hyperparameter ( K ) which controls the number of relaxation rounds (iterations). For example, ( K=2 ) means two global rounds of relaxation.</p><p><strong>2. Relaxation and Layered Exploration</strong><br>- Unlike Dijkstra, which processes one node at a time via a priority queue, this new algorithm operates layer-wise, handling multiple nodes simultaneously.<br>- In each relaxation round, update the shortest distance estimates for all nodes reachable within a specific hop count— the number of edges from the source.<br>- For ( K=2 ):<br> — Round 1: Relax all nodes reachable within 1 edge (hop count = 1).<br> — Round 2: Relax all nodes reachable within 2 edges (hop count = 2).</p><p><strong>3. Frontier Shrinking and Pivot Identification</strong><br>- After processing nodes reachable within ( K ) hops, identify nodes that are finished(shortest path found within these hops).<br>- Nodes still unfinished require more hops to reach (e.g., nodes G, H, I in the example).<br>- The algorithm selects a new set of frontier nodes, called pivots, which are nodes adjacent to unfinished nodes.<br>- These pivots serve as new starting points for recursive calls, effectively shrinking the search frontier and narrowing focus.</p><p><strong>4. Recursive Divide and Conquer</strong><br>- Apply the same relaxation process recursively starting from the pivot nodes to cover the remaining nodes.<br>- Each recursive call handles a smaller subproblem, continuing to relax nodes layer-by-layer within the ( K)-hop boundary.<br>- This divide and conquer approach allows efficient parallel exploration of different graph layers without maintaining a global priority queue.</p><p><strong>5. Bounded Relaxation<br></strong>- Relaxations are bounded to nodes within ( K ) hops from the current frontier.<br>- This limitation avoids unnecessary updates for distant nodes in each iteration, saving computation time.<br>- Nodes outside the current ( K )-hop radius are deferred to later recursive calls.</p><p><strong>6. Distance Updates (Relaxation)</strong><br>- For each node ( U ) in the current frontier and each of its neighbors ( V ):<br> — Check if the path through ( U ) improves the current shortest distance to ( V ).<br> — If yes, update ( V )’s distance.<br>- This relaxation is performed globally for all nodes in the current layer simultaneously rather than individually.</p><p><strong>7. Termination</strong><br>- The algorithm terminates when all nodes have been processed and no further distance updates are possible.<br>- At this point, shortest paths from ( S ) to all other nodes are finalized.</p><p><strong>Summary of Key Improvements Over Dijkstra and Bellman-Ford:</strong></p><p>- Batch Processing of Nodes: Works on whole layers (sets of nodes) at a time instead of single nodes, enabling faster convergence.<br>-No Priority Queue: Eliminates the overhead of sorting nodes via priority queues, reducing complexity.<br>- Frontier Shrinking: Focuses on a subset of nodes (pivots) after each iteration, reducing the search space.<br>- Bounded Relaxation: Limits relaxation to nodes within a fixed hop count, avoiding wasteful computations.<br>- Recursive Divide and Conquer: Breaks down the problem into smaller subproblems recursively, improving efficiency.<br>- Improved Time Complexity:Achieves a complexity of approximately ( m log^{2/3} n ), outperforming Dijkstra’s ( m + n log n ).</p><p><strong>Example Walkthrough (Simplified):</strong></p><p>- Start with source ( S ), ( K=2 ).<br>- Round 1: Relax nodes reachable within 1 hop (e.g., nodes A, B, C).<br>- Round 2: Relax nodes reachable within 2 hops (e.g., nodes D, E, F).<br>- Identify unfinished nodes (e.g., G, H, I).<br>- Set new frontiers as pivots (e.g., D, E, F).<br>- Recursively repeat relaxation rounds from these pivots to cover remaining nodes.<br>- After two full iterations, all nodes’ shortest paths are computed efficiently.</p><p>This new shortest path algorithm represents a significant leap forward by blending classical relaxation with frontier-based recursion and layer-wise processing, achieving faster runtimes especially on large graphs. For a deeper dive, exploring the original paper is highly recommended.</p><p><strong>Bonus:</strong><br><strong><em>Bellman Ford:Visits all edges V-1 times and updates good for negative weights acycling graph</em></strong></p><blockquote>class Solution {<br> public:<br> vector&lt;int&gt; bellmanFord(int V, vector&lt;vector&lt;int&gt;&gt;&amp; edges, int src) {<br> // Code here<br> //approach<br> //bellman ford cause it explores all edges V-1 times allowing negative weight handling<br>//no need for adjacent vector cause we r not doing greedy bfs like djikstra but visited all edges multiple times<br> vector&lt;int&gt;dist(V,1e8);<br> dist[src]=0;<br> for(int i=1;i&lt;=V-1;i++)<br> {<br> for(auto edge:edges)<br> {<br> int u=edge[0];<br> int v=edge[1];<br> int w=edge[2];<br> if(dist[u]!=1e8 &amp;&amp; dist[v]&gt;dist[u]+w)<br> {dist[v]=dist[u]+w;}<br> <br> }<br> }<br> for(auto edge:edges)<br> {<br> int u=edge[0];<br> int v=edge[1];<br> int w=edge[2];<br> if(dist[u]!=1e8 &amp;&amp; dist[v]&gt;dist[u]+w)<br> {return {-1};}<br> <br> }<br> return dist;<br> <br> }<br>};</blockquote><p>Time Complexity of Bellman Ford=O(N²)<br><strong><em>Floyd Warshall:Shortest distance between all edges stored in a distance 2d matrix.</em></strong></p><blockquote>class Solution {<br> public:<br> void floydWarshall(vector&lt;vector&lt;int&gt;&gt; &amp;dist) {<br> //via nodes method<br> int MAX=1e8;<br> <br> for(int i=0;i&lt;dist.size();i++)//taking the node in between<br> {<br> for(int k=0;k&lt;dist.size();k++)<br> {<br> for(int l=0;l&lt;dist[0].size();l++)<br> {if(dist[k][i]!=1e8 &amp;&amp; dist[i][l]!=1e8)<br> {int newdist=dist[k][i]+dist[i][l];<br> dist[k][l]=min(newdist,dist[k][l]);}<br> }<br> }<br> }<br> <br> }<br>};</blockquote><p>Time complexity=O(N³)</p><p>| Algorithm | Negative Weights | Negative Cycles | Graph Type |<br>| — — — — — — — — — -| — — — — — — — — -| — — — — — — — — -| — — — — — — — — — — |<br>| Floyd-Warshall | Yes | No | Cyclic or Acyclic (but NOT with negative cycles) |<br>| Bellman-Ford | Yes | Detects | Not with negative cycle we need to put a seperate negative cycle detector after run|<br>| Dijkstra | No | N/A | Any |</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b38f33e71c27" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to System Design in interviews within 45 minutes?(LLD)]]></title>
            <link>https://medium.com/@zaid03/how-to-system-design-in-interviews-within-45-minutes-1d6c5d2410bc?source=rss-3cd7af860162------2</link>
            <guid isPermaLink="false">https://medium.com/p/1d6c5d2410bc</guid>
            <category><![CDATA[system-design-concepts]]></category>
            <category><![CDATA[low-level-design]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <dc:creator><![CDATA[Zaid]]></dc:creator>
            <pubDate>Thu, 21 Aug 2025 14:26:08 GMT</pubDate>
            <atom:updated>2025-08-21T14:33:46.452Z</atom:updated>
            <content:encoded><![CDATA[<p>⭐Most important-Communication</p><p>⭐First tell the basic interactions/idea in the system design in plain english.</p><p>⭐Then present the basic user behaviour control flow with the usecases .(with diagram is better)</p><p>⭐Ask the interviewer for any other important features to focus on.</p><p>⭐Keep asking the interviewer if you are on the right track after each answer.</p><p>⭐Identify the entities in the flow for the classes to be required.</p><p>⭐Start writing code starting with defining classes and objects.(You can ask interview if the data types can be ignored.)</p><p>⭐Then identify code methods and concurrency handling.Use design patterns for concurrency.Atleast mention about the design patterns if not implementing.</p><p>⭐Ask interviewer — Do you want to deep dive into any particular functionality?</p><p>⭐Start implementing business logic through code of the functionality.Focus on business logic rather than create,read,update,delete operations.Use design principles for clean code.</p><p>⭐If achieved functionality-Time used 40 mins-Done significant work✅✅</p><p>⭐If Time permits — flex with edge cases and exception handling.</p><p>⭐If interview was longer-Implement more functionality by asking.</p><p>⭐Balance simplicity with extensability.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1d6c5d2410bc" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How Do You Really Evaluate an LLM? Two Key Approaches Explained]]></title>
            <link>https://medium.com/@zaid03/how-do-you-really-evaluate-an-llm-two-key-approaches-explained-1b79f1c5a2c8?source=rss-3cd7af860162------2</link>
            <guid isPermaLink="false">https://medium.com/p/1b79f1c5a2c8</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[llm-evaluation]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[llm]]></category>
            <dc:creator><![CDATA[Zaid]]></dc:creator>
            <pubDate>Tue, 12 Aug 2025 10:18:50 GMT</pubDate>
            <atom:updated>2025-08-12T10:18:50.474Z</atom:updated>
            <content:encoded><![CDATA[<p>Large Language Models (LLMs) are transforming how we interact with technology — from chatbots to code assistants. But with their impressive capabilities come big questions: <strong>How do we know if an LLM is actually “good”?</strong> And what does “good” even mean when the answers can be both factual and creative?</p><p>Turns out, the best way to evaluate an LLM is to blend two complementary approaches: <strong>objective factual checks</strong> and <strong>subjective grading</strong>.</p><h3>1. Factual Checks: Grounding AI in Truth</h3><p>First, we want to know if the LLM is getting the facts right. This means comparing its output against a known “ground truth” — like a verified answer or a trusted source.</p><p><strong>How does this work?</strong></p><ul><li><strong>Exact Match:</strong> Did the model give the same answer as the reference?</li><li><strong>Hallucination Rate:</strong> Did it make something up or get details wrong? (Think of frameworks like FACTSCORE, which break down answers into atomic facts and check each one against reliable sources.)</li><li><strong>Relevancy &amp; Correctness:</strong> Is the response not just accurate, but also relevant and concise?</li></ul><p><strong>Why does it matter?</strong><br> In fields like law, medicine, or finance, factual accuracy isn’t optional — it’s essential. Automated tests and benchmarks help ensure LLMs stay grounded in reality. Some of the most widely used include:</p><ul><li><strong>GLUE:</strong> Evaluates general language understanding.</li><li><strong>TruthfulQA:</strong> Tests for truthfulness and resistance to common misconceptions.</li><li><strong>MMLU (Massive Multitask Language Understanding):</strong> Assesses broad academic and professional knowledge across dozens of subjects, making it a gold standard for measuring factual and reasoning abilities in LLMs.</li></ul><h3>2. LLM Grading: The Subjective Side of AI</h3><p>But LLMs aren’t just about facts — they’re also about creativity, tone, and usefulness. Here’s where the <strong>LLM-as-a-Judge</strong> approach comes in: we use one LLM to grade another, based on custom criteria like creativity, helpfulness, or coherence.</p><p><strong>How does this work?</strong></p><ul><li>A “judge” LLM is given the prompt, the answer, and a rubric (e.g., “Rate creativity from 1–5”).</li><li>The judge scores the output or picks the best answer in a pairwise comparison.</li></ul><p><strong>Why use LLMs to judge each other?</strong></p><ul><li>It’s scalable and fast — much quicker than relying solely on human reviewers.</li><li>It can catch subtle qualities (like tone or style) that simple metrics miss.</li></ul><p><strong>But there are limits:</strong><br> LLM judges can be biased, inconsistent, or struggle with truly novel content. That’s why human evaluation is still the gold standard for nuance and ethics.</p><h3>Bringing It All Together: Modern Evaluation Frameworks</h3><p>Today, platforms like <strong>DeepEval</strong> and <strong>ARES</strong> are making LLM evaluation more systematic:</p><ul><li><strong>DeepEval</strong> lets you unit test LLM outputs for metrics like hallucination and answer relevancy, and compare model iterations side-by-side.</li><li><strong>ARES</strong> specializes in evaluating Retrieval-Augmented Generation (RAG) systems, using fine-tuned LLM judges to assess faithfulness and relevance.</li></ul><p><strong>The takeaway:</strong><br> No single method is enough. The smartest teams blend automated metrics, LLM-as-a-Judge, and human review to build trustworthy, effective AI.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1b79f1c5a2c8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[My Google APM Intern Interview Experience: How I Navigated the 45-Minute Challenge]]></title>
            <link>https://medium.com/@zaid03/my-google-apm-intern-interview-experience-how-i-navigated-the-45-minute-challenge-ac66b96fad20?source=rss-3cd7af860162------2</link>
            <guid isPermaLink="false">https://medium.com/p/ac66b96fad20</guid>
            <category><![CDATA[google]]></category>
            <category><![CDATA[communication]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[product-management]]></category>
            <dc:creator><![CDATA[Zaid]]></dc:creator>
            <pubDate>Sun, 20 Jul 2025 18:43:53 GMT</pubDate>
            <atom:updated>2025-07-20T18:43:53.652Z</atom:updated>
            <content:encoded><![CDATA[<p>Getting that email from Google’s APM recruiting team was surreal. After submitting my application and waiting nervously for weeks, the preliminary screening invitation landed in my inbox with detailed prep materials and scheduling instructions. What followed was one of the most intellectually stimulating conversations of my career.</p><h3>The Setup and First Impressions</h3><p>The interview was conducted via Google Meet with a Product Manager from the Gemini AI team. The format followed Google’s standard structure: a brief warm-up, followed by deep-dive product questions designed to assess product insight, strategic thinking, and analytical skills.</p><p>What immediately struck me was how conversational yet rigorous the process felt. My interviewer was genuinely interested in understanding my thought process, not just evaluating my final answers.</p><h3>The Challenge That Defined the Interview</h3><p>After the initial pleasantries, I was presented with a classic Google APM scenario: selecting an app I use regularly and proposing three specific improvements, complete with business impact projections and reasoning. This wasn’t just about ideation — it required combining user empathy, market understanding, and analytical rigor.</p><p>The beauty of this question was its open-ended nature. There was no “right” answer, only an opportunity to demonstrate structured thinking and creativity under pressure.</p><h3>My Strategic Approach</h3><p>I chose to focus on an app I genuinely use daily, which allowed me to speak authentically about real pain points I’d experienced. For each improvement, I structured my response around:</p><ul><li><strong>User problem identification</strong></li><li><strong>Proposed solution with clear value proposition</strong></li><li><strong>Quantified business impact estimates</strong></li><li><strong>Implementation considerations and trade-offs</strong></li></ul><p>This framework helped me stay organized while the interviewer probed deeper with follow-up questions.</p><h3>The Real Test: Cross-Examination</h3><p>What separated this from a typical product discussion was the intensity of the follow-up questioning. Every assumption was challenged, every metric was scrutinized. The interviewer pushed me to:</p><ul><li>Defend my user research assumptions</li><li>Explain my business impact calculations</li><li>Consider technical implementation challenges</li><li>Prioritize features under resource constraints</li><li>Validate market opportunity assessments</li></ul><p>This wasn’t adversarial — it was collaborative problem-solving at the highest level. The interviewer was genuinely helping me think through the complexities of product development at scale.</p><h3>Key Insights About the Google APM Process</h3><p>The experience reinforced several things about Google’s evaluation criteria:</p><p><strong>User-centricity is paramount.</strong> Every solution had to start with a genuine user problem, not a cool technical feature. Google PMs are expected to be customer advocates first.</p><p><strong>Data-driven decision making is essential.</strong> While creativity matters, every hypothesis needed to be grounded in logical reasoning and measurable outcomes.</p><p><strong>Systems thinking is crucial.</strong> Solutions couldn’t exist in isolation — they needed to consider broader ecosystem impacts, technical constraints, and business strategy alignment.</p><p><strong>Intellectual humility is valued.</strong> Being willing to revise assumptions based on new information or alternative perspectives was more important than defending initial positions.</p><h3>What This Experience Taught Me</h3><p>Beyond the specific interview preparation, this conversation crystallized my understanding of what product management actually entails at a company like Google. It’s not just about having good ideas — it’s about rigorous problem-solving methodology, stakeholder empathy, and the ability to navigate ambiguity with structured thinking.</p><p>The experience also highlighted the importance of authentic preparation over memorized frameworks. The most compelling moments came when I could draw on real experiences and genuine insights rather than textbook responses.</p><h3>Preparing for Similar Experiences</h3><p>For anyone facing similar interviews, my biggest recommendation is to practice thinking out loud about products you genuinely use and care about. Develop opinions about what works, what doesn’t, and why. But more importantly, be ready to defend and refine those opinions under scrutiny.</p><p>The Google APM interview isn’t just an evaluation — it’s a preview of the intellectual rigor and collaborative problem-solving that defines product management at scale. Whether or not I advance to the next round, the experience reinforced my passion for building products that solve real problems for millions of users.</p><p>The journey continues, but this conversation was a master class in product thinking that will influence how I approach challenges long beyond this interview process.</p><p><em>Currently navigating the APM interview process at top tech companies. Follow my journey as I explore the intersection of technology, user empathy, and business strategy.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ac66b96fad20" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Amazon SDE 1 University Graduate Interview Experience (Freshers)]]></title>
            <link>https://medium.com/@zaid03/amazon-sde-1-university-graduate-interview-experience-freshers-30f6d896b676?source=rss-3cd7af860162------2</link>
            <guid isPermaLink="false">https://medium.com/p/30f6d896b676</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[amazon]]></category>
            <category><![CDATA[cpp]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Zaid]]></dc:creator>
            <pubDate>Sun, 06 Jul 2025 16:32:32 GMT</pubDate>
            <atom:updated>2025-07-28T20:30:20.318Z</atom:updated>
            <content:encoded><![CDATA[<p><strong><em>Amazon SDE 1 University Graduate Interview Experience (Freshers)</em></strong></p><p><strong>Round 1: Online Test</strong><br>The online test consisted of two Data Structures and Algorithms (DSA) problems. Below is a detailed explanation of the questions and approaches used.</p><p><strong>Problem 1: Greedy Algorithm with Sorting</strong><br>Problem Description : You are given an array of integers, and you need to perform operations that maximize or minimize a certain objective function. The operations involve iterating through the array in a specific order.<br><strong>Approach :</strong><br>Sort the array to arrange elements in ascending or descending order.<br>Use a greedy strategy to alternate between extreme values (smallest and largest elements) to achieve the optimal result.<br>For example, if the task involves maximizing a difference-based calculation, pairing the smallest and largest elements repeatedly yields the best outcome.<br>Complexity : O(NlogN) due to sorting.<br><strong>Problem 2: Simulation with Sorting</strong><br>Problem Description : This problem involved processing two arrays where one array represented resources, and the other represented constraints. The goal was to maximize or minimize a cumulative value while adhering to the constraints.<br><strong>Approach :</strong><br>Pair the two arrays based on their indices.<br>Sort the pairs based on one of the constraints (e.g., thresholds or priorities).<br>Simulate the process by iterating through the sorted data and applying the rules step-by-step.<br>Ensure stricter conditions are handled first to avoid invalid states.<br>Complexity : O(NlogN) due to sorting.<br><strong>Work Simulation</strong><br>The work simulation was designed to mimic a real-life day in the life of an SDE at Amazon. It involved solving practical problems related to software development, debugging, and collaboration. The tasks tested technical skills, decision-making abilities, and alignment with Amazon’s Leadership Principles.</p><p><strong>Culture Fit Questions</strong><br>Behavioral questions were situational.These questions aligned with Amazon’s Leadership Principles and to check Culture fit.</p><blockquote><strong><em>Round 2: Technical Interview</em></strong><br>Two DSA questions were asked during this round. Below are the detailed explanations of the questions and approaches used.There were 2 SDEs who were evaluating.Interviewers gave good hints.To reach the solution.</blockquote><p><strong>Question 1: Graph Traversal</strong><br>Question 1: Minimum Cost to Reach the End Point</p><h4>Problem Statement</h4><p>You are given a grid with N rows and M columns. You need to find the minimum cost to travel from a starting point [start_row, start_col] to an ending point [end_row, end_col]. Movement rules are as follows:</p><ol><li>Moving right in the same row costs 1.</li><li>Moving from the last column of one row to the first column of the next row costs 1.</li><li>Taking a shortcut (if available) costs 1.</li></ol><p>Additionally, you are provided with a list of shortcuts, where each shortcut is represented as [row1, col1, row2, col2], allowing you to jump directly from [row1, col1] to [row2, col2].</p><h4>Approach</h4><p>Graph Representation :</p><ul><li>Treat each cell (row, col) as a node.</li><li>Add edges based on movement rules (rightward, row transitions, shortcuts).</li></ul><p>Algorithm :</p><ul><li>Use Dijkstra’s algorithm to find the shortest path in the graph.</li><li>A priority queue ensures that nodes are processed in order of increasing cost.</li><li>Maintain a distance map to track the minimum cost to reach each cell.</li></ul><p>Complexity :</p><ul><li>Time Complexity : <em>O</em>((<em>N</em>×<em>M</em>+<em>K</em>)log(<em>N</em>×<em>M</em>)) , where <em>K</em> is the number of shortcuts.</li><li>Space Complexity : <em>O</em>(<em>N</em>×<em>M</em>) for the adjacency list and distance map.</li></ul><blockquote>#include &lt;iostream&gt;<br>#include &lt;vector&gt;<br>#include &lt;queue&gt;<br>#include &lt;tuple&gt;<br>using namespace std;</blockquote><blockquote>int min_cost(int N, int M, vector&lt;vector&lt;int&gt;&gt; shortcuts, vector&lt;int&gt; start, vector&lt;int&gt; end) {<br> // Create adjacency list using a flat index (row * M + col)<br> vector&lt;vector&lt;int&gt;&gt; adj(N * M);</blockquote><blockquote>// Add rightward movements<br> for (int r = 0; r &lt; N; ++r) {<br> for (int c = 0; c &lt; M — 1; ++c) {<br> int current_cell = r * M + c;<br> int next_cell = r * M + (c + 1);<br> adj[current_cell].push_back(next_cell);<br> }<br> }</blockquote><blockquote>// Add row transitions<br> for (int r = 0; r &lt; N — 1; ++r) {<br> int current_cell = r * M + (M — 1);<br> int next_cell = (r + 1) * M + 0;<br> adj[current_cell].push_back(next_cell);<br> }</blockquote><blockquote>// Add shortcuts<br> for (const auto&amp; shortcut : shortcuts) {<br> int r1 = shortcut[0] — 1, c1 = shortcut[1] — 1; // Convert to 0-based indexing<br> int r2 = shortcut[2] — 1, c2 = shortcut[3] — 1; // Convert to 0-based indexing<br> int from_cell = r1 * M + c1;<br> int to_cell = r2 * M + c2;<br> adj[from_cell].push_back(to_cell);<br> }</blockquote><blockquote>// Dijkstra’s setup<br> int start_row = start[0] — 1, start_col = start[1] — 1; // Convert to 0-based indexing<br> int end_row = end[0] — 1, end_col = end[1] — 1; // Convert to 0-based indexing</blockquote><blockquote>int start_cell = start_row * M + start_col;<br> int end_cell = end_row * M + end_col;</blockquote><blockquote>// Min-heap priority queue: (cost, cell_id)<br> priority_queue&lt;pair&lt;int, int&gt;, vector&lt;pair&lt;int, int&gt;&gt;, greater&lt;pair&lt;int, int&gt;&gt;&gt; pq;<br> pq.push({0, start_cell});</blockquote><blockquote>// Distance array to store minimum cost to reach each cell<br> vector&lt;int&gt; dist(N * M, -1); // Initialize all distances to -1 (unreachable)<br> dist[start_cell] = 0;</blockquote><blockquote>// Directions to explore neighbors<br> while (!pq.empty()) {<br> auto [cost, cell] = pq.top();<br> pq.pop();</blockquote><blockquote>// If we reach the end, return the cost<br> if (cell == end_cell) {<br> return cost;<br> }</blockquote><blockquote>// Explore neighbors<br> for (const auto&amp; neighbor : adj[cell]) {<br> int new_cost = cost + 1; // Cost to move to the neighbor<br> if (dist[neighbor] == -1 || new_cost &lt; dist[neighbor]) {<br> dist[neighbor] = new_cost;<br> pq.push({new_cost, neighbor});<br> }<br> }<br> }</blockquote><blockquote>return -1; // If the end is unreachable<br>}</blockquote><blockquote>// Example usage<br>int main() {<br> int N = 3, M = 4;<br> vector&lt;vector&lt;int&gt;&gt; shortcuts = {{1, 2, 3, 3}, {2, 4, 1, 1}};<br> vector&lt;int&gt; start = {1, 1};<br> vector&lt;int&gt; end = {3, 4};</blockquote><blockquote>cout &lt;&lt; “Minimum cost: “ &lt;&lt; min_cost(N, M, shortcuts, start, end) &lt;&lt; endl; // Output: 3<br> return 0;<br>}</blockquote><h3>Question 2: Partition Linked List</h3><h4>Problem Statement</h4><p>Given a linked list and a value x, partition it such that:</p><ol><li>All nodes less than x come first.</li><li>All nodes equal to x come next.</li><li>All nodes greater than x come last.</li></ol><p>Preserve the relative order of nodes within each partition.</p><h4>Approach</h4><ol><li>Key Observations :</li></ol><ul><li>Use three dummy heads to collect nodes into three partitions: &lt; x, = x, and &gt; x.</li><li>Traverse the list once, appending nodes to the appropriate partition based on their values.</li><li>Connect the partitions in the correct order.</li></ul><p>Algorithm :</p><ul><li>Create three dummy heads: lessHead, equalHead, greaterHead.</li><li>Traverse the list and append nodes to the respective partitions.</li><li>Connect the partitions and return the head of the modified list.</li></ul><p>Complexity :</p><ul><li>Time Complexity : <em>O</em>(<em>N</em>) , where <em>N</em> is the number of nodes.</li><li>Space Complexity : <em>O</em>(1) , as no additional data structures are used.</li></ul><blockquote><em>#include &lt;iostream&gt;<br>using namespace std;</em></blockquote><blockquote><em>struct Node {<br> int val;<br> Node* next;<br> Node(int x) : val(x), next(nullptr) {}<br>};</em></blockquote><blockquote><em>Node* partition(Node* head, int x) {<br> // Dummy heads for three partitions<br> Node lessHead(0), equalHead(0), greaterHead(0);<br> Node *less = &amp;lessHead, *equal = &amp;equalHead, *greater = &amp;greaterHead;<br> <br> // Traverse the list<br> Node* curr = head;<br> while (curr) {<br> if (curr-&gt;val &lt; x) {<br> less-&gt;next = curr;<br> less = less-&gt;next;<br> } else if (curr-&gt;val == x) {<br> equal-&gt;next = curr;<br> equal = equal-&gt;next;<br> } else {<br> greater-&gt;next = curr;<br> greater = greater-&gt;next;<br> }<br> curr = curr-&gt;next;<br> }<br> <br> // Connect the partitions<br> greater-&gt;next = nullptr; // Avoid cycles<br> equal-&gt;next = greaterHead.next;<br> less-&gt;next = equalHead.next;<br> <br> return lessHead.next;<br>}</em></blockquote><blockquote><em>// Helper function to print the linked list<br>void printList(Node* head) {<br> while (head) {<br> cout &lt;&lt; head-&gt;val &lt;&lt; “ “;<br> head = head-&gt;next;<br> }<br> cout &lt;&lt; endl;<br>}</em></blockquote><blockquote><em>// Example usage<br>int main() {<br> // Create linked list: 1 -&gt; 5 -&gt; 3 -&gt; 2 -&gt; 4 -&gt; 2 -&gt; 3<br> Node* head = new Node(1);<br> head-&gt;next = new Node(5);<br> head-&gt;next-&gt;next = new Node(3);<br> head-&gt;next-&gt;next-&gt;next = new Node(2);<br> head-&gt;next-&gt;next-&gt;next-&gt;next = new Node(4);<br> head-&gt;next-&gt;next-&gt;next-&gt;next-&gt;next = new Node(2);<br> head-&gt;next-&gt;next-&gt;next-&gt;next-&gt;next-&gt;next = new Node(3);</em></blockquote><blockquote><em>int x = 3;<br> Node* result = partition(head, x);</em></blockquote><blockquote><em>// Print the result<br> printList(result); // Output: 1 2 2 3 3 5 4<br> return 0;<br>}</em></blockquote><p><strong>My personal experience:</strong><br>In the tech interview asking the right questions and spending some time on the question is reasonable.I was able to answer first question by drilling down to the right approach of Djiktsras but could not implement in cpp completely.For the second question got the approach coded it and discussed the optimization.<br>Interviewers were really cool,got me calm and helped throughout the interview.</p><h3><strong><em>Onwards and upwards.</em></strong></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=30f6d896b676" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Binary Lifting(Jump pointers)]]></title>
            <link>https://medium.com/@zaid03/binary-lifting-jump-pointers-ae32c0079c61?source=rss-3cd7af860162------2</link>
            <guid isPermaLink="false">https://medium.com/p/ae32c0079c61</guid>
            <category><![CDATA[trees]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[binary-lifting]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Zaid]]></dc:creator>
            <pubDate>Sun, 29 Jun 2025 22:49:54 GMT</pubDate>
            <atom:updated>2025-06-29T22:53:35.741Z</atom:updated>
            <content:encoded><![CDATA[<p>The generic problem it solves:-</p><blockquote>There is a tree of size N, rooted at 0.<br>Answer Q queries:<br>Given v and k, find k-th ancestor of v.</blockquote><p>Ancestor means parent levels</p><p>To represent for example <br>19th ancestor it will need to go 19 levels up from vertex v .<br>Normally if we go manually it might take O(N) time complexity and total of O(N*N) time complexity.<br>To reduce this what we can do it is represent 19 in binary(sum of powers of 2)<br>19=10011=16+2+1</p><p>which are jumps taken to shortest time complexity to O(logn) as power of 2 jump we are taking.</p><p>To achieve this we use Preprocessing:</p><p>int up[N][LOG]<br>up[v][j] — 2^j-th ancestor of v<br>for v = 0 .. N-1:<br>up[v] [0] = parent[v]<br>up[v][1]= up[up[v][0]][0]<br>up[v][2] = up[up[v] [1]][1]<br>up[v][3]= up[up[v][2]][2]</p><p>Now generalizing<br><strong><em>up[v][j]=up[up[v][j−1]][j−1]</em></strong></p><h3><strong><em>Key Idea</em></strong></h3><p>The core idea is that a jump of size 2<em>j</em> can be broken into two smaller jumps of size 2^(<em>j</em>−1) . Why? Because:</p><p><em>2^j</em>=2^(<em>j</em>−1)+2^(<em>j</em>−1)</p><p>This means that to reach the 2<em>j</em> -th ancestor of <em>v</em> , you can:</p><ol><li>First jump 2<em>j</em>−1 levels up from <em>v</em> to some intermediate node <em>x</em> .</li><li>Then, from <em>x</em> , jump another 2<em>j</em>−1 levels up.</li></ol><p>Since both jumps are of size 2<em>j</em>−1 , and we’ve already precomputed all 2<em>j</em>−1 -th ancestors during the preprocessing phase, this allows us to efficiently compute the 2<em>j</em> -th ancestor.</p><blockquote><strong>Note:<br>parent[i] &lt; i//if this condition is valid then only the binary lifting will work</strong></blockquote><p>Pseudocode:</p><blockquote>int up[N][LOG]//LOG is depth <br>up[v][j] — 2^j-th ancestor of v<br>for v = 0 .. N-1:<br>up[v] [0] = parent[v]<br>for j = 1 .. LOG-1:for v = 0 .. N-1:<br>up[v][j] = up[ up[v][j-1] ][j-1]// precomputing each levelwise.</blockquote><h3>Time&amp;Space complexity<br>O(N*log(N))</h3><blockquote>Sample python code to find <strong>Kth common Ancestor using Binary Lifting</strong>:<br>from typing import List</blockquote><blockquote>from math import log2</blockquote><blockquote>class TreeAncestor:</blockquote><blockquote>def __init__(self, n: int, parent: List[int]):</blockquote><blockquote>self.max_depth = int(log2(n)) + 1</blockquote><blockquote>self.ancestor_table = [[-1 for _ in range(self.max_depth)] for _ in range(n)]</blockquote><blockquote>for node in range(n):</blockquote><blockquote>self.ancestor_table[node][0] = parent[node]</blockquote><blockquote>for level in range(1, self.max_depth):</blockquote><blockquote>for node in range(n):</blockquote><blockquote>if self.ancestor_table[node][level — 1] != -1:</blockquote><blockquote>self.ancestor_table[node][level] = self.ancestor_table[</blockquote><blockquote>self.ancestor_table[node][level — 1]</blockquote><blockquote>][level — 1]</blockquote><blockquote>def getKthAncestor(self, node: int, k: int) -&gt; int:</blockquote><blockquote>for level in range(self.max_depth):</blockquote><blockquote>mask = 1 &lt;&lt; level</blockquote><blockquote>if k &amp; mask:</blockquote><blockquote>node = self.ancestor_table[node][level]</blockquote><blockquote>if node == -1:</blockquote><blockquote>return -1</blockquote><blockquote>return node</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ae32c0079c61" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>