Posts tagged as “medium”

花花酱 LeetCode 1195. Fizz Buzz Multithreaded

By zxi on September 22, 2019

Write a program that outputs the string representation of numbers from 1 to n, however:

If the number is divisible by 3, output “fizz”.
If the number is divisible by 5, output “buzz”.
If the number is divisible by both 3 and 5, output “fizzbuzz”.

For example, for n = 15, we output: 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz.

Suppose you are given the following code:

class FizzBuzz {
  public FizzBuzz(int n) { ... }               // constructor
  public void fizz(printFizz) { ... }          // only output "fizz"
  public void buzz(printBuzz) { ... }          // only output "buzz"
  public void fizzbuzz(printFizzBuzz) { ... }  // only output "fizzbuzz"
  public void number(printNumber) { ... }      // only output the numbers
}

Implement a multithreaded version of FizzBuzz with four threads. The same instance of FizzBuzz will be passed to four different threads:

Thread A will call fizz() to check for divisibility of 3 and outputs fizz.
Thread B will call buzz() to check for divisibility of 5 and outputs buzz.
Thread C will call fizzbuzz() to check for divisibility of 3 and 5 and outputs fizzbuzz.
Thread D will call number() which should only output the numbers.

Solution:

4 Semaphores

C++

// Author: Huahua

class Semaphore {

public:

Semaphore (int count = 0): count_(count) {}

inline void notify() {

unique_lock<std::mutex> lock(mtx_);

count_++;

cv_.notify_one();

}

inline void wait() {

unique_lock<std::mutex> lock(mtx_);

while (count_ == 0) cv_.wait(lock);

count_--;

}

private:

mutex mtx_;

condition_variable cv_;

int count_;

};

class FizzBuzz {

private:

int n;

Semaphore sn;

Semaphore s3;

Semaphore s5;

Semaphore s15;

public:

FizzBuzz(int n): n(n), sn(1), s3(0), s5(0), s15(0) {}

void fizz(function<void()> printFizz) {

for (int i = 3; i <= n; i += 3) {

if (i % 5 == 0) continue;

s3.wait();

printFizz();

sn.notify();

}

void buzz(function<void()> printBuzz) {

for (int i = 5; i <= n; i += 5) {

if (i % 3 == 0) continue;

s5.wait();

printBuzz();

sn.notify();

}

void fizzbuzz(function<void()> printFizzBuzz) {

for (int i = 15; i <= n; i += 15) {

s15.wait();

printFizzBuzz();

sn.notify();

}

void number(function<void(int)> printNumber) {

for (int i = 1; i <= n; ++i)

if (i % 15 == 0) { s15.notify(); sn.wait(); }

else if (i % 5 == 0) { s5.notify(); sn.wait(); }

else if (i % 3 == 0) { s3.notify(); sn.wait(); }

else { printNumber(i); }

}

};

花花酱 LeetCode 1202. Smallest String With Swaps

By zxi on September 22, 2019

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination: 
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"

Constraints:

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.

Solution: Connected Components

Use DFS / Union-Find to find all the connected components of swapable indices. For each connected components (index group), extract the subsequence of corresponding chars as a string, sort it and put it back to the original string in the same location.

e.g. s = “dcab”, pairs = [[0,3],[1,2]]
There are two connected components: {0,3}, {1,2}
subsequences:
1. 0,3 “db”, sorted: “bd”
2. 1,2 “ca”, sorted: “ac”
0 => b
1 => a
2 => c
3 => d
final = “bacd”

Time complexity: DFS: O(nlogn + k*(V+E)), Union-Find: O(nlogn + V+E)
Space complexity: O(n)

C++/DFS

// Author: Huahua, 268 ms, 89 MB

class Solution {

public:

string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {

vector<vector<int>> g(s.length());

for (const auto& e : pairs) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

unordered_set<int> seen;

vector<int> idx;

string tmp;

function<void(int)> dfs = [&](int cur) {

if (seen.count(cur)) return;

seen.insert(cur);

idx.push_back(cur);

tmp += s[cur];

for (int nxt : g[cur]) dfs(nxt);

};

for (int i = 0; i < s.length(); ++i) {

if (seen.count(i)) continue;

idx.clear();

tmp.clear();

dfs(i);

sort(begin(tmp), end(tmp));

sort(begin(idx), end(idx));

for (int k = 0; k < idx.size(); ++k)

s[idx[k]] = tmp[k];

}

return s;

}

};

C++/Union-Find

// Author: Huahua, 152 ms, 48.2 MB

class Solution {

public:

string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {

int n = s.length();

vector<int> p(n);

iota(begin(p), end(p), 0); // p = {0, 1, 2, ... n - 1}

function<int(int)> find = [&](int x) {

return p[x] == x ? x : p[x] = find(p[x]);

};

for (const auto& e : pairs)

p[find(e[0])] = find(e[1]); // union

vector<vector<int>> idx(n);

vector<string> ss(n);

for (int i = 0; i < s.length(); ++i) {

int id = find(i);

idx[id].push_back(i); // already sorted

ss[id].push_back(s[i]);

}

for (int i = 0; i < n; ++i) {

sort(begin(ss[i]), end(ss[i]));

for (int k = 0; k < idx[i].size(); ++k)

s[idx[i][k]] = ss[i][k];

}

return s;

}

};

花花酱 LeetCode 1201. Ugly Number III

By zxi on September 22, 2019

Write a program to find the n-th ugly number.

Ugly numbers are positive integers which are divisible by a or b or c.

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 12... The 4th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

Example 4:

Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984

Constraints:

1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
It’s guaranteed that the result will be in range [1, 2 * 10^9]

Solution: Binary Search

Number of ugly numbers that are <= m are:

m / a + m / b + m / c – (m / LCM(a,b) + m / LCM(a, c) + m / LCM(b, c) + m / LCM(a, LCM(b, c))

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int nthUglyNumber(int n, long a, long b, long c) {

long l = 1;

long r = INT_MAX;

long ab = lcm(a, b);

long ac = lcm(a, c);

long bc = lcm(b, c);

long abc = lcm(a, bc);

while (l < r) {

long m = l + (r - l) / 2;

long k = m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc;

if (k >= n) r = m;

else l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1191. K-Concatenation Maximum Sum

By zxi on September 15, 2019

Given an integer array arr and an integer k, modify the array by repeating it k times.

For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.

As the answer can be very large, return the answer modulo 10^9 + 7.

Example 1:

Input: arr = [1,2], k = 3
Output: 9

Example 2:

Input: arr = [1,-2,1], k = 5
Output: 2

Example 3:

Input: arr = [-1,-2], k = 7
Output: 0

Constraints:

1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4

Solution: DP

This problem can be reduced to maxSubarray.
If k < 3: return maxSubarray(arr * k)
ans1 = maxSubarray(arr * 1)
ans2 = maxSubarray(arr * 2)
ans = max([ans1, ans2, ans2 + sum(arr) * (k – 2)])

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int kConcatenationMaxSum(vector<int>& arr, int k) {

constexpr int kMod = 1e9 + 7;

auto maxSum = [&arr](int r) {

long sum = 0;

long ans = 0;

for (int i = 0; i < r; ++i) {

for (long a : arr) {

sum = max(0L, sum += a);

ans = max(ans, sum);

}

return ans;

};

if (k < 3) return maxSum(k) % kMod;

long ans1 = maxSum(1);

long ans2 = maxSum(2);

long sum = accumulate(begin(arr), end(arr), 0L);

return max({ans1, ans2, ans2 + sum * (k - 2)}) % kMod;

}

};

花花酱 LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

By zxi on September 15, 2019

Given a string s that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any bracket.

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"

Example 4:

Input: s = "a(bcdefghijkl(mno)p)q"
Output: "apmnolkjihgfedcbq"

Constraints:

0 <= s.length <= 2000
s only contains lower case English characters and parentheses.
It’s guaranteed that all parentheses are balanced.

Solution: Stack

Use a stack of strings to track all the active strings.
Iterate over the input string:
1. Whenever there is a ‘(‘, push an empty string to the stack.
2. Whenever this is a ‘)’, pop the top string and append the reverse of it to the new stack top.
3. Otherwise, append the letter to the string on top the of stack.

Once done, the (only) string on the top of the stack is the answer.

Time complexity: O(n^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string reverseParentheses(string s) {

stack<string> st;

st.push("");

for (char c : s) {

if (c == '(') st.push("");

else if (c != ')') st.top() += c;

else {

string t = st.top(); st.pop();

st.top().insert(end(st.top()), rbegin(t), rend(t));

}

return st.top();

}

};