Diego Giagio
BAN USERC++ version using Sieve of Eratosthenes. Uses std::vector<bool> which in most implementations is equivalent to a bitset in terms of memory consumption.
#include <iostream>
#include <vector>
#include <iterator>
#include <cstdint>
#include <cmath>
#include <stdexcept>
#include <algorithm>
std::vector<uint64_t> sieve_eratosthenes(uint64_t n) {
if (n <= 2)
throw std::invalid_argument("n must be > 2");
std::vector<bool> sieve(n, true);
sieve[0] = false;
sieve[1] = false;
for (uint64_t i = 2; i < std::sqrt(n); i++) {
for (uint64_t j = i * 2; j < n; j += i) {
sieve[j] = false;
}
}
std::vector<uint64_t> primes;
for (uint64_t i = 2; i < sieve.size(); i++) {
if (sieve[i])
primes.push_back(i);
}
return primes;
}
struct sort_by_digit {
bool operator()(uint64_t a, uint64_t b) {
std::string astr = std::to_string(a);
std::string bstr = std::to_string(b);
if (astr.size() == bstr.size())
return a < b;
else
return astr[0] < bstr[0];
}
};
int main() {
std::vector<uint64_t> primes = sieve_eratosthenes(40);
std::sort(primes.begin(), primes.end(), sort_by_digit());
std::copy(primes.begin(), primes.end(), std::ostream_iterator<uint64_t>(std::cout, " "));
return 0;
}
C++ version.
#include <iostream>
#include <string>
std::string encode(const std::string& str) {
if (str.empty())
return "";
std::string encoded;
encoded.reserve(str.size());
char last_ch = str[0];
int n = 1;
for (size_t i = 1; i < str.size(); i++) {
char ch = str[i];
if (ch != last_ch) {
encoded.push_back(last_ch);
encoded.append(std::to_string(n));
last_ch = ch;
n = 1;
} else {
n++;
}
}
encoded.push_back(last_ch);
encoded.append(std::to_string(n));
return encoded;
}
int main() {
std::cout << encode("aabbaadddc");
return 0;
}
C++ version.
#include <iostream>
#include <regex>
#include <iterator>
#include <map>
#include <unordered_set>
#include <algorithm>
int main() {
std::string content = "Mr. Adam Mada, what's a carthorse? Must be some kind of orchestra! "
"Did you know that 'dama' is lady in portuguese?";
// Remove punctuaction from mail content
content.erase(std::remove_if(content.begin(), content.end(), [](char c) {
return !std::isalpha(c) && !std::isspace(c);
}), content.end());
// Split all words
std::regex re("\\s+");
std::sregex_token_iterator rti(content.begin(), content.end(), re, -1);
std::vector<std::string> words {rti, std::sregex_token_iterator()};
// Create a map where the key is each word in it's sorted form.
// The value of the map is a set of all corresponding anagrams.
std::map<std::string, std::unordered_set<std::string>> words_map;
for (std::string& word : words) {
if (word.size() < 2)
continue;
std::transform(word.begin(), word.end(), word.begin(), ::tolower);
std::string sorted_word(word);
std::sort(sorted_word.begin(), sorted_word.end());
auto it = words_map.find(sorted_word);
if (it == words_map.end()) {
words_map.emplace(sorted_word, std::unordered_set<std::string>{word});
} else {
auto& words = it->second;
words.insert(word);
}
}
// Print all anagrams
for (const auto& p : words_map) {
const auto& words = p.second;
if (words.size() > 1) {
std::copy(words.begin(), words.end(), std::ostream_iterator<std::string>(std::cout, " "));
std::cout << std::endl;
}
}
return 0;
}
C++ version.
#include <iostream>
#include <unordered_set>
std::string find_longest_nonrepeated(const std::string& str) {
if (str.empty())
return "";
std::string longest;
std::string curr;
std::unordered_set<char> seen;
for (char ch : str) {
if (!seen.count(ch)) {
curr.push_back(ch);
seen.insert(ch);
} else {
if (curr.size() > longest.size()) {
longest = curr;
}
curr.clear();
seen.clear();
}
}
if (curr.size() > longest.size())
longest = curr;
return longest;
}
int main() {
std::cout << find_longest_nonrepeated("abcdffghijkabcxptoabccaldoajjz");
std::cout << std::endl;
return 0;
}
C++ version. Uses O(n) space.
#include <iostream>
#include <unordered_set>
void permute(const std::string& perm, const std::string& str, std::unordered_set<std::string>& permutations) {
if (str.empty()) {
if (!permutations.count(perm)) {
std::cout << perm << std::endl;
permutations.insert(perm);
}
return;
}
for (size_t i = 0; i < str.size(); i++) {
permute(perm + str[i], str.substr(0, i) + str.substr(i + 1), permutations);
}
}
void permute(const std::string& str) {
std::unordered_set<std::string> permutations;
permute("", str, permutations);
}
int main() {
permute("aabc");
return 0;
}
C++ version.
#include <iostream>
std::string my_itoa(int n)
{
bool neg = false;
if (n < 0) {
neg = true;
n *= -1;
}
// special case: 0
if (n == 0)
return "0";
std::string s;
while (n > 0) {
s.insert(0, 1, static_cast<char>('0' + n % 10));
n /= 10;
}
if (neg)
s.insert(0, "-");
return s;
}
int main() {
std::cout << my_itoa(0) << std::endl;
std::cout << my_itoa(10) << std::endl;
std::cout << my_itoa(25) << std::endl;
std::cout << my_itoa(256) << std::endl;
std::cout << my_itoa(-10) << std::endl;
std::cout << my_itoa(-25) << std::endl;
std::cout << my_itoa(-256) << std::endl;
return 0;
}
C++ templated version.
#include <iostream>
template <int N>
void print_spiral(int arr[N][N]) {
if (!arr)
return;
int rows = N;
int cols = N;
for (int r = 0, c = 0; r < rows; r++) {
for (int c2 = c; c2 < cols; c2++) {
std::cout << arr[r][c2] << " ";
}
for (int r2 = r + 1; r2 < rows; r2++) {
std::cout << arr[r2][cols - 1] << " ";
}
for (int c2 = cols - 2; c2 >= c; c2--) {
std::cout << arr[rows - 1][c2] << " ";
}
for (int r2 = rows - 2; r2 > r; r2--) {
std::cout << arr[r2][c] << " ";
}
c++;
rows--;
cols--;
}
std::cout << std::endl;
}
int main() {
int arr3[][3] {{1,2,3}, {8,9,4}, {7,6,5}};
print_spiral(arr3);
int arr5[][5] {{1,2,3,4,5}, {16,17,18,19,6}, {15,24,25,20,7}, {14,23,22,21,8}, {13,12,11,10,9}};
print_spiral(arr5);
return 0;
}
This is my C++ version with O(n) time, O(n) space.
#include <iostream>
#include <unordered_set>
#include <vector>
template <typename T>
typename std::vector<T>::iterator find_first_duplicate(std::vector<T>& arr) {
std::unordered_set<T> set;
for (auto it = arr.begin(); it != arr.end(); it++) {
const T& elem = *it;
if (set.count(elem))
return it;
set.insert(elem);
}
return arr.end();
}
int main() {
std::vector<int> arr{4,3,1,2,5,9,5,4};
auto it = find_first_duplicate(arr);
if (it != arr.end())
std::cout << "first duplicate: " << *it << std::endl;
return 0;
}
This is my C++ version, O(n) complexity and O(1) space (in-place). First reverses the entire string. Then reverse each word separated by one or more spaces.
#include <iostream>
void my_reverse(std::string& str, size_t begin, size_t end)
{
while (begin < end)
std::swap(str[begin++], str[end--]);
}
std::string reverse_words(std::string& phrase)
{
// Reverse the entire string
my_reverse(phrase, 0, phrase.size() - 1);
// Reverse each word
size_t begin_pos = 0;
while (begin_pos != std::string::npos) {
size_t end_pos = phrase.find(' ', begin_pos);
if (end_pos == std::string::npos)
end_pos = phrase.length();
my_reverse(phrase, begin_pos, end_pos - 1);
begin_pos = phrase.find_first_not_of(' ', end_pos + 1);
}
return phrase;
}
int main() {
std::string str = "This is a test";
std::cout << reverse_words(str) << std::endl;
return 0;
}
This is my C++ version using two hashmaps. All operations are O(1).
#include <iostream>
#include <unordered_map>
#include <ctime>
template <typename T>
class rand_set {
public:
rand_set() : elem2pos_map_(), pos2elem_map_(), next_slot_(0) {
srand(time(NULL));
}
void add(T elem) {
// Map element -> slot
elem2pos_map_[elem] = next_slot_;
// Map slot -> element
pos2elem_map_[next_slot_] = elem;
// Increase slot
next_slot_++;
}
void remove(T elem) {
// Find element
auto it = elem2pos_map_.find(elem);
if (it != elem2pos_map_.end()) {
// Delete element
elem2pos_map_.erase(it);
size_t pos = it->second;
pos2elem_map_.erase(pos);
}
}
T removeRandom() {
if (pos2elem_map_.empty())
throw std::runtime_error("No elements found");
// Find random element. Must be within 0 and next_slot_
T elem;
size_t pos = rand() % next_slot_;
auto it = pos2elem_map_.find(pos);
if (it != pos2elem_map_.end()) {
elem = it->second;
} else {
elem = pos2elem_map_.begin()->second;
pos = elem2pos_map_.at(elem);
}
elem2pos_map_.erase(elem);
pos2elem_map_.erase(pos);
return elem;
}
private:
typedef std::unordered_map<T, size_t> elem2pos_map;
typedef std::unordered_map<size_t, T> pos2elem_map;
elem2pos_map elem2pos_map_;
pos2elem_map pos2elem_map_;
size_t next_slot_;
};
int main() {
rand_set<int> rset;
for (size_t i = 0; i < 10000; i++)
rset.add(i);
int rand = rset.removeRandom();
std::cout << rand << std::endl;
return 0;
}
This is my C++ solution with O(1) lookup. Basically it uses a hashmap to map the character position to a heap of a structure that holds the frequency and word position.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
class word_suggest {
public:
word_suggest(const std::vector<std::string>& words) {
initialize(words);
}
char suggest(const std::string& str) {
size_t pos = str.length();
const auto it = freq_map_.find(pos);
if (it == freq_map_.end())
return '?';
const frequency_heap& heap = it->second;
const frequency_entry& entry = heap[0];
return entry.c_;
}
private:
struct frequency_entry {
frequency_entry(char c, size_t word_pos) :
c_(c), word_pos_(word_pos), frequency_(1) { }
bool operator==(const frequency_entry& other) {
return c_ == other.c_;
}
bool operator!=(const frequency_entry& other) {
return !operator==(other);
}
bool operator<(const frequency_entry& other) {
// Compare the character
if (c_ == other.c_)
return false;
// Compare the frequency
if (frequency_ < other.frequency_) {
return true;
} else if (frequency_ == other.frequency_) {
// Compare the word position
if (word_pos_ < other.word_pos_)
return false;
else
return true;
} else {
return false;
}
}
char c_;
size_t word_pos_;
size_t frequency_;
};
void initialize(const std::vector<std::string>& words) {
size_t word_pos = 0;
for (const std::string& word : words)
add_word(word, word_pos++);
}
void add_word(const std::string& word, size_t word_pos) {
for (size_t i = 0; i < word.size(); i++) {
// Instantiate the frequency_entry for this character
frequency_entry entry(word[i], word_pos);
// Find the heap of chars of the current position
auto it = freq_map_.find(i);
if (it == freq_map_.end()) {
// There's no heap of this position on map.
// So, create one
frequency_heap heap = frequency_heap();
heap.push_back(entry);
// Add the heap to the map
freq_map_.insert(std::make_pair(i, heap));
} else {
// Found the heap of this position
frequency_heap& heap = it->second;
// Find the frequency_entry related to the current char
auto entry_it = std::lower_bound(heap.begin(), heap.end(), entry);
if (entry_it == heap.end() || *entry_it != entry) {
// Entry not found. Push to the heap
heap.push_back(entry);
std::push_heap(heap.begin(), heap.end());
} else {
// Entry found. Update it
frequency_entry& found_entry = *entry_it;
found_entry.frequency_++;
// Update the heap
std::make_heap(heap.begin(), heap.end());
}
}
}
}
typedef std::vector<frequency_entry> frequency_heap;
typedef std::unordered_map<size_t, frequency_heap> frequency_map;
frequency_map freq_map_;
};
int main() {
std::vector<std::string> words;
words.push_back("ABC");
words.push_back("BCD");
words.push_back("CBA");
word_suggest ws(words);
std::cout << "suggest(A): " << ws.suggest("A") << std::endl;
std::cout << "suggest(AB): " << ws.suggest("AB") << std::endl;
return 0;
}
Java version:
import java.util.HashSet;
import java.util.Set;
public class Main {
public static String removeAlternateDupChars(String str) {
Set<Character> characterSet = new HashSet<>();
char chars[] = str.toCharArray();
int j = 0;
for (int i = 0; i < chars.length; i++) {
if (!characterSet.contains(Character.toLowerCase(chars[i]))) {
chars[j++] = chars[i];
characterSet.add(Character.toLowerCase(chars[i]));
}
}
return new String(chars, 0, j);
}
/*
Write code to remove alternate duplicate characters (case insensitive) from a string in place.
For eg. "Today is the day" -> "Today ishe ". Also give test cases.
*/
public static void main(String[] args) {
System.out.println(removeAlternateDupChars("Today is the day"));
}
}
@yuxiaohui78 There's no stack overflow problem with this algorithm. The rotate_right function uses tail recursion, so this is optimized as a regular loop by the compiler, preventing the use of stack for each call. You can use an array of any size (limited by the maximum value of size_t) and it will work.
- Diego Giagio November 13, 2013C++ implementation with O(n) time and O(1) space using tail recursion.
#include <iostream>
#include <iterator>
static void rotate_right(int arr[], size_t len, int n)
{
n = n % len;
if (n == 0)
return;
for (size_t i = len - n, j = 0; i < len; i++, j++) {
std::swap(arr[i], arr[j]);
}
return rotate_right(arr + n, len - n, n);
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6};
rotate_right(arr, sizeof(arr)/sizeof(arr[0]), 2);
std::copy(std::begin(arr), std::end(arr),
std::ostream_iterator<int>(std::cout, " "));
return 0;
}
Solution in plain C:
#include <stdio.h>
int is_palindrome(const char *beg, const char *end)
{
while (end > beg) {
if (*end != *beg)
return 0;
beg++;
end--;
}
return 1;
}
void find_palindrome(const char *str, int pos, int last)
{
const char *beg;
const char *end;
if (pos == last)
return;
printf("P: %c\n", str[pos]);
find_palindrome(str, pos + 1, last);
beg = str + pos;
end = str + last;
while (end > beg) {
if (is_palindrome(beg, end))
printf("P: %.*s\n", end - beg + 1, beg);
end--;
}
}
void find_palindromes(const char *str)
{
find_palindrome(str, 0, strlen(str));
}
int main(void) {
find_palindromes("abba");
return 0;
}
You must be kidding that you used std::to_string(). Do you think an interviewer will accept this? He wants you to implement that. That's the point of the question.
- Diego Giagio November 24, 2013