Original Source Here
Question 2: Maximum Number of Balls in a Box, by Microsoft
– You are working in a ball factory where you have n balls numbered from lowLimit up to highLimit inclusive (i.e., n == highLimit — lowLimit + 1), and an infinite number of boxes numbered from 1 to infinity.
– Your job at this factory is to put each ball in the box with a number equal to the sum of digits of the ball’s number. For example, the ball number 321 will be put in the box number 3 + 2 + 1 = 6 and the ball number 10 will be put in the box number 1 + 0 = 1.
– Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls.
– Input: lowLimit = 1, highLimit = 10
— Output: 2
Box Number: 1 2 3 4 5 6 7 8 9 10 11 …
Ball Count: 2 1 1 1 1 1 1 1 1 0 0 …
— Box 1 has the most number of balls with 2 balls.
Walk Through My Thinking
Microsoft includes this question.
Honestly, it doesn’t make any sense and takes me a few minutes to get the gist. A quick translation is in order.
1. Iterate over the range from lowLimit to highLimit
2. Calculate the digit sum for each number
3. Count the number of occurrences for each position
In step 1, we iterate over the range(lowLimit, highLimit+1) in a for loop. As a note, we have to add 1 to highLimit for its inclusion; otherwise, we exclude the upper bound.
In step 2, we transform elements into strings and iterate over the digits. Remember, an integer object is not iterable, so convert it into a string; change it back to integer for mathematic calculations.
In step 3, we create a new dictionary to store the key-value pairs: assign 0 for the first occurrence and increment the value by 1 for repeated occurrences.
- An integer object can not be iterable, and we need to convert it into a string for accessing.
- Change the data type back to integer for mathematic calculations, if needed.
Question 3: Relative Sort Array, by Amazon
– Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.
– Sort the elements of arr1 such that the relative ordering of items in arr1 is the same as in arr2. Elements that don’t appear in arr2 should be placed at the end of arr1 in ascending order.
— Example 1:
— Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
— Output: [2,2,2,1,4,3,3,9,6,7,19]
Walk Through My Thinking
Amazon asks this question.
There are two parts to the question.
1. Sort the shared elements in arr1 & arr2 and keep the relative order as in arr1.
2. Rank elements not in arr2 in ascending order.
Let’s solve the first part. It’s relatively easy to keep the original ordering as in arr2, and the tricky part is that some elements appear more than once.
How can we keep these duplicate elements in the original order?
Here is how. We count the occurrences for each element and multiply them by the elements in arr2, which allows us to count the time of occurrences while keeping the original order.
It’s OK to take some time to figure it out as it takes me several rounds of trials and errors.
To solve the second part, we group and sort elements in arr1 that do not appear in arr2.
Finally, combine the results from part 1 and part 2, and we are done.
[2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]
- Understand the differences between extend() and append().
- Use a dictionary to store the occurrences of values.
- collections.Counter() is useful for counting.
Trending AI/ML Article Identified & Digested via Granola by Ramsey Elbasheer; a Machine-Driven RSS Bot