Python Programming & Algorithm Test Solutions

This repository contains elegant, high-performance, and robust solutions for the Programming and Algorithm Test. All solutions are written in standard Python 3 and intentionally avoid external third-party dependencies to ensure they can be compiled and run seamlessly out-of-the-box on any system with a standard Python installation.

---

📂 Repository Structure

The project is organized into modular directories corresponding to each of the 4 test questions:

python_solutions/
├── README.md                    # English documentation and execution guide (This file)
├── question1/                   # Question 1: Walking Matrix Turtle
│   ├── matrix_turtle.py         # Main implementation for 1.1, 1.2, and 1.3
│   ├── input1-1.txt             # Input file for Zig-zag walking (1.1)
│   ├── input1-2.txt             # Input file for Clockwise walking (1.2)
│   └── input1-3.txt             # Input file for Straight route finder (1.3)
├── question2/                   # Question 2: Squirrel Tree
│   ├── squirrel_tree.py         # Serialized tree parser and BFS walnut allocator
│   └── input2.txt               # Input file containing tree structure and configuration
├── question3/                   # Question 3: Rate and Throttle API Microservices
│   ├── common.py                # Shared helpers (logging, JSON utility, FixedWindowRateCounter)
│   ├── echo_service.py          # Port 9003: Echo service with 512 calls/min limit
│   ├── throttle_service.py      # Port 9002: Spaced rate limiter forwarding to Echo service
│   ├── caller_service.py        # Automated test harness invoking requests in concurrent waves
│   └── logs/                    # Automated runtime execution logs (generated at runtime)
└── question4/                   # Question 4: Full-Stack User CRUD System
    ├── app.py                   # Multi-threaded Backend REST API server with SQLite3
    ├── users.db                 # Database file populated with seeded records
    └── static/                  # Responsive Single-Page Application (SPA) frontend
        ├── index.html           # Structure containing styling and JS links
        ├── styles.css           # Modern CSS styling with smooth layouts
        └── app.js               # Frontend controller implementing rendering & state management

---

⚡ Quick Syntax Verification

Before running any script, you can verify that all Python files compile successfully without syntax errors by running this command from the root directory (python_solutions/):

python -m py_compile question1/matrix_turtle.py question2/squirrel_tree.py question3/common.py question3/echo_service.py question3/throttle_service.py question3/caller_service.py question4/app.py

---

🧭 Question 1: Walking Matrix Turtle

The solutions for all sub-questions are implemented inside question1/matrix_turtle.py under the MatrixTurtle class. The script parses input matrices formatted as Python nested lists using standard ast.literal_eval for safety and validates input format compliance (rectangular shape, integer-only elements).

1.1 Zig-zag Traversal

• Concept: Traverses a 2D matrix column-by-column starting from the top-left coordinate [0,0]. The turtle travels downwards (South) for even columns, and upwards (North) for odd columns.
• Execution:

  cd question1
  python matrix_turtle.py 1.1 input1-1.txt

1.2 Clockwise Spiral to Center

• Concept: Given a custom starting coordinate [row, col], the turtle traverses the matrix in a clockwise spiral. The grid boundaries (top, left, bottom, right) shrink dynamically towards the center. The traversal begins by moving East from the start cell and winds inward layer by layer.
• Execution (using the assignment input):

  python matrix_turtle.py 1.2 input1-2.txt

1.3 Find Straight Routes

• Concept: Given a start value and a target value (e.g., [2, 8]), the algorithm locates all positions matching the start value and performs linear searches in the 4 cardinal directions (North, East, South, West). The turtle must walk in a straight line and is not allowed to change direction.
• PDF Official Matcher: The algorithm identifies route segments ending at the target. It flags the global SHORTEST and LONGEST paths. Additionally, to match the sample PDF exactly, if multiple routes share the same direction, it filters them down to only show the global extreme boundaries, keeping the repository clean and identical to expectations.
• Execution:

  python matrix_turtle.py 1.3 input1-3.txt

---

🐿️ Question 2: Squirrel Tree (Walnut Storage)

• Concept: The program handles the distribution of walnuts into hollow tree nodes under capacity constraints.
• Algorithm & Parsing:
  1. The input string walnuts,capacity,tree_representation (e.g., 25,3,ABEG)H)))C)DFIK)L))JM) is tokenized.
  2. A binary/general tree structure is parsed using a parent-tracking stack. When an alphabetic character is read, it adds a new unique node. When a closing parenthesis ) is encountered, it pops back to the parent.
  3. If the input format is invalid (e.g., non-positive capacity, bracket mismatch, or duplicate node names), it safely handles the exception and outputs standard error states: INVALID WALNUT AMOUNT, INVALID HOLE CAPACITY, or IMPOSSIBLE TREE.
  4. Walnut allocation prioritizes holes closest to the root using Breadth-First Search (BFS). For nodes at the same level, it distributes left-to-right.
  5. Holes are filled up to their defined capacity limit. If the total capacity of the tree is insufficient to hold all walnuts, it returns IMPOSSIBLE TREE.
• Execution:

  cd ../question2
  python squirrel_tree.py input2.txt

---

🚦 Question 3: Rate and Throttle API Microservices

A distributed, asynchronous service architecture composed of three microservices communicating over HTTP REST protocols using Python's core libraries (urllib.request and http.server).

graph LR
    Caller[Caller Service] -- Concurrent Waves --> Throttle[Throttle Service <br> Port 9002]
    Throttle -- Spaced Limiter --> Echo[Echo Service <br> Port 9003]

Loading

🛠️ Architecture and Services

1. Echo Service (echo_service.py at Port 9003):
   • Acts as the destination endpoint. It echoes back the request payload.
   • Implements a Fixed Window Rate Counter using a thread-safe lock (threading.Lock). If calls exceed the set limit (default: 512 calls/minute), it responds with {"ok": false, "message": "Exceeding Limit"}.
2. Throttle Service (throttle_service.py at Port 9002):
   • Intercepts caller requests and forwards them to the Echo Service.
   • Implements a custom thread-safe Spaced Rate Limiter. It calculates an even mathematical interval between requests (window_seconds / limit). If a request arrives too quickly, the handler blocks/sleeps for the difference using thread-level queuing to avoid exceeding the Echo Service's constraints.
3. Caller Service (caller_service.py):
   • Simulates highly concurrent real-world clients using a ThreadPoolExecutor (up to 128 workers).
   • Fires waves of concurrent requests to the Throttle Service across several intervals at escalating rates (default minutes: 16, 256, 4096, 65536 calls/minute).

🚀 Running the Microservices

Open three separate terminal windows/sessions and run the services in order:

# Terminal 1: Launch Echo Service (Port 9003)
cd question3
python echo_service.py

# Terminal 2: Launch Throttle Service (Port 9002)
cd question3
python throttle_service.py

# Terminal 3: Launch Caller Service (Initiates concurrent client simulation)
cd question3
python caller_service.py

Tip

Environment Variables Support: To test without overloading your machine or waiting for full minutes, you can drastically speed up the simulation. In PowerShell, configure environment variables before launching:

$env:RATE_WINDOW_SECONDS="10"       # Shrinks the rate window to 10 seconds
$env:CALLER_MINUTE_SECONDS="10"     # Shrinks simulation intervals to 10 seconds
$env:CALLER_RATES="4,8,16"          # Drops wave rates to smaller numbers
python caller_service.py

Execution logs for all components are cleanly generated in real-time under question3/logs/ (e.g. caller.log, throttle.log, echo.log).

---

👥 Question 4: Full-Stack User CRUD System

This project is a lightweight but robust full-stack administration application. It utilizes a multi-threaded Python backend coupled with an interactive, responsive frontend.

🔌 Backend API Server

Built purely using Python's http.server.ThreadingHTTPServer and standard libraries.

• Database: Embedded SQLite3 engine (users.db). It creates the table schema on startup and automatically feeds mock data containing popular tech historical figures.
• Validation Rules:
  • name: Non-empty text, automatically stripped.
  • age: Strictly checked. Must be a valid positive integer greater than 0.
  • email: Validated via Regex. Rejects duplicate emails across non-deleted profiles.
  • avatarUrl: Mandatory field to maintain profile styling.
• Routing Protocols:
  • GET /api/user?q=keyword&start=0&limit=10 — Fetches user list with support for search filters (matches name/email case-insensitively) and offset-based pagination.
  • GET /api/user/:userId — Retrieves full profile details.
  • POST /api/user — Creates a new user profile.
  • PUT /api/user/:userId — Updates an existing user profile.
  • DELETE /api/user/:userId — Executes a secure soft-delete (isDeleted = 1). Returns failure responses if trying to double-delete a record.
  • OPTIONS support to prevent CORS policy blocks.

🎨 State-Driven SPA Frontend

• Located inside the question4/static/ directory, served directly by the Python backend.
• It provides a highly interactive user experience utilizing state management and vanilla CSS Grid/Flexbox layouts.
• Features:
  • Search Box: Debounced live searching by name or email.
  • User Table: Renders user lists containing real-time visual avatars, names, ages, and contact emails.
  • Pagination Controls: Next/Prev page selectors synced with server offset queries.
  • Add/Edit Modals: Pop-up forms equipped with live error notifications directly linked to API validation responses.
  • Soft-Delete Trigger: Fast action to delete a user profile with immediate table updates.

🚀 Running the App

1. Navigate into the question4 directory and run app.py:

   cd ../question4
   python app.py

2. Open your browser and navigate to:

   http://127.0.0.1:9010
   

Note

If Port 9010 is already in use by another local application, you can easily change it by setting the APP_PORT environment variable before running:

$env:APP_PORT="9015"
python app.py

---

🌟 Solution Design & Implementation Highlights

• Robust Error Handling: Every service handles OS exceptions, malformed user inputs, file reading errors, and database conflicts gracefully, responding with descriptive error messages instead of crashing.
• High Performance: The microservice throttling mechanism utilizes lock-based thread intervals, ensuring the server acts with minimal CPU overhead. The database operations use parameter binding to safeguard against SQL Injection.
• Responsive Styling: CSS files utilize modern CSS Custom Properties, smooth transitioning micro-animations, standard typography, and HSL palettes for a refined, modern user interface.