about summary refs log tree commit diff
path: root/scratch/deepmind/part_two
diff options
context:
space:
mode:
Diffstat (limited to 'scratch/deepmind/part_two')
-rw-r--r--scratch/deepmind/part_two/.envrc2
-rw-r--r--scratch/deepmind/part_two/delete-node.py57
-rw-r--r--scratch/deepmind/part_two/misc/matrix-traversals.py104
-rw-r--r--scratch/deepmind/part_two/package-lock.json73
-rw-r--r--scratch/deepmind/part_two/package.json15
-rw-r--r--scratch/deepmind/part_two/reverse-string-in-place.ts13
-rw-r--r--scratch/deepmind/part_two/shell.nix10
-rw-r--r--scratch/deepmind/part_two/todo.org77
8 files changed, 351 insertions, 0 deletions
diff --git a/scratch/deepmind/part_two/.envrc b/scratch/deepmind/part_two/.envrc
new file mode 100644
index 000000000000..b80e28b4b815
--- /dev/null
+++ b/scratch/deepmind/part_two/.envrc
@@ -0,0 +1,2 @@
+source_up
+eval "$(lorri direnv)"
diff --git a/scratch/deepmind/part_two/delete-node.py b/scratch/deepmind/part_two/delete-node.py
new file mode 100644
index 000000000000..4ed02ec30832
--- /dev/null
+++ b/scratch/deepmind/part_two/delete-node.py
@@ -0,0 +1,57 @@
+import unittest
+
+
+def delete_node(node):
+    if node.next:
+        node.value = node.next.value
+        node.next = node.next.next
+    else:
+        raise Exception(
+            "We cannot delete the last node in a linked list using this function"
+        )
+
+
+# Tests
+class Test(unittest.TestCase):
+    class LinkedListNode(object):
+        def __init__(self, value, next=None):
+            self.value = value
+            self.next = next
+
+        def get_values(self):
+            node = self
+            values = []
+            while node is not None:
+                values.append(node.value)
+                node = node.next
+            return values
+
+    def setUp(self):
+        self.fourth = Test.LinkedListNode(4)
+        self.third = Test.LinkedListNode(3, self.fourth)
+        self.second = Test.LinkedListNode(2, self.third)
+        self.first = Test.LinkedListNode(1, self.second)
+
+    def test_node_at_beginning(self):
+        delete_node(self.first)
+        actual = self.first.get_values()
+        expected = [2, 3, 4]
+        self.assertEqual(actual, expected)
+
+    def test_node_in_middle(self):
+        delete_node(self.second)
+        actual = self.first.get_values()
+        expected = [1, 3, 4]
+        self.assertEqual(actual, expected)
+
+    def test_node_at_end(self):
+        with self.assertRaises(Exception):
+            delete_node(self.fourth)
+
+    def test_one_node_in_list(self):
+        unique = Test.LinkedListNode(1)
+        with self.assertRaises(Exception):
+            delete_node(unique)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/deepmind/part_two/misc/matrix-traversals.py b/scratch/deepmind/part_two/misc/matrix-traversals.py
new file mode 100644
index 000000000000..52354f990e11
--- /dev/null
+++ b/scratch/deepmind/part_two/misc/matrix-traversals.py
@@ -0,0 +1,104 @@
+# Herein I'm practicing two-dimensional matrix traversals in all directions of
+# which I can conceive:
+# 0. T -> B; L -> R
+# 1. T -> B; R -> L
+# 2. B -> T; L -> R
+# 3. B -> T; R -> L
+#
+# Commentary:
+# When I think of matrices, I'm reminded of cartesian planes. I think of the
+# cells as (X,Y) coordinates. This has been a pitfall for me because matrices
+# are usually encoded in the opposite way. That is, to access a cell at the
+# coordinates (X,Y) given a matrix M, you index M like this: M[Y][X]. To attempt
+# to avoid this confusion, instead of saying X and Y, I will prefer saying
+# "column" and "row".
+#
+# When traversing a matrix, you typically traverse vertically and then
+# horizontally; in other words, the rows come first followed by the columns. As
+# such, I'd like to refer to traversal orders as "top-to-bottom, left-to-right"
+# rather than "left-to-right, top-to-bottom".
+#
+# These practices are all in an attempt to rewire my thinking.
+
+# This is a list of matrices where the index of a matrix corresponds to the
+# order in which it should be traversed to produce the sequence:
+# [1,2,3,4,5,6,7,8,9].
+boards = [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[3, 2, 1], [6, 5, 4], [9, 8, 7]],
+          [[7, 8, 9], [4, 5, 6], [1, 2, 3]], [[9, 8, 7], [6, 5, 4], [3, 2, 1]]]
+
+# T -> B; L -> R
+board = boards[0]
+result = []
+for row in board:
+    for col in row:
+        result.append(col)
+print(result)
+
+# T -> B; R -> L
+board = boards[1]
+result = []
+for row in board:
+    for col in reversed(row):
+        result.append(col)
+print(result)
+
+# B -> T; L -> R
+board = boards[2]
+result = []
+for row in reversed(board):
+    for col in row:
+        result.append(col)
+print(result)
+
+# B -> T; R -> L
+board = boards[3]
+result = []
+for row in reversed(board):
+    for col in reversed(row):
+        result.append(col)
+print(result)
+
+################################################################################
+# Neighbors
+################################################################################
+
+import random
+
+
+# Generate a matrix of size `rows` x `cols` where each cell contains an item
+# randomly selected from `xs`.
+def generate_board(rows, cols, xs):
+    result = []
+    for _ in range(rows):
+        row = []
+        for _ in range(cols):
+            row.append(random.choice(xs))
+        result.append(row)
+    return result
+
+
+# Print the `board` to the screen.
+def print_board(board):
+    print('\n'.join([' '.join(row) for row in board]))
+
+
+board = generate_board(4, 5, ['R', 'G', 'B'])
+print_board(board)
+
+
+# Return all of the cells horizontally and vertically accessible from a starting
+# cell at `row`, `col` in `board`.
+def neighbors(row, col, board):
+    result = {'top': [], 'bottom': [], 'left': [], 'right': []}
+    for i in range(row - 1, -1, -1):
+        result['top'].append(board[i][col])
+    for i in range(row + 1, len(board)):
+        result['bottom'].append(board[i][col])
+    for i in range(col - 1, -1, -1):
+        result['left'].append(board[row][i])
+    for i in range(col + 1, len(board[0])):
+        result['right'].append(board[row][i])
+    return result
+
+
+print(neighbors(1, 2, board))
diff --git a/scratch/deepmind/part_two/package-lock.json b/scratch/deepmind/part_two/package-lock.json
new file mode 100644
index 000000000000..94c89c5979c4
--- /dev/null
+++ b/scratch/deepmind/part_two/package-lock.json
@@ -0,0 +1,73 @@
+{
+  "name": "deepmind-part-two",
+  "version": "1.0.0",
+  "lockfileVersion": 1,
+  "requires": true,
+  "dependencies": {
+    "arg": {
+      "version": "4.1.3",
+      "resolved": "https://registry.npmjs.org/arg/-/arg-4.1.3.tgz",
+      "integrity": "sha512-58S9QDqG0Xx27YwPSt9fJxivjYl432YCwfDMfZ+71RAqUrZef7LrKQZ3LHLOwCS4FLNBplP533Zx895SeOCHvA==",
+      "dev": true
+    },
+    "buffer-from": {
+      "version": "1.1.1",
+      "resolved": "https://registry.npmjs.org/buffer-from/-/buffer-from-1.1.1.tgz",
+      "integrity": "sha512-MQcXEUbCKtEo7bhqEs6560Hyd4XaovZlO/k9V3hjVUF/zwW7KBVdSK4gIt/bzwS9MbR5qob+F5jusZsb0YQK2A==",
+      "dev": true
+    },
+    "diff": {
+      "version": "4.0.2",
+      "resolved": "https://registry.npmjs.org/diff/-/diff-4.0.2.tgz",
+      "integrity": "sha512-58lmxKSA4BNyLz+HHMUzlOEpg09FV+ev6ZMe3vJihgdxzgcwZ8VoEEPmALCZG9LmqfVoNMMKpttIYTVG6uDY7A==",
+      "dev": true
+    },
+    "make-error": {
+      "version": "1.3.5",
+      "resolved": "https://registry.npmjs.org/make-error/-/make-error-1.3.5.tgz",
+      "integrity": "sha512-c3sIjNUow0+8swNwVpqoH4YCShKNFkMaw6oH1mNS2haDZQqkeZFlHS3dhoeEbKKmJB4vXpJucU6oH75aDYeE9g==",
+      "dev": true
+    },
+    "source-map": {
+      "version": "0.6.1",
+      "resolved": "https://registry.npmjs.org/source-map/-/source-map-0.6.1.tgz",
+      "integrity": "sha512-UjgapumWlbMhkBgzT7Ykc5YXUT46F0iKu8SGXq0bcwP5dz/h0Plj6enJqjz1Zbq2l5WaqYnrVbwWOWMyF3F47g==",
+      "dev": true
+    },
+    "source-map-support": {
+      "version": "0.5.16",
+      "resolved": "https://registry.npmjs.org/source-map-support/-/source-map-support-0.5.16.tgz",
+      "integrity": "sha512-efyLRJDr68D9hBBNIPWFjhpFzURh+KJykQwvMyW5UiZzYwoF6l4YMMDIJJEyFWxWCqfyxLzz6tSfUFR+kXXsVQ==",
+      "dev": true,
+      "requires": {
+        "buffer-from": "^1.0.0",
+        "source-map": "^0.6.0"
+      }
+    },
+    "ts-node": {
+      "version": "8.6.2",
+      "resolved": "https://registry.npmjs.org/ts-node/-/ts-node-8.6.2.tgz",
+      "integrity": "sha512-4mZEbofxGqLL2RImpe3zMJukvEvcO1XP8bj8ozBPySdCUXEcU5cIRwR0aM3R+VoZq7iXc8N86NC0FspGRqP4gg==",
+      "dev": true,
+      "requires": {
+        "arg": "^4.1.0",
+        "diff": "^4.0.1",
+        "make-error": "^1.1.1",
+        "source-map-support": "^0.5.6",
+        "yn": "3.1.1"
+      }
+    },
+    "typescript": {
+      "version": "3.7.5",
+      "resolved": "https://registry.npmjs.org/typescript/-/typescript-3.7.5.tgz",
+      "integrity": "sha512-/P5lkRXkWHNAbcJIiHPfRoKqyd7bsyCma1hZNUGfn20qm64T6ZBlrzprymeu918H+mB/0rIg2gGK/BXkhhYgBw==",
+      "dev": true
+    },
+    "yn": {
+      "version": "3.1.1",
+      "resolved": "https://registry.npmjs.org/yn/-/yn-3.1.1.tgz",
+      "integrity": "sha512-Ux4ygGWsu2c7isFWe8Yu1YluJmqVhxqK2cLXNQA5AcC3QfbGNpM7fu0Y8b/z16pXLnFxZYvWhd3fhBY9DLmC6Q==",
+      "dev": true
+    }
+  }
+}
diff --git a/scratch/deepmind/part_two/package.json b/scratch/deepmind/part_two/package.json
new file mode 100644
index 000000000000..c9ef307ca0ee
--- /dev/null
+++ b/scratch/deepmind/part_two/package.json
@@ -0,0 +1,15 @@
+{
+  "name": "deepmind-part-two",
+  "version": "1.0.0",
+  "description": "Practicing coding interview questions",
+  "main": "index.js",
+  "scripts": {
+    "test": "echo \"Error: no test specified\" && exit 1"
+  },
+  "author": "William Carroll",
+  "license": "MIT",
+  "devDependencies": {
+    "ts-node": "^8.6.2",
+    "typescript": "^3.7.5"
+  }
+}
diff --git a/scratch/deepmind/part_two/reverse-string-in-place.ts b/scratch/deepmind/part_two/reverse-string-in-place.ts
new file mode 100644
index 000000000000..d714dfef997f
--- /dev/null
+++ b/scratch/deepmind/part_two/reverse-string-in-place.ts
@@ -0,0 +1,13 @@
+// Reverse array of characters, `xs`, mutatively.
+function reverse(xs: Array<string>) {
+  let i: number = 0;
+  let j: number = xs.length - 1;
+
+  while (i < j) {
+    let tmp = xs[i];
+    xs[i] = xs[j]
+    xs[j] = tmp
+    i += 1
+    j -= 1
+  }
+}
diff --git a/scratch/deepmind/part_two/shell.nix b/scratch/deepmind/part_two/shell.nix
new file mode 100644
index 000000000000..606dd7167f7c
--- /dev/null
+++ b/scratch/deepmind/part_two/shell.nix
@@ -0,0 +1,10 @@
+{ pkgs ? import <nixpkgs> {}, ... }:
+
+pkgs.mkShell {
+  buildInputs = with pkgs; [
+    nodejs
+    python3
+    go
+    goimports
+  ];
+}
diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org
new file mode 100644
index 000000000000..510073e6e2cd
--- /dev/null
+++ b/scratch/deepmind/part_two/todo.org
@@ -0,0 +1,77 @@
+* Array and string manipulation
+** TODO Merging Meeting Times
+** DONE Reverse String in Place
+** TODO Reverse Words
+** TODO Merge Sorted Arrays
+** TODO Cafe Order Checker
+* Hashing and hash tables
+** TODO Inflight Entertainment
+** TODO Permutation Palindrome
+** TODO Word Cloud Data
+** TODO Top Scores
+* Greedy Algorithms
+** TODO Apple Stocks
+** TODO Highest Product of 3
+** TODO Product of All Other Numbers
+** TODO Cafe Order Checker
+** TODO In-Place Shuffle
+* Sorting, searching, and logarithms
+** TODO Find Rotation Point
+** TODO Find Repeat, Space Edition
+** TODO Top Scores
+** TODO Merging Meeting Times
+* Trees and graphs
+** TODO Balanced Binary Tree
+** TODO Binary Search Tree Checker
+** TODO 2nd Largest Item in a Binary Search Tree
+** TODO Graph Coloring
+** TODO MeshMessage
+** TODO Find Repeat, Space Edition BEAST MODE
+* Dynamic programming and recursion
+** TODO Recursive String Permutations
+** TODO Compute nth Fibonacci Number
+** TODO Making Change
+** TODO The Cake Thief
+** TODO Balanced Binary Tree
+** TODO Binary Search Tree Checker
+** TODO 2nd Largest Item in a Binary Search Tree
+* Queues and stacks
+** TODO Largest Stack
+** TODO Implement A Queue With Two Stacks
+** TODO Parenthesis Matching
+** TODO Bracket Validator
+* Linked lists
+** DONE Delete Node
+** TODO Does This Linked List Have A Cycle?
+** TODO Reverse A Linked List
+** TODO Kth to Last Node in a Singly-Linked List
+** TODO Find Repeat, Space Edition BEAST MODE
+* System design
+** TODO URL Shortener
+** TODO MillionGazillion
+** TODO Find Duplicate Files
+* General programming
+** TODO Rectangular Love
+** TODO Temperature Tracker
+* Bit manipulation
+** TODO Binary Numbers
+** TODO The Stolen Breakfast Drone
+* Combinatorics, probability, and other math
+** TODO Which Appears Twice
+** TODO Find in Ordered Set
+** TODO In-Place Shuffle
+** TODO Simulate 5-sided die
+** TODO Simulate 7-sided die
+** TODO Two Egg Problem
+* JavaScript
+** TODO JavaScript Scope
+** TODO What&#39;s Wrong with This JavaScript?
+* Coding interview tips
+** TODO How The Coding Interview Works
+** TODO General Coding Interview Advice
+** TODO Impostor Syndrome
+** TODO Why You Hit Dead Ends
+** TODO Tips for Getting Unstuck
+** TODO The 24 Hours Before Your Interview
+** TODO Beating Behavioral Questions
+** TODO Managing Your Interview Timeline
generated by cgit-pink 1.4.1 (git 2.44.2) at 2024-10-27T19ยท30+0000