Amazon OA SD1 Question and Answer

Round 1

Questions: Given a string org_code of size n representing the digits in decimal notation and integer k, find a string new_code representing the digits in decimal notation, which satisfies org_code <= new_code, and which is also attractive, given that there are no leading zeroes in the code.

A string S of size n representing the digits in decimal notation is lexicographically less than string P of length m if one of the two statements is correct:

1. n < m, and S is the beginning (prefix) of string P.
2. S[1] = P[1], S[2] = P[2], ..., S[k-1] = P[k-1], S[k] < P[k] for some k (1 <= k <= min(n, m)), here characters in strings are numbered starting from 1.

Example:

org_code = 1234
k = 2

Given org_code = 1234, where org_code / n = 4, and k = 2, the task is to find the smallest new_code such that it is greater than or equal to org_code and satisfies the attractiveness condition, meaning digits repeat every k positions.

First, take the first k digits from org_code (12) and repeat them to form the candidate new_code = 1212. Since 1212 is smaller than 1234, we increment the first two digits, resulting in 13, and repeat it to get new_code = 1313.

This new code is attractive because b[0] = b[2] = 1 and b[1] = b[3] = 3, and it also satisfies org_code <= new_code (as 1313 >= 1234). Thus, 1313 is the required new_code.

Input Format for Custom Testing:

1. The first line contains a string old_code.
2. The second line contains an integer k.

Sample Case 0:

Input:

41242
4

Output:

41244

Explanation: We need to find a new product code new_code greater than or equal to 41242 and attractive with k = 4. This means the first digit must be the same as the fifth digit (because 4 + 0 = 4).

We can change the last digit of 41242 from 2 to 4, resulting in 41244. This new code is still greater than 41242 and meets the attractiveness condition, as the first digit 4 matches the fifth digit 4.

Hence, 41244 is the smallest attractive integer new_code.

public String findSmallestAppealing(String old_code, int k) {
    if (k > old_code.length()) {
        return "";
    }

    String firstKChars = old_code.substring(0, k);
    StringBuilder result = new StringBuilder();
    while (result.length() < old_code.length()) {
        result.append(firstKChars);
    }

    result.setLength(old_code.length());

    if (result.toString().compareTo(old_code) >= 0) {
        return result.toString();
    }

    BigInteger firstKNum = new BigInteger(firstKChars);
    BigInteger incrementedNum = firstKNum.add(BigInteger.ONE);
    String newFirstKChars = String.format("%0" + k + "d", incrementedNum);

    if (newFirstKChars.length() > k) {
        result = new StringBuilder();
        while (result.length() < old_code.length()) {
            result.append(newFirstKChars.substring(0, k));
        }
    } else {
        result = new StringBuilder();
        while (result.length() < old_code.length()) {
            result.append(newFirstKChars);
        }
    }

    result.setLength(old_code.length());
    return result.toString();
}

Candidate's Approach

The candidate first checks if k is greater than the length of old_code, returning an empty string if true. They extract the first k characters from old_code and repeat them to form a candidate new_code. If this candidate is greater than or equal to old_code, it is returned. If not, the candidate is incremented, and the process is repeated to ensure the new_code is attractive.

Interviewer's Feedback

No feedback provided.

---