Question: Latest HackerRank OA Coding Questions & Solutions | Server Faults & Modified Knapsack

Entering edit mode

Question 1: Faulty Server Replacement

Problem Statement:

Implement a prototype service to automate the detection and replacement of faulty servers to improve the availability of an application.

There are n servers with IDs s1, s2, ..., sn, and an array of strings, logs, of size m. The log format is "<server_id> <success/error>", representing the ID of the server and the status of the processed request. If a particular server ID logs an error for three consecutive requests, it is considered faulty and is replaced with a new server with the same ID.

Given n and the array logs, find the number of times a faulty server was replaced.

Example:

n = 2

logs = ["s1 error", "s1 error", "s2 error", "s1 error", "s1 error", "s2 success"]

Output: 1

Explanation:

s1 logs its 1st error.
s1 logs its 2nd error.
s2 logs its 1st error.
s1 logs its 3rd error Detected, s1 is replaced. (Count = 1)
s1 logs its 1st error (since it was replaced, the count resets).
s2 logs a success (s2's error count resets to 0).

Question 2: Madam C.J. Walker (Modified 0-1 Knapsack)

Problem Statement:

Madam C.J. Walker is historically renowned for becoming the first African-American businesswoman in America. One of her business plans involving the sale of cosmetics is a modification of the standard 0-1 knapsack problem.

Walker's business plan begins with an array of n items. She wants to buy products and resell them for profit. The cost of buying the ith item is cost_i, and it earns her a profit of 2^i. She has a total of x amount of money.

Find the maximum profit that can be generated for the given amount of money. As the answer can be rather large, report the answer as maxProfit mod{10^9+7}.

Example:

n = 5, cost = [10, 20, 14, 40, 50], x = 70

A possible optimal combination:

She can buy item 4 (cost 50) and item 2 (cost 14) for a total cost of 64 (<=70).

Her profit will be 2^4 + 2^2 = 16 + 4 = 20.

ADD COMMENT • link 22 days ago admin 1.9k

Entering edit mode

Madam C.J. Walker (Modified 0-1 Knapsack) Solution

Overview

Because the profit grows as powers of two, taking a larger item is strictly better than taking every single smaller item combined.
This mathematical certainty bypasses the standard dynamic programming approach and turns this into a pure greedy problem!
By iterating backward from the most profitable items down to the least, we simply buy whatever we can afford with our remaining budget.

Approach

1. The Power of Two Trick

This is an amazing problem, and there is a brilliant catch! When you see "0-1 Knapsack", your brain immediately jumps to complex Dynamic Programming. But look closely at the profit: 2^i. Think of a situation where you are choosing between a $\$100$ bill or a handful of 1, 2, 5, and 10 bills. In binary math, 2^i is always strictly greater than the sum of all powers of two before it (2^4 > 2^3 + 2^2 + 2^1 + 2^0). Therefore, if we can afford item i, we should always buy it.

2. The Greedy Choice

Knowing this, we don't need DP. We just start at the end of the array (the items with the highest i and thus the highest profit) and work our way backward to 0. If our current budget x is greater than or equal to cost[i], we buy it! We subtract the cost from our budget, and add 2^i to our total profit (making sure to use modulo 10^9+7 to prevent massive number overflows).

Time Complexity

Time: O(N)- We only need to iterate through the list of items once, from right to left. Calculating the power of 2 can be done as we go or via fast exponentiation.
Space: O(1) - We only use a few variables to track the budget and the profit.

#include <iostream>
#include <vector>

using namespace std;

long long p2(int p) {
    long long res = 1, base = 2, mod = 1e9+7;
    while (p > 0) {
        if (p % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        p /= 2;
    }
    return res;
}

long long maxProf(vector<int>& c, int x) {
    long long ans = 0, mod = 1e9+7;
    for (int i = c.size() - 1; i >= 0; i--) {
        if (x >= c[i]) {
            x -= c[i];
            ans = (ans + p2(i)) % mod;
        }
    }
    return ans;
}

int main() {
    vector<int> c = {10, 20, 14, 40, 50};
    cout << maxProf(c, 70) << endl; 
    return 0;
}

ADD REPLY • link

Entering edit mode

Question 1: Faulty Server Replacement

Faulty Server Replacement Solution

Topics Involved / Prerequisites

Hash Maps (Dictionaries)
String Parsing
Simulation

Overview

We need to track the consecutive error count for each individual server as we read through the logs chronologically.
A hash map is the perfect tool to link each unique server ID directly to its current consecutive error streak.
Whenever a server's streak hits three, we log a replacement and immediately reset its error count back to zero.

Approach

1. Tracking the Streaks

This is a neat little problem! There’s a small catch—if you spot it, the logic falls right into place. Think of a situation where you are a bouncer keeping an eye on misbehaving guests. You don't care about their total lifetime mistakes; you only care if they mess up three times in a row. We can use a hash map to keep a running tally of consecutive errors for each server ID.

2. Parsing and Resetting

As we loop through the logs, we split the string into the server_id and the status. If the status is an error, we add 1 to that server's tally in the map. If the tally reaches 3, we've found a faulty server! We increment our total replacement counter and reset that specific server's tally back to 0. Crucially, if a server logs a "success", we must also reset its error tally to 0, breaking the consecutive streak.

Code Implementation

function countReplacements(n, logs):
    create a hash map 'errorCount' (string to integer)
    replacements = 0
    
    for each log in logs:
        // Split the log string by space
        serverId = getFirstWord(log)
        status = getSecondWord(log)
        
        if status == "error":
            errorCount[serverId] = errorCount[serverId] + 1
            
            // Check if it reached the faulty threshold
            if errorCount[serverId] == 3:
                replacements = replacements + 1
                errorCount[serverId] = 0 // Reset after replacement
        else:
            // A success breaks the consecutive error streak
            errorCount[serverId] = 0
            
    return replacements

ADD COMMENT • link