Panda Guru LogoPanda
Guru

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.