SDE - Intern

Tip 1: Have complete conceptual clarity of OOPs pillars: Encapsulation, Inheritance, Polymorphism, and Abstraction — along with practical examples.
Tip 2: Practice writing small code snippets for concepts like virtual functions, constructor overloading, and deep copy vs shallow copy so you can explain them confidently.
Tip 3: Don’t just memorize definitions. Focus on how and when each concept is used in real-world scenarios.

Step 1: Restate and choose approach
Goal: reverse links so each node points to its previous node.
Constraint: must use recursion → think in terms of solving for the sublist and then fixing one pointer.
Step 2: Identify base cases
If head == null (empty list) → return null.
If head->next == null (single node) → already reversed; return head.
Step 3: Recurse on the smaller subproblem
Let newHead = reverse(head->next) which reverses the sublist starting at head->next.
Step 4: Fix the current node’s pointers (the crux)
After recursion returns, head->next points to the last node of the reversed sublist.
Set head->next->next = head to link current node to the tail of reversed sublist.
Set head->next = null to terminate the list correctly.
Step 5: Return the new head
newHead is the head of the fully reversed list; return it up the call stack.
Step 6: Complexity
Time: O(N) — each node visited once.
Space: O(N) call stack due to recursion (no extra heap structures).

Tip 1: Understand the four pillars of OOPs (Encapsulation, Inheritance, Polymorphism, Abstraction) with examples — don’t just memorize them.
Tip 2: Practice writing small snippets of C++ code to demonstrate concepts like virtual functions, constructor chaining, and function overriding.
Tip 3: Be prepared to differentiate between similar concepts like compile-time vs runtime polymorphism, deep vs shallow copy, and abstract class vs interface.

Step 1: Brute idea (hashing) — works but extra space
Traverse the list, store each node’s address in a hash set.
If you ever see a node that’s already in the set → cycle found.
Time: O(N), Space: O(N).
Interviewer asked to optimize space.
Step 2: Optimize to O(1) space (Floyd’s Hare & Tortoise)
Use two pointers: slow moves 1 step, fast moves 2 steps.
If there’s a cycle, they will meet; if fast or fast->next becomes NULL, no cycle.
Time: O(N), Space: O(1).
Step 3 (Follow-up): Find the cycle’s starting node
After slow and fast meet inside the cycle, reset one pointer to head.
Move both one step at a time; the node where they meet again is the cycle start.
Return that node (or its value), depending on the function signature.
Step 4: Complexity & reasoning
Time: O(N) — each pointer traverses at most ~N+K steps.
Space: O(1) — only pointers used.
Why it works: meeting point proves a loop (relative speed difference is 1), and the reset trick aligns distances to the loop entry.

Tip 1: Think logically and visualize the problem. Focus on the non-uniform burning condition; you can’t assume half the rope burns in 30 minutes.
Tip 2: The key trick:
Light Rope 1 from both ends and Rope 2 from one end at the same time.
Rope 1 will burn out in 30 minutes (since lighting both ends doubles the burning rate).
As soon as Rope 1 finishes, light the other end of Rope 2. Now Rope 2 will burn in 15 minutes (half of 30, since both ends are burning).
Total = 30 + 15 = 45 minutes.
Tip 3: Always explain your reasoning clearly step by step, not just the final answer; interviewers look for your approach and thought process more than the end result.