50 trucks with payload
Posted on October 7, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem : Given a fleet of 50 trucks, each with a full fuel tank and a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Assume all the payload will fit in one truck.
Solution : We want to use as little fuel as possible so we try minimize the number of trucks we use as we go along.
[Read More]Camel and Banana
Posted on October 7, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem : The owner of a banana plantation has a camel. He wants to transport his 3000 bananas to the market, which is located after the desert. The distance between his banana plantation and the market is about 1000 kilometer. So he decided to take his camel to carry the bananas. The camel can carry at the maximum of 1000 bananas at a time, and it eats one banana for every kilometer it travels.
[Read More]Red, Green and Yellow Balls - heavy and light
Posted on October 7, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : You are give two red balls, two green balls and two yellow balls. One ball from each color is heavier than the other one. All the heavier balls weigh the same and all the lighter balls weigh the same. You are only provided with a weighing balance. How many tries would it take to identify which one is heavier and which one is lighter?
Solution : Let’s label the balls R1, R2 (Red ones), G1, G2 (Green ones) and Y1, Y2 (Yellow ones).
[Read More]One duplicate , one missing element in an array
Posted on October 1, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
You have an array of size 100 which stores integers from 0 to 99.
In this array one number is a duplicate, that means one is missing.
How can we find duplicate and missing ?
Method 1
1. Since one element is missing , some element must be repeated once in the array.
2. Let x be the missing and y be the repeated element
3. Calculate the sum of all the elements and sum of squares of all the elements of array.
[Read More]Given numbers from 1 to N+1, with number being from 1 and N and one of the number being repeatative. Find the repeating element.
Posted on September 30, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?
[Read More]Find the smallest window in a string containing all characters of another string
Posted on September 30, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example
S = “ADOBECODEBANC”, T = “ABC”,
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string “”. If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
[Read More]Deleting a node in singly linked list if it is less than any of the successor nodes
Posted on September 26, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Hi, try with 1,7,0,10. output must be 10. but your…
Unknown - Jun 6, 2012
Hi,
try with 1,7,0,10.
output must be 10.
but your algorithm outputs wrong answer
it seems that algo is correct..
1,7,0,10
reverse
10 0 7 1
max_till_here= 10
0 < 10 delete 0
left : 10 7 1
7 < 10 : delete 7
1 < 10 : delete 1
output : 10
Deleting a node in singly linked list if it is less than any of the successor nodes
Posted on September 26, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Question : Given a link list of integers delete all nodes which have value smaller than the value of any following node.
**Example :**7 4 5 2 3 6
**Output : ** 7 6
Solution:
The solution is to :
1. Reverse the list
6 3 2 5 4 7
2. Delete all the elements which are below the max-till-now element.
eg. max-till-now=6….Delete all the elements below 6…till you find another max element = max-till-now = 7
[Read More]Duplicate removal in Binary Search Tree
Posted on September 26, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
#include <stdio.h\> class BinarySearchTree { private: int data; BinarySearchTree \*left, \*right; public: BinarySearchTree(const int d):data(d), left(NULL), right(NULL){} ~BinarySearchTree() { if(left !\= NULL) { delete left; } if(right !\= NULL) { delete right; } } //remove duplicates void removeDup() { if(left) { left\-\>removeDup(); left\-\>remove(data, this); } if(right) right\-\>removeDup(); } void remove(int value, BinarySearchTree \*parent) { if(value < data && left) { left\-\>remove(value, this); } else if(value \> data && right) { right\-\>remove(value, this); } else remove(parent); } void remove(BinarySearchTree \*parent) //remove this node { if(left \=\= NULL && right \=\= NULL) //leaf { ((parent\-\>left \=\= this) ?
[Read More]Squeeze all multiple spaces in a string into one space
Posted on September 26, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
#include <stdio.h>
void trimspace(char \*dst) {
const char \*src = dst;
int tocopy = 1;
char c;
while((c = \*src++)) {
if(tocopy)
\*dst++ = c;
tocopy = (c != ' ') || (\*src != ' ');
}
\*dst = '\\0';
}
int main() {
char s\[64\];
scanf("%\[^\\n\]c", s);
trimspace(s);
printf("%s\\n", s);
}