aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--fizz_buzz_multithread.c145
-rw-r--r--fizz_buzz_multithread.py94
-rw-r--r--leetcode.h1
-rw-r--r--max_diff_remap_digit.c30
-rw-r--r--max_diff_remap_digit.py26
-rw-r--r--valid_square.c46
-rw-r--r--valid_square.py41
7 files changed, 383 insertions, 0 deletions
diff --git a/fizz_buzz_multithread.c b/fizz_buzz_multithread.c
new file mode 100644
index 0000000..67da100
--- /dev/null
+++ b/fizz_buzz_multithread.c
@@ -0,0 +1,145 @@
+// 1195. Fizz Buzz Multithreaded
+#include "leetcode.h"
+
+/*
+ * you have the following functions:
+ * 'printFizz' prints the word "fizz" to the console
+ * 'printBuzz' prints the word "buzz" to the console
+ * 'printFizzBuzz' prints the word "fizzbuzz" to the console
+ * 'printNumber' that prints a given integer to the console
+ * you are given an instance of the class 'fizzbuzz' that has four functions
+ * 'fizz', 'buzz', 'fizzbuzz', and 'number'. the same instance of 'fizzbuzz'
+ * will be passed to four different threads.
+ * thread a calls 'fizz()' that should output the word "fizz"
+ * thread b calls 'buzz()' that should output the word "buzz"
+ * thread c calls 'fizzbuzz()' that should output the word "fizzbuzz"
+ * thread d calls 'number()' that should output the given integer
+ * modify the given class to output the series '[1, 2, "fizz", 4, "buzz", ...]'
+ * where the i'th toek of the series is.
+ */
+
+typedef struct {
+ int n;
+ int curr;
+ int turn;
+} FizzBuzz;
+
+pthread_mutex_t mutex;
+pthread_cond_t cond;
+
+FizzBuzz *fizzBuzzCreate(int n) {
+ FizzBuzz *obj = (FizzBuzz *)malloc(sizeof(FizzBuzz));
+ obj->n = n;
+ obj->curr = 1;
+ obj->turn = 0;
+ return obj;
+}
+
+// Don't change the following declarations
+void printNumber(int a);
+void printFizz();
+void printBuzz();
+void printFizzBuzz();
+
+int helper(FizzBuzz *obj, int turn) {
+ pthread_mutex_lock(&mutex);
+ while (obj->turn != turn && obj->curr <= obj->n)
+ pthread_cond_wait(&cond, &mutex);
+ if (obj->curr > obj->n)
+ return -1;
+ switch (turn) {
+ case 0:
+ printNumber(obj->curr);
+ break;
+ case 1:
+ printFizz();
+ break;
+ case 2:
+ printBuzz();
+ break;
+ case 3:
+ printFizzBuzz();
+ break;
+ }
+ obj->curr++;
+ if ((obj->curr % 3 == 0) && (obj->curr % 5 == 0))
+ obj->turn = 3;
+ else if (obj->curr % 3 == 0)
+ obj->turn = 1;
+ else if (obj->curr % 5 == 0)
+ obj->turn = 2;
+ else
+ obj->turn = 0;
+ pthread_cond_broadcast(&cond);
+ pthread_mutex_unlock(&mutex);
+ return 0;
+}
+
+// printFizz() outputs "fizz".
+void fizz(FizzBuzz *obj) {
+ while (1)
+ if (helper(obj, 1) == -1)
+ break;
+ pthread_mutex_unlock(&mutex);
+}
+
+// printBuzz() outputs "buzz".
+void buzz(FizzBuzz *obj) {
+ while (1)
+ if (helper(obj, 2) == -1)
+ break;
+ pthread_mutex_unlock(&mutex);
+}
+
+// printFizzBuzz() outputs "fizzbuzz".
+void fizzbuzz(FizzBuzz *obj) {
+ while (1)
+ if (helper(obj, 3) == -1)
+ break;
+ pthread_mutex_unlock(&mutex);
+}
+
+// You may call global function `void printNumber(int x)`
+// to output "x", where x is an integer.
+void number(FizzBuzz *obj) {
+ while (1)
+ if (helper(obj, 0) == -1)
+ break;
+ pthread_mutex_unlock(&mutex);
+}
+
+void fizzBuzzFree(FizzBuzz *obj) {
+ if (obj)
+ free(obj);
+}
+
+void printNumber(int a) { printf("%d ", a); }
+
+void printFizz() { printf("fizz "); }
+
+void printBuzz() { printf("buzz "); }
+
+void printFizzBuzz() { printf("fizzbuzz "); }
+
+int main() {
+ FizzBuzz *obj1 = fizzBuzzCreate(15);
+ FizzBuzz *obj2 = fizzBuzzCreate(5);
+ pthread_t t1[4], t2[4];
+ pthread_create(&t1[0], NULL, (void *)fizz, obj1);
+ pthread_create(&t1[1], NULL, (void *)buzz, obj1);
+ pthread_create(&t1[2], NULL, (void *)fizzbuzz, obj1);
+ pthread_create(&t1[3], NULL, (void *)number, obj1);
+ for (int i = 0; i < 4; i++)
+ pthread_join(
+ t1[i],
+ NULL); // expect:
+ // [1,2,"fizz",4,"buzz","fizz",7,8,"fizz","buzz",11,"fizz",13,14,"fizzbuzz"]
+ pthread_create(&t2[0], NULL, (void *)fizz, obj2);
+ pthread_create(&t2[1], NULL, (void *)buzz, obj2);
+ pthread_create(&t2[2], NULL, (void *)fizzbuzz, obj2);
+ pthread_create(&t2[3], NULL, (void *)number, obj2);
+ for (int i = 0; i < 4; i++)
+ pthread_join(t1[i], NULL); // expect: [1,2,"fizz",4,"buzz"]
+ fizzBuzzFree(obj1);
+ fizzBuzzFree(obj2);
+}
diff --git a/fizz_buzz_multithread.py b/fizz_buzz_multithread.py
new file mode 100644
index 0000000..5292164
--- /dev/null
+++ b/fizz_buzz_multithread.py
@@ -0,0 +1,94 @@
+# 1195. Fizz Buzz Multithreaded
+import threading
+
+"""
+you have the following functions:
+'printFizz' prints the word "fizz" to the console
+'printBuzz' prints the word "buzz" to the console
+'printFizzBuzz' prints the word "fizzbuzz" to the console
+'printNumber' that prints a given integer to the console
+you are given an instance of the class 'fizzbuzz' that has four functions
+'fizz', 'buzz', 'fizzbuzz', and 'number'. the same instance of 'fizzbuzz'
+will be passed to four different threads.
+thread a calls 'fizz()' that should output the word "fizz"
+thread b calls 'buzz()' that should output the word "buzz"
+thread c calls 'fizzbuzz()' that should output the word "fizzbuzz"
+thread d calls 'number()' that should output the given integer
+modify the given class to output the series '[1, 2, "fizz", 4, "buzz", ...]'
+where the i'th toek of the series is.
+"""
+
+
+class FizzBuzz(object):
+ def __init__(self, n):
+ self.n = n
+ self.f = threading.Lock()
+ self.b = threading.Lock()
+ self.fb = threading.Lock()
+ self.f.acquire()
+ self.b.acquire()
+ self.fb.acquire()
+ self.main = threading.Lock()
+
+ # printFizz() outputs "fizz"
+ def fizz(self, printFizz):
+ """
+ :type printFizz: method
+ :rtype: void
+ """
+ while True:
+ self.f.acquire()
+ if self.n == 0:
+ return
+ printFizz()
+ self.main.release()
+
+ # printBuzz() outputs "buzz"
+ def buzz(self, printBuzz):
+ """
+ :type printBuzz: method
+ :rtype: void
+ """
+ while True:
+ self.b.acquire()
+ if self.n == 0:
+ return
+ printBuzz()
+ self.main.release()
+
+ # printFizzBuzz() outputs "fizzbuzz"
+ def fizzbuzz(self, printFizzBuzz):
+ """
+ :type printFizzBuzz: method
+ :rtype: void
+ """
+ while True:
+ self.fb.acquire()
+ if self.n == 0:
+ return
+ printFizzBuzz()
+ self.main.release()
+
+ # printNumber(x) outputs "x", where x is an integer.
+ def number(self, printNumber):
+ """
+ :type printNumber: method
+ :rtype: void
+ """
+ for i in range(1, self.n + 1):
+ self.main.acquire()
+ if i % 15 == 0:
+ self.fb.release()
+ elif i % 3 == 0:
+ self.f.release()
+ elif i % 5 == 0:
+ self.b.release()
+ else:
+ printNumber(i)
+ self.main.release()
+ self.main.acquire()
+ self.n = 0
+ self.f.release()
+ self.b.release()
+ self.fb.release()
+ return
diff --git a/leetcode.h b/leetcode.h
index c68a56a..0f0ca7c 100644
--- a/leetcode.h
+++ b/leetcode.h
@@ -4,6 +4,7 @@
#include <ctype.h>
#include <limits.h>
#include <math.h>
+#include <pthread.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
diff --git a/max_diff_remap_digit.c b/max_diff_remap_digit.c
new file mode 100644
index 0000000..3eff54a
--- /dev/null
+++ b/max_diff_remap_digit.c
@@ -0,0 +1,30 @@
+// 2566. Maximum Difference by Remapping a Digit
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'num'. you know that bob will sneakily remap one of
+ * the 10 possible digits to another digit. return the difference between the
+ * maximum and minimum values bob can make by remapping exactly one digit in
+ * nums.
+ */
+
+int minMaxDifference(int num) {
+ int min = num, max = num;
+ for (int i = 0; i < 10; ++i) {
+ int low = 0, high = 0, mult = 1;
+ for (int j = num; j; j /= 10) {
+ bool replace = j % 10 == i;
+ low += (replace ? 0 : j % 10) * mult;
+ high += (replace ? 9 : j % 10) * mult;
+ mult *= 10;
+ }
+ min = fmin(min, low);
+ max = fmax(max, high);
+ }
+ return max - min;
+}
+
+int main() {
+ printf("%d\n", minMaxDifference(11891)); // expect: 99009
+ printf("%d\n", minMaxDifference(90)); // expect: 99
+}
diff --git a/max_diff_remap_digit.py b/max_diff_remap_digit.py
new file mode 100644
index 0000000..5d802ed
--- /dev/null
+++ b/max_diff_remap_digit.py
@@ -0,0 +1,26 @@
+# 2566. Maximum Difference by Remapping a Digit
+
+"""
+you are given an integer 'num'. you know that bob will sneakily remap one of
+the 10 possible digits to another digit. return the difference between the
+maximum and minimum values bob can make by remapping exactly one digit in
+nums.
+"""
+
+
+class Solution(object):
+ def minMaxDifference(self, num):
+ """
+ :type num: int
+ :rtype: int
+ """
+ num, i = str(num), 0
+ while num[i] == "9" and i < len(num) - 1:
+ i += 1
+ return int(num.replace(num[i], "9")) - int(num.replace(num[0], "0"))
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minMaxDifference(num=11891))
+ print(obj.minMaxDifference(num=90))
diff --git a/valid_square.c b/valid_square.c
new file mode 100644
index 0000000..8d1bd06
--- /dev/null
+++ b/valid_square.c
@@ -0,0 +1,46 @@
+// 593. Valid Square
+#include "leetcode.h"
+
+/*
+ * given the coordinates of four points in a 2d space 'p1 .. p4', return true if
+ * the four points oncstruct a square. the coordinate of a point 'p_i' is
+ * represented as '[x_i, y_i]'. the input is not given in any order. a valid
+ * square has four equal sides with positive length and four equal angles
+ * (90-degree angles)
+ */
+
+int dist(int x, int y) { return x * x + y * y; }
+
+bool validSquare(int *p1, int p1Size, int *p2, int p2Size, int *p3, int p3Size,
+ int *p4, int p4Size) {
+ int *p[4] = {p1, p2, p3, p4}, e[2] = {0};
+ for (int i = 0; i < 4; i++) {
+ for (int j = i + 1; j < 4; j++) {
+ int n = dist(p[i][0] - p[j][0], p[i][1] - p[j][1]);
+ if (!n)
+ return false;
+ if (n == e[0] || (!e[0] && n != e[1]))
+ e[0] = n;
+ else if (n == e[1] || (!e[1] && n != e[0]))
+ e[1] = n;
+ else
+ return false;
+ }
+ }
+ return true;
+}
+
+int main() {
+ int p11[] = {0, 0}, p21[] = {1, 1}, p31[] = {1, 0}, p41[] = {0, 1};
+ int p12[] = {0, 0}, p22[] = {1, 1}, p32[] = {1, 0}, p42[] = {0, 12};
+ int p13[] = {1, 0}, p23[] = {-1, 0}, p33[] = {0, 1}, p43[] = {0, -1};
+ printf("%d\n",
+ validSquare(p11, ARRAY_SIZE(p11), p21, ARRAY_SIZE(p21), p31,
+ ARRAY_SIZE(p31), p41, ARRAY_SIZE(p41))); // expect: 1
+ printf("%d\n",
+ validSquare(p12, ARRAY_SIZE(p12), p22, ARRAY_SIZE(p22), p32,
+ ARRAY_SIZE(p32), p42, ARRAY_SIZE(p42))); // expect: 0
+ printf("%d\n",
+ validSquare(p13, ARRAY_SIZE(p13), p23, ARRAY_SIZE(p23), p33,
+ ARRAY_SIZE(p33), p43, ARRAY_SIZE(p43))); // expect: 1
+}
diff --git a/valid_square.py b/valid_square.py
new file mode 100644
index 0000000..a9a75c1
--- /dev/null
+++ b/valid_square.py
@@ -0,0 +1,41 @@
+# 593. Valid Square
+
+"""
+given the coordinates of four points in a 2d space 'p1 .. p4', return true if
+the four points oncstruct a square. the coordinate of a point 'p_i' is
+represented as '[x_i, y_i]'. the input is not given in any order. a valid
+square has four equal sides with positive length and four equal angles
+(90-degree angles)
+"""
+
+
+class Solution(object):
+ def validSquare(self, p1, p2, p3, p4):
+ """
+ :type p1: List[int]
+ :type p2: List[int]
+ :type p3: List[int]
+ :type p4: List[int]
+ :rtype: bool
+ """
+
+ def dist(p, q):
+ return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2
+
+ def check(p1, p2, p3, p4):
+ if p1[0] + p2[0] != p3[0] + p4[0] or p1[1] + p2[1] != p3[1] + p4[1]:
+ return False
+ if dist(p1, p2) != dist(p3, p4) or dist(p1, p4) != dist(p2, p4):
+ return False
+ if p1 == p2:
+ return False
+ return True
+
+ return check(p1, p2, p3, p4) or check(p1, p3, p2, p4) or check(p1, p4, p2, p3)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.validSquare(p1=[0, 0], p2=[1, 1], p3=[1, 0], p4=[0, 1]))
+ print(obj.validSquare(p1=[0, 0], p2=[1, 1], p3=[1, 0], p4=[0, 12]))
+ print(obj.validSquare(p1=[1, 0], p2=[-1, 0], p3=[0, 1], p4=[0, -1]))