deepak_gta
BAN USERExactly. We need to write a Abstract Storage Class from which DBStorage and FileStorage are inherited, Then by using Factory class on top of it to determine which function to invoke during run time from Singleton Logger class.
- deepak_gta July 30, 2014Please Explain me whats the purpose of searching in the right subtree if the remaining sum is already less than the current node. As per BST, only the elements greater than should be on the right. can you explain with an example?
Say for Example, we have a BST
5
3 6
And the sum we are searching for is 9, we come to root and the remaining sum will be 9 -5 = 4, then we search it in the left subtree to get the pathcount or no pathcount. We dont need to search in the right subtree since no elements greater than 5 can be present.
- deepak_gta June 23, 2014Dude. I have a quick question. As per requirements, we are supposed to print the outline elements and not the inner elements in the loop. When i run through your program, I am able to Print - ADHIJEFGC. Here, E should not be printed. Please correct me if i am wrong.
- deepak_gta June 19, 2014Bad Complexity. You can better it by using a count Array.
- deepak_gta June 17, 2014Good catching on the corner case where we should consider only the unique elements in each string for the count array.
- deepak_gta June 17, 2014This program works for all the cases and TC is O(N) and SC = N
Input:
aaab
ab
b
O/P: 1
VisitedArray is used to identify only the unique elements in each string.
#include<iostream>
using namespace std;
// Function to find the common characters
int CommonCount( char input[100][100], int m)
{
//Count Array to track the count of each characters
// a to z only has 26 characters
int charcount[26];
bool visited[26];
for(int k =0;k<26;k++)
{
charcount[k] = 0;
visited[k] = false;
}
//set Variables
int count = 0, i = 0, j = 0, index = 0, avalue = 'a';
while(i<m)
{
while(input[i][j] != '\0')
{
index = input[i][j];
index = index%avalue;
if(visited[index] == false)
{
charcount[index] ++;
visited[index] = true;
}
j++;
}
for(int k=0;k<26;k++) visited[k] = false;
i++;
j=0;
}
//Count the common characters
for(int k=0;k<26;k++)
{
if(charcount[k] == m) count++;
}
return count;
}
int main()
{
char input[100][100] = {"aaab","ab","b"};
cout<<CommonCount(input, 3);
return 0;
}
There is no right answer for this and its a thought provoking question.
There are many variables and many assumptions to be made.
Assumptions:
1. Each car is of length 1 and Speed 1.
2. Assumed the Lane is finite (like 10 meters, so 10 slots and only up to 10 cars at a time)
3. The Frog will jump in to the first empty spot in Lane 1.
4. The Jump/Wait will take time-1.
5. The frog can jump both backwards or forwards.
Algorithm:
1. Jump in to the first empty spot(say slot-3) in Lane 1
2. See if the previous spot in the next lane is empty( slot-2 in Lane-2), then Jump
Else if (see if there is a vehicle behind frog in the current lane) then Jump back
Else wait
3. Keep adding the Lanes in the Queue as we progress and Do BFS.
4. If the Current Lane is destination, then get out of the loop
#include<iostream>
using namespace std;
int QCnt = 0;
void ADDval(char Input[], int flag, int Count)
{
int i = 0;
int Val = QCnt - Count;
while(Input[i] != '\0')
{
if(Input[i] == '?' || Input[i] == '0' || Input[i] == '1')
{
if(Val == 0)
{
Input[i] = flag + '0';
break;
}
else Val --;
}
i++;
}
}
int CountQ(char Input[])
{
int i = 0;
int cnt = 0;
while(Input[i] != '\0')
{
if(Input[i] == '?')
{
cnt++;
}
i++;
}
return cnt;
}
void ProcessString(char Input[],int Count)
{
if(Count == 0)
{
cout<<Input<<endl;
}
else if(Count > 0)
{
ADDval(Input,0,Count);
ProcessString(Input,Count-1);
ADDval(Input,1,Count);
ProcessString(Input,Count-1);
}
}
int main()
{
char Input[] = {"a?b?c?"};
int length = sizeof(Input)/sizeof(Input[0]);
QCnt = CountQ(Input);
ProcessString(Input,QCnt);
getchar();
return 0;
}
I think the complexity is O(2^N).
Can someone confirm this?
@Ajeet FYI: Linear Probing worst case is O(N) but i agree that Average Case is O(1) since even Hashtable itself works on Average cases( Search AVG: O(1), Worst: O(N) due to collision or probing)
- deepak_gta August 07, 2014