Huahua's Tech Road

花花酱 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 1200. Minimum Absolute Difference

By zxi on September 22, 2019

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints:

2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6

Solution: Sorting

The min abs difference could only happen between consecutive numbers in sorted form.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> minimumAbsDifference(vector<int>& arr) {

sort(begin(arr), end(arr));

vector<vector<int>> ans;

int best = INT_MAX;

for (int i = 1; i < arr.size(); ++i) {

int d = abs(arr[i] - arr[i - 1]);

if (d < best) {

ans.clear();

best = d;

}

if (d == best) ans.push_back({arr[i - 1], arr[i]});

}

return ans;

}

};

花花酱 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 1192. Critical Connections in a Network

By zxi on September 15, 2019

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some server unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Constraints:

1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections[i][0] != connections[i][1]
There are no repeated connections.

Solution: Tarjan

Time complexity: O(v+e)
Space complexity: O(v+e)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {

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

vector<int> ts(n, INT_MAX);

vector<vector<int>> ans;

int t = 0;

function<int(int, int)> tarjan = [&](int i, int p) {

int min_i = ts[i] = ++t;

for (int j : g[i]) {

if (ts[j] == INT_MAX) {

int min_j = tarjan(j, i);

min_i = min(min_i, min_j);

if (ts[i] < min_j)

ans.push_back({i, j});

} else if (j != p) {

min_i = min(min_i, ts[j]);

}

return min_i;

};

for (const auto& e : connections) {

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

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

}

tarjan(0, -1);

return ans;

}

};