Answers Notebook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 1\n",
    "\n",
    "Given two strings `s` and `t`, determine whether some anagram of `t` is a substring\n",
    "of `s`. For example: if `s = \"udacity\"` and `t = \"ad\"`, then the function returns\n",
    "True. Your function definition should look like: `question1(s, t)` and return a\n",
    "boolean `True` or `False`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('udacity', 'ad') -> True\n",
      "('udacity', 'da') -> True\n",
      "('udacity', 'au') -> False\n",
      "('udacity', 'ciy') -> False\n",
      "('udacity', 'xyz') -> False\n",
      "('udacity', '') -> True\n",
      "('udacity', '12863742302323232746') -> False\n",
      "('ad', 'udacity') -> False\n",
      "('panama', '1pana') -> False\n",
      "('banana', 'anana') -> True\n"
     ]
    }
   ],
   "source": [
    "# Turn on/off to enable/disable debugging\n",
    "debug = False\n",
    "\n",
    "\n",
    "def is_anagram(s, t):\n",
    "    \"\"\"\n",
    "    # Find if strings are anagram. t anagram of s\n",
    "    # @param {string, string} input strings\n",
    "    # @return bool if strings are anagram of each other or not\n",
    "    \"\"\"\n",
    "    s = list(s)\n",
    "    # Sort a string and then compare with each other\n",
    "    s.sort()   # Quick sort O(n*log(n))\n",
    "    return s == t\n",
    "\n",
    "\n",
    "def question1(s,t):\n",
    "    \"\"\"\n",
    "    # Find out sorted(possible substring of s) and compare with sorted(t)\n",
    "    # @param main_string, ana_string input strings\n",
    "    # @return bool Question1 answer\n",
    "    \"\"\"\n",
    "    global debug\n",
    "    sort_t = list(t)\n",
    "    sort_t.sort()     # Quick sort O(n*log(n))\n",
    "\n",
    "    for i in range(len(s) - len(t) + 1):\n",
    "        if debug:\n",
    "            print (s[i: i+len(t)], t)\n",
    "        if is_anagram(s[i: i+len(t)], sort_t):\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "# Main program\n",
    "def main():\n",
    "    unit_tests = [(\"udacity\", \"ad\"),\n",
    "                 (\"udacity\", \"da\"),\n",
    "                 (\"udacity\", \"au\"),\n",
    "                 (\"udacity\", \"ciy\"),\n",
    "                 (\"udacity\", \"xyz\"),\n",
    "                 (\"udacity\", \"\"),\n",
    "                 (\"udacity\", \"12863742302323232746\"),\n",
    "                 (\"ad\", \"udacity\" ),\n",
    "                 (\"panama\", \"1pana\"),\n",
    "                 (\"banana\", \"anana\")]\n",
    "\n",
    "    for test in unit_tests:\n",
    "        print(\"{} -> {}\".format(test,question1(test[0],test[1])))\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Answer\n",
    "\n",
    "So the code was chosen to be the most optimal for the problem in hands. It has complexity of O(Nlogm) since it only iterates through the entry string once. There are two sort functions applied, once to the string t, which if it is large, will take some time, this has complexity O(NlogN). But in most cases string t will be short and not cause much problems. Also, there is a need for a second sort function on the substring from main string. This will have the same length as the string t, so sorting can take some time. This sort will also occur several times throughout the routine. Se if S is length 8 and t is length 2, this sort will occur 4 times total.\n",
    "\n",
    "Sort will occur on string t with complexity O(mlogm), m being the length of string t.\n",
    "Sort will occur on substring of S with complexity O(nlogm), n being length of string S.\n",
    "\n",
    "Given the test cases bellow:\n",
    "\n",
    "* Case 1: (\"udacity\", \"ad\") -> True\n",
    "string with 2 characters reversed from order in S\n",
    "\n",
    "*  Case 2: (\"udacity\", \"da\") -> True\n",
    "string with 2 characters same as in order in S\n",
    "\n",
    "*  Case 3: (\"udacity\", \"au\") -> False\n",
    "string with 2 alternative characters and reversed from order in S\n",
    "\n",
    "*  Case 4: (\"udacity, dacity\") -> True\n",
    "string with 6 characters same as in order in S\n",
    "\n",
    "*  Case 5: (\"udacity\", \"ciy\") -> False\n",
    "string with 2 characters same as in order in S and 1 character out of order.\n",
    "\n",
    "*  Case 6: (\"udacity\", \"xyz\") -> False\n",
    "string with new characters not in string S.\n",
    "\n",
    "* Case 7: (\"udacity\", \"\") -> True\n",
    "empty string.\n",
    "\n",
    "*  Case 8: (\"ad\", \"udacity\" ) -> False\n",
    "string t's length is greater than string S.\n",
    "\n",
    "*  Case 9: (\"panama\", \"1pana\" ) -> False\n",
    "string t's contains a number before.\n",
    "\n",
    "*  Case 10: (\"banana\", \"anana\" ) -> False\n",
    "string t's is an anagram of string S\n",
    "\n",
    "All tests are passed as it can be seen above.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 2\n",
    "Given a string a, find the longest palindromic substring contained in a.\n",
    "Your function definition should look like `question2(a)`, and return a string.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abuttuba -> abuttuba\n",
      "acaramanamaraca -> acaramanamaraca\n",
      "adogapanicinapagoda -> adogapanicinapagoda\n",
      "anutforajaroftuna -> anutforajaroftuna\n",
      "asantaatnasa -> asantaatnasa\n",
      "amoreroma -> amoreroma\n",
      "ABCBACADCBBCDA -> ADCBBCDA\n",
      "iriwmairanariairie -> airanaria\n",
      "anaannaanne -> naannaan\n",
      " -> \n",
      "1234432 -> 234432\n"
     ]
    }
   ],
   "source": [
    "debug = False\n",
    "\n",
    "def isPalindrome(string):\n",
    "    \"\"\"\n",
    "    # @param string s input string\n",
    "    # @return bool if string is palindrome or not\n",
    "    \"\"\"\n",
    "    if not string:\n",
    "        return False\n",
    "    # reverse compare\n",
    "    return string == string[::-1]\n",
    "\n",
    "\n",
    "def question2(string):\n",
    "    \"\"\"\n",
    "    # @param string s input string\n",
    "    # @return string the longest palindromic substring\n",
    "    \"\"\"\n",
    "    global debug\n",
    "    \n",
    "    if not string: # if null entry\n",
    "        return \"\"\n",
    "\n",
    "    n = len(string)\n",
    "    longest, left, right = 0, 0, 0\n",
    "    for i in range(0, n):\n",
    "        for j in range(i + 1, n + 1):\n",
    "            substr = string[i:j] # going through all substrings possible\n",
    "            \n",
    "            \n",
    "            if isPalindrome(substr) and len(substr) > longest: # see if it is palindrome and is longer than the one before\n",
    "                longest = len(substr)\n",
    "                left, right = i, j\n",
    "    # construct longest substr\n",
    "    result = string[left:right]\n",
    "    return result\n",
    "\n",
    "# Main program\n",
    "def main():\n",
    "    unit_tests = [\"abuttuba\",\n",
    "                 \"acaramanamaraca\",\n",
    "                 \"adogapanicinapagoda\",\n",
    "                 \"anutforajaroftuna\",\n",
    "                 \"asantaatnasa\",\n",
    "                 \"amoreroma\",\n",
    "                 \"ABCBACADCBBCDA\",\n",
    "                 \"iriwmairanariairie\",\n",
    "                 \"anaannaanne\",\n",
    "                 \"\",\n",
    "                 \"1234432\"]\n",
    "\n",
    "\n",
    "\n",
    "    for test in unit_tests:\n",
    "        print(\"{} -> {}\".format(test,question2(test)))\n",
    "\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Answer\n",
    "The complexity of the algorithm above will be O(N^2 / 2) because there is a nested loop and necessarily we have to iterate through all the string everytime. This is the simplest form I found to to make this routine work on the spot, it is still functional and easy to understand. The choice for nested loops was due to be the most logical solution to look within a string for substrings that are palindromes. Since every 2 letter combination can be a palindrome, all possible combinations of letters within the string will have to be tested. For example, the string abcba will have the following breakdown:\n",
    "\n",
    "* Iteration: 0 -> a\n",
    "* Iteration: 1 -> ab\n",
    "* Iteration: 1 -> ab\n",
    "* Iteration: 2 -> abc\n",
    "* Iteration: 3 -> abcb\n",
    "* Iteration: 4 -> abcba\n",
    "* Iteration: 5 -> b\n",
    "* Iteration: 6 -> bc\n",
    "* Iteration: 7 -> bcb\n",
    "* Iteration: 8 -> bcba\n",
    "* Iteration: 9 -> c\n",
    "* Iteration: 10 -> cb\n",
    "* Iteration: 11 -> cba\n",
    "* Iteration: 12 -> b\n",
    "* Iteration: 13 -> ba\n",
    "* Iteration: 14 -> a\n",
    "\n",
    "Basically, the Complexity of the Algorithm will be exactly O(1/2*N*(N+1)) where N is the length of the String. This is better than O(N^2) by almost 50%.\n",
    "Given the test cases bellow:\n",
    "\n",
    "* Case 1: A But Tuba\n",
    "* Case 2: A car, a man, a maraca\n",
    "* Case 3: A dog! A panic in a pagoda\n",
    "* Case 4: A nut for a jar of tuna\n",
    "* Case 5: A Santa at Nasa.\n",
    "* Case 6: Amore, Roma.\n",
    "* Case 7: ABCBAC ADCBBCDA\n",
    "* Case 8: iriwm airanaria irie\n",
    "* Case 9: a naannaan ne\n",
    "* Case 10: null entry\n",
    "* Case 11: 1 234432 \n",
    "\n",
    "All tests are passed as it can be seen above.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 3\n",
    "\n",
    "Given an undirected graph G, find the minimum spanning tree within G. A minimum spanning tree connects all vertices in a graph with the smallest possible total weight of edges. Your function should take in and return an adjacency list structured like this:\n",
    "\n",
    "```python\n",
    "{'A': [('B', 2)],\n",
    " 'B': [('A', 2), ('C', 5)], \n",
    " 'C': [('B', 5)]}\n",
    "\n",
    "```\n",
    "\n",
    "\n",
    "Vertices are represented as unique strings. The function definition should be `question3(G)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'A': [('B', 2)], 'B': [('C', 5)]}\n"
     ]
    }
   ],
   "source": [
    "# Python Program for union-find algorithm to detect cycle in a undirected graph\n",
    "from collections import defaultdict\n",
    "debug = False\n",
    "\n",
    "#This class represents a undirected graph using adjacency list representation\n",
    "class Graph:\n",
    "    def __init__(self,vertices):\n",
    "        self.V= vertices #No. of vertices\n",
    "        self.graph = defaultdict(list) # default dictionary to store graph\n",
    "    # function to add an edge to graph\n",
    "    def addEdge(self,u,v):\n",
    "        self.graph[u].append(v)\n",
    "    # function to remove edge from Graph\n",
    "    def removeEdge(self,u,v):\n",
    "        del self.graph[u][-1]\n",
    "\n",
    "    # A utility function to find the subset of an element i\n",
    "    def find_parent(self, parent,i):\n",
    "        if parent[i] == -1:\n",
    "            return i\n",
    "        if parent[i]!= -1:\n",
    "             return self.find_parent(parent,parent[i])\n",
    "\n",
    "    # A utility function to do union of two subsets\n",
    "    def union(self,parent,x,y):\n",
    "        x_set = self.find_parent(parent, x)\n",
    "        y_set = self.find_parent(parent, y)\n",
    "        parent[x_set] = y_set\n",
    "\n",
    "    # The main function to check whether a given graph\n",
    "    # contains cycle or not\n",
    "    def isCyclic(self):\n",
    "        # Allocate memory for creating V subsets and\n",
    "        # Initialize all subsets as single element sets\n",
    "        parent = [-1]*(self.V)\n",
    "        # Iterate through all edges of graph, find subset of both\n",
    "        # vertices of every edge, if both subsets are same, then\n",
    "        # there is cycle in graph.\n",
    "        for i in self.graph:\n",
    "            for j in self.graph[i]:\n",
    "                x = self.find_parent(parent, i)\n",
    "                y = self.find_parent(parent, j)\n",
    "                if x == y:\n",
    "                    return True\n",
    "                self.union(parent,x,y)\n",
    "\n",
    "    def node_hash(self, keys):\n",
    "        # Function to transform graphs where Nodes are Chars instead of Ints\n",
    "        self.str_hash = {}\n",
    "        node = 0\n",
    "        for key in keys:\n",
    "            # if the key is a string and its still not in ditct\n",
    "            if str(key) == key and self.str_hash.get(key, 'No Key') == 'No Key':\n",
    "                self.str_hash[key] = node\n",
    "                node += 1;\n",
    "            elif int(key) == key: # if key is a Int\n",
    "                self.str_hash[key] = key\n",
    "\n",
    "\n",
    "    def reverse_hash(self, value):\n",
    "        # Function to obtain key name from value in dict\n",
    "        for key in self.str_hash:\n",
    "            if self.str_hash[key] == value:\n",
    "                return key\n",
    "\n",
    "    def adjacency_list(self):\n",
    "        # Creates Adjacent List to present results\n",
    "        self.adj_list = defaultdict(list)\n",
    "        for min_edge in self.mst:\n",
    "            self.adj_list[min_edge[0]].append((min_edge[1],min_edge[2]))\n",
    "\n",
    "\n",
    "    def KruskalMST(self):\n",
    "    # Kruskal’s Minimum Spanning Tree Algorithm\n",
    "        self.mst = [] # Minimum Spanning Tree\n",
    "        for w,s,d in zip(self.weight,self.src,self.dest):\n",
    "            self.addEdge(s,d) # Add a new edge to graph\n",
    "            if self.isCyclic(): # If edge added makes a cycle, reject\n",
    "                self.removeEdge(s,d)\n",
    "                if debug: print(\"Graph contains cycle\")\n",
    "            else : # if no cycle, add edge to minimum spanning tree\n",
    "                self.mst.append([self.reverse_hash(s), self.reverse_hash(d), w])\n",
    "                if debug: print (\"Graph does not contain cycle \")\n",
    "        return(self.adjacency_list())\n",
    "\n",
    "    def order_edges(self, graph_adj_list):\n",
    "        # Initiate Variables\n",
    "        self.src, self.dest, self.weight = [],[],[]\n",
    "        for key, content in graph_adj_list.items():\n",
    "            for entry in content:\n",
    "                self.src.append(self.str_hash[key])\n",
    "                self.dest.append(self.str_hash[entry[0]])\n",
    "                self.weight.append(entry[1])\n",
    "        # return weight, src, dest sorted by edge weight\n",
    "        self.weight, self.src, self.dest  = zip(*sorted(zip(self.weight, self.src, self.dest)))\n",
    "\n",
    "\n",
    "def question3(G):\n",
    "    g = Graph(len(G)) # Create a graph with given adjacency list\n",
    "    g.node_hash(G.keys()) # Hash node names, in case they are strigs\n",
    "    g.order_edges(G) # Order all edges by weight, ascending order\n",
    "    g.KruskalMST() # Run Kruska Greedy Algorith\n",
    "    return dict(g.adj_list) # Put together final adjacency List with MST\n",
    "\n",
    "\n",
    "def main():\n",
    "    G1 = {0: [(1,4),(7,8)],\n",
    "        1: [(2,8),(7,11)],\n",
    "        2: [(3,7),(8,2),(5,4)],\n",
    "        3: [(4,9),(5,14)],\n",
    "        4: [(5,10)],\n",
    "        5: [(6,2)],\n",
    "        6: [(8,6),(7,1)],\n",
    "        7: [(8,7)],\n",
    "        8: []}\n",
    "    G = {'A': [('B', 2)],\n",
    "          'B': [('A', 2), ('C', 5)],\n",
    "          'C': [('B', 5)]}\n",
    "\n",
    "    print(question3(G))\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Answer\n",
    "This was the hardest coding question in this set. Returning the Minimun Spanning Tree (MST) given the graph in the form of a Adjency List (AL). I created the `class Graph` to handle all instances realted to a Graph. If we look at the function `question3(G)` we see the order of operations I chose to perform.\n",
    "\n",
    "`g = Graph(len(G))` First I create a object type Graph, which received the length of G the input. This will be the number of nodes in our Graph.\n",
    "\n",
    "`g.node_hash(G.keys())` I create this function to handle some complication I had while coding this solution. I needed the nodes to be integers, but the question is handed nodes with `Chars` *A,B,C...* I decided to hash them, so A will be 0, B will 1 for instance. Then I solve the problem and in the end I return my solution in the original form. This is, if it was given Char Nodes they will be returned as such, if they were given integers, then that will be the outcome. \n",
    "\n",
    "`g.order_edges(G)` This function will order all edges in ascending weight. This is done so we run the Greedy Algorithm, *Kruskal*\n",
    "\n",
    "`g.KruskalMST()` After all edges are ordered, a for loop will go through each, connection the graph, making sure each edge addition does not form a cycle within the graph. Once all Nodes are connected, the function will return the outcome.\n",
    "\n",
    "`g.adj_list` Return a dictionary, same format as it was input with the MST.\n",
    "\n",
    "This algorithm has the complexity of *O(E log V)* where E are number of edges and V number of Nodes or Vertices. We apply sorting on all Edges and then we loop throgh all of them.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 4\n",
    "\n",
    "Find the least common ancestor between two nodes on a binary search tree. The least common ancestor is the farthest node from the root that is an ancestor of both nodes. For example, the root is a common ancestor of all nodes on the tree, but if both nodes are descendents of the root's left child, then that left child might be the lowest common ancestor. You can assume that both nodes are in the tree, and the tree itself adheres to all BST properties. The function definition should look like question4(T, r, n1, n2), where T is the tree represented as a matrix, where the index of the list is equal to the integer stored in that node and a 1 represents a child node, r is a non-negative integer representing the root, and n1 and n2 are non-negative integers representing the two nodes in no particular order. For example, one test case might be\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class BST(object):\n",
    "    def __init__(self, root):\n",
    "        self.root = Node(root)\n",
    "\n",
    "    def insert(self, new_val):\n",
    "        self.insert_helper(self.root, new_val)\n",
    "\n",
    "    def insert_helper(self, current, new_val):\n",
    "        if current.value < new_val: # Push sub-node to right\n",
    "            if current.right:\n",
    "                self.insert_helper(current.right, new_val)\n",
    "            else:\n",
    "                current.right = Node(new_val)\n",
    "        else: # Push sub-node to left\n",
    "            if current.left:\n",
    "                self.insert_helper(current.left, new_val)\n",
    "            else:\n",
    "                current.left = Node(new_val)\n",
    "\n",
    "    def search(self, find_val):\n",
    "        return self.search_helper(self.root, find_val)\n",
    "\n",
    "    def search_helper(self, current, find_val):\n",
    "        if current:\n",
    "            if current.value == find_val:\n",
    "                return True\n",
    "            elif current.value < find_val:\n",
    "                return self.search_helper(current.right, find_val)\n",
    "            else:\n",
    "                return self.search_helper(current.left, find_val)\n",
    "        return False\n",
    "\n",
    "    def makeBST(self, matrix):\n",
    "        for i, subnode in enumerate(matrix[self.root.value]): # Start at root row\n",
    "            if subnode !=0: # if subnode is a child, insert it.\n",
    "                self.insert(i)\n",
    "\n",
    "        for i,node in enumerate(matrix):\n",
    "            for j,child in enumerate(node):\n",
    "                if child != 0 and i != self.root.value:\n",
    "                    self.insert(j)\n",
    "                    #print(\"Node {} has child {}\".format(i,j))\n",
    "\n",
    "    def lca(self, head_node, n1, n2):\n",
    "        # Base Case\n",
    "        if head_node is None:\n",
    "            return None\n",
    "\n",
    "        # # If both n1 and n2 are smaller than root, then LCA\n",
    "        # # lies in left\n",
    "        if(head_node.value > n1 and head_node.value > n2):\n",
    "            return self.lca(head_node.left, n1, n2)\n",
    "\n",
    "        # If both n1 and n2 are greater than root, then LCA\n",
    "        # lies in right\n",
    "        if(head_node.value < n1 and head_node.value < n2):\n",
    "            return self.lca(head_node.right, n1, n2)\n",
    "\n",
    "        return head_node.value\n",
    "\n",
    "\n",
    "\n",
    "def question4(matrix, root, n1, n2):\n",
    "    head = BST(root)\n",
    "    head.makeBST(matrix)\n",
    "    return head.lca(head.root,n1, n2)\n",
    "\n",
    "# Main program\n",
    "def main():\n",
    "    print(question4([[0, 1, 0, 0, 0],\n",
    "                     [0, 0, 0, 0, 0],\n",
    "                     [0, 0, 0, 0, 0],\n",
    "                     [1, 0, 0, 0, 1],\n",
    "                     [0, 0, 0, 0, 0]],\n",
    "                     3, 1, 4))\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Answer\n",
    "Given a Binary Search Tree represented in Matrix form, determining the Least Common Ancestral (LCA) takes a lot of code for what it seems to be a very simple task. Although, the `class BST(object):` has a couple extra functions not needed for this answer, but I included them for the sake of completness. I chose to create two classes, `node` and `BST`. The Node class will just include the vlue of the Node and if It has a subnode to the Right or Left. If this it he casem subnode will be class *Node*. \n",
    "\n",
    "`BST` has function to create the Tree, adding nodes accordingly to the input Matrix. This include the function `lca` which will return the Least Common Ancestral, which is the value of the Node that is common to both *n1* and *n2*. This Algorithm takes advantage of the way binary search trees are buit. Where all subnode values larger to the node are pushed to the right and smaller to the left. This makes it very easy to search for values within the tree, making the search time of linear complexity.\n",
    "\n",
    "Given n1 and n2, it is easy to see if the root node above is the LCA or not. If n1 is larger than root and n2 smaller, this means the root has to be the LCA. Other cases will be if n1 and n2 are both smaller or large, then we can advance on step deeper on the tree, and make a new root with the node at that step. This cycle will continue until n1 is larger than root, and n2 smaller or vice-versa.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 5\n",
    "\n",
    "Find the element in a singly linked list that's m elements from the end. For example, if a linked list has 5 elements, the 3rd element from the end is the 3rd element. The function definition should look like question5(ll, m), where ll is the first node of a linked list and m is the \"mth number from the end\". You should copy/paste the Node class below to use as a representation of a node in the linked list. Return the value of the node at that position.\n",
    "\n",
    "```Python\n",
    "class Node(object):\n",
    "  def __init__(self, data):\n",
    "    self.data = data\n",
    "    self.next = None\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "class Node(object):\n",
    "\tdef __init__(self, data):\n",
    "\t\tself.data = data\n",
    "\t\tself.next = None\n",
    "\n",
    "\n",
    "\n",
    "def question5(ll, m):\n",
    "\t# Setting up initial values - head of linked list\n",
    "\tp1 = ll\n",
    "\tp2 = ll\n",
    "\n",
    "\t# This cycle sets p1 m positions in front of p2\n",
    "\tfor i in range(0, m):\n",
    "\t\tif (p1 == None):\n",
    "\t\t\treturn None\n",
    "\t\tp1 = p1.next\n",
    "\t# This while loop will run until p1 get to the last element of list\n",
    "\t# at the time p2 will be m positions behin\n",
    "\t# p2 value is returned, since that with be the mth element\n",
    "\t# in the linked list\n",
    "\twhile (p1 != None):\n",
    "\t\tp1 = p1.next\n",
    "\t\tp2 = p2.next\n",
    "\treturn p2.data\n",
    "\n",
    "\n",
    "A = Node(2)\n",
    "B = Node(3)\n",
    "C = Node(8)\n",
    "D = Node(1)\n",
    "E = Node(6)\n",
    "\n",
    "A.next = B\n",
    "B.next = C\n",
    "C.next = D\n",
    "D.next = E\n",
    "\n",
    "print(question5(A, 3))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Answer\n",
    "\n",
    "Given a linked list, find the value of the element mth positions from the end of list. The problem with this situation is that on a linked list, we do not know the total length of the list to start with. Linked lists are basically a vlue with  pointer to the next value. So we do not know all values on the list, just the next one, given any value. This is done to save time and memory space. In comparison, if we just store  whole list, we can always aaccess the mth element from the end using `list[-mth]` making this exercise rather trivial. \n",
    "\n",
    "The algorithm for this problem is rather simple. `Class Node(obect)` basically creates a node of the list with a pointer to the next element on the list, if there is one. So creating a linked list such as:\n",
    "```python\n",
    "A = Node(2)\n",
    "B = Node(3)\n",
    "C = Node(8)\n",
    "D = Node(1)\n",
    "E = Node(6)\n",
    "\n",
    "A.next = B\n",
    "B.next = C\n",
    "C.next = D\n",
    "D.next = E\n",
    "```\n",
    "\n",
    "Where basically we create node `A` with value `2` and pointing to next Node `B` with value `3`. So fouth and so on, until the whole Linked List (LL) is created.\n",
    "\n",
    "Th algorithm basically operates within two loops. First one, `for i in range(0, m):`, will place `p1`, basically a pointer, `m` positions ahead of `p2`, which points to the first node. Then we have `while (p1 != None):` which will cycle through the whole linked list, until it hits the last element, where `p1.next` is none. At that point, `p2`, will be `m` positions lagging behind `p1`, or better saying, `mth` nodes from the end of list. The value of the `mth` node is then returned.\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}