Omkar
BAN USEROf course these questions don't have values unless very specific scaled up things need some tuning. O(n2) is common implementation that works well. Here is O(n) implementation based on Manacher's algorithm for odd-length palindromes e.g. madam (can be extended to include even-length palindromes e.g. deed - more complex, but possible)
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
using namespace std;
inline bool areEqualCharacters(char c1, char c2)
{
// May be replaced with case-insensitive compare
if (tolower(c1) == tolower(c2))
return true;
return false;
}
int expand(string &s, size_t sLen, int c, int offset = 1)
{
int left = c - offset;
int right = c + offset;
int start = left;
// Assuming odd compare.
// Logic can be expanded for palindrome of even length.
while ((left >= 0) && (right < sLen))
{
if (!areEqualCharacters(s[left], s[right]))
{
break;
}
--left;
++right;
}
if (left != start) {
++left;
--right;
return (right - left + 1);
}
return 0; // Unable to expand
}
string findLargestPalindrome(string& s)
{
size_t sLen = s.length();
vector<int> expansion(sLen);
multimap<int, int> sortedExpansion;
for (int center = 0; center < sLen;)
{
int expandedRange = expand(s, sLen, center);
expansion[center] = expandedRange;
sortedExpansion.emplace(expandedRange, center);
if (expandedRange > 0)
{
// Mirror right and select next center
int halfRange = expandedRange / 2;
int mirrorValue, rightIndex = 0, largestRight = 0;
while (halfRange > 0) {
mirrorValue = expansion[center - halfRange];
rightIndex = center + halfRange;
expansion[rightIndex] = mirrorValue;
sortedExpansion.emplace(mirrorValue, rightIndex);
if (expansion[largestRight] < mirrorValue)
largestRight = rightIndex;
--halfRange;
}
// Move center to next possible largest palindrome
// or beyond current mirrored right boundary
center = (0 != largestRight) ? largestRight: (rightIndex + 1);
}
else
++center;
}
auto largestString = sortedExpansion.rbegin();
if (1 < largestString->first)
{
pair<int, int> p = *largestString;
string largestPalindromeSub = s.substr(largestString->second - (largestString->first/2), largestString->first);
return largestPalindromeSub;
}
return ""; // No palindrome sub-string found.
}
int main()
{
//string s = "abracadabra";
string s = "aaaomkaraKmoa";
string lp = findLargestPalindrome(s);
return 0;
}
C++
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
void processDeps(int item, map<int, set<int>>& depList, stack<int>& depOrder, set<int>& visitedItems) {
if (visitedItems.end() != visitedItems.find(item))
return;
visitedItems.insert(item);
if (depList[item].empty()) {
depOrder.push(item);
return;
}
for (auto dependencyChild : depList[item]) {
if (visitedItems.end() != visitedItems.find(dependencyChild))
continue;
processDeps(dependencyChild, depList, depOrder, visitedItems);
}
depOrder.push(item);
}
bool isValidOrder(int* order, int nElems, map<int, set<int>>& invertDepList) {
vector<int> v(order, order + nElems);
bool isValid = true;
for (int i = 1; (i < nElems) && isValid; ++i) {
for (int vElem : invertDepList[v[i]])
{
vector<int> v2(order, order + i);
if (v2.end() != find(v2.begin(), v2.end(), vElem)) {
isValid = false;
break;
}
}
}
return isValid;
}
int main()
{
typedef enum {
SHIRT, TIE, TROUSER, BELT, SOCKS, SHOES
} Item;
map<int, string> items = { { SHIRT, "Shirt" },{ TIE, "Tie" },{ TROUSER, "Trouser" },{ BELT, "Belt" },
{ SOCKS, "Socks" },{ SHOES, "Shoes" } };
map<int, set<int>> depList = {
{ SHIRT,{} },
{ TIE,{ SHIRT } },
{ TROUSER,{} },
{ BELT,{ SHIRT, TROUSER } },
{ SOCKS,{ TROUSER } },
{ SHOES,{ SOCKS } }
};
map<int, set<int>> invertDepList = {
{ SHIRT,{ TIE, BELT, TROUSER } },
{ TIE,{} },
{ TROUSER,{ BELT, SOCKS } },
{ BELT,{} },
{ SOCKS,{ SHOES } },
{ SHOES,{} }
};
stack<int> depOrder;
set<int> visitedItems;
for (auto item : items) {
processDeps(item.first, invertDepList, depOrder, visitedItems);
}
int order[6], i = 0;
int currentOrder[6] = { 0, 1, 2, 3, 4, 5 };
while (!depOrder.empty()) {
order[i] = depOrder.top();
depOrder.pop();
++i;
}
set<int> indepNodes;
for_each(depList.begin(), depList.end(), [&indepNodes](pair<int, set<int>> itm) { if (itm.second.empty()) indepNodes.insert(itm.first); });
// Calculate combinations those start from independent nodes
vector<vector<int>> possibleCombinations;
do {
vector<int> v(currentOrder, currentOrder + 6);
if (isValidOrder(currentOrder, 6, invertDepList)) {
possibleCombinations.push_back(v);
}
} while (next_permutation(currentOrder, currentOrder + 6));
// Display possible combinations
for_each(possibleCombinations.begin(), possibleCombinations.end(), [&items](vector<int>& itms) {
for (auto i : itms)
cout << items[i].c_str() << ", ";
cout << "\b\b \n";
});
return 0;
}
C++ implementation
#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int nArray[] = {
5, 4, 2, 3, 6, 7, 8, 3, 4, 5,
6, 7, 9, 3, 2, 3, 5, 6, 10, 5,
3, 2, 5, 2, 3
};
int N = 5; // Get top 5 frequent numbers
map<int, int> mCounts;
for (auto number : nArray)
mCounts[number] ++;
vector<pair<int, int>> counts(mCounts.begin(), mCounts.end()); // Get counts into sortable container
sort(counts.rbegin(), counts.rend(), [](pair<int, int> a, pair<int, int>b) { // Sort according to counts
return (a.second < b.second);
});
for (int i = 0; (i < N) && i < counts.size(); ++i) // Display frequent N numbers
cout << i + 1 << "] " << counts[i].first << ": " << counts[i].second << " times" << endl;
cout << "Press enter to close.";
getline(cin, string());
return 0;
}
Please ignore earlier unformatted posts.. For some reason links are not allowed. Had to remove data and format the code..
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <thread>
#include <list>
#include <chrono>
using namespace std;
class Cache {
map <string, time_t> CacheItems;
public:
void add(string url, time_t timeoutSeconds)
{
timeoutSeconds += time(NULL);
CacheItems[url] = timeoutSeconds;
cout << "Added ==> " << url << ": " << timeoutSeconds << endl;
}
void eraseTimedOut() {
time_t now = time(NULL);
cout << now << endl;
list<string> expiredCacheItems;
for (auto iItem = CacheItems.rbegin(); iItem != CacheItems.rend(); ++iItem) {
if (0 >= difftime(iItem->second, now)) {
cout << "Expired: " << iItem->first << endl;
expiredCacheItems.push_back(iItem->first);
}
}
if (!expiredCacheItems.empty()) {
for (auto expiredItem : expiredCacheItems) {
CacheItems.erase(expiredItem);
}
expiredCacheItems.clear();
}
}
bool empty() {
return CacheItems.empty();
}
volatile static bool AbortCache;
static void waitForCacheExpiry()
{
Cache CacheItems;
CacheItems.add("google", 6);
CacheItems.add("quickexpire", 3);
CacheItems.add("myurl", 12);
while ((!CacheItems.empty()) && (!AbortCache)) {
this_thread::sleep_for(chrono::milliseconds(1000));
CacheItems.eraseTimedOut();
}
}
};
volatile bool Cache::AbortCache = false;
int main()
{
Cache c;
thread cacheExpiry(c.waitForCacheExpiry);
cacheExpiry.join();
string line;
cout << "Press enter to close.";
getline(cin, line);
return 0;
}
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <thread>
#include <list>
#include <chrono>
using namespace std;
class Cache {
map <string, time_t> CacheItems;
public:
void add(string url, time_t timeoutSeconds)
{
timeoutSeconds += time(NULL);
CacheItems[url] = timeoutSeconds;
cout << "Added ==> " << url << ": " << timeoutSeconds << endl;
}
void eraseTimedOut() {
time_t now = time(NULL);
cout << now << endl;
list<string> expiredCacheItems;
for (auto iItem = CacheItems.rbegin(); iItem != CacheItems.rend(); ++iItem) {
if (0 >= difftime(iItem->second, now)) {
cout << "Expired: " << iItem->first << endl;
expiredCacheItems.push_back(iItem->first);
}
}
if (!expiredCacheItems.empty()) {
for (auto expiredItem : expiredCacheItems) {
CacheItems.erase(expiredItem);
}
expiredCacheItems.clear();
}
}
bool empty() {
return CacheItems.empty();
}
volatile static bool AbortCache;
static void waitForCacheExpiry()
{
Cache CacheItems;
CacheItems.add("google", 6);
CacheItems.add("quickexpire", 3);
CacheItems.add("myurl", 12);
while ((!CacheItems.empty()) && (!AbortCache)) {
this_thread::sleep_for(chrono::milliseconds(1000));
CacheItems.eraseTimedOut();
}
}
};
volatile bool Cache::AbortCache = false;
int main()
{
Cache c;
thread cacheExpiry(c.waitForCacheExpiry);
cacheExpiry.join();
string line;
cout << "Press enter to close.";
getline(cin, line);
return 0;
}
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <thread>
#include <list>
#include <chrono>
using namespace std;
class Cache {
map <string, time_t> CacheItems;
public:
void add(string url, time_t timeoutSeconds)
{
timeoutSeconds += time(NULL);
CacheItems[url] = timeoutSeconds;
cout << "Added ==> " << url << ": " << timeoutSeconds << endl;
}
void eraseTimedOut() {
time_t now = time(NULL);
cout << now << endl;
list<string> expiredCacheItems;
for (auto iItem = CacheItems.rbegin(); iItem != CacheItems.rend(); ++iItem) {
if (0 >= difftime(iItem->second, now)) {
cout << "Expired: " << iItem->first << endl;
expiredCacheItems.push_back(iItem->first);
}
}
if (!expiredCacheItems.empty()) {
for (auto expiredItem : expiredCacheItems) {
CacheItems.erase(expiredItem);
}
expiredCacheItems.clear();
}
}
bool empty() {
return CacheItems.empty();
}
volatile static bool AbortCache;
static void waitForCacheExpiry()
{
Cache CacheItems;
CacheItems.add("google", 6);
CacheItems.add("quickexpire", 3);
CacheItems.add("myurl", 12);
while ((!CacheItems.empty()) && (!AbortCache)) {
this_thread::sleep_for(chrono::milliseconds(1000));
CacheItems.eraseTimedOut();
}
}
};
volatile bool Cache::AbortCache = false;
int main()
{
Cache c;
thread cacheExpiry(c.waitForCacheExpiry);
cacheExpiry.join();
string line;
cout << "Press enter to close.";
getline(cin, line);
return 0;
}
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <stack>
#include <vector>
using namespace std;
map<char, list<char>> str = {
{ '1', { 'a', 'b', 'c', 'd', 'e' } },
{ '2', { 'v', 'w', 'x', 'y', 'z' } }
};
list<string> combs;
void getCombinations(string& currentCombination, string& sub) {
if (sub.empty()) {
combs.push_back(currentCombination);
return;
}
for (auto ch : str[sub[0]]) {
currentCombination.push_back(ch);
getCombinations(currentCombination, sub.substr(1));
currentCombination.pop_back();
}
}
int main()
{
string input = "12212";
string currentCombination;
getCombinations(currentCombination, input);
for (auto combination : combs) {
cout << combination << endl;
}
string line;
cout << "Press enter to close" << endl;
getline(cin, line);
return 0;
}
void sortMatrix(int* matrix, int row, int col) {
std::qsort(matrix, row*col, sizeof(int), [](const void *left, const void *right) -> int {
int *i = (int*)left;
int *j = (int*)right;
return (*j - *i);
});
std::qsort(matrix, row, sizeof(int)*col, [](const void *left, const void *right) -> int {
return ((*(int*)left) - (*(int*)right));
});
}
int main()
{
int matrix[][4] = {
{ 3, 2, 5, 11 },
{ 6, 8, 7, 1 },
{ 4, 10, 9, 12 }
};
sortMatrix(&matrix[0][0], 3, 4);
for (int r = 0; r < 3; ++r) {
for (int c = 0; c < 4; ++c) {
cout << matrix[r][c] << " ";
}
cout << endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main ()
{
// Example 1
//int a[] = { 1, 5 };
//int b[] = { 5, 9 };
//int c[] = { 1, 5 };
// Example 2; No restrictions on array length equality, but must contain at least one element each.
int a[] = { -3, -2, 0, 0, 1, 4 };
int b[] = { -10, -8, -5, -3, -1 };
int c[] = { 1, 5, 10, 15, 20 };
// Get array sizes;
int aSize = (sizeof(a) / sizeof(int));
int bSize = (sizeof(b) / sizeof(int));
int cSize = (sizeof(c) / sizeof(int));
// Calculate mean value of array b
int bm = 0;
for_each(b, b + bSize, [&bm](int bb) {
bm += bb;
});
bm /= bSize;
// Calculate closeness of each element in array a and array c to mean value of array b (bm)
map<int, int> aClosest, bClosest, cClosest;
int i = 0;
for_each(a, a + aSize, [&a, &bm, &i, &aClosest](int aa) {
aClosest[abs(aa - bm)] = i;
++i;
});
i = 0;
for_each(c, c + cSize, [&c, &bm, &i, &cClosest](int cc) {
cClosest[abs(cc - bm)] = i;
++i;
});
int ai = 0, bi = 0, ci = 0;
// Simply lookup for element at minimal distant to bm
ai = min_element(aClosest.begin(), aClosest.end())->second;
ci = min_element(cClosest.begin(), cClosest.end())->second;
int acm = (ai + ci) / 2;
i = 0;
// Calculate closeness of each element in array b to its mean value (or to closest element in array a/b)
for_each(b, b + bSize, [&bClosest, &acm, &i](int bb) {
bClosest[abs(acm - bb)] = i;
++i;
});
// Locate closest element in array b
bi = min_element(bClosest.begin(), bClosest.end())->second;
// we have required ai, bi and ci values
return 0;
}
Feedbacks please? Any scope to optimize? I would love to hear improvements...
- Omkar June 15, 2017class Node {
char c;
public:
Node()
{
c = 0;
next = NULL;
}
Node *next;
Node(char ch)
{
c = ch;
next = NULL;
}
bool operator != (Node& n)
{
return (c != n.c);
}
};
Node* getNthNode(Node *current, int offset)
{
while ((offset > 0) && (current))
{
--offset;
current = current->next;
}
return current;
}
bool isPalindrome(Node *first) {
Node *forwardCompare = first, *reverseCompare, *last;
int i = 1, stringLength;
if (NULL == first)
return false;
while (forwardCompare->next)
{
forwardCompare = forwardCompare->next;
i++;
}
stringLength = i;
reverseCompare = last = forwardCompare;
forwardCompare->next = first; // create circular linked-list.
forwardCompare = first;
bool isNotPalindrome = false;
for (i = 0; i < (stringLength / 2); ++i)
{
if (*forwardCompare != *reverseCompare)
{
isNotPalindrome = true;
break;
}
forwardCompare = forwardCompare->next;
reverseCompare = getNthNode(reverseCompare, stringLength - 1); // Simulate backward traversal
}
last->next = NULL;
return !isNotPalindrome;
}
int main()
{
Node singlyString[] = { 'a', 's', 'd' };
const int nChars = (sizeof(singlyString) / sizeof(Node));
for (int i = 0; i < (nChars - 1); ++i)
singlyString[i].next = &singlyString[i + 1];
cout << ((isPalindrome(singlyString)) ? "true" : "false");
}
How about this C++ implementation? (Based on azambhrgn May 12, 2017 algorithm.)
- Omkar June 25, 2017