3
\$\begingroup\$

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/

There are N workers. The i-th worker has a quality[i] and a minimum wage expectation wage[i].

Now we want to hire exactly K workers to form a paid group. When hiring a group of K workers, we must pay them according to the following rules:

  1. Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
  2. Every worker in the paid group must be paid at least their minimum wage expectation.

Return the least amount of money needed to form a paid group satisfying the above conditions.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], K = 2
Output: 105.00000
Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.

Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
Output: 30.66667
Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately. 

Note:

  1. 1 <= K <= N <= 10000, where N = quality.length = wage.length
  2. 1 <= quality[i] <= 10000
  3. 1 <= wage[i] <= 10000
  4. Answers within \$10^{-5}\$ of the correct answer will be considered correct.

This is one of the hardest problems I met on leetcode

Please review the code as if this was 45 minute interview. Performance is the main issue here. this solution is same as the leetcode solution, I have one question also is why not use use maxHeap and do the "trick" of multiplying the quality with -1, before pushing into the heap?

using System;
using Heap;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/minimum-cost-to-hire-k-workers/
    /// </summary>
    [TestClass]
    public class MinimumCostToHirekWorkers
    {
        [TestMethod]
        public void MinCost2()
        {
            int[] quality = { 10, 20, 5 };
            int[] wage = { 70, 50, 30 };
            int k = 2;

            Assert.AreEqual(105.0, MincostToHireWorkersHeap(quality, wage, k));

        }

        [TestMethod]
        public void MinCost3()
        {
            int[] quality = { 3, 1, 10, 10, 1 };
            int[] wage = { 4, 8, 2, 2, 7 };
            int k = 3;

            Assert.AreEqual(30.66667, MincostToHireWorkersHeap(quality, wage, k), 0.001);

        }



        public double MincostToHireWorkersHeap(int[] quality, int[] wage, int K)
        {
            Worker[] workers = new Worker[quality.Length];
            for (int i = 0; i < quality.Length; i++)
            {
                workers[i] = new Worker(quality[i], wage[i]);
            }
            //we sort the workers by their ratio, low ratio X low quality == low cost
            Array.Sort(workers);
            double ans = double.MaxValue;

            int sumq = 0;
            BinaryHeap heap = new BinaryHeap((uint)quality.Length);
            foreach (var worker in workers)
            {
                //we push into the min heap the negative value of quality
                // this is a max heap after that
                heap.InsertKey(-1 * worker.Quality);
                sumq += worker.Quality;
                //if we have more than k we will remove the biggest negative value
                // which is the height quality
                if (heap.Count > K)
                {
                    sumq += heap.ExtractMin();
                }

                // we compute the sum with this worker ratio
                if (heap.Count == K)
                {
                    ans = Math.Min(ans, sumq * worker.Ratio);
                }
            }

            return ans;
        }
    }

    public class Worker : IComparable<Worker>
    {
        public int Quality;
        public int Wage;

        public Worker(int q, int w)
        {
            Quality = q;
            Wage = w;
        }
        public double Ratio
        {
            get { return (double)Wage / Quality; }
        }

        public int CompareTo(Worker other)
        {
            if (Ratio > other.Ratio)
            {
                return 1;
            }
            if (Ratio < other.Ratio)
            {
                return -1;
            }
            return 0;
        }
    }
}

This is the code for the MinHeap no need to review it, I assume that you don't need to implement this is a 45 minutes interview

 public class BinaryHeap
    {
        private readonly int[] _harr;// pointer to array of elements in heap
        private readonly uint _capacity; // maximum possible size of min heap
        public uint _heapSize; // Current number of elements in min heap

        public BinaryHeap(uint capacity)
        {
            _capacity = capacity;
            _heapSize = 0;
            _harr = new int[capacity];
        }

        public void InsertKey(int key)
        {
            if (_heapSize == _capacity)
            {
                throw new StackOverflowException("overflow can't insert key");
            }

            //insert the new key at the end
            _heapSize++;
            uint i = _heapSize - 1;
            _harr[i] = key;

            //fix the heap  as min heap
            // Fix the min heap property if it is violated
            while (i != 0 && _harr[Parent(i)] > _harr[i]) //bubble is generic specific
            {
                Swap(i, Parent(i));
                i = Parent(i);
            }
        }

        /// <summary>
        /// This function deletes key at index i. It first reduced value to minus
        /// infinite, then calls extractMin()
        /// </summary>
        public void DeleteKey(uint i)
        {
            DecreaseKey(i, Int32.MinValue);
            ExtractMin();
        }

        public void DecreaseKey(uint i, int newValue)
        {
            _harr[i] = newValue;
            while (i != 0 && _harr[Parent(i)] > _harr[i]) //bubble is generic specific
            {
                Swap(i, Parent(i));
                i = Parent(i);
            }
        }
        /// <summary>
        /// you switch the root with the last index in the array, the end of the heap
        /// and you heapify the root node.
        /// </summary>
        /// <returns></returns>
        public int ExtractMin()
        {
            if (_heapSize <= 0)
            {
                return Int32.MaxValue;
            }
            if (_heapSize == 1)
            {
                _heapSize--;
                return _harr[0];
            }

            // Store the minimum value, and remove it from heap
            int root = _harr[0];
            _harr[0] = _harr[_heapSize - 1];
            _heapSize--;
            Heapify(0);
            return root;
        }
        /// <summary>
        /// the first call is done with index 0,
        /// since this is recursive function you compare to right subtree and left subtree
        /// you choose the lower node and swap the root with it, than you call
        /// the same function from the last index you swapped with
        /// </summary>
        /// <param name="i"></param>
        private void Heapify(uint i)
        {
            uint l = Left(i);
            uint r = Right(i);
            uint smallest = i;
            if (l < _heapSize && _harr[l] < _harr[i])
            {
                smallest = l;
            }
            if (r < _heapSize && _harr[r] < _harr[smallest])
            {
                smallest = r;
            }
            if (smallest != i)
            {
                Swap(i, smallest);
                Heapify(smallest);
            }
        }

        private uint Right(uint i)
        {
            return 2 * i + 2;
        }

        private uint Left(uint i)
        {
            return 2 * i + 1;
        }

        private uint Parent(uint i)
        {
            return (i - 1) / 2;
        }

        private void Swap(uint key1, uint key2)
        {
            int temp = _harr[key2];
            _harr[key2] = _harr[key1];
            _harr[key1] = temp;
        }

        public int GetMin()
        {
            return _harr[0];
        }
        public uint Count
        {
            get { return _heapSize; }
        }
    }
\$\endgroup\$
  • \$\begingroup\$ "this solution is same as the leetcode solution, I have one question" - so is this your code? \$\endgroup\$ – vnp May 23 at 0:30
  • \$\begingroup\$ Yes this is my code \$\endgroup\$ – Gilad May 23 at 3:31
  • 1
    \$\begingroup\$ Worker.CompareTo does not check if other is null. Also, you could simply defer to double's CompareTo as in return Ratio.CompareTo(other.Ratio). \$\endgroup\$ – Rick Davin May 23 at 15:00
4
\$\begingroup\$

Please review the code as if this was 45 minute interview.

I don't know what you expect from answerers with this statement. The evaluation of some code produced within 45 minutes is subjective, highly dependent on the company and position, and dozens of other factors. Whether a reviewer says "good job in 45 minutes" or "poor job in 45 minutes", I think it's going to be meaningless.

I suggest to focus on writing the best possible code, and post just that. By doing this exercise a lot, your performance within 45 minutes will also naturally improve. And performance within 45 minutes is never the end goal anyway for any job.

I have one question also is why not use use maxHeap and do the "trick" of multiplying the quality with -1, before pushing into the heap?

I don't understand this question. But maybe I can still help. Consider a heap as a collection + a comparator function. Then there is no more "max heap" and "min heap", simply a heap, where the top element is determined by the function.

The "trick" of multiplying elements by -1 seems fragile to me. I think the implied context here is that the elements are numbers, and the comparator function is the natural ordering of numbers. As such, the behavior is a "min heap": the element is the smallest one. If you insert values multiplied by -1, and then when you remove the top element and multiply it by -1, it has the effect as if the behavior is changed to a "max heap".

I find this fragile because you have to remember to multiply values when adding and removing. Such behavior is best encapsulated somewhere. And that's what the comparator function can do for you. Using an appropriate comparator function will allow you to use the heap naturally, adding and removing values without extra manipulation.

Improving Worker

Wage is only used to compute Ratio. The ratio is recomputed every time Ratio is called. It would be better to compute the ratio ones, store it, and drop the Wage field.

Where to put the comparator logic?

In the posted code the comparator logic is in the Worker. And that's fine, the program works. But is this ordering an inherent property of the Worker? Not really. On the other hand, it's a crucial piece to understanding how the solution works. So instead of the comment at Arrays.Sort, I would define the sorting function there. It would make the solution easier to read and understand, the comment would become unnecessary, and if later you need another kind of sorting of workers, you will be free to define a different appropriate comparator.

Getting rid of if (heap.Count == K)

I think it's a code smell when a condition in a loop will be false for the first couple of values, and then always true. It would be better to reorganize the code to avoid unnecessary evaluations.

Consider this alternative:

  • add to heap the first K values
  • compute sumq as the sum of the first K values
  • initialize minCost as sumq multiplied by the ratio of the K-th worker
  • loop from K until the last worker
    • add to heap the quality q of the current worker
    • sumq += q - heap.poll() (this assumes that the ordering of heap is defined as the reverse of natural ordering (largest number on top), and that quality values are added as they are, without multiplying by -1)
    • minCost = Math.Min(minCost, sumq * worker.Ratio)

Notice that in this alternative organization there is no more need for the useless assignment double ans = double.MaxValue; (and I renamed ans to minCost).

A word on BinaryHeap

This is the code for the MinHeap no need to review it

If no need to review it, then it would have been better to post just the definition of the interface. And I think it would have guided you in a good direction. For example, even in this text, you refer to it as "MinHeap", but the class is actually called "BinaryHeap", which is an implementation detail, irrelevant in the implementation of the solution.

\$\endgroup\$
  • \$\begingroup\$ thanks for your great reviews, I will give it another try! \$\endgroup\$ – Gilad May 26 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.