Basu
BAN USER- 0of 0 votes
AnswersGiven an arbitrary tree starting at “root” where each node contains a pair of values (x, y), write a boolean function find(Node root, int x, int y) that returns true iff
- Basu in United States
* x is equal to a value "x" of any node n1 in the tree
* and y is equal to a value "y" of any node n2 in the tree
* and both n1 and n2 are at the same level in the tree
boolean find(Node root, int x, int y)
Example:
(1,120)
/ | \
/ | \
/ | \
(5,15) (30,70) (80,110)
/ | \ |
/ | \ |
/ | \ |
(35, 40) (45,50) (55, 65) (90, 100)
boo == true
find(root, 45, 100) == true
find(root, 30, 100) == false
find(root, 30, 70) == true
find(root, 70, 30) == false| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm
#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;
bool IsMatchRegexSources(const char * regex1, const char * regex2)
{
if (!*regex2)
return !(*regex1);
if (regex2[1] == '*')
return IsMatchRegexSources(regex1, regex2 + 2) || ((*regex2 == '?' && *regex1) || (*regex1 == *regex2));
if (*regex2 == '?')
return *regex1 && IsMatchRegexSources(regex1 + 1, regex2 + 1);
if (*regex2 == '*')
return *regex1 && *regex2;
return (*regex1 == *regex2) && IsMatchRegexSources(regex1 + 1, regex2 + 1);
}
int main()
{
IsMatchRegexSources("abc", "a?c") ? cout << "TRUE" << endl : cout << "FALSE" << endl;
IsMatchRegexSources("abc", "a*?c") ? cout << "TRUE" << endl : cout << "FALSE" << endl;
IsMatchRegexSources("abc", "*") ? cout << "TRUE" << endl : cout << "FALSE" << endl;
IsMatchRegexSources("abc", "?c") ? cout << "TRUE" << endl : cout << "FALSE" << endl;
return 0;
}
/*
It is presidential election time.Mr X is fighting for the president.The country has N number of cities.
The cities are divided into developed & developing city on basis of a developemt index A.
If A is 1, then the city is developed. If A is 0, then the city is developing.
A close source to Mr X told that all the people from developing cities will vote for him while people
from only k number of developed cities will vote for him.
Find out the no of maximum vote in favour & minimum vote in against Mr X will get.
Input
------
10 3
0 12
0 6
0 7
1 8
1 12
1 17
1 20
1 22
1 5
1 6
First 2 line gives no of cities N= 10 & number of developed cities vote for Mr X k= 3
Next 10 lines give the development index A & number of people in the city
For example in the first line A= 0, no of people= 12
Algorithm -
1) Build the rank of residents by sorting the lines
2) Used quick sort to do that
3) Finally, computed the max & min votes prediction
Test Cases -
If all developing cities will vote for Mr X, then he has 25 certain votes.
From the developed cities, 3 of them are going to vote for Mr X.
If we order the developed cities according to their number of votes, we will have the following array: 5,6,8,12,17,20,22.
The maximum number of votes for Mr X will be:
the number of certain votes plus the votes of the 3 biggest cities 25 +(17+20+22)=84
The minimum votes against Mr X are: (Total Votes) - (Max Votes for Mr X) = 115-84 = 31
Time & Space complexity
O(LogN)
O(N) - Auxilary Array
*/
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
typedef struct city_developed
{
int No_Of_City;
int No_Of_DevelopedCity_vote;
};
typedef struct development_index
{
int index;
int No_of_resident;
};
void printPresidentVotePrediction(city_developed city_developed_arr, development_index *development_index_arr, int development_index_arr_size, int *rank)
{
int total_certain_votes = 0, total_developed_votes = 0, total_votes = 0;
for (int i = 0; i < development_index_arr_size; i++)
{
if (development_index_arr[i].index == 0)
total_certain_votes += development_index_arr[i].No_of_resident;
total_votes += development_index_arr[i].No_of_resident;
}
for (int i = 0; i < city_developed_arr.No_Of_DevelopedCity_vote; i++)
{
total_developed_votes += rank[i];
}
cout << "The maximum number of votes for Mr X will be : the number of certain votes plus the votes of the 3 biggest cities = " << (total_certain_votes + total_developed_votes) << endl;
cout << "The minimum votes against Mr X are: (Total Votes) - (Max Votes for Mr X) = " << (total_votes - (total_certain_votes + total_developed_votes)) << endl;
}
// Function for comparing two students according
// to given rules
int compareTwoCity(const void* a, const void* b)
{
development_index *I1 = (development_index*)a;
development_index *I2 = (development_index*)b;
// If No_of_resident are not same then returns true for higher total
return (I2->No_of_resident - I1->No_of_resident);
}
// Fills ranks of all city residents
void computeRanks(development_index *a, int n, int *rank)
{
// Sort structure array using user defined
// function compareTwoCity()
qsort(a, n, sizeof(development_index), compareTwoCity);
// Assigning ranks after sorting
for (int i = 0, j = 0; i<n; i++, j++)
rank[j] = a[i].No_of_resident;
}
// Driver program to test above functions
int main()
{
city_developed city_developed_arr = { 10, 3 };
development_index development_index_arr[] = { {0,12}, {0,6}, {0,7}, {1,8}, {1,12}, {1,17}, {1,20}, {1,22}, {1,5}, {1,6} };
int development_index_arr_size = sizeof(development_index_arr) / sizeof(development_index_arr[0]);
int rank[sizeof(development_index_arr) / sizeof(development_index_arr[0])] = { 0 };
computeRanks(development_index_arr, development_index_arr_size, rank);
// Print ranks after sorting
/*for (int i = 0; i<sizeof(rank) / sizeof(rank[0]); i++)
cout << rank[i] << endl;*/
printPresidentVotePrediction(city_developed_arr, development_index_arr, development_index_arr_size, rank);
getchar();
return 0;
}
- Basu May 08, 2017#include<iostream>
using namespace std;
void ContinuousSequence(int *sequence, int length, int sum)
{
bool flag = false;
if (!sequence || length < 0)
return;
int curSum = sequence[0], start = 0, end, i;
for (i = 1; i <= length; i++)
{
while (curSum > sum && start < i - 1)
{
curSum -= sequence[start];
start++;
}
if (curSum == sum)
{
flag = true;
end = i - 1;
}
if (i< length)
curSum += sequence[i];
}
if (flag)
{
cout << "\nThere is a Continuous Sequence to targeted Sum" << endl;
for (int i = start; i <= end; i++)
cout << sequence[i] << endl;
}
else
cout << "\nThere is no Continuous Sequence to targeted Sum" << endl;
cout << endl;
}
int main()
{
int sequence[] = { 23, 5, 4, 7, 2, 11 };
int length = sizeof(sequence) / sizeof(sequence[0]);
ContinuousSequence(sequence, length, 20);
}
- Basu March 16, 2016write a function that calculates the minimum number of meeting rooms that can accommodate given schedules
input: same
output: # of rooms
Also back to back events are allowed e.g. {2,5} {5,9} correct o/p:1
#include <iostream>
#include <algorithm>
using namespace std;
struct Schedule{
int start;
int end;
};
// Compares two intervals according to their staring time.
// This is needed for sorting the intervals using library
bool compareInterval(Schedule i1, Schedule i2)
{
return (i1.start < i2.start);
}
int count_meeting_rooms(Schedule* input, int len)
{
// sort the intervals in increasing order of start time
sort(input, input + len, compareInterval);
// rooms_needed indicates number of meeting rooms needed at a time
int rooms_needed = 1, result = 1;
int i = 1, j = 0;
// Similar to merge in merge sort to process all events in sorted order
while (i < len && j < len)
{
// If next event in sorted order is start time, increment count of
// rooms needed
if (input[i].start < input[j].end)
{
rooms_needed++;
i++;
if (rooms_needed > result) // Update result if needed
result = rooms_needed;
}
else // Else decrement count of rooms needed
{
rooms_needed--;
j++;
}
}
return result;
}
int main()
{
Schedule arr[] = { { 2, 5 }, { 5, 9 }, { 3, 4 } };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The Number of meeting rooms required to accomodate the schedules is - " << count_meeting_rooms(arr, n)<<endl;
return 0;
}
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
void ScheduleTaskWithColdTime(char *sequence, int sizeSeq, int coldTime)
{
char wait = '_';
int j = 0, count = 0;
char matchChar;
// Create an empty queue of strings
queue<char> q;
for (int i = 1; i < sizeSeq; i++)
{
matchChar = sequence[j];
if (sequence[i] != sequence[j])
{
swap((sequence + i), (sequence + ++j));
j++;
}
}
for (int j = 0; j <= sizeSeq; j++)
{
q.push(sequence[j]);
count++;
if (count == coldTime && j < sizeSeq)
{
q.push(wait);
count = 0;
}
}
while (!q.empty())
{
cout << q.front();
q.pop();
}
cout<<"\nModified Sequence is - "<<sequence<<endl;
}
/* Driver program to test above functions */
int main()
{
char str[] = "AAABBB";
int n = strlen(str);
ScheduleTaskWithColdTime(str, n - 1, 2);
return 0;
}
}
- Basu May 11, 2017