Jobs

Interviews

Discussions

Counter II

#900 Most AskedEasy

Counter II #900 Most Asked

Easy

Microsoft

7 views

Write a function createCounter. It should accept an initial integer init. It should return an object with three functions.

The three functions are:

increment() increases the current value by 1 and then returns it.
decrement() reduces the current value by 1 and then returns it.
reset() sets the current value to init and then returns it.

Example 1:

Input: init = 5, calls = ["increment","reset","decrement"]
Output: [6,5,4]
Explanation:
const counter = createCounter(5);
counter.increment(); // 6
counter.reset(); // 5
counter.decrement(); // 4

Example 2:

Input: init = 0, calls = ["increment","increment","decrement","reset","reset"]
Output: [1,2,1,0,0]
Explanation:
const counter = createCounter(0);
counter.increment(); // 1
counter.increment(); // 2
counter.decrement(); // 1
counter.reset(); // 0
counter.reset(); // 0

Constraints:

-1000 <= init <= 1000
0 <= calls.length <= 1000
calls[i] is one of "increment", "decrement" and "reset"

Try coding it in LeetCode

Counter II

#900 Most AskedEasy

Counter II #900 Most Asked

Easy

Microsoft

7 views

Write a function createCounter. It should accept an initial integer init. It should return an object with three functions.

The three functions are:

increment() increases the current value by 1 and then returns it.
decrement() reduces the current value by 1 and then returns it.
reset() sets the current value to init and then returns it.

Example 1:

Input: init = 5, calls = ["increment","reset","decrement"]
Output: [6,5,4]
Explanation:
const counter = createCounter(5);
counter.increment(); // 6
counter.reset(); // 5
counter.decrement(); // 4

Example 2:

Input: init = 0, calls = ["increment","increment","decrement","reset","reset"]
Output: [1,2,1,0,0]
Explanation:
const counter = createCounter(0);
counter.increment(); // 1
counter.increment(); // 2
counter.decrement(); // 1
counter.reset(); // 0
counter.reset(); // 0

Constraints:

-1000 <= init <= 1000
0 <= calls.length <= 1000
calls[i] is one of "increment", "decrement" and "reset"

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 expected data type for the initial value, and what is the expected range of possible values it could take?
What should happen if the `increment` or `decrement` function is called an extremely large number of times, potentially exceeding integer limits?
Is the counter expected to wrap around if it reaches a maximum or minimum value, or should it throw an error/return a specific value?
Are there any memory constraints I should be aware of, assuming a large number of counter instances might be created?
Is the counter thread-safe, or is it expected to be used in a single-threaded environment?

Brute Force Solution

Approach

The brute force way to create a counter involves going through all possible numbers within the specified range. We'll manually check each number to see if it matches our criteria, incrementing one by one. This guarantees we'll find the correct value eventually.

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

Start with the initial number that's provided.
When the counter is asked for its next value, simply return the current number and then increase it by one.
Before returning the number, always check if it has exceeded the maximum value that was defined at the start. If it has, reset it back to the initial value.
If the maximum value has not been exceeded, then we just return the current value which has been incremented.

Code Implementation

class Counter2:

    def __init__(self, initial_value: int):
        self.current_value = initial_value
        self.initial_value = initial_value

    def increment(self) -> int:
        # Store the current value for return
        return_value = self.current_value
        self.current_value += 1
        # Check if the counter exceeded maximum
        if self.current_value > 1000000:
            self.current_value = self.initial_value

        return return_value

Big(O) Analysis

Time Complexity

O(1) – The operations involved in this counter implementation consist of incrementing a counter and checking if it exceeds a predefined maximum value. Both of these operations take constant time, regardless of the range or the initial value. Thus, each call to the counter function performs a fixed amount of work. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The algorithm stores only the current number, initial number, and potentially the maximum number. The number of these variables does not scale with any input size. Therefore, the auxiliary space required is constant.

Optimal Solution

Approach

The challenge is to create a function that acts like a counter, allowing you to increment or decrement a number. The efficient approach is to use a feature that allows you to remember the initial value and track changes relative to that starting point.

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

First, remember the initial number given to the function.
Then, define a way to either increase the number by one or decrease it by one each time the function is called.
When the function is called, either increase or decrease the remembered number and return the updated value.
This way, the function always remembers where it started and how many times it has been changed.

Code Implementation

def createCounter(initial_value):
    current_value = initial_value

    def increment():
        nonlocal current_value
        current_value += 1
        return current_value

    def decrement():
        nonlocal current_value
        current_value -= 1
        return current_value

    def reset():
        nonlocal current_value
        # Reset current value to initial value.
        current_value = initial_value

        return current_value

    return {
        "increment": increment,
        "decrement": decrement,
        "reset": reset
    }

def counter_ii(initial_value):

    # Capture the initial value in the closure.
    def counter():
        nonlocal initial_value

        # Store original value
        original_value = initial_value

        # Increment initial value
        initial_value += 1

        return original_value

    # We return the object with special functions attached
    return counter

Big(O) Analysis

Time Complexity

O(1) – The counter function performs either an increment or decrement operation, which takes constant time regardless of any input size. The initial assignment of the number also takes constant time. Since all operations within the returned object have a time complexity of O(1), the overall time complexity of the counter function and the increment/decrement calls are O(1).

Space Complexity

O(1) – The provided solution only needs to store the initial number. No additional data structures that scale with the input are created. Therefore, the extra space required remains constant regardless of the initial number provided. The space complexity is O(1).

Edge Cases

Case	How to Handle
Initial value is positive infinity	Handle this case by either throwing an error, setting it to the maximum safe integer value, or letting the increment continue, depending on the expected behavior
Initial value is negative infinity	Handle this case by either throwing an error, setting it to the minimum safe integer value, or letting the increment continue, depending on the expected behavior
Incrementing beyond the maximum safe integer	Check for potential integer overflow and either throw an exception, cap the value, or use a larger data type.
Decrementing beyond the minimum safe integer	Check for potential integer underflow and either throw an exception, cap the value, or use a larger data type.
Initial value is NaN	Return NaN immediately as any subsequent operations will also result in NaN.
Incrementing after reaching maximum safe integer	Define if the counter rolls over, stays at max, or throws an error.
Decrementing after reaching minimum safe integer	Define if the counter rolls over, stays at min, or throws an error.
Calling increment/decrement excessively	Consider if limits or resource exhaustion would become a concern in the environment, and implement appropriate safeguards or logging.

Initial value is positive infinity

How to Handle:

Handle this case by either throwing an error, setting it to the maximum safe integer value, or letting the increment continue, depending on the expected behavior

Initial value is negative infinity

How to Handle:

Handle this case by either throwing an error, setting it to the minimum safe integer value, or letting the increment continue, depending on the expected behavior

Incrementing beyond the maximum safe integer

How to Handle:

Check for potential integer overflow and either throw an exception, cap the value, or use a larger data type.

Decrementing beyond the minimum safe integer

How to Handle:

Check for potential integer underflow and either throw an exception, cap the value, or use a larger data type.

Initial value is NaN

How to Handle:

Return NaN immediately as any subsequent operations will also result in NaN.

Incrementing after reaching maximum safe integer

How to Handle:

Define if the counter rolls over, stays at max, or throws an error.

Decrementing after reaching minimum safe integer

How to Handle:

Define if the counter rolls over, stays at min, or throws an error.

Calling increment/decrement excessively

How to Handle:

Consider if limits or resource exhaustion would become a concern in the environment, and implement appropriate safeguards or logging.

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 expected data type for the initial value, and what is the expected range of possible values it could take?
What should happen if the `increment` or `decrement` function is called an extremely large number of times, potentially exceeding integer limits?
Is the counter expected to wrap around if it reaches a maximum or minimum value, or should it throw an error/return a specific value?
Are there any memory constraints I should be aware of, assuming a large number of counter instances might be created?
Is the counter thread-safe, or is it expected to be used in a single-threaded environment?

Brute Force Solution

Approach

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

Start with the initial number that's provided.
When the counter is asked for its next value, simply return the current number and then increase it by one.
Before returning the number, always check if it has exceeded the maximum value that was defined at the start. If it has, reset it back to the initial value.
If the maximum value has not been exceeded, then we just return the current value which has been incremented.

Code Implementation

class Counter2:

    def __init__(self, initial_value: int):
        self.current_value = initial_value
        self.initial_value = initial_value

    def increment(self) -> int:
        # Store the current value for return
        return_value = self.current_value
        self.current_value += 1
        # Check if the counter exceeded maximum
        if self.current_value > 1000000:
            self.current_value = self.initial_value

        return return_value

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, remember the initial number given to the function.
Then, define a way to either increase the number by one or decrease it by one each time the function is called.
When the function is called, either increase or decrease the remembered number and return the updated value.
This way, the function always remembers where it started and how many times it has been changed.

Code Implementation

def createCounter(initial_value):
    current_value = initial_value

    def increment():
        nonlocal current_value
        current_value += 1
        return current_value

    def decrement():
        nonlocal current_value
        current_value -= 1
        return current_value

    def reset():
        nonlocal current_value
        # Reset current value to initial value.
        current_value = initial_value

        return current_value

    return {
        "increment": increment,
        "decrement": decrement,
        "reset": reset
    }

def counter_ii(initial_value):

    # Capture the initial value in the closure.
    def counter():
        nonlocal initial_value

        # Store original value
        original_value = initial_value

        # Increment initial value
        initial_value += 1

        return original_value

    # We return the object with special functions attached
    return counter

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Initial value is positive infinity	Handle this case by either throwing an error, setting it to the maximum safe integer value, or letting the increment continue, depending on the expected behavior
Initial value is negative infinity	Handle this case by either throwing an error, setting it to the minimum safe integer value, or letting the increment continue, depending on the expected behavior
Incrementing beyond the maximum safe integer	Check for potential integer overflow and either throw an exception, cap the value, or use a larger data type.
Decrementing beyond the minimum safe integer	Check for potential integer underflow and either throw an exception, cap the value, or use a larger data type.
Initial value is NaN	Return NaN immediately as any subsequent operations will also result in NaN.
Incrementing after reaching maximum safe integer	Define if the counter rolls over, stays at max, or throws an error.
Decrementing after reaching minimum safe integer	Define if the counter rolls over, stays at min, or throws an error.
Calling increment/decrement excessively	Consider if limits or resource exhaustion would become a concern in the environment, and implement appropriate safeguards or logging.

Initial value is positive infinity

How to Handle:

Handle this case by either throwing an error, setting it to the maximum safe integer value, or letting the increment continue, depending on the expected behavior

Initial value is negative infinity

How to Handle:

Handle this case by either throwing an error, setting it to the minimum safe integer value, or letting the increment continue, depending on the expected behavior

Incrementing beyond the maximum safe integer

How to Handle:

Check for potential integer overflow and either throw an exception, cap the value, or use a larger data type.

Decrementing beyond the minimum safe integer

How to Handle:

Check for potential integer underflow and either throw an exception, cap the value, or use a larger data type.

Initial value is NaN

How to Handle:

Return NaN immediately as any subsequent operations will also result in NaN.

Incrementing after reaching maximum safe integer

How to Handle:

Define if the counter rolls over, stays at max, or throws an error.

Decrementing after reaching minimum safe integer

How to Handle:

Define if the counter rolls over, stays at min, or throws an error.

Calling increment/decrement excessively

How to Handle:

Consider if limits or resource exhaustion would become a concern in the environment, and implement appropriate safeguards or logging.

0/1114 Microsoft questions completed

0/1114 completed