Teh Kok How
BAN USER- 0of 0 votes
AnswersGiven a 2-dimensional array with arbitrary sizes and contains random positive values, you are required to move from the first element [0][0] to the last element [n][n] using the path which will yield the maximum sum of all the elements traversed. You can only move right and down; NOT left and up.
- Teh Kok How in United States| Report Duplicate | Flag | PURGE
Amazon Algorithm
The answer given in the question is wrong. It should be "ABCDEF" (6) * "XTFN" (4) = 24.
long MaxLengths(vector<string>& data)
{
sort(data.begin(), data.end(), [&](string a, string b) {return a.size() > b.size(); });
map<long, vector<string>&> lengths;
for (vector<string>::const_iterator it = data.begin(); it != data.end(); it++)
for (vector<string>::const_iterator it1 = it + 1; it1 != data.end(); it1++) {
size_t i = 0;
for (; i < it1->size(); i++)
if (it->find(it1[i]) != string::npos)
break;
if (i != it1->size() - 1)
return it->size() * it1->size();
}
return 0;
}
vector<char> AddVectors(vector<char>& a, vector<char>& b)
{
char carry = 0;
vector<char> result;
vector<char>::reverse_iterator aIt = a.rbegin();
vector<char>::reverse_iterator bIt = b.rbegin();
for (; aIt != a.rend() && bIt != b.rend(); aIt++, bIt++) {
result.push_back((*aIt + *bIt + carry) % 10);
carry = (*aIt + *bIt + carry) / 10;
}
if (aIt != a.rend()) {
result.push_back((*aIt + carry) % 10);
carry = (*aIt + carry) / 10;
}
if (bIt != b.rend()) {
result.push_back((*bIt + carry) % 10);
carry = (*bIt + carry) / 10;
}
if (carry > 0)
result.push_back(carry);
reverse(result.begin(), result.end());
return result;
}
bool JSONValidation(string json)
{
size_t keyCount = 0, valueCount = 0, leftBraceCount = 0, rightBraceCount = 0;
ostringstream oss;
string key = "", value = "";
for (string::const_iterator it = json.begin(); it != json.end(); it++)
{
if (*it == '{')
{
leftBraceCount++;
key = "";
value = "";
oss.str("");
}
else if (*it == '}' || *it == ' ' || *it == ',') {
value = oss.str();
oss.str("");
if (value != "")
valueCount++;
if (*it == '}')
rightBraceCount++;
if (leftBraceCount > rightBraceCount && keyCount > valueCount)
valueCount++;
}
else if (*it == ':') {
key = oss.str();
oss.str("");
if (key != "")
keyCount++;
}
else
oss << *it;
}
return leftBraceCount == rightBraceCount && keyCount == valueCount;
}
Use Suffix Tree.
For example: s "Mississippi"
t1: "is" -> index 1, 4
t2: "si" -> index 3, 6
t2: "ssi" -> index 2, 5
shortest substring of s which contains t1,t2 and t3 would be substring with index 1 to 4.
long buildmax(vector<long>& a, vector<long>& b, size_t size)
{
long maxA = 0, maxB = 0, result = 0;
size_t indexA = 0, indexB = 0;
for (size_t i = 0; i < size; i++)
{
result *= 10;
for (size_t i = indexA; i < a.size(); i++)
if (a[i] >= maxA)
{
maxA = a[i];
indexA = i;
}
for (size_t i = indexB; i < b.size(); i++)
if (b[i] >= maxB)
{
maxB = b[i];
indexB = i;
}
if (maxA > maxB)
{
result += maxA;
indexA++;
maxA = 0;
} else {
result += maxB;
indexB++;
maxB = 0;
}
}
return result;
}
(1) Check for Invalid numbers in the array for "Invalid"
(2) Check the sum of the arrays for "Equal" / "Unequal"
long concat(vector<long>& data)
{
ostringstream oss;
std::sort(data.begin(), data.end(), [&data](long i, long j) -> bool {
ostringstream a, b;
a << i << j;
b << j << i;
return a.str() < b.str();
});
for (vector<long>::reverse_iterator it = data.rbegin(); it != data.rend(); it++)
oss << *it;
istringstream iss(oss.str());
long result;
iss >> result;
return result;
}
O(N) solution:
size_t diffpairs(set<long>& numbers, long diff)
{
size_t count = 0;
long tmp;
set<long>::iterator srcIt;
for (set<long>::const_iterator it = numbers.begin(); it != numbers.end(); it++)
{
tmp = diff + *it;
srcIt = numbers.find(tmp);
if (srcIt != numbers.end())
{
count++;
cout << *it << ", " << *srcIt << endl;
}
}
return count;
}
unsigned long long XOR(unsigned long long n)
{
if (n <= 1)
return n;
return n ^ XOR(n - 1);
}
vector<string> numbersegments(vector<long>& data)
{
ostringstream oss;
vector<string> result;
oss << data.front();
for (vector<long>::iterator it = data.begin(); it != data.end(); it++)
{
if (it == (data.end() - 1) || *it != (*(it + 1) - 1))
{
if (!oss.str().empty())
oss << '-';
oss << *it;
result.push_back(oss.str());
oss.str("");
} else if (oss.str().empty())
oss << *it;
}
return result;
}
vector<int> Increment(vector<int>& data)
{
int j = 1;
vector<int> result;
for (vector<int>::reverse_iterator it = data.rbegin(); it != data.rend(); it++)
{
j += *it;
if (j < 10) {
result.push_back(j);
j = 0;
} else {
result.push_back(j - 10);
j = 1;
}
}
if (j == 1)
result.push_back(j);
reverse(result.begin(), result.end());
return result;
}
I don't understand the question. What does "lexicographical order of the new string is smallest" mean?
- Teh Kok How September 11, 2015void * alignedMalloc(size_t size, size_t alignment)
{
size_t bytes = alignment / 8;
return malloc(size + (size % bytes) / bytes);
}
void alignedFree(void **p)
{
std::free(*p);
*p = nullptr;
}
set<string> process(string& file, int n)
{
ostringstream oss;
vector<string> words;
set<string> ngrams;
split(file, ' ', words);
for (size_t i = 0; i <= words.size() - n; i++)
{
oss << words[i] << ' ' << words[i+1] << ' ' << words[i+2];
ngrams.emplace(oss.str());
oss.str("");
}
return ngrams;
}
set<string> intersectionNgram(string& file1, string& file2, int n)
{
set<string> result;
set<string> ngrams1 = process(file1, n);
if (!ngrams1.size())
return result;
set<string> ngrams2 = process(file2, n);
set_intersection(ngrams1.begin(), ngrams1.end(), ngrams2.begin(), ngrams2.end(), std::inserter(result,result.begin()));
return result;
}
Much better O(N) solution:
// 0 1 2 3 4 5 6 7 8 9
// ^ (10 / 2 - 1)
// (0,9), (0,8) 2
// (1,9), (1,8), (1,7), 3
// (2,9), (2,8), (2,7), (2,6), 4
// (3,9), (3,8), (3,7), (3,6), (3,5) 5
// (4,9), (4,8), (4,7), (4,6), (4,5), (4,4) 6
// (5,9), (5,8), (5,7), (5,6), (5,5) 5
// (6,9), (6,8), (6,7), (6,6) 4
// (7,9), (7,8), (7,7) 3
// (8,9), (8,8) 2
// (9,9) 1
// Count = 35
// 0 1 2 3 4 5 6 7 8 9 10
// ^ (11 / 2 - 1)
// (0,10), (0,9), (0,8) 3
// (1,10), (1,9), (1,8), (1,7), 4
// (2,10), (2,9), (2,8), (2,7), (2,6), 5
// (3,10), (3,9), (3,8), (3,7), (3,6), (3,5) 6
// (4,10), (4,9), (4,8), (4,7), (4,6), (4,5), (4,4) 7
// (5,10), (5,9), (5,8), (5,7), (5,6), (5,5) 6
// (6,10), (6,9), (6,8), (6,7), (6,6) 5
// (7,10), (7,9), (7,8), (7,7) 4
// (8,10), (8,9), (8,8) 3
// (9,10), (9,9) 2
// Count = 45
size_t greaterthansumpairs(vector<long>& numbers, long sum)
{
size_t count = 0, count1;
for (size_t it = 0; it <= numbers.size()/2 - 1; it++) {
count1 = 0;
for (size_t rit = numbers.size() - 1; rit >= 0 && numbers[it] + numbers[rit] >= sum && it <= rit; rit--)
count1++;
if (it == 0 && count1 > 0)
count += count1 - 1;
if (it != numbers.size() / 2 - 1)
count1 *= 2;
count += count1;
}
return count;
}
typedef struct Position {
Position() : row(-1), col(-1) {}
Position(size_t r, size_t c) : row(r), col(c) {}
size_t row;
size_t col;
} position_t;
bool PathExists(vector<vector<char>>& grid, size_t r, size_t c, size_t y, size_t x, queue<string>& result, char obstacle)
{
string pos, origin;
ostringstream oss, oss1;
set<string> visited;
map<string, string> route;
vector<position_t> positions;
positions.push_back(position_t(r, c));
oss << r << c;
origin = oss.str();
oss.str("");
while (!positions.empty()) {
vector<position_t> nextHops(positions);
positions.clear();
for (vector<position_t>::const_iterator it = nextHops.begin(); it != nextHops.end(); it++) {
oss1.str("");
oss1 << it->row << it->col;
// Go Down
if (it->row + 1 < grid.size())
if (it->row + 1 == y && it->col == x) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row + 1 << it->col;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row + 1][it->col] != obstacle) {// Obstacle. Cancel this route
oss.str("");
oss << it->row + 1 << it->col;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row + 1, it->col));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
// Go Right
if (it->col + 1 < grid[it->row].size())
if (it->row == y && it->col + 1 == x) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row << it->col + 1;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row][it->col + 1] != obstacle) {
oss.str("");
oss << it->row << it->col + 1;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row, it->col + 1));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
// Go Up
if (it->row > 0)
if (it->row - 1 == y && it-> col == x) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row - 1 << it->col;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row - 1][it->col] != obstacle) {
oss.str("");
oss << it->row - 1 << it->col;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row - 1, it->col));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
// Go Left
if (it->col > 0)
if (it->row == y && it->col + 1 == x) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row << it->col - 1;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row][it->col - 1] != obstacle) {
oss.str("");
oss << it->row << it->col - 1;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row, it->col - 1));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
}
}
return false;
}
static string find(List<Item> items, int rank)
{
if (rank > 0 && items != null && items.Any() && items.Count() >= rank)
{
return items.OrderByDescending(i => i.Count).ElementAt(rank - 1).ID;
} else
return string.Empty;
}
static string subtract(Stream a, Stream b)
{
int i;
StringBuilder sb = new StringBuilder();
while ((i = b.ReadByte()) > 0)
sb.Append(a.ReadByte() - i);
return sb.ToString();
}
string subtract(istream& a, istream& b)
{
ostringstream oss;
char i, j;
while (b.read(&j, 1))
{
a.read(&i, 1);
oss << i - j;
}
return oss.str();
}
public void Merge(StateLinkedList states)
{
if (states == null || !states.States.Any())
return;
if (States == null || !States.Any() && states.States != null && states.States.Any())
States = states.States;
for (var state = States.First; state != null; state = state.Next)
for (var st = states.States.First; st != null; )
{
if (state.Value.CompareTo(st.Value) > 0)
{
LinkedListNode<State> old = st;
st = st.Next;
states.States.Remove(old);
States.AddBefore(state, old);
} else
st = st.Next;
}
}
long NextSparseNumber(long number)
{
long i = number;
long shift;
for (shift = 0; i > 0; shift++, i=i>>1)
{
if (!(i & 3))
return i + 1 << shift;
else if ((i & 7) == 1)
return 1 << (shift + 1) > number ? 1 << (shift + 1) : number - (1 << shift) + (1 << (shift + 1));
}
return number == 0 ? 1 : 1 << (shift + 1);
}
Test cases:
assert(NextSparseNumber(0) == 1);
assert(NextSparseNumber(1) == 2);
assert(NextSparseNumber(2) == 4);
assert(NextSparseNumber(3) == 4);
assert(NextSparseNumber(4) == 5);
assert(NextSparseNumber(5) == 8);
assert(NextSparseNumber(6) == 8);
assert(NextSparseNumber(7) == 8);
assert(NextSparseNumber(8) == 9);
assert(NextSparseNumber(9) == 10);
string GetRange(vector<long>& input)
{
ostringstream oss;
vector<long> numbers(input);
sort(numbers.begin(), numbers.end());
if (!numbers.empty())
{
size_t first = 0;
for (size_t i = 1; i < numbers.size(); i++)
{
if ((numbers[i] - numbers[i - 1]) > 1)
{
oss << numbers[first];
if (first != i - 1)
oss << " - " << numbers[i - 1] << ", ";
else
oss << ", ";
first = i;
}
}
oss << numbers[first];
if (first != numbers.size() - 1)
oss << " - " << numbers[numbers.size() - 1];
}
return oss.str();
}
Implementation using std::map
bool isPalindrome(string const& s)
{
size_t odd = 0;
size_t length = s.length();
map<char, size_t> counts;
for (string::const_iterator it = s.begin(); it != s.end(); it++)
counts[*it]++;
for (map<char, size_t>::const_iterator it = counts.begin(); it != counts.end(); it++)
if (it->second % 2)
if (!(length % 2))
return false;
else if (++odd > 1)
return false;
return true;
}
Implementation using sort() one for-loop:
bool isPalindrome1(string const& s)
{
size_t count = 1, odd = 0;
size_t length = s.length();
string s1(s);
sort(s1.begin(), s1.end());
for (size_t i = 1; i < length; i++)
{
if (s1[i] == s1[i - 1])
count++;
else
{
if (count % 2)
if (!(length % 2))
return false;
else if (++odd > 1)
return false;
count = 1;
}
}
return true;
}
Need 2 binary search operations. The difference between the 2 returned indices is the count of the age.
int BinarySearchCountUpper(vector<long> source, int toSearch, int start, int end)
{
int mid = start + (end - start) / 2 + (end - start) % 2;
if (end < start)
return 0;
if (source[mid] == toSearch && (mid == end || source[mid + 1] != toSearch))
return mid;
else if (source[mid] <= toSearch)
return BinarySearchCountUpper(source, toSearch, mid + 1, end);
else
return BinarySearchCountUpper(source, toSearch, start, mid - 1);
}
int BinarySearchCountLower(vector<long> source, int toSearch, int start, int end)
{
int mid = start + (end - start) / 2 + (end - start) % 2;
if (end < start)
return 0;
if (source[mid] == toSearch && (mid == start || source[mid - 1] != toSearch))
return mid;
else if (source[mid] < toSearch)
return BinarySearchCountLower(source, toSearch, mid + 1, end);
else
return BinarySearchCountLower(source, toSearch, start, mid - 1);
}
Test:
count = BinarySearchCountUpper(ages, 20, 0, ages.size() - 1) - BinarySearchCountLower(ages, 20, 0, ages.size() - 1) + 1;
assert(round(1234.5678, 1) == 1234.6);
assert(round(1234.5678, 2) == 1234.57);
assert(round(1234.5678, 3) == 1234.568);
assert(round(1234.5678, 4) == 1234.5678);
assert(round(0.1234, 1) == 0.1);
assert(round(0.1234, 2) == 0.12);
assert(round(0.1234, 3) == 0.123);
assert(round(0.1234, 4) == 0.1234);
double round(double num , int n)
{
unsigned long long tmp, tmp1;
tmp = num * pow(10, n+1);
tmp1 = num * pow(10, n);
if (tmp%10 >= 5)
tmp1++;
return tmp1 / pow(10, n);
}
I can confirm that the implementation given at the url is WRONG.
- Teh Kok How September 04, 2014My C++ implementation:
void EqualAverageDivide(vector<long>& data, vector<long> &left)
{
long sum = 0, P = 0;
size_t N = data.size(), K;
// Sort the data
std::sort(data.begin(), data.end());
for (vector<long>::const_iterator it = data.begin(); it != data.end(); it++)
sum += *it;
for (K = 1; K < (N - K); K++) {
if (((K * sum) % N)) // check if such P can be integer (we operate with array of integers).
continue;
// picking K integers with sum of P from sorted array of integers
P = K * sum / N;
if (GetSum(data, K, P, 0, left))
break;
}
}
bool GetSum(vector<long> &data, size_t K, long P, size_t index, vector<long>& left)
{
if (!P)
return K == 0;
else if (!K)
return P == 0;
else if (index >= data.size())
return false;
for (size_t i = index; i < data.size(); i++) {
if (GetSum(data, K - 1, P - data[i], i + 1, left)) {
left.push_back(data[i]);
return true;
}
}
return false;
}
Yes, worst-case is not O(N). It's O(N^2). Any idea how to improve this code is appreciated.
- Teh Kok How September 04, 2014O(1)-space but not sure O(N) time-complexity solution:
void sortNumbers(vector<long> &data)
{
size_t j;
long tmp;
for (size_t i = 0; i < data.size(); i++) {
if (data[i] < 0 && data[i + 1] < 0) {// Look for positive number
for (j = i + 1; j < data.size() && data[j] < 0; j++);
if (j == data.size())
break;
// Shift i+1 to j-1
tmp = data[j];
for (size_t k = j; k > i; k--)
data[k] = data[k - 1];
data[i + 1] = tmp;
} else if (data[i] > 0 && data[i + 1] > 0) {// Look for positive number
for (j = i + 1; j < data.size() && data[j] > 0; j++);
if (j == data.size())
break;
// Shift i+1 to j-1
tmp = data[j];
for (size_t k = j; k > i; k--)
data[k] = data[k - 1];
data[i + 1] = tmp;
}
}
}
O(1)-space but not sure O(N) time-complexity solution:
void sortNumbers(vector<long> &data)
{
size_t j;
long tmp;
for (size_t i = 0; i < data.size(); i++) {
if (data[i] < 0 && data[i + 1] < 0) {// Look for positive number
for (j = i + 1; j < data.size() && data[j] < 0; j++);
if (j == data.size())
break;
// Shift i+1 to j-1
tmp = data[j];
for (size_t k = j; k > i; k--)
data[k] = data[k - 1];
data[i + 1] = tmp;
} else if (data[i] > 0 && data[i + 1] > 0) {// Look for positive number
for (j = i + 1; j < data.size() && data[j] > 0; j++);
if (j == data.size())
break;
// Shift i+1 to j-1
tmp = data[j];
for (size_t k = j; k > i; k--)
data[k] = data[k - 1];
data[i + 1] = tmp;
}
}
}
static List<string> FindTopNVisitedKPageSequence(List<string> data, int N, int K)
{
string sequence;
Dictionary<string, long> pages = new Dictionary<string, long>();
data.ForEach(d =>
{
if (d.Length >= K)
for (int i = 0; i < d.Length; i++)
if (i + K <= d.Length)
{
sequence = d.Substring(i, K);
if (!pages.ContainsKey(sequence))
pages.Add(sequence, 1);
else
pages[sequence]++;
}
});
List<IGrouping<long, KeyValuePair<string, long>>> groups = (from item in pages orderby item.Value descending select item).GroupBy(i => i.Value).ToList();
List<string> result = new List<string>();
int count = 0;
foreach (IGrouping<long, KeyValuePair<string, long>> item in groups)
{
foreach (KeyValuePair<string, long> pageSequence in item)
{
Console.WriteLine("Top {0} visited page sequence: {1} ({2})", count, pageSequence.Key, pageSequence.Value);
result.Add(pageSequence.Key);
if (++count > (N - 1))
return result;
}
}
return result;
}
bool areAnagrams(string const &s1, string const &s2)
{
string str1(s1), str2(s2);
sort(str1.begin(), str1.end());
sort(str2.begin(), str2.end());
return str1 == str2;
}
vector<size_t> FindSubString(string const &s1, string const s2)
{
vector<size_t> result;
for (size_t i = 0; i < s1.size(); i++) {
if (areAnagrams(s1.substr(i, s2.size()), s2))
result.push_back(i);
}
return result;
}
bool AreRotatedStrings(string const &s1, string const &s2, size_t n)
{
string str(s1);
rotate(str.begin(), str.begin() + n, str.end());
return (str == s2);
}
Just use one suffix tree for all keys (first name, last name, phone number). Reference the Contact data structure from the leave of the tree.
- Teh Kok How September 02, 2014vector<string> findUnique(vector<string> const& a, vector<string>const& b)
{
vector<string> result;
vector<string> c(a);
c.insert(c.end(), b.begin(), b.end());
sort(c.begin(), c.end());
for (vector<string>::const_iterator it = c.begin(); it != c.end(); it++) {
if (it != (c.end() - 1)) {
if (*it != *(it + 1))
result.push_back(*it);
else {
while (*it == *(it + 1))
it++;
}
} else
result.push_back(*it);
}
return result;
}
vector<string> findUnique(vector<string> const& a, vector<string>const& b)
{
vector<string> result;
vector<string> c(a);
c.insert(c.end(), b.begin(), b.end());
sort(c.begin(), c.end());
for (vector<string>::const_iterator it = c.begin(); it != c.end(); it++) {
if (it != (c.end() - 1)) {
if (*it != *(it + 1))
result.push_back(*it);
else {
while (*it == *(it + 1))
it++;
}
} else
result.push_back(*it);
}
return result;
}
typedef struct Position {
Position() : row(-1), col(-1) {}
Position(size_t r, size_t c) : row(r), col(c) {}
size_t row;
size_t col;
} position_t;
bool FindShortestPath(vector<vector<char>>& grid, size_t r, size_t c, queue<string>& result, char dest, char obstacle)
{
string pos, origin;
ostringstream oss, oss1;
set<string> visited;
map<string, string> route;
vector<position_t> positions;
positions.push_back(position_t(r, c));
oss << r << c;
origin = oss.str();
oss.str("");
while (!positions.empty()) {
vector<position_t> nextHops(positions);
positions.clear();
for (vector<position_t>::const_iterator it = nextHops.begin(); it != nextHops.end(); it++) {
oss1.str("");
oss1 << it->row << it->col;
// Go Down
if (it->row + 1 < grid.size())
if (grid[it->row + 1][it->col] == dest) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row + 1 << it->col;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row + 1][it->col] != obstacle) {// Obstacle. Cancel this route
oss.str("");
oss << it->row + 1 << it->col;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row + 1, it->col));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
// Go Right
if (it->col + 1 < grid[it->row].size())
if (grid[it->row][it->col + 1] == dest) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row << it->col + 1;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row][it->col + 1] != obstacle) {
oss.str("");
oss << it->row << it->col + 1;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row, it->col + 1));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
// Go Up
if (it->row > 0)
if (grid[it->row - 1][it->col] == dest) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row - 1 << it->col;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row - 1][it->col] != obstacle) {
oss.str("");
oss << it->row - 1 << it->col;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row - 1, it->col));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
// Go Left
if (it->col > 0)
if (grid[it->row][it->col - 1] == dest) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row << it->col - 1;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row][it->col - 1] != obstacle) {
oss.str("");
oss << it->row << it->col - 1;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row, it->col - 1));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
}
}
return false;
}
Binary Search O(lg(N)) solution:
int BinarySearch(vector<long> source, int toSearch)
{
int lower, middle, upper;
lower = 0;
upper = source.size() - 1;
while (lower <= upper) {
middle = lower + (upper - lower) / 2 + (upper - lower) % 2;
if (toSearch == source[middle])
return middle;
else if (toSearch == source[lower])
return lower;
else if (toSearch == source[upper])
return upper;
else if (source[lower] <= source[middle]) {
// 15 16 19 20 25 30 1 3 4 5 7 10 14
// L M U
// 4 8 9 9 9 10 12 13 1 2 2 3
// L M U
if (toSearch > source[middle]) // Ex: toSearch>30; toSearch=13
lower = middle + 1;
else if (toSearch > source[lower]) // Ex: toSearch=20; toSearch=9
upper = middle - 1;
else // Ex: toSearch=5; toSearch=2
lower = middle + 1;
} else { // Middle < Lower
// 15 16 19 20 25 30 1 3 4 5 7 10 11 14
// L M U
// 4 8 9 9 9 10 12 13 1 2 2 3
// L M U
if (toSearch < source[middle]) // Ex: toSearch=1
upper = middle - 1;
else if (toSearch < source[upper]) // Ex: toSearch=10; toSearch=2
lower = middle + 1;
else // Ex: toSearch=20; toSearch=12
upper = middle - 1;
}
}
return -1;
}
O(n^2) solution:
void MatrixDistance(vector<vector<long>>& data, size_t x, size_t y)
{
if (x < data.size() && y < data[0].size()) {
for (size_t i = 0; i < data.size(); i++) {
for (size_t j = 0; j < data[0].size(); j++) {
if (x != i && y != j)
data[i][j] = abs((int)(x - i)) + abs((int)(y - j));
else if (x == i && y != j)
data[i][j] = abs((int)(y - j));
else if (x != i && y == j)
data[i][j] = abs((int)(x - i));
}
}
}
}
static long ReadDigitalNumber(string file)
{
char[,] digitalEight = new char[,] {
{ '|', '-', '|'},
{ '|', '-', '|'},
{ '|', '_', '|'},
};
char[,] digitalSix = new char[,] {
{ '|', '-', '-'},
{ '|', '-', '-'},
{ '|', '_', '|'},
};
char[,] digitalThree = new char[,] {
{ '-', '-', '|'},
{ '_', '_', '|'},
{ '_', '_', '|'},
};
List<char[,]> numbers = new List<char[,]>(3);
string[] lines = File.ReadAllLines(file);
int x = 0, y = 0, index = 0;
foreach (string line in lines)
{
index = 0;
for (int i = 0; i < line.Length; i++) {
if (i != (line.Length - 1) && (i % 3) == 0)
{
if (i != 0)
index++;
y = 0;
if (numbers.Count < (index + 1))
numbers.Add(new char[3, 3]);
}
numbers[index][x,y] = line[i];
y++;
}
x++;
}
long result = 0;
numbers.ForEach(digit =>
{
int[] match = new int[10];
for (int i = 0; i < digit.GetLength(0); i++) {
for (int j = 0; j < digit.GetLength(1); j++) {
if (digit[i, j] == digitalEight[i, j])
match[8]++;
if (digit[i, j] == digitalSix[i, j])
match[6]++;
if (digit[i, j] == digitalThree[i, j])
match[3]++;
}
}
if (match[8] == digit.GetLength(0) * digit.GetLength(1))
{
if (result > 0)
result *= 10;
result += 8;
}
if (match[6] == digit.GetLength(0) * digit.GetLength(1))
{
if (result > 0)
result *= 10;
result += 6;
}
if (match[3] == digit.GetLength(0) * digit.GetLength(1))
{
if (result > 0)
result *= 10;
result += 3;
}
});
return result;
}
O(n) solution:
size_t findLongestContiguousPattern(string& str, char c)
{
size_t max = 0;
int index = -1;
size_t count = 0;
for (size_t i = 0; i < str.size(); i++) {
if (str[i] == c)
count++;
else {
if (max < count) {
max = count;
if (i > 0 && str[i - 1] == c && str[i + 1] == c)
index = i;
} else
count = 0;
}
}
if (index > 0)
str[index] = c;
return index;
}
string uncompress(string const& str)
{
ostringstream oss;
for (size_t i = 0; i < str.size(); ) {
if (isalpha(str[i]))
oss << str[i++];
else if (isdigit(str[i])) {
char *end(nullptr);
errno = 0;
unsigned long repeat = strtoul(&str[i], &end, 10);
if (!errno && repeat > 0 && repeat < ULONG_MAX) {
if (*end)
while (str[i] != end[0])
i++;
else
i++;
ostringstream oss1;
for (size_t k = 0; k < repeat; k++)
oss1 << oss.str();
oss.str("");
oss << oss1.str();
} else
i++;
}
}
return oss.str();
}
typedef struct PathResult {
PathResult() : sum(0), path("") {}
unsigned long sum;
string path;
} pathResult_t;
pathResult_t FindMaxPath(vector<vector<unsigned long>>& grid, size_t r, size_t c)
{
ostringstream oss;
pathResult_t result;
if (r >= grid.size() || c >= grid[r].size())
return result;
if (r == grid.size() - 1 && c == grid[r].size() - 1) {
result.sum = grid[r][c];
oss << "[" << r << "][" << c <<"]";
result.path = oss.str();
return result;
}
pathResult_t path1 = FindMaxPath(grid, r, c + 1);
pathResult_t path2 = FindMaxPath(grid, r + 1, c);
oss << "[" << r << "][" << c << "] ";
if (path1.sum >= path2.sum)
oss << path1.path;
else
oss << path2.path;
result.sum = grid[r][c] + Max(path1.sum, path2.sum);
result.path = oss.str();
return result;
}
void findPrime(unsigned long n, vector<long>& result)
{
if (n <= 3) {
result.push_back(2);
result.push_back(3);
} else {
long double j;
result.push_back(2);
result.push_back(3);
for (long i = 4; i <= n; i++) {
long double sqrtI = sqrt(i);
for (j = 2; j <= sqrtI && (i % (long)j); j++);
if (j >= sqrtI && (i % (long)j))
result.push_back(i);
}
}
}
void findDistinct(vector<long>& input, vector<long>& output)
{
for (vector<long>::const_iterator it = input.begin(); it != input.end(); it++) {
vector<long>::const_iterator it1 = it + 1;
for (; it1 != input.end() && (*it ^ *it1); it1++);
if (it1 == input.end())
output.push_back(*it);
}
}
Dictionary<string, List<string>> collection = new Dictionary<string, List<string>>();
List<string> items = new List<string>{"Burger", "French Fries", "Potato Chips"};
collection.Add("American", items);
items = new List<string>{ "Pizza", "Bread Sticks", "Potato Chips"};
collection.Add("Italian", items);
int count = 0;
collection.AsParallel().ForAll(i =>
{
if (i.Value.Contains("Potato Chips"))
count++;
});
Console.WriteLine("Potato Chips is found in {0} categories", count);
void trim(string &str)
{
size_t i = 0, j = 0;
for (i = 0; i < str.size(); i++) {
if (str[i] == ' ') {
if (i > 0 && str[i - 1] != ' ')
str[j++] = str[i];
} else
str[j++] = str[i];
}
for (; j < str.size(); j++)
str[j] = ' ';
}
- Teh Kok How December 28, 2015