aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_num_arr_k_match_elem.c48
-rw-r--r--count_num_arr_k_match_elem.py28
-rw-r--r--fizz_buzz_multithread.c145
-rw-r--r--fizz_buzz_multithread.py94
-rw-r--r--leetcode.h1
-rw-r--r--max_diff_between_incr_elem.c25
-rw-r--r--max_diff_between_incr_elem.py28
7 files changed, 369 insertions, 0 deletions
diff --git a/count_num_arr_k_match_elem.c b/count_num_arr_k_match_elem.c
new file mode 100644
index 0000000..dd8838e
--- /dev/null
+++ b/count_num_arr_k_match_elem.c
@@ -0,0 +1,48 @@
+// 3405. Count the Number of Arrays with K Matching Adjacent Elements
+#include "leetcode.h"
+
+/*
+ * you are given three integers 'n', 'm', and 'k'. a good array 'arr' of size
+ * 'n' is defined as follows: each element in 'arr' is in inclusive range '[1,
+ * m]', and exactly 'k' indices 'i' where '1 <= i < n' satisfy the condition
+ * 'arr[i - 1] == arr[i]'. return the number of good arrays that can be formed.
+ * since the answer may be very large, return it modulo 10^9+7.
+ */
+
+const int mod = 1e9 + 7;
+
+long long mult(long long n, long long m) { return (n * m) % mod; }
+
+long long power(long long n, long long m) {
+ long long res = 1, base = n;
+ while (m > 0) {
+ if (m & 1)
+ res = mult(res, base);
+ base = mult(base, base);
+ m >>= 1;
+ }
+ return res;
+}
+
+long long inv(long long n) { return power(n, mod - 2); }
+
+long long factorial(long long n) {
+ long long res = 1;
+ for (long long i = 2; i <= n; ++i)
+ res = mult(res, i);
+ return res;
+}
+
+long long combine(long long n, long long m) {
+ return mult(factorial(n), inv(mult(factorial(m), factorial(n - m))));
+}
+
+int countGoodArrays(int n, int m, int k) {
+ return mult(mult(combine(n - 1, n - 1 - k), m), power(m - 1, n - 1 - k));
+}
+
+int main() {
+ printf("%d\n", countGoodArrays(3, 2, 1)); // expect: 4
+ printf("%d\n", countGoodArrays(4, 2, 2)); // expect: 6
+ printf("%d\n", countGoodArrays(5, 2, 0)); // expect: 2
+}
diff --git a/count_num_arr_k_match_elem.py b/count_num_arr_k_match_elem.py
new file mode 100644
index 0000000..a3bc73f
--- /dev/null
+++ b/count_num_arr_k_match_elem.py
@@ -0,0 +1,28 @@
+# 3405. Count the Number of Arrays with K Matching Adjacent Elements
+from math import comb
+
+"""
+you are given three integers 'n', 'm', and 'k'. a good array 'arr' of size
+'n' is defined as follows: each element in 'arr' is in inclusive range '[1,
+m]', and exactly 'k' indices 'i' where '1 <= i < n' satisfy the condition
+'arr[i - 1] == arr[i]'. return the number of good arrays that can be formed.
+since the answer may be very large, return it modulo 10^9+7.
+"""
+
+
+class Solution(object):
+ def countGoodArrays(self, n, m, k):
+ """
+ :type n: int
+ :type m: int
+ :type k: int
+ :rtype: int
+ """
+ return m * pow(m - 1, n - k - 1, mod := 1**9 + 7) * comb(n - 1, k) % mod
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countGoodArrays(n=3, m=2, k=1))
+ print(obj.countGoodArrays(n=4, m=2, k=2))
+ print(obj.countGoodArrays(n=5, m=2, k=0))
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_between_incr_elem.c b/max_diff_between_incr_elem.c
new file mode 100644
index 0000000..bf35ab0
--- /dev/null
+++ b/max_diff_between_incr_elem.c
@@ -0,0 +1,25 @@
+// 2016. Maximum Difference Between Increasing Elements
+#include "leetcode.h"
+
+/*
+ * given a 0-indexed integer array 'nums' of size 'n', find the maximum
+ * difference between 'nums[i]' and 'nums[j]' (ie. 'nums[j] - nums[i]') such
+ * that '0 <= i < j < n' and 'nums[i] < nums[j]'. return the maximum difference.
+ * if no such 'i' and 'j' exist, return -1
+ */
+
+int maximumDifference(int *nums, int numsSize) {
+ int min = nums[0], ans = -1;
+ for (int i = 1; i < numsSize; ++i) {
+ ans = fmax(ans, nums[i] - min);
+ min = fmin(min, nums[i]);
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {7, 1, 5, 4}, n2[] = {9, 4, 3, 2}, n3[] = {1, 5, 2, 10};
+ printf("%d\n", maximumDifference(n1, ARRAY_SIZE(n1))); // expect: 4
+ printf("%d\n", maximumDifference(n2, ARRAY_SIZE(n2))); // expect: -1
+ printf("%d\n", maximumDifference(n3, ARRAY_SIZE(n3))); // expect: 9
+}
diff --git a/max_diff_between_incr_elem.py b/max_diff_between_incr_elem.py
new file mode 100644
index 0000000..d277298
--- /dev/null
+++ b/max_diff_between_incr_elem.py
@@ -0,0 +1,28 @@
+# 2016. Maximum Difference Between Increasing Elements
+
+"""
+given a 0-indexed integer array 'nums' of size 'n', find the maximum
+difference between 'nums[i]' and 'nums[j]' (ie. 'nums[j] - nums[i]') such
+that '0 <= i < j < n' and 'nums[i] < nums[j]'. return the maximum difference.
+if no such 'i' and 'j' exist, return -1
+"""
+
+
+class Solution(object):
+ def maximumDifference(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ minn, ans = nums[0], -1
+ for i in range(len(nums)):
+ ans = max(ans, nums[i] - minn)
+ minn = min(minn, nums[i])
+ return ans if ans != 0 else -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maximumDifference(nums=[7, 1, 5, 4]))
+ print(obj.maximumDifference(nums=[9, 4, 3, 2]))
+ print(obj.maximumDifference(nums=[1, 5, 2, 10]))