MIG
BAN USERTushar is solving totally different problem
i.e. arrayOne = {1,1,1};
i.e arrayTwo = {2,10, 13};
i.e arrayThree = {3,20, 23};
So Tushar's answer will give 1 1 and 1 but the question says "Find three numbers a, b, c from each of array A, B, C" a,b and c from each array. So the correct answer is 1 , 2 and 3
Voting -1.
// Here is the recursive logic
#include <iostream>
using namespace std;
#define EXACT_DOTS 3
#define MAX_GAP_BETWEEN_DOTS 3
//private
void generateIpV4(string& ipStr , string& opStr , int ipIndex , int opIndex, int dotCount , int prevDotPos)
{
if(opIndex - prevDotPos -1 <= MAX_GAP_BETWEEN_DOTS )
{
if(ipStr.size() + EXACT_DOTS == opIndex && dotCount == EXACT_DOTS)
{
cout<<"\n"<<opStr;
}
else
{
if(dotCount < EXACT_DOTS && prevDotPos + 2 <= opIndex)
{
opStr[opIndex] = '.';
opStr[opIndex + 1] = ipStr[ipIndex];
generateIpV4(ipStr , opStr , ipIndex + 1 , opIndex + 2 , dotCount + 1 , opIndex);
}
opStr[opIndex] = ipStr[ipIndex];
generateIpV4(ipStr , opStr , ipIndex + 1 , opIndex + 1 , dotCount , prevDotPos);
}
}
}
//public
void generateIpV4(string& ipStr)
{
if(ipStr.size() >= 4 && ipStr.size() <= 12)
{
// Just initializing a string with input size + exact number of dots
string opStr(ipStr + "...");
cout<<"\n\nGenerating IP addreses for "<<ipStr;
generateIpV4(ipStr , opStr , 0, 0, 0, -1);
}
else
cout<<"\n\nNo Ip addresses can be generated from string "<<ipStr;
}
int main()
{
string ip = "12345678";
generateIpV4(ip);
string ip1 = "1234";
generateIpV4(ip1);
string ip2 = "123";
generateIpV4(ip2);
string ip3 = "1234567812345678";
generateIpV4(ip3);
}
@ cnu. Question says "Tip: Just return the longest words which match, not all"
So what about input words { "bck" , "cab", "ack" , "back", "ackb", " abac","abba" }
Your code will only print:"back" but we need print all words for length 4 which can be made back , ackb , abac. Your code is incorrect.
Also to cater above case you can't do that in O(1) space complexity and if you can please present your solution.
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
#define topElemetsN 3
typedef string pattern;
typedef int patternCount;
typedef pair<pattern, patternCount> lookUp;
// Using > operator we can achieve min heap
// so we can pop minimum element so that we are left with
// Max n elements
bool compareLookUp(lookUp lhs , lookUp rhs)
{
return lhs.second > rhs.second;
}
void topElmentsPatternLengthK(vector<string> ip , int k)
{
unordered_map<pattern, patternCount> lookUpTable;
for(int i = 0 ; i < ip.size(); ++i)
{
for(int ss = 0 ; ss + k <= ip[i].size() ; ++ss)
{
// if there is not key than key is inserted and count is set as 0
++lookUpTable[ip[i].substr(ss,k)];
}
}
priority_queue<lookUp , vector<lookUp> , decltype(&compareLookUp) > topElements(&compareLookUp);
//Working out topElements
for(auto aPair : lookUpTable)
{
topElements.push(aPair);
//Keeping size not more than topElemetsN
if(topElements.size() > topElemetsN)
{
topElements.pop();
}
}
//Printing pairs
while(!topElements.empty())
{
cout<<topElements.top().first<<" ";
topElements.pop();
}
}
int main()
{
vector<string> strVec( { "xyzabcdef" ,
"zabcd",
"yzabcd",
"abcd"});
topElmentsPatternLengthK(strVec , 3);
return 0;
}
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct coOrdinates
{
int row;
int col;
coOrdinates(int i ,int j): row(i) , col(j){}
};
void printRegion(vector<vector<int> >& matrix , int row , int col)
{
queue<coOrdinates> q;
q.push(coOrdinates(row,col));
int i, j;
while(!q.empty())
{
i = q.front().row;
j = q.front().col;
q.pop();
if(i >= 0 && i< matrix.size() &&
j >= 0 && j< matrix[0].size() &&
matrix[i][j] != 0)
{
cout<<matrix[i][j]<<" ";
// Marking as visited
matrix[i][j] = 0;
// Top
q.push(coOrdinates(i+1 , j ));
// bottom
q.push(coOrdinates(i-1 , j ));
// Right
q.push(coOrdinates(i , j+1));
// left
q.push(coOrdinates(i , j-1));
}
}
}
void printRegions(vector<vector<int> >& matrix)
{
for(int i = 0 ; i < matrix.size() ; ++i)
{
for(int j = 0 ; j < matrix[0].size() ; ++j)
{
if(matrix[i][j] != 0)
{
cout<<"{ ";
printRegion(matrix , i , j);
cout<<"} ";
}
}
}
}
int main()
{
vector<vector<int> > matrix = {{0, 1, 0, 0, 3},
{0, 3, 3, 0, 0},
{0, 0, 0, 0, 2},
{0, 0, 1, 0, 2},
{0, 0, 0, 0, 0}};
printRegions(matrix);
}
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct coOrdinates
{
int row;
int col;
coOrdinates(int i ,int j): row(i) , col(j){}
};
void markRegion(vector<vector<int> >& matrix , vector<vector<bool> >& visited, int row , int col , int regionNum)
{
queue<coOrdinates> q;
q.push(coOrdinates(row,col));
int i, j;
while(!q.empty())
{
i = q.front().row;
j = q.front().col;
q.pop();
if(i >= 0 && i< matrix.size() &&
j >= 0 && j< matrix[0].size() &&
!visited[i][j] && matrix[i][j] == 1)
{
// Marking with pixel with region number
matrix[i][j] = regionNum;
// making sure we are not visiting again
visited[i][j] = true;
// Top
q.push(coOrdinates(i+1 , j ));
// bottom
q.push(coOrdinates(i-1 , j ));
// Right
q.push(coOrdinates(i , j+1));
// left
q.push(coOrdinates(i , j-1));
}
}
}
void markRegions(vector<vector<int> >& matrix)
{
vector<vector<bool> > visited(matrix.size() , vector<bool>(matrix[0].size() , false));
int regionNum = 1;
for(int i = 0 ; i < matrix.size() ; ++i)
{
for(int j = 0 ; j < matrix[0].size() ; ++j)
{
// Call this function
if(matrix[i][j] == 1 && !visited[i][j])
{
markRegion(matrix , visited , i , j , regionNum);
++regionNum;
}
}
}
}
int main()
{
vector<vector<int> > matrix = {{0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
{1, 1, 0, 0, 1, 1, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 1, 1, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 0, 0, 0}};
markRegions(matrix);
// print results
for(int i = 0 ; i < matrix.size() ; ++i)
{
for(int j = 0 ; j < matrix[0].size() ; ++j)
{
cout<<matrix[i][j]<<" ";
}
cout<<"\n";
}
}
#include<iostream>
using namespace std;
void generate(string& iStr , int index)
{
if(index == iStr.size())
{
cout<<"\n"<<iStr;
}
else
{
if(iStr[index] == '?')
{
iStr[index] = '0';
generate(iStr , index + 1);
iStr[index] = '1';
generate(iStr , index + 1);
iStr[index] = '?';
}
else
{
generate(iStr , index + 1);
}
}
}
void generate(string iStr)
{
generate(iStr , 0);
}
int main()
{
generate("a?bc?def?g");
}
int getMaxLengthDiffOne(vector<int> input)
{
sort(input.begin() , input.end());
int maxLength = 0, size = input.size(), prevStart = 0 , currentStart = 0 ;
for(int i = 1 ; i < size ; ++i)
{
if(input[i] != input[i -1])
{
//checking if the diff of number is one
if(input[currentStart] - input[prevStart] == 1)
{
// Mark the length as potential result
maxLength = max(maxLength , i - prevStart);
}
prevStart = currentStart;
currentStart = i;
}
}
// to take care of the last bit
return max(maxLength , size - prevStart);
}
doesn't work for 1,1,1,1
- MIG March 27, 2015your approach will give
1 + 1 = 2;
2 + 1 = 3
3 + 1 = 4
total 9
but the most optimum is
1 + 1 = 2
1 + 1 = 2
2 + 2 = 4
total 8
voting -1