Diego Giagio
BAN USERSimple and concise recursive solution in Java.
public class PrintStrings {
public static void main(String... args) {
printStrings("a?bc?def?g");
}
private static void printStrings(String str) {
printStrings(str, 0);
}
private static void printStrings(String str, int pos) {
if (pos == str.length() - 1) {
System.out.println(str);
return;
}
for (; pos < str.length(); ++pos) {
if (str.charAt(pos) == '?') {
byte[] chars = str.getBytes();
chars[pos] = '0';
printStrings(new String(chars), pos + 1);
chars[pos] = '1';
printStrings(new String(chars), pos + 1);
break;
}
}
}
}
Solution written in C++, both recursive and iterative versions. The recursive version also allows tail-call optimization by the compiler.
Output:
x3y4z6 -> xyz346 (iterative)
x3y4z6 -> xyz346 (recursive)
x3y4z6a7 -> xyza3467 (iterative)
x3y4z6a7 -> xyza3467 (recursive)
a1b2c3d4 -> abcd1234 (iterative)
a1b2c3d4 -> abcd1234 (recursive)
Code:
#include <iostream>
static void transform_recursive(std::string& str, size_t pos = 0) {
if (str.empty())
return;
if (str.size() - pos == 2) {
return;
}
if (str.size() - pos == 3) {
std::swap(str[pos], str[pos+1]);
return;
}
size_t mid = (str.size() - pos) / 2;
for (size_t i = pos + 1, j = 1; i+j < str.size(); ++i, ++j) {
std::swap(str[i], str[i+j]);
}
// tail-call recursion, can be optimized by the compiler
transform_recursive(str, pos + mid);
}
static void transform_iterative(std::string& str) {
if (str.empty())
return;
size_t pos = 0;
while (true) {
if (str.size() - pos == 2) {
break;
}
if (str.size() - pos == 3) {
std::swap(str[pos], str[pos+1]);
break;
}
size_t mid = (str.size() - pos) / 2;
for (size_t i = pos + 1, j = 1; i+j < str.size(); ++i, ++j) {
std::swap(str[i], str[i+j]);
}
pos += mid;
}
}
int main() {
std::string s1_a = "x3y4z6";
std::cout << s1_a << " -> ";
transform_iterative(s1_a);
std::cout << s1_a << " (iterative)" << std::endl;
std::string s1_b = "x3y4z6";
std::cout << s1_b << " -> ";
transform_recursive(s1_b);
std::cout << s1_b << " (recursive)" << std::endl;
std::string s2_a = "x3y4z6a7";
std::cout << s2_a << " -> ";
transform_iterative(s2_a);
std::cout << s2_a << " (iterative)" << std::endl;
std::string s2_b = "x3y4z6a7";
std::cout << s2_b << " -> ";
transform_recursive(s2_b);
std::cout << s2_b << " (recursive)" << std::endl;
std::string s3_a = "a1b2c3d4";
std::cout << s3_a << " -> ";
transform_iterative(s3_a);
std::cout << s3_a << " (iterative)" << std::endl;
std::string s3_b = "a1b2c3d4";
std::cout << s3_b << " -> ";
transform_recursive(s3_b);
std::cout << s3_b << " (recursive)" << std::endl;
}
@Amit Petkar you are absolutely right. I corrected the code and now it seems good. Thanks for the heads up!
- Diego Giagio January 04, 2014Since there's no right solution yet posted, I'm posting a C++ solution. Please notice that the question says nothing about the rock size or weight, it just counts the rocks on the layers.
Code:
#include <iostream>
void arrange_rocks_recursive(int k, int n, int& nways) {
for (int i = k; i <= n; i++) {
int j = n - i;
if (j <= i) {
continue;
}
//std::cout << "n = " << n << ", i=" << i << ", j=" << j << std::endl;
arrange_rocks_recursive(i+1, n-1, ++nways);
}
}
int arrange_rocks(int n) {
if (n == 0)
return 0;
if (n < 0)
return -1;
int nways = 0;
arrange_rocks_recursive(1, n, nways);
return nways;
}
/**
* A child is arranging rocks in layers. He can arrange the rocks, in such way
* that, any layer has lesser rocks than its base layer. Given n rocks, In how
* many ways can the child arrange the rocks.
*/
int main() {
std::cout << arrange_rocks(7) << std::endl;
}
@justhack4fun688 Of course it will, it's a huge string. What's you suggestion?
I could save on the set only the pairs of the begin and end indexes of each palindrome on the original string. That would save a lot of memory, but I chose not to for this exercise.
@justhack4fun688 The worst case for space is a string with repeated chars, like 'aaaaaaaaa'. Which gives 'a', 'aa', 'aaa', 'aaaa', etc. The formula to calculate the worst case is (n * (n+1))/2 where n is the length of the input string. For a string with 9 repeated 'a's it gives (9 * 10) / 2 = 45. So I would say the worst case space is O(n*(n+1)/2).
- Diego Giagio December 16, 2013@echen57 what about the monthly sales of the recruited members of the current recruit? It needs a recursive logic.
- Diego Giagio December 15, 2013Looks good. +1
- Diego Giagio December 15, 2013@justhack4fun688 I just did some performance improvements by skipping indexes of already found palindromes. It much faster on the average case, but it's still O(n^2) worst case.
- Diego Giagio December 15, 2013@justhack4fun688 O(n^2) time worst case. I've heard it's possible to have O(n) but it's a bit more complicated and you have to use Manacher’s Algorithm.
- Diego Giagio December 15, 2013@justhack4fun688 Wow, thanks. Now it is. Can you check again? :-)
- Diego Giagio December 15, 2013@justhack4fun688 You are correct. I fixed the code. It's simpler and worked with everything I tried. Can you please check again?
- Diego Giagio December 15, 2013@one of candidate this is one of the easiest linear-time searching algorithms to write on a whiteboard in 20 minutes. It looks a bit complicated on the code above because I used C++ templates, but it can be much simpler without that. If you are asked to write a linear-time string searching algorithm in 20 minutes, I suggest you to go with Rabin Karp.
- Diego Giagio December 14, 2013@justhack4fun688 and @Anonymous1: Thanks for pointing that out. I fixed the code and it should work now.
@Anonymous2: The condition of the while loop cannot be changed to left >= 0 simply because left is of type size_t. This is an unsigned type and left >= 0 will always evaluate to true. Yes, we should return vectors or sets by value when it makes sense[1] (like this code). C++03 compilers use RVO and C++11 have even more room for optimization for copy elision.[2]
[1] http://en.wikipedia.org/wiki/Return_value_optimization
[2] http://stackoverflow.com/questions/3350385/how-to-return-an-object-in-c
My algorithm iterates the string from left to right once and try to match the palindromes from inside out, adding the matches to a std::unordered_set (hash set). Written in C++.
Output for "civic":
ivi
v
i
civic
c
Output for "aba":
aba
b
a
Code:
#include <iostream>
#include <unordered_set>
#include <string>
#include <vector>
std::vector<std::string> find_palindromes(const std::string& s, size_t center) {
std::vector<std::string> palindromes;
// Add current char
palindromes.emplace_back(1, s[center]);
size_t left = center;
size_t right = center;
while (left != -1 && right < s.size()) {
if (s[left] != s[right]) {
// Try to match one char to the left
if (left != -1) {
if (s[left--] == s[right])
palindromes.emplace_back(s.substr(left, right - left + 1));
}
continue;
}
// Only add palindrome if length is bigger than 1
// since we already added it before the loop.
if (left != right) {
palindromes.emplace_back(s.substr(left, right - left + 1));
++right;
} else {
--left;
}
}
return palindromes;
}
std::unordered_set<std::string> distinct_palindromes(const std::string& s) {
if (s.empty())
return std::unordered_set<std::string>();
std::unordered_set<std::string> result;
for (size_t i = 0; i < s.size(); ) {
auto palindromes = find_palindromes(s, i);
// Insert on the set, keeping track of the longest
size_t longest = 0;
for (const std::string& p : palindromes) {
result.insert(p);
longest = std::max(longest, p.size());
}
// Skip as much as the longest palindrome found
if (longest > i)
i += longest - i;
else
++i;
}
return result;
}
int main() {
std::unordered_set<std::string> civic = distinct_palindromes("civic");
for (const std::string& p : civic) {
std::cout << p << std::endl;
}
std::cout << "--" << std::endl;
std::unordered_set<std::string> aba = distinct_palindromes("aaaa");
for (const std::string& p : aba) {
std::cout << p << std::endl;
}
}
@Marey make sure the input is correct (like the example, for instance). Otherwise you will get runtime error because the program exits with code 1.
- Diego Giagio December 11, 2013@Marey no, there's not. Please use a recent compiler (at least supporting C++11). You can try the code on ideone.com if you prefer.
- Diego Giagio December 11, 2013@Sunny you are right. I changed the algorithm logic and now it's working. Thanks.
- Diego Giagio December 10, 2013Written in C++.
Input:
2
3
7
Output:
5
11
Code:
#include <iostream>
int count_bits(int n) {
int i = 0;
while (n > 0) {
if (n & 1)
i++;
n >>= 1;
}
return i;
}
int smallest_greater_same_weight(int n) {
int i = count_bits(n);
int m = n;
for (;;) {
if (i == count_bits(++m))
break;
}
return m;
}
int main() {
int ntests;
std::cin >> ntests;
if (std::cin.fail())
return 1;
while (ntests--) {
int n;
std::cin >> n;
if (std::cin.fail())
return 1;
std::cout << smallest_greater_same_weight(n) << std::endl;
}
return 0;
}
My algorithm uses counting sort (or bucket sort) in O(n+m) and then count how many the elements are duplicated (count = 2). Written in C++.
Input:
3
4 4
1 2 3 4
3 4 5 6
4 5
1 2 3 4
1 2 3 5 6
3 4
1 2 3
5 6 7 4
Output:
2
3
0
Code:
#include <iostream>
#include <vector>
#include <algorithm>
bool read_array(std::vector<int>& vec, int len) {
int n;
vec.reserve(len);
while (len--) {
std::cin >> n;
vec.push_back(n);
}
return !std::cin.fail();
}
int strength(const std::vector<int>& nvec, const std::vector<int>& mvec) {
// Uses counting sort (or bucket sort) - O(n+m)
std::vector<int> count_sort(101);
for (int n : nvec)
count_sort[n]++;
for (int n : mvec)
count_sort[n]++;
// Count duplicate elements - O(100)
return std::count(count_sort.begin(), count_sort.end(), 2);
}
int main() {
int ntests;
std::cin >> ntests;
if (std::cin.fail())
return 1;
while (ntests--) {
int nlen;
int mlen;
std::cin >> nlen;
std::cin >> mlen;
if (std::cin.fail())
return 1;
std::vector<int> nvec;
if (!read_array(nvec, nlen))
return 1;
std::vector<int> mvec;
if (!read_array(mvec, mlen))
return 1;
std::cout << strength(nvec, mvec) << std::endl;
}
}
C++ version. Avoid unnecessary recursion to the left subtree after the element has already been found.
#include <iostream>
#include <memory>
#include <stdexcept>
#include <iterator>
#include <vector>
template <typename T>
struct bst_node {
bst_node(T data) : left_(nullptr), right_(nullptr), data_(data) { }
~bst_node() { delete left_; delete right_; }
bst_node<T>* left_;
bst_node<T>* right_;
T data_;
};
template <typename T, typename RandIt>
bst_node<T>* create_bst_r(RandIt beg, RandIt end) {
if (beg > end)
return nullptr;
RandIt mid = beg + (end - beg) / 2;
bst_node<T>* node = new bst_node<T>(*mid);
node->left_ = create_bst_r<T>(beg, mid - 1);
node->right_ = create_bst_r<T>(mid + 1, end);
return node;
}
template <typename T, typename RandIt>
bst_node<T>* create_bst(RandIt beg, RandIt end) {
return create_bst_r<T>(beg, end - 1);
}
template <typename T>
void find_kth_largest_r(bst_node<T>* node, size_t kth, size_t& pos, T& largest) {
if (!node || pos == kth)
return;
// Find the largest node by traversing right
find_kth_largest_r(node->right_, kth, pos, largest);
// Increment counter and check if it's kth
if (++pos == kth) {
largest = node->data_;
return;
} else if (pos > kth) {
// No need to recurse again. We already found our element.
return;
}
// Also traverse left
find_kth_largest_r(node->left_, kth, pos, largest);
}
template <typename T>
T find_kth_largest(bst_node<T>* root, size_t kth) {
T largest = T();
size_t zero = 0;
find_kth_largest_r(root, kth, zero, largest);
return largest;
}
int main() {
std::vector<int> arr{1, 2, 3, 4, 5, 6, 7, 8, 9};
std::unique_ptr<bst_node<int>> root(create_bst<int>(std::begin(arr), std::end(arr)));
std::cout << "4th largest: " << find_kth_largest(root.get(), 4) << std::endl;
}
Solution in O(n) time, written in C++.
Input:
10:20 - 10:30
11:10 - 11:30
11:20 - 12:40
11:30 - 13:00
Output:
Longest slot is between 11:10 and 13:00
Code:
#include <iostream>
#include <vector>
#include <stdexcept>
#include <limits>
struct log_entry {
log_entry(int start, int end) : start_(start), end_(end) { }
int start_;
int end_;
};
std::pair<int, int> longest_slot(const std::vector<log_entry>& entries) {
if (entries.empty())
throw std::invalid_argument("log entries must not be empty");
int min_start = 0;
int max_end = 0;
int max_diff = 0;
int cur_start = -1;
int cur_end = -1;
for (size_t i = 0; i < entries.size(); i++) {
const log_entry& entry = entries[i];
// Current entry not yet set?
if (cur_start == -1 && cur_end == -1) {
cur_start = entry.start_;
cur_end = entry.end_;
}
// Is this entry starting between the last slot?
if (entry.start_ >= cur_start && entry.start_ <= cur_end) {
cur_start = std::min(cur_start, entry.start_);
cur_end = std::max(cur_end, entry.end_);
} else {
cur_start = entry.start_;
cur_end = entry.end_;
}
// Update maximum diff
if (cur_end - cur_start > max_diff) {
min_start = cur_start;
max_end = cur_end;
max_diff = max_end - min_start;
}
}
return std::make_pair(min_start, max_end);
}
/**
* Using a log generated by a multiprocessor machine, which contains start and
* end time of each process, find the longest slot of time in which the machine
* wasn't idle. The log is sorted by the process's start time.
*/
int main() {
std::vector<log_entry> entries{{1000, 1100},
{1020, 1030},
{1110, 1130},
{1120, 1240},
{1130, 1300}};
std::pair<int, int> r = longest_slot(entries);
std::cout << "Longest slot is between " << r.first << " and " << r.second << std::endl;
return 0;
}
@gameboy1024 and @sambatyon you are right. The algorithm didn't include the sum of the weight of the children. I fixed it and now it does, and it's still O(nlogn). Can you please check?
- Diego Giagio December 06, 2013I think it's not necessary to parse the CSV into a tree. I just sorted the entries by parent and accumulated the weights of the children (and the children of the children) for every parent. Time complexity O(nlogn). Written in C++.
Output:
0=20
30=10
40=3
Code:
#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>
#include <vector>
struct node {
node(int id, int parent_id, int weight) :
id_(id), parent_id_(parent_id), weight_(weight) { }
bool operator<(const node& other) const {
return parent_id_ < other.parent_id_;
}
int id_;
int parent_id_;
int weight_;
};
std::map<int, int> find_node_tree_weights(std::vector<node>& nodes) {
if (nodes.empty())
return std::map<int,int>();
// Sort the nodes by parent - O(nlogn)
std::sort(nodes.begin(), nodes.end());
// Loop throught the nodes - O(n)
std::map<int, int> paren_weights;
for (auto it = nodes.rbegin(); it != nodes.rend(); it++) {
const node& node = *it;
// Calculate weight for this parent
paren_weights[node.parent_id_] += node.weight_;
if (paren_weights.count(node.id_))
paren_weights[node.parent_id_] += paren_weights[node.id_];
}
// Return
return paren_weights;
}
int main() {
std::vector<node> nodes{{10,30,1},
{30,0,10},
{20,30,2},
{50,40,3},
{40,30,4}};
std::map<int, int> weights = find_node_tree_weights(nodes);
for (const auto& p : weights) {
std::cout << p.first << "=" << p.second << std::endl;
}
return 0;
}
@loveCoding it seems like you didn't understand the problem. The answer for (1,2) (3,4) (5,6) (7,8) is (1,2) (3,4) (5,6) (7,8).
- Diego Giagio December 03, 2013@loveCoding First the array will be sorted. I'm using std::sort. Some implementations use quicksort (n^2 worst case), others use mergesort (nlogn worst case). Then the array will be traversed and every range will be checked against next range only - O(n). If the next range overlaps, it's removed. Total complexity: O(nlogn) + O(n) = O(nlogn).
- Diego Giagio December 03, 2013@loveCoding you are wrong. The array of ranges is sorted and the comparison is made only with adjacent ranges, not with all of them.
- Diego Giagio December 03, 2013@Gerald thanks for the heads up. I fixed the overlaps() method and it appears to be working now. The output for your example is (1, 2) (4, 6) (8, 10).
- Diego Giagio December 03, 2013@Anonymous, @Gerald and @Raj, my first code just removed overlapping ranges. But I modified the code since I was confused about the question. Anyway, I've restored the old code and it's now removing the overlapping ranges. Please check again. It was a 2 line change.
- Diego Giagio December 03, 2013C++ version.
#include <iostream>
#include <sstream>
#include <stdexcept>
std::string decode(const std::string& str) {
std::stringstream ss(str);
std::string out;
out.reserve(str.size() * 3); // estimated size to avoid reallocation
while (!ss.eof()) {
char c; int n;
ss >> c >> n;
if (ss.fail())
throw std::invalid_argument("can't decode");
out.append(n, c);
}
return out;
}
int main() {
std::cout << decode("a3b2c4") << std::endl;
return 0;
}
Sort the ranges and remove one of the ranges that are overlapping. Time complexity O(nlogn), written in C++.
Output:
(1, 2) (3, 6) (8, 10)
Code:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
struct range {
range(int a, int b) : a_(a), b_(b) { }
bool operator<(const range& other) const {
return a_ < other.a_ || b_ < other.b_;
}
int a_;
int b_;
};
std::ostream& operator<<(std::ostream& os, const range& r) {
os << "(" << r.a_ << ", " << r.b_ << ")";
return os;
}
bool overlaps(const range& r1, const range& r2) {
return (r2.a_ <= r1.b_) || (r2.a_ == r1.b_ && r2.b_ >= r1.b_);
}
std::vector<range> find_non_overlap(std::vector<range>& ranges) {
// Sort the ranges. Uses operator< from range struct. O(nlogn)
std::sort(ranges.begin(), ranges.end());
// Remove ranges that are overlapping. O(n)
for (auto it = std::next(ranges.begin()); it != ranges.end(); it++) {
auto prev_it = std::prev(it);
if (overlaps(*prev_it, *it)) {
it = ranges.erase(prev_it);
}
}
return ranges;
}
/**
* Given a list of ranges as input ((1,2),(3,4),(3,6),(8,10)), the output would
* be those ranges that don't overlap. For example, the output could be merging
* the ranges 1) (1,2) (3,4) 2) (1,2) (3,6) etc.
*
* The output cannot contain (3,4),(3,6) as 3 is common to both.
*/
int main() {
std::vector<range> ranges{{1,2}, {3,4}, {3,6}, {8,10}};
std::vector<range> result = find_non_overlap(ranges);
std::copy(result.begin(), result.end(), std::ostream_iterator<range>(std::cout, " "));
}
@azil. Ok, and what about 011 + 11? The sum is 22. All the digits are contained in the array and it's the smallest sum.
- Diego Giagio December 02, 2013@azil Can you explain why 11110 should be 112?
- Diego Giagio December 02, 2013Solution written in C++. Time complexity O(nlogn).
Output:
-470 - -520 = 50
30 - -20 = 50
Code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
std::vector<std::pair<int, int>> find_min_abs_diff(std::vector<int>& arr) {
// Sort the vector O(nlogn)
std::sort(arr.begin(), arr.end());
// Find the difference between every adjacent elements. O(n)
// Keep track of minimum
int min_so_far = std::numeric_limits<int>::max();
std::vector<std::pair<int, int>> pairs;
for (size_t i = 1; i < arr.size(); i++) {
int diff = std::abs(arr[i] - arr[i-1]);
if (diff <= min_so_far) {
min_so_far = diff;
pairs.emplace_back(arr[i], arr[i-1]);
}
}
// Remove elements that are greater than the minimum found.
pairs.erase(std::remove_if(pairs.begin(), pairs.end(),
[&](const std::pair<int, int>& p) {
return p.first - p.second > min_so_far;
}), pairs.end());
return pairs;
}
int main() {
std::vector<int> arr{-20, -3916237, -357920, -3620601, 7374819, -7330761,
30, 6246457, -6461594, 266854, -520, -470};
std::vector<std::pair<int, int>> min_pairs = find_min_abs_diff(arr);
for (const auto& p: min_pairs) {
std::cout << p.first << " - " << p.second << " = ";
std::cout << p.first - p.second << std::endl;
}
}
C++ version.
#include <iostream>
#include <limits>
template <typename T>
struct bst_node {
bst_node() : left_(nullptr), right_(nullptr), data_() { }
bst_node(const T& data) : left_(nullptr), right_(nullptr), data_(data) { }
~bst_node() { delete left_; delete right_; }
bst_node *left_;
bst_node *right_;
T data_;
};
template <typename T>
bool is_valid_bst_r(const bst_node<T>* root, const bst_node<T>*& prev) {
if (!root)
return true;
if (!is_valid_bst_r(root->left_, prev))
return false;
if (prev && root->data_ <= prev->data_)
return false;
prev = root;
return is_valid_bst_r(root->right_, prev);
}
template <typename T>
bool is_valid_bst(const bst_node<T>& root) {
const bst_node<T>* prev = nullptr;
return is_valid_bst_r(&root, prev);
}
int main() {
std::cout << std::boolalpha;
bst_node<int> root(5);
root.left_ = new bst_node<int>(4);
root.right_ = new bst_node<int>(6);
root.left_->left_ = new bst_node<int>(1);
//root.right_->left_ = new bst_node<int>(3);
std::cout << is_valid_bst(root) << std::endl;
return 0;
}
@Anonymous you're right. Removed recursion.
- Diego Giagio November 29, 2013My approach was to create two vectors with alternate elements after sorting the original vector in O(nlogn) time complexity. Then sum each vector's digit. Written in C++.
Output:
207
Code:
#include <iostream>
#include <vector>
#include <algorithm>
int calculate_min_sum(std::vector<int>& vec) {
std::vector<int> vec_a;
std::vector<int> vec_b;
// Sort the vector
std::sort(vec.begin(), vec.end());
// Create two vectors with alternate elements
for (size_t i = 0; i < vec.size(); i++) {
if (i % 2 == 0)
vec_a.push_back(vec[i]);
else
vec_b.push_back(vec[i]);
}
// Convert vectors to numbers
int vec_a_val = 0;
for (size_t i = 0; i < vec_a.size(); i++) {
vec_a_val = vec_a_val * 10 + vec_a[i];
}
int vec_b_val = 0;
for (size_t i = 0; i < vec_b.size(); i++) {
vec_b_val = vec_b_val * 10 + vec_b[i];
}
// Return sum
return vec_a_val + vec_b_val;
}
int main() {
std::vector<int> vec{7, 9, 1, 8, 2};
std::cout << calculate_min_sum(vec) << std::endl;
}
@Ehsan you are right, thanks. I corrected my code.
- Diego Giagio November 27, 2013C++ recursive version.
Output:
98
Code:
#include <iostream>
#include <cmath>
long max_number_recurse(int o, long limit, long total) {
if (o == 0)
return total;
long result = 0;
for (int i = 2; i <= 9; i++) {
long maxn = max_number_recurse(o-1, limit, total * i);
if (maxn > result && maxn <= limit)
result = maxn;
}
return result;
}
long max_number(int n, int o) {
if (n <= 0 || o <= 0)
return -1;
long limit = std::pow(10, n) - 1;
return max_number_recurse(o, limit, 1);
}
int main() {
std::cout << max_number(2, 3) << std::endl;
return 0;
}
C++ version. Used a stack to check for matching open/close brackets and parenthesis.
#include <iostream>
#include <deque>
#include <stack>
class char_stream {
public:
char_stream(const std::string& data) : data_(data.begin(), data.end()) { }
bool has_next() const { return !data_.empty(); }
char next() { char n = data_.front(); data_.pop_front(); return n; }
private:
std::deque<char> data_;
};
bool is_valid(char_stream& s) {
std::stack<char> st;
while (s.has_next()) {
char next = s.next();
switch (next) {
case '[':
case '(':
st.push(next);
break;
case ']':
if (st.top() != '[')
return false;
st.pop();
break;
case ')':
if (st.top() != '(')
return false;
st.pop();
break;
default:
std::cout << "unknown char: " + next << std::endl;
return false;
}
}
return st.empty();
}
int main() {
std::cout << std::boolalpha;
char_stream good("()(([]))");
std::cout << is_valid(good) << std::endl;
char_stream bad("(]");
std::cout << is_valid(bad) << std::endl;
char_stream bad2("([)]");
std::cout << is_valid(bad2) << std::endl;
return 0;
}
Care to give an example? Thanks.
- Diego Giagio November 27, 2013C++ Rabin-Karp implementation. O(n+m) time.
#include <iostream>
#include <iterator>
static const int prime_mod = 2147483647;
static const int prime_factor = 257;
template <typename T>
long long rabinkarp_hash(long long value, T elem) {
return (value + elem) * prime_factor % prime_mod;
}
template <typename RandIt1, typename RandIt2>
RandIt2 rabinkarp_find(RandIt1 bneedle, RandIt1 eneedle,
RandIt2 bhaystack, RandIt2 ehaystack) {
if (bneedle >= eneedle || bhaystack >= ehaystack)
return ehaystack;
RandIt1 needle = bneedle;
typename std::iterator_traits<RandIt1>::difference_type needle_len =
std::distance(bneedle, eneedle);
// Calculate initial hash for needle, haystack and power
long long power = 1;
long long needle_hash = 0;
long long haystack_hash = 0;
while (bneedle < eneedle && bhaystack < ehaystack) {
power = rabinkarp_hash(power, 0);
needle_hash = rabinkarp_hash(needle_hash, *bneedle++);
haystack_hash = rabinkarp_hash(haystack_hash, *bhaystack++);
}
while (bhaystack < ehaystack) {
if (haystack_hash != needle_hash) {
// Remove first element from haystack hash
haystack_hash -= power * *(bhaystack - needle_len) % prime_mod;
haystack_hash = rabinkarp_hash(haystack_hash, *bhaystack++);
}
if (haystack_hash == needle_hash) {
// Hashes are equal, make sure the contents are equal
if (std::equal(needle, eneedle, bhaystack - needle_len)) {
bhaystack -= needle_len;
break;
}
}
}
return bhaystack;
}
size_t rabinkarp_find(const std::string& needle, const std::string& haystack) {
auto it = rabinkarp_find(needle.begin(), needle.end(), haystack.begin(), haystack.end());
if (it != haystack.end())
return std::distance(haystack.begin(), it);
return std::string::npos;
}
int main() {
size_t pos = rabinkarp_find("tl", "bottle");
std::cout << pos << std::endl;
return 0;
}
I edited the answer after better explanation of the question.
- Diego Giagio November 27, 2013C++ version using recursion. First I sort the elements by parent: O(nlogn). Then I do a binary search O(logn) to find each parent on the list and recursively print it's children.
Output:
A (parent id = null)
B (parent id = A)
C (parent id = B)
D (parent id = C)
H (parent id = B)
E (parent id = A)
F (parent id = E)
G (parent id = F)
Code:
#include <iostream>
#include <vector>
#include <algorithm>
template <typename T>
struct node {
typedef T value_type;
node(T id, T parent_id) : id_(id), parent_id_(parent_id) { }
node(T id) : id_(id), parent_id_(0) { }
T id_;
T parent_id_;
};
template <typename T>
std::ostream& operator<<(std::ostream& os, const node<T>& n) {
os << n.id_ << " (parent id = ";
if (!n.parent_id_)
os << "null)";
else
os << n.parent_id_ << ")";
os << std::endl;
return os;
}
template <typename T>
struct order_by_parent {
bool operator()(const node<T>& a, const node<T>& b) {
// Is it the root?
if (!a.parent_id_)
return true;
// Is the same parent?
if (a.parent_id_ == b.parent_id_) {
// Order by id
return a.id_ < b.id_;
}
// Else, order by parent
return a.parent_id_ < b.parent_id_;
}
};
template <typename T>
struct find_by_parent {
bool operator()(const node<T>& a, const node<T>& b) {
return a.parent_id_ < b.parent_id_;
}
};
template <typename ForwardIt>
void print_children_tree(ForwardIt begin, ForwardIt end, int indent) {
// Base case
if (begin >= end)
return;
typename ForwardIt::value_type node = *begin;
// Print node
for (int i = 0; i < indent; i++)
std::cout << " ";
std::cout << node;
// Binary search all childrens of this node
typename ForwardIt::value_type parent(0, node.id_);
ForwardIt it = std::lower_bound(begin, end, parent, find_by_parent<typename ForwardIt::value_type::value_type>());
if (it == end) {
// No children for this node.
return;
}
// Print all children
for (;;) {
const typename ForwardIt::value_type& curr_n = *it;
if (curr_n.parent_id_ != node.id_)
break;
// Recurse
print_children_tree(it++, end, indent + 1);
}
}
template <typename ForwardIt>
void print_tree(ForwardIt begin, ForwardIt end) {
// Print children
print_children_tree(begin, end, 1);
}
int main() {
// Create the nodes
std::vector<node<char>> nodes{{'A'}, {'B', 'A'}, {'C', 'B'}, {'D', 'C'},
{'H', 'B'}, {'E', 'A'}, {'F', 'E'},
{'G', 'F'}};
// Sort all nodes by parent
std::sort(nodes.begin(), nodes.end(), order_by_parent<char>());
// Print all the nodes
print_tree(nodes.begin(), nodes.end());
}
I don't understand why many complex solutions showed up for a simple problem. Perhaps I'm missing something.
C++ version with O(n^2) time.
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <sstream>
std::string readline() {
std::string line;
std::getline(std::cin, line);
if (!std::cin.good()) {
std::cout << "premature end of input" << std::endl;
std::exit(1);
}
return line;
}
int calculate_diff(const std::string& a, const std::string& b) {
int diff = 0;
for (size_t i = 0; i < a.size(); i++) {
if (a[i] != b[i])
diff++;
}
return diff;
}
int main() {
size_t n;
size_t b;
std::stringstream(readline()) >> n >> b;
std::vector<std::string> bar_vec;
for (size_t i = 0; i < n; i++) {
std::string bar = readline();
bar.erase(std::remove(bar.begin(), bar.end(), ' '), bar.end());
if (bar.size() != b) {
std::cout << "unexpected size of barcode" << std::endl;
std::exit(1);
}
bar_vec.push_back(bar);
}
std::unordered_set<int> diff_set;
for (size_t i = 0; i < bar_vec.size(); i++) {
for (size_t j = 0; j < bar_vec.size(); j++) {
// Avoid comparing the same bar
if (i == j)
continue;
int diff = calculate_diff(bar_vec[i], bar_vec[j]);
if (diff_set.count(diff)) {
break;
} else {
diff_set.insert(diff);
}
}
}
std::cout << diff_set.size() << " bags needed." << std::endl;
return 0;
}
C++ version with O(n^2) time.
#include <iostream>
#include <vector>
std::string find_max_composite(const std::vector<std::string>& words) {
std::string max_str;
size_t max_count = 0;
for (size_t i = 0; i < words.size(); i++) {
size_t count = 0;
for (size_t j = 0; j < words.size(); j++) {
// Don't compare the same word
if (j == i)
continue;
// A string is only composed of other strings if it's longer
if (words[i].size() > words[j].size()) {
if (words[i].find(words[j]) != std::string::npos)
count++;
}
}
if (count > max_count) {
max_count = count;
max_str = words[i];
}
}
return max_str;
}
int main() {
std::vector<std::string> words { "rat", "cat", "abc", "xyz", "abcxyz",
"ratcatabc", "xyzcatratabc" };
std::cout << find_max_composite(words);
return 0;
}
C++ implementation of a LRU cache. All operations are O(1).
#include <iostream>
#include <unordered_map>
#include <list>
#include <stdexcept>
template <typename K, typename V>
class lru_cache {
private:
typedef std::pair<K, V> cache_entry;
typedef std::list<cache_entry> cache_list;
typedef std::unordered_map<K, typename cache_list::iterator> cache_map;
public:
typedef typename cache_list::iterator iterator;
typedef typename cache_list::const_iterator const_iterator;
lru_cache(size_t size) : size_(size) {
cache_map_.reserve(size_);
}
void add(const K& key, const V& value) {
if (cache_map_.size() >= size_)
remove_eldest();
auto map_it = cache_map_.find(key);
if (map_it == cache_map_.end()) {
// Add element to list and save iterator on map
auto list_it = cache_list_.insert(cache_list_.begin(), std::make_pair(key, value));
cache_map_.emplace(key, list_it);
} else {
// Copy entry from list
auto& list_it = map_it->second;
cache_entry entry = *list_it;
// Remove entry from list
cache_list_.erase(list_it);
// Update entry and add to beginning of the list
entry.second = value;
cache_list_.push_front(entry);
}
}
V remove(const K& key) {
auto map_it = cache_map_.find(key);
if (map_it == cache_map_.end())
throw std::runtime_error("key not found");
auto& list_it = map_it->second;
cache_map_.erase(map_it);
cache_entry entry = *list_it;
cache_list_.erase(list_it);
return entry.second;
}
V remove_eldest() {
if (cache_map_.empty())
throw std::runtime_error("cache is empty");
cache_entry entry = cache_list_.back();
cache_map_.erase(entry.first);
cache_list_.pop_back();
return entry.second;
}
iterator begin() {
return cache_list_.begin();
}
iterator end() {
return cache_list_.end();
}
const_iterator cbegin() const {
return cache_list_.cbegin();
}
const_iterator cend() const {
return cache_list_.cend();
}
size_t size() const {
return cache_map_.size();
}
bool empty() const {
return cache_map_.empty();
}
private:
size_t size_;
cache_map cache_map_;
cache_list cache_list_;
};
int main() {
lru_cache<std::string, int> cache(3);
cache.add("one", 1);
cache.add("two", 2);
cache.add("three", 3);
cache.add("four", 4);
std::cout << cache.size() << std::endl;
std::cout << cache.remove("four") << std::endl;
std::cout << cache.size() << std::endl;
for (const auto& p : cache)
std::cout << p.first << " = " << p.second << std::endl;
return 0;
}
C++ version. Uses a trie with search() and search_prefix() for matching complete words and prefixes for best match.
#include <iostream>
#include <initializer_list>
#include <iterator>
#include <vector>
class trie {
public:
trie() : root_(new node(0)) { }
trie(const std::initializer_list<std::string>& words) : root_(new node(0)) {
for (const std::string& word : words)
add(word);
}
~trie() {
delete root_;
}
void add(const std::string& word) {
if (word.empty())
return;
node* curr = root_;
for (size_t i = 0; i < word.size(); i++) {
char ch = ::tolower(word[i]);
size_t idx = ch - 'a';
if (curr->children_[idx]) {
curr = curr->children_[idx];
} else {
curr->children_[idx] = new node(ch);
curr = curr->children_[idx];
}
}
curr->is_word_ = true;
}
bool search(const std::string& word) const {
node* curr = search_common(word);
return curr && curr->is_word_;
}
bool search_prefix(const std::string& word) const {
node* curr = search_common(word);
return curr;
}
private:
struct node {
node(char ch) : ch_(ch), is_word_(false), children_{nullptr} { }
~node() {
for (node* n : children_)
delete n;
}
char ch_;
bool is_word_;
node* children_[26];
};
node* search_common(const std::string& word) const {
if (word.empty())
return nullptr;
node* curr = root_;
for (size_t i = 0; i < word.size(); i++) {
char ch = ::tolower(word[i]);
size_t idx = ch - 'a';
curr = curr->children_[idx];
if (!curr)
break;
}
return curr;
}
node* root_;
};
std::vector<std::string> find_words(const trie& tr, const std::string& str)
{
std::vector<std::string> words;
if (str.empty())
return words;
std::string longest_match;
for (size_t beg = 0, end = 1; end <= str.size(); end++) {
std::string curr_match = str.substr(beg, end - beg);
if (tr.search(curr_match)) {
// We are looking for the best (or longest) match
if (curr_match.size() > longest_match.size()) {
longest_match = curr_match;
}
} else {
// If there's no prefix with this match, save the longest so far
if (!tr.search_prefix(curr_match)) {
// Is there a best match?
if (!longest_match.empty()) {
words.push_back(longest_match);
longest_match.clear();
beg = end - 1;
end--;
} else {
// No best match found.
// Increment the begin position for the next match.
beg++;
}
}
}
}
if (!longest_match.empty())
words.push_back(longest_match);
return words;
}
int main() {
trie tr{"i", "love", "beer", "and", "wine", "out", "put", "output"};
std::string str = "ilovebeerandwineoutput";
std::vector<std::string> words = find_words(tr, str);
std::copy(words.begin(), words.end(), std::ostream_iterator<std::string>(std::cout, " "));
std::cout << std::endl;
return 0;
}
Yes, I saw that. Almost exactly like mine.
- Diego Giagio November 24, 2013
Simple solution using a symbol table and a digraph written in Java.
- Diego Giagio June 03, 2014