vikalpveer
BAN USERclass Solution {
std::vector<int> V;
std::map<int, int> m;
public:
Solution(std::vector<int> v) : V(v) {
m[1] = 1;
m[6] = 9;
m[8] = 8;
m[9] = 9;
m[0] = 0;
}
bool validateRotation() {
int len = V.size();
int start;
int end;
if(len %2 == 0) {
end = len/2;
start = end - 1;
}else {
start = end = len / 2;
}
while(start >=0 && end < len) {
if(m.find(V[start]) == m.end() || m.find(V[end]) == m.end()) {
return false;
}
if(m[V[start]] == V[end] || V[start] == m[V[end]]) {
start--;
end++;
continue;
}
return false;
}
return true;
}
}
use stack to push root initially. Then iterate the stack until empty, pop out top and push child starting from right.
void preOrder(Node *root) {
std::stack<Node *> S;
S.push(root);
while(!S.empty()) {
Node *temp = S.top();
S.pop();
std::cout << temp->val << " ";
for(int i = temp->child.size(); I >=0; i--) {
if(temp->child[i]
S.push(temp->child[I];
}
}
}
class findPattern:
def __init__(self, indices):
self.indices = indices
def compute(self, str):
if not len(str):
return {}
i = 0
c_ret = set()
for i,c in enumerate(str):
if str[0:i+1] in self.indices:
s = str[0:i+1]
res = self.compute(str[i+1:])
for x in self.indices[s]:
if not len(res):
c_ret.add(x)
else:
for y in res:
c_ret.add(x+y)
return c_ret
X = {'1': ['A', 'B', 'C'], '2': ['D', 'E'], '12' : ['X'], '3' : ['P', 'Q']}
P = findPattern(X)
print list(P.compute('123'))
class IPv4:
def __init__(self, ips):
self.ip_list = ips
def validate(self):
ip_list = self.ip_list
if(len(ip_list)):
for ip in ip_list:
if(not len(ip)):
print("Empty IP provided")
continue
if(bool(re.match('[\d.]+$',ip))) :
token = ip.split(".")
if(len(token) and len(token) == 4):
isValid = True
for t in token:
if t.isdigit() and int(t) >=0 and int(t) <=255:
continue
else:
print("Invalid token %s"%ip)
isValid = False
break
if isValid:
print("valid IP %s" %ip)
else:
print ("Too few subnets in %s"%ip)
else:
print("%s has characters not allowed"%(ip))
else:
print("IP Address list is empty");
ip = IPv4(["10.5.6.4", "10", "", "a.b.c.d", "256,0,254.1", "1,2,3.4", "1.2.3.4"])
ip.validate()
#include <iostream>
#include <string>
using namespace std;
class Palindrome {
public:
string s;
Palindrome(string s):s(s) {}
void longestSubstringPalindrome();
};
void Palindrome::longestSubstringPalindrome() {
int max_len = 1;
int len = s.length();
int i = 1;
int j;
int k;
int start = 0;
while(i < len) {
// considering odd.
j = i -1;
k = i + 1;
int len_so_far = 1;
while( j >=0 && k <len) {
if(s[j] == s[k]) {
j--;
k++;
len_so_far +=2;
continue;
}
break;
}
if(max_len < len_so_far) {
max_len = len_so_far;
start = j + 1;
}
// Cosidering Even case
if(s[i] == s[i+1]) {
j = i - 1;
k = i + 2;
len_so_far = 2;
while( j >=0 && k <len) {
if(s[j] == s[k]) {
j--;
k++;
len_so_far +=2;
continue;
}
break;
}
}
if(max_len < len_so_far) {
max_len = len_so_far;
start = j + 1;
}
i++;
}
cout<<"Longest Palindrom substring is of length " << max_len << " : "<< s.substr(start,max_len) <<"\n";
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class SubsetSum {
public:
int num;
vector <int> V;
SubsetSum() {
num = 0;
}
void findNumSubsetSum(int start, int sum);
};
void SubsetSum::findNumSubsetSum(int start, int sum) {
if (start >= V.size()) {
return ;
}
if(V[start] == sum) {
num++;
return;
}
findNumSubsetSum(start + 1, sum - V[start]);
findNumSubsetSum(start + 1, sum);
}
int main() {
SubsetSum S;
S.V.push_back(2);
S.V.push_back(-2);
S.V.push_back(1);
S.V.push_back(4);
S.V.push_back(5);
S.V.push_back(-8);
S.findNumSubsetSum(0, 0);
cout << "Number of Sum :"<<S.num <<"\n";
}
void printPathSum(struct tree *node, int k, vector<int> &v) {
static int sum = 0;
if(node == NULL) {
return;
}
v.push_back(node->key);
sum = sum + node->key;
if(sum > k) {
return;
}
if(sum == k) {
printf("Found sum \n");
for(int i = 0;i < v.size(); i++) {
cout <<v[i] <<" ";
}
printf("\n");
return;
}
printPathSum(node->left, k, v);
sum = sum - node->left->key;
v.pop_back();
printPathSum(node->right, k, v);
sum = sum - node->right->key;
v.pop_back();
}
Assum root of the tree is given, you can do recursive in-order call to right and left subtrees and get the sum.
sumTree(struct tree* node, int *sum) {
if(node == NULL) {
return;
}
/* Do in order traversal */
sumTree(node->left, sum);
*sum = *sum + node->data;
sumTree(node->right, sum);
}
int main() {
int rightSum = 0;
int leftSum = 0;
sumTree(root->left, &leftSum);
sumTree(root->right, &rightSum);
if(leftSum == rightSum) {
printf("Tree is balanced \n");
}else {
printf("Tree not balanced \n");
}
}
here is my Solution
int max_str(char *str, int i) {
int c = *str - '0';
int p,m;
if(*str == '\0') {
return i;
}else {
p = i + max_str(str+1,c);
m = max_str(str+1,i*c);
return (p > m ? p:m);
}
}
void main() {
printf("\n sum of string = %d \n",max_str("2111", 0));
printf("\n sum of string = %d \n",max_str("21119", 0));
printf("\n sum of string = %d \n",max_str("212", 0));
printf("\n sum of string = %d \n",max_str("202", 0));
printf("\n sum of string = %d \n",max_str("419", 0));
printf("\n sum of string = %d \n",max_str("409", 0));
}
And output
sum of string = 5
sum of string = 18
sum of string = 5
sum of string = 4
sum of string = 36
sum of string = 13
Linear Time approach :
For further read :
- vikalpveer September 14, 2018http://worldkosh.com/blog/2018/09/13/largest-sum-subarray/