Skip to content

Instantly share code, notes, and snippets.

@ganadist

ganadist/ch1.ipynb

Created August 4, 2018 11:49
Show Gist options
  • Save ganadist/d3782265f44a4523b9b3a6f38c595d32 to your computer and use it in GitHub Desktop.
Save ganadist/d3782265f44a4523b9b3a6f38c595d32 to your computer and use it in GitHub Desktop.
Download ZIP
ch1.ipynb
Display the source blob
Display the rendered blob
Raw
ch1.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "ch1.ipynb",
"version": "0.3.2",
"provenance": [],
"collapsed_sections": [],
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"[View in Colaboratory](https://colab.research.google.com/gist/ganadist/d3782265f44a4523b9b3a6f38c595d32/ch1.ipynb)"
]
},
{
"metadata": {
"id": "XhvmG2hO7Xtj",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 87
},
"outputId": "02a0dd97-912a-48a9-c010-cee418843085"
},
"cell_type": "code",
"source": [
"# 1.1\n",
"def find_duplicate(string, ch):\n",
" assert len(ch) == 1\n",
" count = 0\n",
" for ch1 in string:\n",
" if ch1 == ch:\n",
" count += 1\n",
" if count > 1:\n",
" return True\n",
" return False\n",
"\n",
"print(find_duplicate(\"abc\", \"a\"))\n",
"print(find_duplicate(\"abc\", \"d\"))\n",
"print(find_duplicate(\"aabc\", \"a\"))\n",
"print(find_duplicate(\"abca\", \"a\"))\n",
" "
],
"execution_count": 8,
"outputs": [
{
"output_type": "stream",
"text": [
"False\n",
"False\n",
"True\n",
"True\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "mMcOl_3V8tUX",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 52
},
"outputId": "4b74eccd-2b6b-4eff-c0dd-8e6f34cb9e0c"
},
"cell_type": "code",
"source": [
"# 1.2\n",
"def is_permutation(str1, str2):\n",
" if len(str1) != len(str2):\n",
" return False\n",
" \n",
" def count_character(str):\n",
" counter = [0, ] * 255 # ascii range\n",
" for ch in str:\n",
" counter[ord(ch)] += 1\n",
" return counter\n",
" \n",
" counter1 = count_character(str1)\n",
" counter2 = count_character(str2)\n",
" return counter1 == counter2\n",
"\n",
"print(is_permutation('abcd', 'dbac'))\n",
"print(is_permutation('abcd', 'dbab'))\n",
" "
],
"execution_count": 10,
"outputs": [
{
"output_type": "stream",
"text": [
"True\n",
"False\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "-Gdxcay6_HY3",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "130de2cc-148f-42bc-8a36-629de70a98fd"
},
"cell_type": "code",
"source": [
"# 1.3\n",
"def encode_url(url, urllen):\n",
" assert type(url) is list\n",
" length = len(url)\n",
" diff = length - urllen\n",
" for i in range(length - 1, length - urllen -1, -1):\n",
" url[i] = url[i - diff]\n",
" \n",
" index = 0\n",
" for ch in url[diff:]:\n",
" if ch == ' ':\n",
" url[index] = '%'\n",
" url[index+1] = '2'\n",
" url[index+2] = '0'\n",
" index += 3\n",
" else:\n",
" url[index] = ch\n",
" index += 1\n",
"\n",
"def create_url(url):\n",
" l = list(url)\n",
" from collections import Counter\n",
" l += [' '] * Counter(l)[' '] * 2\n",
" return l, len(url)\n",
"\n",
"url, length = create_url('Mr John Smith')\n",
"encode_url(url, length)\n",
"print(url)"
],
"execution_count": 18,
"outputs": [
{
"output_type": "stream",
"text": [
"['M', 'r', '%', '2', '0', 'J', 'o', 'h', 'n', '%', '2', '0', 'S', 'm', 'i', 't', 'h']\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "YhQD_qpuGlrN",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "1aa0603c-770e-4841-e198-6e04b9b5be7e"
},
"cell_type": "code",
"source": [
"# 1.4\n",
"ORD_A = ord('a')\n",
"ORD_Z = ord('z')\n",
"def is_palindrome(str):\n",
" def count_character(str):\n",
" counter = [0, ] * 26 # alphabet only\n",
" length = 0\n",
" for ch in str:\n",
" if ORD_A <= ord(ch) <= ORD_Z:\n",
" counter[ord(ch) - ORD_A] += 1\n",
" length += 1\n",
" return counter, length\n",
" counter, length = count_character(str.lower())\n",
" maxodd = 1 if length%2 else 0\n",
" oddcount = 0\n",
"\n",
" for c in counter:\n",
" if c % 2: oddcount += 1\n",
" if oddcount > maxodd: return False\n",
" return True\n",
"\n",
"print(is_palindrome('tact coa'))"
],
"execution_count": 37,
"outputs": [
{
"output_type": "stream",
"text": [
"True\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "tDrS606nKUY8",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 87
},
"outputId": "0d28d7ba-0702-43e3-f487-131a6afde8ae"
},
"cell_type": "code",
"source": [
"# 1.5\n",
"def equal_with_one_edit(str1, str2):\n",
" if len(str1) == len(str2):\n",
" for i, (ch1, ch2) in enumerate(zip(str1, str2)):\n",
" if (ch1 != ch2):\n",
" return str1[i + 1:] == str2[i + 1:]\n",
" else:\n",
" if len(str1) > len(str2):\n",
" str_large, str_small = str1, str2\n",
" else:\n",
" str_large, str_small = str2, str1\n",
" \n",
" for i, (ch1, ch2) in enumerate(zip(str_large, str_small)):\n",
" if (ch1 != ch2):\n",
" return str1[i + 1:] == str2[i:]\n",
" return True\n",
"\n",
"print(equal_with_one_edit('pale', 'ple'))\n",
"print(equal_with_one_edit('pales', 'pale'))\n",
"print(equal_with_one_edit('pale', 'bale'))\n",
"print(equal_with_one_edit('pale', 'bake'))"
],
"execution_count": 31,
"outputs": [
{
"output_type": "stream",
"text": [
"True\n",
"True\n",
"True\n",
"False\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "KvT3xgtoMy9D",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "deeb5a7f-8d4b-4be2-8ead-162e94778275"
},
"cell_type": "code",
"source": [
"# 1.6\n",
"def encode_runlength(str):\n",
" out = ''\n",
" count = 1\n",
" old = str[0]\n",
" for ch in str[1:]:\n",
" if ch == old: count += 1\n",
" else:\n",
" out += old + '%d'%count\n",
" count = 1\n",
" old = ch\n",
" return out + old + '%d'%count\n",
"\n",
"print(encode_runlength('aabccccaaa'))"
],
"execution_count": 36,
"outputs": [
{
"output_type": "stream",
"text": [
"a2b1c4a3\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "4uvKXj_BN7pL",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 122
},
"outputId": "34abeb7f-51f3-4466-a819-8ffc320bfb22"
},
"cell_type": "code",
"source": [
"# 1.7\n",
"def rotate_matrix(mat):\n",
" length = len(mat)\n",
" for row in mat:\n",
" assert length == len(row)\n",
" \n",
" length -= 1\n",
" for y in range(length//2):\n",
" for x in range(y, length - y):\n",
" v = mat[y][x]\n",
" mat[y][x] = mat[length - x][y]\n",
" mat[length - x][y] = mat[length - y][length - x]\n",
" mat[length - y][length - x] = mat[x][length - y]\n",
" mat[x][length - y] = v\n",
" \n",
"mat = [[0, 0, 0, 0, 1], [0, 0, 0, 0, 1], [0, 0, 0, 0, 1], [0, 0, 0, 0, 1], [0, 0, 0, 0, 1]]\n",
"for i in range(3):\n",
" rotate_matrix(mat)\n",
" print(mat)\n",
"mat = [[1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]\n",
"for i in range(3):\n",
" rotate_matrix(mat)\n",
" print(mat)\n"
],
"execution_count": 34,
"outputs": [
{
"output_type": "stream",
"text": [
"[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [1, 1, 1, 1, 1]]\n",
"[[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]\n",
"[[1, 1, 1, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]\n",
"[[0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 1]]\n",
"[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 1, 1]]\n",
"[[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]\n"
],
"name": "stdout"
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment