Forum Posts
- 1 Answer variation of bin packing problem
We have “k” bins and “n” objects where each bin has same capacity and capacity is equal to sum of weights of all “n” objects divided by k.
- abhijeetnarkhede69198 December 11, 2014
We need to pack these all “n” items in “k” bins such a way that all bins are equally heavy.
some test cases –
input –
5 items { 2,3,4,5,7 }
and 3 bins
output –
{ {7},{5,2},{3,4} }
input –
6 items { 4,4,4,4,4,5 }
and 5 bins
output –
NOT POSSIBLE| Flag | PURGE - 0 Answers variation of bin packing problem
We have “k” bins and “n” objects where each bin has same capacity and capacity is equal to sum of weights of all “n” objects divided by k.
- abhijeetnarkhede69198 December 11, 2014
We need to pack these all “n” items in “k” bins such a way that all bins are equally heavy.
some test cases –
input –
5 items { 2,3,4,5,7 }
and 3 bins
output –
{ {7},{5,2},{3,4} }
input –
6 items { 4,4,4,4,4,5 }
and 5 bins
output –
NOT POSSIBLE| Flag | PURGE - 5 Answers variation of bin packing problem
We have “k” bins and “n” objects where each bin has same capacity and capacity is equal to sum of weights of all “n” objects divided by k.
- abhijeetnarkhede69198 December 11, 2014
We need to pack these all “n” items in “k” bins such a way that all bins are equally heavy.
some test cases –
input –
5 items { 2,3,4,5,7 }
and 3 bins
output –
{ {7},{5,2},{3,4} }
input –
6 items { 4,4,4,4,4,5 }
and 5 bins
output –
NOT POSSIBLE| Flag | PURGE - 1 Answer Recursion-
/*Imagine a robot sitting on the upper left comer of an X by Ygrid. The robot can only
- raady.rockcity December 11, 2014
move in two directions: right and down. How many possible paths are there for the
robot to go from (0, 0) to (X, Y) ?
Imagine certain spots are "off limits," such that the robot cannot step on them.
Design an algorithm to find a path for the robot from the top left to the bottom right.
*/
/*This solution will print the path in the reverse order */
/*What happens if there are two paths - This solution will not work ?*/
boolean canmove(x,y) {
if Valid(x,y) return TRUE:
else return FALSE;
}
boolean findpath(int x , int y, ArrayList<Coordinate> path) {
if(x == X-1) || (y ==Y+1){
path.add(Coordinate(x,y));
return TRUE;
}
else if( canmove(x+1,y) && !(canmove(x,y-1)){
if(findpath(x+1,y) {
path.add(x+1,y);
}
}
else if( canmove(x,y-1) && !(canmove(x+1,y)){
if(findpath(x+1,y) {
path.add(x,y-1);
}
}
else {
findpath(x+1,y) ;
findpath(x,y-1);
}
}| Flag | PURGE - 0 Answers CTCI Question 2.5 - add linked lists
The answer in the book is not terribly compact, especially for part 2. Here is a better version in C++.
- Aurelius December 07, 2014
Node * list_add(Node * pN0, Node * pN1)
{
Node * pNReturn = nullptr;
Node ** ppNNext = & pNReturn;
unsigned carry = 0;
while (pN0 != nullptr || pN1 != nullptr || carry > 0)
{
unsigned sum = carry;
if (pN0 != nullptr)
{
sum += pN0->data;
pN0 = pN0->next;
}
if (pN1 != nullptr)
{
sum += pN1->data;
pN1 = pN1->next;
}
if (sum >= 10)
{
sum -= 10;
carry = 1;
}
else
{
carry = 0;
}
*ppNNext = new Node;
(*ppNNext)->data = sum;
(*ppNNext)->next = nullptr;
ppNNext = &(*ppNNext)->next;
}
return pNReturn;
}
// helper function
Node * list_reverse(Node * pNHead)
{
Node * pNRet = pNHead;
if (pNHead != nullptr && pNHead->next != nullptr)
{
Node * pN0 = pNHead, * pN1 = pNHead->next;
pN0->next = nullptr;
while (pN1 != nullptr)
{
Node * pNHold = pN1->next;
pN1->next = pN0;
pN0 = pN1;
pN1 = pNHold;
}
pNRet = pN0;
}
return pNRet;
}
// Now part 2 becomes a piece of cake
Node * list_add2(Node * pNHead0, Node * pNHead1)
{
return list_reverse(list_add(list_reverse(pNHead0), list_reverse(pNHead1)));
}| Flag | PURGE - 4 Answers Binary Trees?
Take a list of integers (left to right order) and return an integer of the number of identical binary trees that can be created from the same list.
- A. December 04, 2014
Input: [10, 8, 15, 6, 9, 4, 5]
Output: 24
Input: [12, 6, 19, 15, 5]
Output: 6
Input: [44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64]
Output: 1
I wrote a brute-force 'solution', creating a binary tree for each permutation of the list (with the same root as Input list) and compared each to the binary tree from the Input list. For large input lists (length > 10), my 'solution' is way too slow.| Flag | PURGE - 2 Answers Combination
Suppose you are managing 16 employees, and you need to form three teams to work on different projects. Assume that all employees will work on a team, and that each employee has the same qualifications/skills so that everyone has the same probability of getting chosen. In how many different ways can the teams be chosen so that the number of employees on each project are as follows:
- nlavee December 01, 2014
8,4,4| Flag | PURGE