david.sanchez.plaza
BAN USERBrute force. Space O(1) Time i guess is O(n* m) being m the total depth
#include <iostream>
using namespace std;
// No idea why we cant calculate the size ourself :(, and we need to pass as parameter
int getMaximumDepth(int array[], int arraySize){
cout<<"getMaximumDepth start \n";
if(array == NULL){
return 0;
}
// int arraySize = sizeof(array)/sizeof(*array);
cout<<"arraySize" << arraySize << "\n";
int currentDept;
int maxDept = 1;
for(int i = 0; i < arraySize; i++) {
cout<<"i" << i << "\n";
cout<<"array[" << i << "] = " << array[i] << "\n";
currentDept = 1;
int parent = array[i];
while(parent != -1){
currentDept ++;
parent = array[parent];
}
cout<<"currentDept" << currentDept << "\n";
if(maxDept < currentDept){
maxDept = currentDept;
}
}
return maxDept;
}
int main()
{
int array [] = {3,3,3,-1,2,0,1,2,3,4};
int arraySize = sizeof(array)/sizeof(*array);
cout<<"arraySize" << arraySize << "\n";
cout<<"maxDept:" << getMaximumDepth(array, arraySize) << "\n";
return 0;
}
Brute force. Give all the water to the first one, and start overflowing
#include <iostream>
using namespace std;
class Glass {
public:
Glass *leftChild;
Glass *rightChild;
double maxQuantity;
double currentQuantity = 0;
int index;
Glass(){
}
Glass(int q, int i){
maxQuantity = q;
index = i;
}
double calculateWater(double water);
void setLeftChild(Glass *leftChild);
void setRightChild(Glass *rightChild);
void giveWater(double givenQuantiy);
};
double Glass::calculateWater(double water) {
//cout<<"Glass calculateWater() water " << water << "\n";
}
void Glass::setLeftChild(Glass *leftChild) {
this->leftChild = leftChild;
}
void Glass::setRightChild(Glass *rightChild) {
this->rightChild = rightChild;
}
void Glass::giveWater(double givenQuantiy) {
if(currentQuantity < maxQuantity){
if(givenQuantiy < maxQuantity - currentQuantity){
currentQuantity += givenQuantiy;
givenQuantiy = 0;
}else {
givenQuantiy -= (maxQuantity - currentQuantity);
currentQuantity = maxQuantity;
}
}
if(givenQuantiy <= 0)
return;
if(leftChild != NULL){
cout<<"Giving to " << leftChild->index << " " << givenQuantiy/2 << " liters\n";
leftChild->giveWater(givenQuantiy/2);
}
if(rightChild != NULL){
cout<<"Giving to " << rightChild->index << " " << givenQuantiy/2 << " liters\n";
rightChild->giveWater(givenQuantiy/2);
}
}
int main()
{
cout<<"Hello World \n";
int totalGlasses = 15;
double givenQuantiy = 6;
Glass * glasses [totalGlasses];
for (int i = 0; i < totalGlasses; i++){
Glass *glass = new Glass(i+1, i+1);
glasses[i] = glass;
}
int level = 1;
int currentLevelItems = 0;
for (int i = 0; i < totalGlasses; i++){
if(currentLevelItems >= level){
level++;
currentLevelItems = 0;
}
currentLevelItems ++;
if(i + level < totalGlasses)
glasses[i]->leftChild = glasses[i + level];
if(i + level + 1 < totalGlasses)
glasses[i]->rightChild = glasses[i + level + 1];
}
//Starts problem. We give the total quantity to first node. He will recursively give to childs
glasses[0]->giveWater(givenQuantiy);
for (int i = 0; i < totalGlasses; i++){
cout<<"Index: " << (i+1) << " - " << glasses[i]->currentQuantity << " liters.\n";
}
return 0;
}
My solution. We first need to generate all the possible windows of each string, and after SORTING, we will store it in a hashMap for each string.
Once we have all the possible windows, we need to check if any window from string1 is present on the hash of the second, and we return the biggest.
- david.sanchez.plaza September 03, 2017