Krzysztof.G
BAN USERMy solution:
bool isWordCorrect(const std::string word)
{
if (word.length() == 0) return false;
std::vector<char> allowedSigns = {'h', 'i', 'r', 'e'};
std::vector<unsigned int> countSigns(allowedSigns.size(), 0);
auto wordIt = begin(word);
// repeat till end of word
while (wordIt != end(word)) {
int count = 0; // counts signs per one word
auto counterIt = begin(countSigns);
// count signs in one word (from possible many w1w2..)
for (const auto &ch : allowedSigns) {
while (wordIt != end(word) && (*wordIt) == ch) {
++(*counterIt);
++wordIt;
++count;
}
++counterIt;
}
// verify it
for (auto &num : countSigns) {
if (num != count / allowedSigns.size()) return false;
else num = 0;
}
}
return true;
}
Example outputs:
isWordCorrect("hirehhhiiirrreee") => true
isWordCorrect("hiree") => false
isWordCorrect("") => false n=0
Hi,
Well, I think anyway that common definition of whatever (in this case BST) is more than needed. In other case we can both be right even if we have completely opposit opinions on topic. Especially in computer science these definitions of things is our language. If it is not common there will be problems with understand each other.
To be consistent (at least in C++) it would be misleading to say that "set" can have non-unique values -> It is multiset. Every definition I found - and wikipedia seems to be right here - says that BST has only unique values.
(including Steven Skiena's "The Algorithm Design Manual"). If we do not follow definitions somebody can say you "Hey, your's solution does not allow duplicate values. Your solution is wrong!".
And of course algorithms written for BST will mostly work in BST-like (with duplicates) trees. But it is no more pure BST (at least for me ;-) ). No offense - just wanted clarify my point of view.
Thanks for finding bugs in my previous solution. Here is updated one (going from down to up of a tree):
bool isBinarySearchTree2(BTreeNode *node, int &min, int&max)
{
if (node)
{
int leftMin, leftMax, rightMin, rightMax;
bool leftOK = node->left ?
isBinarySearchTree2(node->left, leftMin, leftMax) && (min = leftMin, node->value > leftMax) : (min = node->value, true);
bool rightOK = node->right ?
isBinarySearchTree2(node->right, rightMin, rightMax) && (max = rightMax, node->value < rightMin) : (max = node->value, true);
if (!leftOK || !rightOK) return false;
}
return true;
}
BTW why somebody gave me minus for providing definition of BST from wikipedia... "somebody" - shame on you ! :-)
- Krzysztof.G October 25, 2013Excuse me? The common business (and only) scenario is to store unique values in each node. This is how all stuff works (sets, maps/dictionaries).
If you need store more same values (whatever value is) you put in each node structure container to store all these values.
If you would like to support same values in tree (it would not be a BST!) then in this case:
10
/ \
5 15
/ \
3 7
If you would like to put '5' one more time in the tree you would need to re-build all tree below existing 5 number. What business case requires such ineffective and slow way of storing things?
Definition of BST is to contain *only unique values* in each node:
From wikipedia:
In computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree each must also be a binary search tree.
- There must be no duplicate nodes.
Yes, I have checked that on many cases. Can you find any that proves it does not work?
- Krzysztof.G October 24, 2013Complete example in C++11. Should be O(n):
#include <iostream>
#include <vector>
#include <iterator>
#include <sstream>
#include <algorithm>
void findMax(std::vector<int> &v, unsigned int& idx)
{
unsigned int currIdx = idx++;
do {
if (idx == v.size()) return;
if (v[currIdx] < v[idx]) {
v[currIdx] = v[idx];
return;
}
findMax(v, idx);
} while (true);
}
void SetNearestMax(std::vector<int> &v)
{
unsigned int idx = 0;
while (idx < v.size() - 1)
{
findMax(v, idx);
}
}
int main()
{
std::vector<int> v = {7, 5, 6, 3, 4, 1, 2, 9, 11};
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl;
SetNearestMax(v);
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl;
return 0;
}
With such a definition of tree node:
struct BTreeNode
{
BTreeNode *left;
BTreeNode *right;
int value;
};
Here is solution:
bool isBinarySearchTree(BTreeNode *node)
{
if (node) {
bool leftOK = node->left ? (node->left->value < node->value) && isBinarySearchTree(node->left) : true;
bool rightOK = node->right ? (node->right->value > node->value) && isBinarySearchTree(node->right) : true;
if (!leftOK || !rightOK) return false;
}
return true;
}
#include <set>
#include <utility>
#include <iostream>
typedef std::set<std::pair<int, int>> PairOfNums;
void findNotMachingPairs(int n, PairOfNums& s)
{
// at least 2 numbers needed
if (n >= 2) {
for (int a = 1; a <= n - 1; ++a) {
for (int b = 2; b <= n; ++b) {
if (a > 10 * b || b > 10 * a) s.insert(std::make_pair(a, b));
}
}
}
}
int main()
{
int n = 40;
PairOfNums s;
findNotMachingPairs(n, s);
for (PairOfNums::const_iterator it = s.begin(); it != s.end(); ++it)
{
std::cout << (*it).first << " " << (*it).second << "\n";
}
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
char *findSubstring(const char *str1, const char*str2)
{
int len1 = strlen(str1);
int len2 = strlen(str2);
// find maximum length of common substring
int n = 1;
int max = 0;
while (n <= len1 && n <= len2) {
if (!strncmp(str1, str2 + len2 - n, n)) max = n;
n++;
}
// create substring
char *output = (char*)malloc(max+1);
strncpy(output, str1, max);
output[max] = '\0';
return output;
}
int main()
{
const char *str1 = "ABCABCzzzzzzzzzzzzzzzzzzzzzzzzzzz";
const char *str2 = "xxxxxxxxxxxxxxxABCABC";
char *output = findSubstring(str1, str2);
printf("[%s]\n", output);
free(output);
return 0;
}
Correct answer is that assignment operator will be used in that case - default one generated by compiler or provided by "sample" class designer.
Persons who say that copy constructor would be invoked in that case are wrong. Constructor is supposed to *construct* object and in presented scenario both objects - pointed by s1 and s2 - are already created.
Copy constructor would be called in such scenario:
- Krzysztof.G December 10, 2013