Code_Craft_SparseArray.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNG+k5F+n+Bx5QUMsLeaA6S",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/walkerjian/DailyCode/blob/main/Code_Craft_SparseArray.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Problem:\n",
        "You have a large array with most of the elements as zero.\n",
        "\n",
        "Use a more space-efficient data structure, SparseArray, that implements the same interface:\n",
        "\n",
        "init(arr, size): initialize with the original large array and size.\n",
        "set(i, val): updates index at i with val.\n",
        "get(i): gets the value at index i."
      ],
      "metadata": {
        "id": "StVA5pgVPCne"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Solution:\n",
        "To implement a space-efficient `SparseArray`, we can use a dictionary (or a similar associative array structure) to store only the non-zero elements of the array. The key idea is to store only the elements that are different from the default value (zero in this case), significantly reducing memory usage when the array contains a large number of zeros.\n",
        "\n",
        "Here's how we can implement the `SparseArray` class in Python:\n",
        "\n",
        "1. **Initialization (`init`)**: Store the size of the array and create an empty dictionary to hold the non-zero elements.\n",
        "\n",
        "2. **Set (`set`)**: Update the dictionary with the new value if it's non-zero. If the value is zero, remove the key from the dictionary if it exists.\n",
        "\n",
        "3. **Get (`get`)**: Return the value from the dictionary if the key exists; otherwise, return zero.\n",
        "\n"
      ],
      "metadata": {
        "id": "1kl0DnwrPGU6"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Implementation:\n",
        "Here's the implementation:\n",
        "\n"
      ],
      "metadata": {
        "id": "TQ4dosfCPIIi"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "v7kdhgsfPBk_"
      },
      "outputs": [],
      "source": [
        "class SparseArray:\n",
        "    def __init__(self, arr, size):\n",
        "        self.size = size\n",
        "        self.data = {}\n",
        "        for i, val in enumerate(arr):\n",
        "            if val != 0:\n",
        "                self.data[i] = val\n",
        "\n",
        "    def set(self, i, val):\n",
        "        if i >= self.size:\n",
        "            raise IndexError(\"Index out of bounds\")\n",
        "        if val != 0:\n",
        "            self.data[i] = val\n",
        "        elif i in self.data:\n",
        "            del self.data[i]\n",
        "\n",
        "    def get(self, i):\n",
        "        if i >= self.size:\n",
        "            raise IndexError(\"Index out of bounds\")\n",
        "        return self.data.get(i, 0)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "This class efficiently handles large arrays with many zero elements. The `set` and `get` methods operate in O(1) time complexity on average, as they utilize the dictionary's hash table implementation. The space complexity is O(k), where k is the number of non-zero elements, which is much more efficient than O(n) for a traditional array when k << n."
      ],
      "metadata": {
        "id": "hVvXDNi6PSZ6"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Testing:\n",
        "To create a test harness for the `SparseArray` class, we'll write a series of tests that demonstrate its functionality and correctness. These tests will include:\n",
        "\n",
        "1. **Initialization Test**: Create a `SparseArray` with a predefined array and verify its size and contents.\n",
        "2. **Set and Get Tests**: Test the `set` and `get` methods to ensure they correctly update and retrieve values.\n",
        "3. **Boundary Conditions**: Test how the `SparseArray` handles edge cases, like setting and getting values at invalid indices.\n",
        "4. **Efficiency Test**: Demonstrate the space efficiency of `SparseArray` compared to a regular array, especially with a large number of zeros.\n",
        "\n",
        "Here's the Python code for the test harness:\n",
        "\n",
        "This test harness comprehensively evaluates the `SparseArray` class's functionality and efficiency. Each test is designed to confirm different aspects of the class's behavior, ensuring it works as expected under various conditions."
      ],
      "metadata": {
        "id": "oweeNj4RPrhe"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def test_sparse_array():\n",
        "    print(\"Testing SparseArray...\")\n",
        "\n",
        "    # Test 1: Initialization\n",
        "    original_array = [0, 0, 5, 0, 0, 0, 3, 0, 0]\n",
        "    sparse_array = SparseArray(original_array, len(original_array))\n",
        "    assert len(sparse_array.data) == 2  # Only two non-zero elements\n",
        "    print(\"Test 1 passed: Initialization\")\n",
        "\n",
        "    # Test 2: Set and Get\n",
        "    sparse_array.set(2, 0)  # Set existing non-zero element to zero\n",
        "    sparse_array.set(4, 7)  # Set new non-zero element\n",
        "    assert sparse_array.get(2) == 0\n",
        "    assert sparse_array.get(4) == 7\n",
        "    print(\"Test 2 passed: Set and Get\")\n",
        "\n",
        "    # Test 3: Boundary Conditions\n",
        "    try:\n",
        "        sparse_array.set(100, 1)\n",
        "    except IndexError:\n",
        "        print(\"Test 3 passed: Set with invalid index\")\n",
        "\n",
        "    try:\n",
        "        sparse_array.get(100)\n",
        "    except IndexError:\n",
        "        print(\"Test 3 passed: Get with invalid index\")\n",
        "\n",
        "    # Test 4: Efficiency\n",
        "    large_array = [0] * 1000000\n",
        "    large_array[123456] = 1\n",
        "    sparse_large_array = SparseArray(large_array, len(large_array))\n",
        "    assert len(sparse_large_array.data) == 1\n",
        "    print(\"Test 4 passed: Efficiency\")\n",
        "\n",
        "    print(\"All tests passed!\")\n",
        "\n",
        "test_sparse_array()\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TV1YOJYiPVkA",
        "outputId": "32c2b6e8-9d92-4c6b-f339-e7b0ea014d6c"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Testing SparseArray...\n",
            "Test 1 passed: Initialization\n",
            "Test 2 passed: Set and Get\n",
            "Test 3 passed: Set with invalid index\n",
            "Test 3 passed: Get with invalid index\n",
            "Test 4 passed: Efficiency\n",
            "All tests passed!\n"
          ]
        }
      ]
    }
  ]
}