Jobs

Interviews

Discussions

Print FooBar Alternately

Medium

Asked by:

10 views

Topics:

ArraysStringsTwo Pointers

Suppose you are given the following code:

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

The same instance of FooBar will be passed to two different threads:

thread A will call foo(), while
thread B will call bar().

Modify the given program to output "foobar" n times.

Example 1:

Input: n = 1
Output: "foobar"
Explanation: There are two threads being fired asynchronously. One of them calls foo(), while the other calls bar().
"foobar" is being output 1 time.

Example 2:

Input: n = 2
Output: "foobarfoobar"
Explanation: "foobar" is being output 2 times.

Constraints:

1 <= n <= 1000

Try coding it in LeetCode

Print FooBar Alternately

Medium

Asked by:

10 views

Topics:

ArraysStringsTwo Pointers

Suppose you are given the following code:

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

The same instance of FooBar will be passed to two different threads:

thread A will call foo(), while
thread B will call bar().

Modify the given program to output "foobar" n times.

Example 1:

Input: n = 1
Output: "foobar"
Explanation: There are two threads being fired asynchronously. One of them calls foo(), while the other calls bar().
"foobar" is being output 1 time.

Example 2:

Input: n = 2
Output: "foobarfoobar"
Explanation: "foobar" is being output 2 times.

Constraints:

1 <= n <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the input `n` representing? Is it the number of times "foo" and "bar" should be printed in total, or is it the number of "foo" and "bar" pairs?
What is the expected data type of the input `n`? Is it always a positive integer, or can it be zero or negative?
Should I print "foo" first, then "bar" in each pair, or "bar" first, then "foo"?
Is the printing of "foo" and "bar" atomic (thread-safe) required, or can I assume a single-threaded environment?
What should happen if `n` is zero? Should I print nothing, or throw an exception?

Brute Force Solution

Approach

The basic idea is to print 'Foo' and 'Bar' a certain number of times, but always alternating them. A brute force method simply tries printing each word ('Foo' or 'Bar') in order and checks if the sequence has reached the total number of times requested.

Here's how the algorithm would work step-by-step:

Decide how many times 'Foo' and 'Bar' need to be printed overall.
Start printing 'Foo'.
Then print 'Bar'.
Keep alternating 'Foo' and 'Bar'.
After each print, check if you've printed the correct total number of words.
If you have, you're done.
If not, continue alternating and checking until you reach the total count.

Code Implementation

def print_foo_bar_alternately(number_of_prints):
    foo_bar_counter = 0
    print_foo = True

    # Keep printing until we've reached the desired number of prints
    while foo_bar_counter < number_of_prints:
        if print_foo:
            print("Foo")

            # Set the flag so next time it prints 'Bar'
            print_foo = False

        else:
            print("Bar")

            # Set the flag so next time it prints 'Foo'
            print_foo = True

        # Increment the counter for each print to track total prints
        foo_bar_counter += 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates a fixed number of times based on the total number of 'Foo' and 'Bar' prints required, which we can represent as 'n'. In each iteration, it performs a constant amount of work: printing a string ('Foo' or 'Bar') and checking if the total count has been reached. Since the number of iterations is directly proportional to 'n', the time complexity is O(n).

Space Complexity

O(1) – The provided plain English explanation does not describe the use of any auxiliary data structures. The algorithm focuses on printing and checking a counter. Therefore, there are no dynamic data structures like arrays, lists, or hash maps being used. The space needed is only for a few constant memory variables to keep track of the printing process and the total count, which does not scale with the input size N. Hence, the space complexity is constant.

Optimal Solution

Approach

The goal is to print 'Foo' and 'Bar' alternately, but only after one has finished printing completely. We'll use a communication system (like flags) to signal when each word is ready to be printed by the other.

Here's how the algorithm would work step-by-step:

Create two signals, one for 'Foo' to tell 'Bar' it's done, and another for 'Bar' to tell 'Foo' it's done.
Have 'Foo' print itself, then signal to 'Bar' that it's finished.
Have 'Bar' wait for the signal from 'Foo', then print itself and signal back to 'Foo'.
Repeat these steps a number of times as specified by the input.
Make sure that each of them wait after their operation to allow the other thread to proceed.

Code Implementation

import threading

class FooBar:
    def __init__(self, n):
        self.n = n
        self.foo_done = threading.Lock()
        self.bar_done = threading.Lock()
        self.bar_done.acquire()

    def foo(self, printFoo):
        for i in range(self.n):
            # Bar must finish printing before Foo starts
            self.foo_done.acquire()
            printFoo()

            # Signal that Foo is done printing
            self.bar_done.release()

    def bar(self, printBar):
        for i in range(self.n):
            # Wait for Foo to finish printing
            self.bar_done.acquire()
            printBar()

            # Signal that Bar is done printing
            self.foo_done.release()

Big(O) Analysis

Time Complexity

O(n) – The code iterates 'n' times, where 'n' is the number of times 'Foo' and 'Bar' need to be printed alternately. Inside the loop, there are constant-time operations: printing 'Foo' or 'Bar', and signaling/waiting on the signals. Since the operations inside the loop take constant time and the loop runs 'n' times, the overall time complexity is O(n).

Space Complexity

O(1) – The provided solution uses a fixed number of signals or flags to coordinate the printing of 'Foo' and 'Bar'. The number of signals does not depend on the input N, which represents the number of times 'Foo' and 'Bar' are printed. Therefore, the auxiliary space used remains constant irrespective of N. No dynamic data structures that scale with N are involved. Consequently, the space complexity is O(1).

Edge Cases

Case	How to Handle
n is zero	Print nothing as there are no iterations to perform; return immediately.
n is a very large number (potential integer overflow)	Ensure the loop counter variable is of a type that can hold the maximum value of n to prevent integer overflow issues.
The program is interrupted or encounters an exception during execution	Use try-finally blocks to ensure any necessary cleanup (e.g., releasing locks) occurs even if an exception is thrown.
Multi-threading issues if using threads/processes.	Use synchronization primitives (e.g., locks, semaphores) to prevent race conditions when accessing shared resources.
Memory exhaustion if repeatedly printing to a very long output stream	If memory exhaustion is a real concern, flush output stream periodically or use a bounded buffer.
Negative input values for n.	Treat negative input as an invalid argument and throw an exception or handle it gracefully.
System clock issues could affect timing if implemented with sleep commands	If timing precision is crucial, use monotonic clocks instead of system time.
Extreme values close to integer limits for internal calculations	Use appropriate data types (e.g., long) to accommodate potentially large intermediate results and prevent overflows.

n is zero

How to Handle:

Print nothing as there are no iterations to perform; return immediately.

n is a very large number (potential integer overflow)

How to Handle:

Ensure the loop counter variable is of a type that can hold the maximum value of n to prevent integer overflow issues.

The program is interrupted or encounters an exception during execution

How to Handle:

Use try-finally blocks to ensure any necessary cleanup (e.g., releasing locks) occurs even if an exception is thrown.

Multi-threading issues if using threads/processes.

How to Handle:

Use synchronization primitives (e.g., locks, semaphores) to prevent race conditions when accessing shared resources.

Memory exhaustion if repeatedly printing to a very long output stream

How to Handle:

If memory exhaustion is a real concern, flush output stream periodically or use a bounded buffer.

Negative input values for n.

How to Handle:

Treat negative input as an invalid argument and throw an exception or handle it gracefully.

System clock issues could affect timing if implemented with sleep commands

How to Handle:

If timing precision is crucial, use monotonic clocks instead of system time.

Extreme values close to integer limits for internal calculations

How to Handle:

Use appropriate data types (e.g., long) to accommodate potentially large intermediate results and prevent overflows.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the input `n` representing? Is it the number of times "foo" and "bar" should be printed in total, or is it the number of "foo" and "bar" pairs?
What is the expected data type of the input `n`? Is it always a positive integer, or can it be zero or negative?
Should I print "foo" first, then "bar" in each pair, or "bar" first, then "foo"?
Is the printing of "foo" and "bar" atomic (thread-safe) required, or can I assume a single-threaded environment?
What should happen if `n` is zero? Should I print nothing, or throw an exception?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Decide how many times 'Foo' and 'Bar' need to be printed overall.
Start printing 'Foo'.
Then print 'Bar'.
Keep alternating 'Foo' and 'Bar'.
After each print, check if you've printed the correct total number of words.
If you have, you're done.
If not, continue alternating and checking until you reach the total count.

Code Implementation

def print_foo_bar_alternately(number_of_prints):
    foo_bar_counter = 0
    print_foo = True

    # Keep printing until we've reached the desired number of prints
    while foo_bar_counter < number_of_prints:
        if print_foo:
            print("Foo")

            # Set the flag so next time it prints 'Bar'
            print_foo = False

        else:
            print("Bar")

            # Set the flag so next time it prints 'Foo'
            print_foo = True

        # Increment the counter for each print to track total prints
        foo_bar_counter += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Create two signals, one for 'Foo' to tell 'Bar' it's done, and another for 'Bar' to tell 'Foo' it's done.
Have 'Foo' print itself, then signal to 'Bar' that it's finished.
Have 'Bar' wait for the signal from 'Foo', then print itself and signal back to 'Foo'.
Repeat these steps a number of times as specified by the input.
Make sure that each of them wait after their operation to allow the other thread to proceed.

Code Implementation

import threading

class FooBar:
    def __init__(self, n):
        self.n = n
        self.foo_done = threading.Lock()
        self.bar_done = threading.Lock()
        self.bar_done.acquire()

    def foo(self, printFoo):
        for i in range(self.n):
            # Bar must finish printing before Foo starts
            self.foo_done.acquire()
            printFoo()

            # Signal that Foo is done printing
            self.bar_done.release()

    def bar(self, printBar):
        for i in range(self.n):
            # Wait for Foo to finish printing
            self.bar_done.acquire()
            printBar()

            # Signal that Bar is done printing
            self.foo_done.release()

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is zero	Print nothing as there are no iterations to perform; return immediately.
n is a very large number (potential integer overflow)	Ensure the loop counter variable is of a type that can hold the maximum value of n to prevent integer overflow issues.
The program is interrupted or encounters an exception during execution	Use try-finally blocks to ensure any necessary cleanup (e.g., releasing locks) occurs even if an exception is thrown.
Multi-threading issues if using threads/processes.	Use synchronization primitives (e.g., locks, semaphores) to prevent race conditions when accessing shared resources.
Memory exhaustion if repeatedly printing to a very long output stream	If memory exhaustion is a real concern, flush output stream periodically or use a bounded buffer.
Negative input values for n.	Treat negative input as an invalid argument and throw an exception or handle it gracefully.
System clock issues could affect timing if implemented with sleep commands	If timing precision is crucial, use monotonic clocks instead of system time.
Extreme values close to integer limits for internal calculations	Use appropriate data types (e.g., long) to accommodate potentially large intermediate results and prevent overflows.

n is zero

How to Handle:

Print nothing as there are no iterations to perform; return immediately.

n is a very large number (potential integer overflow)

How to Handle:

Ensure the loop counter variable is of a type that can hold the maximum value of n to prevent integer overflow issues.

The program is interrupted or encounters an exception during execution

How to Handle:

Use try-finally blocks to ensure any necessary cleanup (e.g., releasing locks) occurs even if an exception is thrown.

Multi-threading issues if using threads/processes.

How to Handle:

Use synchronization primitives (e.g., locks, semaphores) to prevent race conditions when accessing shared resources.

Memory exhaustion if repeatedly printing to a very long output stream

How to Handle:

If memory exhaustion is a real concern, flush output stream periodically or use a bounded buffer.

Negative input values for n.

How to Handle:

Treat negative input as an invalid argument and throw an exception or handle it gracefully.

System clock issues could affect timing if implemented with sleep commands

How to Handle:

If timing precision is crucial, use monotonic clocks instead of system time.

Extreme values close to integer limits for internal calculations

How to Handle:

Use appropriate data types (e.g., long) to accommodate potentially large intermediate results and prevent overflows.