Topic: Linked Lists in Python – Part 4: Merging, Sorting, and Advanced Interview Problems

---

In this final part of the Linked List series, we’ll tackle more advanced and practical use cases like merging sorted lists, sorting a linked list, and interview-level challenges.

---

1. Merging Two Sorted Linked Lists

def merge_sorted_lists(l1, l2):
    dummy = Node(0)
    tail = dummy

    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 or l2
    return dummy.next

---

2. Sorting a Linked List (Merge Sort – O(n log n))

def merge_sort(head):
    if not head or not head.next:
        return head

    # Split list
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    left = merge_sort(head)
    right = merge_sort(mid)

    return merge_sorted_lists(left, right)

• Attach this to your LinkedList class to sort self.head.

---

3. Removing Duplicates from a Sorted List

def remove_duplicates(self):
    current = self.head
    while current and current.next:
        if current.data == current.next.data:
            current.next = current.next.next
        else:
            current = current.next

---

4. Intersection Point of Two Linked Lists

def get_intersection_node(headA, headB):
    if not headA or not headB:
        return None

    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a  # Can be None or the intersecting node

---

5. Flatten a Multilevel Linked List

Imagine a list where each node has next and child pointers. Recursively flatten:

def flatten(node):
    if not node:
        return None

    next_node = node.next
    if node.child:
        child_tail = flatten(node.child)
        node.next = node.child
        node.child = None
        child_tail.next = flatten(next_node)
        return child_tail if child_tail.next else child_tail
    else:
        node.next = flatten(next_node)
        return node

---

Summary

• You now know how to merge, sort, and deduplicate linked lists.

• Techniques like merge sort, two-pointer traversal, and recursive flattening are essential for mastering linked lists.

• These problems are frequently asked in interviews at top tech companies.

---

Exercise

• Given two unsorted linked lists, write a function that returns a new linked list containing only the elements present in both lists (intersection), without using extra space or sets.

---

#DSA #LinkedList #MergeSort #AdvancedDSA #CodingInterview

https://t.iss.one/DataScience4

In Python, the collections module offers specialized container datatypes that solve real-world coding challenges with elegance and efficiency. These tools are interview favorites for optimizing time complexity and writing clean, professional code! 💡

import collections  

# defaultdict - Eliminate key errors with auto-initialization  
from collections import defaultdict  
gradebook = defaultdict(int)  
gradebook['Alice'] += 95  
print(gradebook['Alice'])  # Output: 95  
print(gradebook['Bob'])    # Output: 0  

# defaultdict for grouping operations  
anagrams = defaultdict(list)  
words = ["eat", "tea", "tan"]  
for w in words:  
    key = ''.join(sorted(w))  
    anagrams[key].append(w)  
print(anagrams['aet'])  # Output: ['eat', 'tea']  

# Counter - Frequency analysis in one line  
from collections import Counter  
text = "abracadabra"  
freq = Counter(text)  
print(freq['a'])          # Output: 5  
print(freq.most_common(2)) # Output: [('a', 5), ('b', 2)]  

# Counter arithmetic for problem-solving  
inventory = Counter(apples=10, oranges=5)  
sales = Counter(apples=3, oranges=2)  
print(inventory - sales)  # Output: Counter({'apples': 7, 'oranges': 3})  

# namedtuple - Self-documenting data structures  
from collections import namedtuple  
Employee = namedtuple('Employee', 'name role salary')  
dev = Employee('Alex', 'Developer', 95000)  
print(dev.role)           # Output: Developer  
print(dev[2])             # Output: 95000  

# deque - Optimal for BFS and sliding windows  
from collections import deque  
queue = deque([1, 2, 3])  
queue.append(4)  
queue.popleft()  
print(queue)              # Output: deque([2, 3, 4])  
queue.rotate(1)  
print(queue)              # Output: deque([4, 2, 3])  

# OrderedDict - Track insertion order (LRU cache essential)  
from collections import OrderedDict  
cache = OrderedDict()  
cache['A'] = 1  
cache['B'] = 2  
cache.move_to_end('A')  
cache.popitem(last=False)  
print(list(cache.keys())) # Output: ['B', 'A']  

# ChainMap - Manage layered configurations  
from collections import ChainMap  
defaults = {'theme': 'dark', 'font': 'Arial'}  
user_prefs = {'theme': 'light'}  
settings = ChainMap(user_prefs, defaults)  
print(settings['font'])   # Output: Arial  

# Practical Interview Tip: Anagram detection  
print(Counter("secure") == Counter("rescue"))  # Output: True  

# Pro Tip: Sliding window maximum  
def max_sliding_window(nums, k):  
    dq, result = deque(), []  
    for i, n in enumerate(nums):  
        while dq and nums[dq[-1]] < n:  
            dq.pop()  
        dq.append(i)  
        if dq[0] == i - k:  
            dq.popleft()  
        if i >= k - 1:  
            result.append(nums[dq[0]])  
    return result  
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # Output: [3,3,5,5,6,7]  

# Expert Move: Custom LRU Cache implementation  
class LRUCache:  
    def __init__(self, capacity):  
        self.cache = OrderedDict()  
        self.capacity = capacity  
    def get(self, key):  
        if key not in self.cache:  
            return -1  
        self.cache.move_to_end(key)  
        return self.cache[key]  
    def put(self, key, value):  
        if key in self.cache:  
            del self.cache[key]  
        self.cache[key] = value  
        if len(self.cache) > self.capacity:  
            self.cache.popitem(last=False)  
cache = LRUCache(2)  
cache.put(1, 10)  
cache.put(2, 20)  
cache.get(1)  
cache.put(3, 30)  
print(list(cache.cache.keys()))  # Output: [2, 1, 3] → Wait! Correction: Should be [1, 3] (capacity=2 triggers eviction of '2')  

# Bonus: Multiset operations with Counter  
primes = Counter([2, 3, 5, 7])  
odds = Counter([1, 3, 5, 7, 9])  
print(primes | odds)  # Output: Counter({3:1, 5:1, 7:1, 2:1, 9:1, 1:1})  

By: @DatascienceN🌟

#Python #CodingInterview #DataStructures #collections #Programming #TechJobs #Algorithm #LeetCode #DeveloperTips #CareerGrowth

# Django ORM Comparison - Know both frameworks
# Django model (contrast with SQLAlchemy)
from django.db import models

class Department(models.Model):
    name = models.CharField(max_length=50)

class Employee(models.Model):
    name = models.CharField(max_length=100)
    email = models.EmailField(unique=True)
    department = models.ForeignKey(Department, on_delete=models.CASCADE)

# Django query (similar but different syntax)
Employee.objects.filter(department__name="HR").select_related('department')

# Async ORM - Modern Python requirement
# Requires SQLAlchemy 1.4+ and asyncpg
from sqlalchemy.ext.asyncio import create_async_engine, AsyncSession

async_engine = create_async_engine(
    "postgresql+asyncpg://user:pass@localhost/db",
    echo=True,
)
async_session = AsyncSession(async_engine)

async with async_session.begin():
    result = await async_session.execute(
        select(Employee).where(Employee.name == "Alice")
    )
    employee = result.scalar_one()

# Testing Strategies - Interview differentiator
from unittest import mock

# Mock database for unit tests
with mock.patch('sqlalchemy.create_engine') as mock_engine:
    mock_conn = mock.MagicMock()
    mock_engine.return_value.connect.return_value = mock_conn
    
    # Test your ORM-dependent code
    create_employee("Test", "[email protected]")
    mock_conn.execute.assert_called()

# Production Monitoring - Track slow queries
from sqlalchemy import event

@event.listens_for(engine, "before_cursor_execute")
def before_cursor(conn, cursor, statement, params, context, executemany):
    conn.info.setdefault('query_start_time', []).append(time.time())

@event.listens_for(engine, "after_cursor_execute")
def after_cursor(conn, cursor, statement, params, context, executemany):
    total = time.time() - conn.info['query_start_time'].pop(-1)
    if total > 0.1:  # Log slow queries
        print(f"SLOW QUERY ({total:.2f}s): {statement}")

# Interview Power Move: Implement caching layer
from functools import lru_cache

class CachedEmployeeRepository(EmployeeRepository):
    @lru_cache(maxsize=100)
    def get_by_id(self, employee_id):
        return super().get_by_id(employee_id)
    
    def invalidate_cache(self, employee_id):
        self.get_by_id.cache_clear()

# Reduces database hits by 70% in read-heavy applications

# Pro Tip: Schema versioning in CI/CD pipelines
# Sample .gitlab-ci.yml snippet
deploy_db:
  stage: deploy
  script:
    - alembic upgrade head
    - pytest tests/db_tests.py  # Verify schema compatibility
  only:
    - main

# Real-World Case Study: E-commerce inventory system
class Product(Base):
    __tablename__ = 'products'
    id = Column(Integer, primary_key=True)
    sku = Column(String(20), unique=True)
    stock = Column(Integer, default=0)
    
    # Atomic stock update (prevents race conditions)
    def decrement_stock(self, quantity, session):
        result = session.query(Product).filter(
            Product.id == self.id,
            Product.stock >= quantity
        ).update({"stock": Product.stock - quantity})
        if not result:
            raise ValueError("Insufficient stock")

# Usage during checkout
product.decrement_stock(2, session)

By: @DATASCIENCE4 🔒

#Python #ORM #SQLAlchemy #Django #Database #BackendDevelopment #CodingInterview #WebDevelopment #TechJobs #SystemDesign #SoftwareEngineering #DataEngineering #CareerGrowth #APIs #Microservices #DatabaseDesign #TechTips #DeveloperTools #Programming #CareerTips

# Interview Power Move: Parallel Merging
from concurrent.futures import ThreadPoolExecutor
from PyPDF2 import PdfMerger

def parallel_merge(pdf_list, output, max_workers=4):
    chunks = [pdf_list[i::max_workers] for i in range(max_workers)]
    temp_files = []
    
    def merge_chunk(chunk, idx):
        temp = f"temp_{idx}.pdf"
        merger = PdfMerger()
        for pdf in chunk:
            merger.append(pdf)
        merger.write(temp)
        return temp
    
    with ThreadPoolExecutor() as executor:
        temp_files = list(executor.map(merge_chunk, chunks, range(max_workers)))
    
    # Final merge of chunks
    final_merger = PdfMerger()
    for temp in temp_files:
        final_merger.append(temp)
    final_merger.write(output)

parallel_merge(["doc1.pdf", "doc2.pdf", ...], "parallel_merge.pdf")

# Pro Tip: Validate PDFs before merging
from PyPDF2 import PdfReader

def is_valid_pdf(path):
    try:
        with open(path, "rb") as f:
            reader = PdfReader(f)
            return len(reader.pages) > 0
    except:
        return False

valid_pdfs = [f for f in pdf_files if is_valid_pdf(f)]
merger.append(valid_pdfs)  # Only merge valid files

# Real-World Case Study: Invoice Processing Pipeline
import glob
from PyPDF2 import PdfMerger

def process_monthly_invoices():
    # 1. Download invoices from SFTP
    download_invoices("sftp://vendor.com/invoices/*.pdf")
    
    # 2. Validate and sort
    invoices = sorted(
        [f for f in glob.glob("invoices/*.pdf") if is_valid_pdf(f)],
        key=lambda x: extract_invoice_date(x)
    )
    
    # 3. Merge with cover page
    merger = PdfMerger()
    merger.append("cover_template.pdf")
    for inv in invoices:
        merger.append(inv, outline_item=get_client_name(inv))
    
    # 4. Add metadata and encrypt
    merger.add_metadata({"/InvoiceCount": str(len(invoices))})
    merger.encrypt(owner_pwd="finance_team_2023")
    merger.write(f"Q3_Invoices_{datetime.now().strftime('%Y%m')}.pdf")
    
    # 5. Upload to secure storage
    upload_to_s3("secure-bucket/processed/", "Q3_Invoices.pdf")

process_monthly_invoices()

By: https://t.iss.one/DataScience4

#Python #PDFProcessing #DocumentAutomation #PyPDF2 #CodingInterview #BackendDevelopment #FileHandling #DataEngineering #TechJobs #Programming #SystemDesign #DeveloperTips #CareerGrowth #CloudComputing #Docker #Microservices #Productivity #TechTips #Python3 #SoftwareEngineering

Top 100 Python Interview Questions & Answers

#Python #InterviewQuestions #CodingInterview #Programming #PythonDeveloper

Part 1: Core Python Fundamentals (Q1-20)

#1. Is Python a compiled or an interpreted language?
A: Python is an interpreted language. The Python interpreter reads and executes the source code line by line, without requiring a separate compilation step. This makes development faster but can result in slower execution compared to compiled languages like C++.

#2. What is the GIL (Global Interpreter Lock)?
A: The GIL is a mutex (a lock) that allows only one thread to execute Python bytecode at a time within a single process. This means even on a multi-core processor, a single Python process cannot run threads in parallel. It simplifies memory management but is a performance bottleneck for CPU-bound multithreaded programs.

#3. What is the difference between Python 2 and Python 3?
A: Key differences include:
• print: In Python 2, print is a statement (print "hello"). In Python 3, it's a function (print("hello")).
• Integer Division: In Python 2, 5 / 2 results in 2 (floor division). In Python 3, it results in 2.5 (true division).
• Unicode: In Python 3, strings are Unicode (UTF-8) by default. In Python 2, you had to explicitly use u"unicode string".

#4. What are mutable and immutable data types in Python?
A:
• Mutable: Objects whose state or contents can be changed after creation. Examples: list, dict, set.
• Immutable: Objects whose state cannot be changed after creation. Examples: int, float, str, tuple, frozenset.

# Mutable example
my_list = [1, 2, 3]
my_list[0] = 99
print(my_list)

[99, 2, 3]

#5. How is memory managed in Python?
A: Python uses a private heap to manage memory. A built-in garbage collector automatically reclaims memory from objects that are no longer in use. The primary mechanism is reference counting, where each object tracks the number of references to it. When the count drops to zero, the object is deallocated.

#6. What is the difference between is and ==?
A:
• == (Equality): Checks if the values of two operands are equal.
• is (Identity): Checks if two variables point to the exact same object in memory.

list_a = [1, 2, 3]
list_b = [1, 2, 3]
list_c = list_a

print(list_a == list_b)  # True, values are the same
print(list_a is list_b)  # False, different objects in memory
print(list_a is list_c)  # True, same object in memory

True
False
True

#7. What is PEP 8?
A: PEP 8 (Python Enhancement Proposal 8) is the official style guide for Python code. It provides conventions for writing readable and consistent Python code, covering aspects like naming conventions, code layout, and comments.

#8. What is the difference between a .py and a .pyc file?
A:
• .py: This is the source code file you write.
• .pyc: This is the compiled bytecode. When you run a Python script, the interpreter compiles it into bytecode (a lower-level, platform-independent representation) and saves it as a .pyc file to speed up subsequent executions.

#9. What are namespaces in Python?
A: A namespace is a system that ensures all names in a program are unique and can be used without conflict. It's a mapping from names to objects. Python has different namespaces: built-in, global, and local.

# Check if `n > 0` and `(n & (n - 1)) == 0`.

• Pow(x, n): Implement pow(x, n).

# Use exponentiation by squaring for an O(log n) solution.

• Majority Element:

# Boyer-Moore Voting Algorithm for an O(n) time, O(1) space solution.

• Excel Sheet Column Number:

# Base-26 conversion from string to integer.

• Valid Number:

# Use a state machine or a series of careful conditional checks.

• Integer to English Words:

# Handle numbers in chunks of three (hundreds, tens, ones) with helper functions.

• Sqrt(x): Compute and return the square root of x.

# Use binary search or Newton's method.

• Gray Code:

# Formula: `i ^ (i >> 1)`.

• Shuffle an Array:

# Implement the Fisher-Yates shuffle algorithm.

IX. Python Concepts

• Explain the GIL (Global Interpreter Lock):

# Conceptual: A mutex that allows only one thread to execute Python bytecode at a time in CPython.

• Difference between __str__ and __repr__:

# __str__ is for end-users (readable), __repr__ is for developers (unambiguous).

• Implement a Context Manager (with statement):

class MyContext:
    def __enter__(self): # setup
        return self
    def __exit__(self, exc_type, exc_val, exc_tb): # teardown
        pass

• Implement itertools.groupby logic:

# Iterate through the sorted iterable, collecting items into a sublist until the key changes.

#Python #CodingInterview #DataStructures #Algorithms #SystemDesign

━━━━━━━━━━━━━━━
By: @DataScience4 ✨

❔ Interview Question

What is the potential pitfall of using a mutable object (like a list or dictionary) as a default argument in a Python function?

Answer: A common pitfall is that the default argument is evaluated only once, when the function is defined, not each time it is called. If that default object is mutable, any modifications made to it in one call will persist and be visible in subsequent calls.

This can lead to unexpected and buggy behavior.

Incorrect Example (The Pitfall):

def add_to_list(item, my_list=[]):
    my_list.append(item)
    return my_list

# First call seems to work fine
print(add_to_list(1))  # Output: [1]

# Second call has unexpected behavior
print(add_to_list(2))  # Output: [1, 2] -- The list from the first call was reused!

# Third call continues the trend
print(add_to_list(3))  # Output: [1, 2, 3]

The Correct, Idiomatic Solution:

The standard practice is to use None as the default and create a new mutable object inside the function if one isn't provided.

def add_to_list_safe(item, my_list=None):
    if my_list is None:
        my_list = []  # Create a new list for each call
    my_list.append(item)
    return my_list

# Each call now works independently
print(add_to_list_safe(1))  # Output: [1]
print(add_to_list_safe(2))  # Output: [2]
print(add_to_list_safe(3))  # Output: [3]

tags: #Python #Interview #CodingInterview #PythonTips #Developer #SoftwareEngineering #TechInterview

━━━━━━━━━━━━━━━
By: @DataScience4 ✨