Amazon wants to implement a new backup system, in which files are stored into data tapes.


  • 4
    T

    Coding exercise:


    Amazon wants to implement a new backup system, in which files are stored into data tapes. This new system must follow the following 2 rules:

    • Never place more than two files on the same tape.
    • Files cannot be split across multiple tapes.

    It's guaranteed that all tapes have the same size and that they will always be able to store the largest file.

    Every time this process is executed, we already know the size of each file, and the capacity of the tapes. Having that in mind, we want to design a system that is able to count how many tapes will be required to store the backup in the most efficient way.

    The parameter of your function will be a structure that will contain the file sizes and the capacity of the tapes. You must return the minimum amount of tapes required to store the files.



    Example:


    Input: Tape Size = 100; Files: 70, 10, 20

    Output: 2


  • 0
    P
      public static int getNumTapesRequired(int tapeCapacity, int[] filesWithSizes) {
        int tapeCounter = 0;
        PriorityQueue<Integer> minheap = new PriorityQueue<Integer>(filesWithSizes.length);
        PriorityQueue<Integer> maxheap = new PriorityQueue<Integer>(filesWithSizes.length,
            new Comparator<Integer>() {
    
              @Override
              public int compare(Integer o1, Integer o2) {
                return o2 - o1;
              }
            });
    
        for (int i = 0; i < filesWithSizes.length; i++) {
          if (filesWithSizes[i] >= tapeCapacity / 2)
            maxheap.add(filesWithSizes[i]);
          else
            minheap.add(filesWithSizes[i]);
        }
        if (minheap.size() == 0)
          return maxheap.size();
    
        int maxelesize = maxheap.size();
        boolean bpaired = false;
        Integer minele = minheap.remove();
        for (int i = 0; i < maxelesize; i++) {
          Integer maxele = maxheap.remove();
          if (maxele + minele <= tapeCapacity) {
            bpaired = true;
          }
          
          if (bpaired) {
            if (minheap.isEmpty())
              minele = tapeCapacity;
            else
              minele = minheap.remove();
            bpaired = false;
          }
          tapeCounter++;
        }
    
        int minremeles = minheap.size();
        if (!bpaired)
          minremeles += 1;
    
        tapeCounter = tapeCounter + minremeles / 2 + minremeles % 2;
    
        return tapeCounter;
    
      }

  • 11
    J

    I use two pointers to solve this issue.

    1. Sort the input as ascending
    2. assign two pointers i,j to first item & last item
    3. sum the i, j: if sum is less than capacity, then counter++; i++, j--, else j--
    4. loop with i <= j
    public static int GetMinimumTapeCount(List<int> files, int tapeCapacity)
            {
                //sort in ascending
                files.Sort(new MyComparer());
    
                int count = 0;
                int i = 0;
                int j = files.Count - 1;
    
    
                while (i <= j)
                {
                    //if the largest file is less than half of capacity
                    if (files[j] <= tapeCapacity / 2)
                    {
                        count += (j-i)/ 2 + 1;
                        break;
                    }
    
                    if (files[i] + files[j] <= tapeCapacity)
                    {
                        i++;
                        j--;
                    }
                    else
                        j--;
    
                    count++;
                }
    
                return count;
            }
    

  • 3
    L

    @tferreira Here is a simple Java solution. The idea is trying to combine the smallest and largest files into one tap at first. If their sum greater than tap size, then put largest one only and let high index -1; else low++ and high--.

        public int getMinTapCount(int tapSize, int[] fileSizes) {
            Arrays.sort(fileSizes);
            int tapCount = 0;
            for (int low = 0, high = fileSizes.length - 1; low <= high; ) {
                //Combine larger and smaller files into one tap.
                if (fileSizes[high] + fileSizes[low] <= tapSize) low++;
                high--;
                tapCount++;
            }
            return tapCount;
        }
    

  • 0
    This post is deleted!

  • 0
    U

    @laqxs the above algorithms have clear concept. however, they need to prove that they can find the optimum answer.


  • 0
    M

    @JohnsonJiang How to deal with the situation that files[j]>size and files[j]-size+files[i]<size?


  • 0
    I

    I wrote this and then realized it was a very similar concept to what praveenik wrote. I haven't really looked too closely at the differences other than to note the idea of splitting and putting in priority queues that pivot the midpoint is a similar theme.

    I don't know if this is the most efficient solution. popping and re-pushing the unused small priority queue elements seems like there might be an optimization there but I didn't put too much thought into it. I do believe it produces the correct answer.

    Basically you have to match the largest of elements that is greater than the midpoint collection with the largest element that is smaller that the midpoint that the sum doesn't exceed the size limit. Call it pair. pop them off the queues and move on. If no element is found in the smaller than midpoint collection then it has to go solo onto a tape. Once the large queue is emptied then whatever is left in the small priority queue can just be paired up with anything else in the small queue in no particular order. So you just pop off the remaining elements in pairs and add one to the tape count for each pair.

    // TestCase  returns 11;
    		TapeCount tc;
    		vector<int> sizes = {52, 30, 30, 1, 1, 1, 49, 52, 48, 52, 49, 51, 51, 48, 48, 49, 70, 80, 80, 80, 80};
    		tc.getCount(sizes, 100);
    
    class TapeCount{
    public:
    	int getCount(vector<int> sizes, int maxSize)
    	{
    		priority_queue<int> pqLarge;
    		priority_queue<int> pqSmall;
    		int TCount = 0;
    		int midpoint = ceil(maxSize / 2);
    		for (auto s : sizes) {
    			if (s < midpoint)
    			{
    				pqSmall.push(s);
    			}
    			else {
    				pqLarge.push(s);
    			}
    		}
    
    		queue<int> lq;
    		while (!pqLarge.empty())
    		{
    			int lTop = pqLarge.top();
    			bool paired = false;
    			while (!pqSmall.empty() && !paired)
    			{
    				int sTop = pqSmall.top();
    				if (lTop + sTop <= maxSize)
    				{
    					paired = true;
    					pqSmall.pop();
    					pqLarge.pop();
    					TCount++;
    				}
    				else {
    					lq.push(sTop);
    					pqSmall.pop();
    				}
    			}
    			while (!lq.empty())
    			{
    				pqSmall.push(lq.front());
    				lq.pop();
    			}
    
    			if (!paired) {
    				TCount++;
    				pqLarge.pop();
    			}
    		}
    
    		while (!pqSmall.empty())
    		{
    			pqSmall.pop();
    			pqSmall.pop();
    			TCount++;
    		}
    		return TCount;
    	}
    };
    

  • 0
    R
    This post is deleted!

  • 0
    R
    This post is deleted!

  • 1
    S

    @laqxs I'm trying to understand how does code takes care of the following condition mentioned in the problem, "Never place more than two files on the same tape.". ?


  • 0
    O

    I believe the algorithm described by praveenlk and intelzombi is correct. Using a priority queue is not optimal, however, as noted by intelzombi. I believe only C++ has the built-ins necessary to easily improve the running time, namely, the lower_bound function.

    #include <set>
    #include <vector>
    #include <algorithm>
    #include <functional>
    
    int getTapeCount(std::vector<int>& sizes, int tapeSize)
    {
        // Sort in descending order.
        std::sort(sizes.begin(), sizes.end(), std::greater<int>());
    
        // Find the files larger than tapeSize / 2.
        auto beginBig = sizes.begin();
        auto endBig = std::lower_bound(sizes.begin(), sizes.end(), tapeSize / 2,
            std::greater<int>());
    
        // Find the files less than or equal to tapeSize / 2.
        auto beginSmall = endBig;
        auto endSmall = sizes.end();
    
        // Create a red black tree of the small files so we can search in O(log n)
        // time.
        std::multiset<int, std::greater<int>> smallFiles(beginSmall, endSmall);
    
        // Pair the biggest file remaining with the largest small file remaining.
        int tapeCount = 0;
        for (; beginBig != endBig; ++beginBig)
        {
            const int fileSize = *beginBig;
    
            auto iterFind = smallFiles.lower_bound(tapeSize - fileSize);
            if (iterFind != smallFiles.end())
            {
                smallFiles.erase(iterFind);
            }
            ++tapeCount;
        }
    
        // The remaining small files can be paired.
        return tapeCount + (smallFiles.size() + 1) / 2;
    }
    
    void main()
    {
        std::vector<int> fileSizes = { 52, 30, 30, 1, 1, 1, 49, 52, 48, 52, 49, 51, 51, 48, 48, 49, 70, 80, 80, 80, 80, 50, 50 };
        const int tapeCount = getTapeCount(fileSizes, 100);
    }
    

  • 0
    G
    This post is deleted!

  • 0
    L

    @gui0506 See the rules below:

    • Never place more than two files on the same tape.
    • Files cannot be split across multiple tapes.

  • 0
    G

    @laqxs Ah, sorry I did not pay enough attention. I saw a similar problem before that does not have that constrain.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.