Vistaprint Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
This is an 2D bin packing problem.
Bin packing is known as a NP-hard problem. We can use heuristic/approximation algorithms to solve it: first fit, next fit, best fit,...
Well you have a fixed width and height for the paper, why would you try to guess fits? You just need to know how much surface you need to cover by making the total surface of the array of papers and then divide it by the surface occupied by one sheet of paper of width xx and height yy.
#include <iostream>
#define SIZE _whatever_number_you_like
struct paper{
string name;
int width;
int height;
} array[SIZE];
int numberOfSheets(int xx,int yy){
int surface = 0;
for(int i=0;i<SIZE;i++)
surface += array[i].width*array[i].height;
return (int)surface/xx*yy;
}
Time Complexity: O(SIZE)
Space Complexity: O(1)
(Sorry for the edit, I forgot to preserve the whitespace)
You underestimate the answer.
Look at this example:
Products' size: 4x4, 5x1
Paper size: 4x6
#include <iostream>
- Anonymous October 24, 2014#define SIZE _whatever_number_you_like
struct paper{
string name;
int width;
int height;
} array[SIZE];
int numberOfSheets(int xx,int yy){
int surface = 0;
for(int i=0;i<SIZE;i++)
surface += array[i].width*array[i].height;
return (int)surface/xx*yy;
}
Time Complexity: O(SIZE)
Space Complexity: O(1)