Recently HackerRank launched their own certifications. Among the tests they offer is "Problem Solving". The test contains 2 problems; they give you 90 minutes to solve them. Being inexperienced as I am, I failed, because it took me longer than that.
Specifically, I came up with the solution for the first problem (filled orders, see below) in, like 30 minutes, and spent the rest of the time trying to debugg it. The problem with it wasn't that the solution didn't work, but that it worked on only some of the test cases.
Out of 14 testcases the solution worked on 7 (including all the open ones and a bunch of closed ones), and didn't work on the remaining 7 (all closed). Closed means that the input data is not available, as well as expected output. (Which makes sense, because some of the lists there included 250K+ elements.)
But it drives me crazy; I can't figure out what might be wrong with it. I tried putting print statements all over the place, but the only thing I came to is that 1 too many elements get added to the list - hence, the last if statement (to drop the last added element), but it made no difference whatsoever, so it's probably wrong.
Here's the problem:
A widget manufacturer is facing unexpectedly high demand for its new product,. They would like to satisfy as many customers as possible. Given a number of widgets available and a list of customer orders, what is the maximum number of orders the manufacturer can fulfill in full?
Function Description
Complete the function filledOrders in the editor below. The function must return a single integer denoting the maximum possible number of fulfilled orders.
filledOrders has the following parameter(s):
order : an array of integers listing the orders
k : an integer denoting widgets available for shipment
Constraints
1 ≤ n ≤ 2 x 105
1 ≤ order[i] ≤ 109
1 ≤ k ≤ 109
Sample Input For Custom Testing
2
10
30
40
Sample Output
2
And here's my function:
def filledOrders(order, k):
total = k
fulf = []
for r in order:
if r <= total:
fulf.append(r)
total -= r
else:
break
if sum(fulf) > k:
fulf.pop()
return len(fulf)
9 Answers
Java Solution
int count = 0;
Collections.sort(order);
for(int i=0; i<order.size(); i++) {
if(order.get(i)<=k) {
count++;
k = k - order.get(i);
}
}
return count;
Code Revision
def filledOrders(order, k):
total = 0
for i, v in enumerate(sorted(order)):
if total + v <= k:
total += v # total stays <= k
else:
return i # provides the count
else:
return len(order) # was able to place all orders
print(filledOrders([3, 2, 1], 3)) # Out: 2
print(filledOrders([3, 2, 1], 1)) # Out: 1
print(filledOrders([3, 2, 1], 10)) # Out: 3
print(filledOrders([3, 2, 1], 0)) # Out: 0
Advanced Javascript solution :
function filledOrders(order, k) {
// Write your code here
let count = 0; let total=0;
const ordersLength = order.length;
const sortedOrders = order.sort(function(a,b) {
return (+a) - (+b);
});
for (let i = 0; i < ordersLength; i++) {
if (total + sortedOrders[i] <= k) {
// if all orders able to be filled
if (total <= k && i === ordersLength - 1) return ordersLength;
total += sortedOrders[i];
count++;
} else {
return count;
}
}
}
Python code
def filledOrders(order, k):
orderfulfilled=0
for i in range(1,len(order)):
m=k-order[i]
if(m>=0):
orderfulfilled+=1
k-=order[i]
return(orderfulfilled)
Javascript solution
Option1:
function filledOrders(order, k) {
let count=0;
let arr= [];
arr = order.sort().filter((item, index) => {
if (item<=k) {
k = k - item;
return item
}
})
return arr.length
}
Option2:
function filledOrders(order, k) {
let count=0;
for(var i=0; i<order.sort().length; i++) {
if(order[i]<=k) {
count++;
k = k - order[i]
}
}
return count;
}
C#
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
using System.Reflection.Metadata.Ecma335;
class Result
{
/*
* Complete the 'filledOrders' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER_ARRAY order
* 2. INTEGER k
*/
public static int filledOrders(List<int> order, int k)
{
if (order.Sum() <= k)
{
return order.Count();
}
else
{
int counter = 0;
foreach (int element in order)
{
if (element <= k)
{
counter++;
k = k - element;
}
}
return counter;
}
}
}
class Solution
{
public static void Main(string[] args)
{
int orderCount = Convert.ToInt32(Console.ReadLine().Trim());
List<int> order = new List<int>();
for (int i = 0; i < orderCount; i++)
{
int orderItem = Convert.ToInt32(Console.ReadLine().Trim());
order.Add(orderItem);
}
int k = Convert.ToInt32(Console.ReadLine().Trim());
var orderedList = order.OrderBy(a=>a).ToList();
int result = Result.filledOrders(orderedList, k);
Console.WriteLine(result);
}
}
I think, the better way to approach (to decrease time complexity) is to solve without use of sorting. (Ofcourse, that comes that cost of readability)
Below is a solution without use of sort. (Not sure if I covered all edge cases.)
import os, sys
def max_fulfilled_orders(order_arr, k):
# track the max no.of orders in the arr.
max_num = 0
# order count, can be fulfilled.
order_count = 0
# iter over order array
for i in range(0, len(order_arr)):
# if remain value < 0 then
if k - order_arr[i] < 0:
# add the max no.of orders to total
k += max_num
if order_count > 0:
# decrease order_count
order_count -= 1
# if the remain value >= 0
if(k - order_arr[i] >= 0):
# subtract the current no.of orders from total.
k -= order_arr[i]
# increase the order count.
order_count += 1
# track the max no.of orders till the point.
if order_arr[i] > max_num:
max_num = order_arr[i]
return order_count
print(max_fulfilled_orders([3, 2, 1], 0)) # Out: 0
print(max_fulfilled_orders([3, 2, 1], 1)) # Out: 1
print(max_fulfilled_orders([3, 1, 1], 2)) # Out: 2
print(max_fulfilled_orders([3, 2, 4], 9)) # Out: 3
print(max_fulfilled_orders([3, 2, 1, 4], 10)) # Out: 4
In python,
def order_fillers(order,k):
if len(order)==0 or k==0:
return 0
order.sort()
max_orders=0
for item in order:
if k<=0:
return max_orders
if item<=k:
max_orders+=1
k-=item
return max_orders
JavaScript Solution
function filledOrders(order, k) {
let total = 0;
let count = 0;
const ordersLength = order.length;
const sortedOrders = order.sort();
for (let i = 0; i < ordersLength; i++) {
if (total + sortedOrders[i] <= k) {
// if all orders able to be filled
if (total <= k && i === ordersLength - 1) return ordersLength;
total += sortedOrders[i];
count++;
} else {
return count;
}
}
}
// Validation
console.log(filledOrders([3, 2, 1], 3)); // 2
console.log(filledOrders([3, 2, 1], 1)); // 1
console.log(filledOrders([3, 2, 1], 10)); // 3
console.log(filledOrders([3, 2, 1], 0)); // 0
console.log(filledOrders([3, 2, 2], 1)); // 0
