tjcbs2
BAN USER- 0of 0 votes
AnswersWrite a function ShortestPath which accepts an integer array with dimensions M and N, and two points P and Q.
- tjcbs2 in United States
The array represents a terrain grid. A value of '0' means the terrain at that location can be crossed, '1' means the terrain is impassible. P and Q represent two locations in the grid.
The function is to find and return the shortest path from P to Q. If there is no path, then return an empty path.| Report Duplicate | Flag | PURGE
Software Engineer Algorithm
The algorithm:
Sort both arrays. Step through B, looking to see if it is a match to the current element of B. If it is, store it in the answers hash. If not, append it to the "junk" array. Don't worry about matching higher elements in B until the lower ones have been matched first.
Complexity: n*log(n) (sort)
#include <vector>
#include <algorithm>
#include <unordered_map>
void ShuffleArray(std::vector<int>& a, const std::vector<int>& b)
{
std::unordered_map<int, int> answers;
std::vector<int> sa = a, sb = b, remainder;
std::sort(sa.begin(), sa.end());
std::sort(sb.begin(), sb.end());
for (int i = 0; i < (int)sa.size(); i++)
if (sa[i] > sb[answers.size()])
answers[sb[answers.size()]] = sa[i];
else
remainder.push_back(sa[i]);
for (int r : remainder)
answers[sb[answers.size()]] = r;
for (int i = 0; i < (int)sa.size(); i++)
a[i] = answers[b[i]];
}
void main()
{
std::vector<int> a = {12,24,8,32};
ShuffleArray(a, {12,25,32,11});
Print(a);
}
output: 24,32,8,12
There are three properties that must be satisfied for the array to be a binary tree:
*For every node, the binary tree property must be satisfied (left must be <= val, right must be >= val)
*There must be one node with no parents (the root)
*Every other node must have one parent.
We determine this by filling a hash table with the number of times each node is referenced by another; aka, the number of parents it has.
#include <vector>
#include <unordered_map>
bool IsBTree(std::vector<node>& nodes)
{
std::unordered_map<node*, int> counts;
for (int i = 0; i < (int)nodes.size(); i++)
{
if ((nodes[i].pLeft->val > nodes[i].val) || (nodes[i].pRight->val < nodes[i].val))
return false;
counts[nodes[i].pLeft]++;
counts[nodes[i].pRight]++;
}
int parentless = 0, singleParent = 0;
for (auto elt : counts)
{
parentless += elt.second == 0;
singleParent += elt.second == 1;
}
return ((parentless == 1) && (singleParent == nodes.size()-1));
}
#include <vector>
#include <algorithm>
int SearchEnd(const std::vector<int>& arr, int start, int end, int val, bool bLow)
{
int edge = bLow ? 0 : (int)arr.size() -1;
int edgeStep = bLow ? - 1 : 1;
int& vLow = bLow ? start : end;
int& vHigh = bLow ? end : start;
while (start < end - 1 )
{
int mid = (start + end)/2;
if (arr[mid] == val)
{
if (!mid || arr[mid-1] != val)
return mid;
else
vHigh = mid;
}
else
vLow = mid;
}
return start;
}
std::vector<int> FindN4(const std::vector<int>& arr, int div)
{
std::vector<int> result;
int sz = arr.size()/div;
for (int i = sz-1; i < (int)arr.size(); i += sz)
{
int start = SearchEnd(arr, i - sz + 1, i + 1, arr[i], true);
int end = SearchEnd(arr, i, std::min(i + sz, (int)arr.size()), arr[i], false);
if ((end - start + 1 >= sz) && (!result.size() || (result.back() != arr[i])))
result.push_back(arr[i]);
}
return result;
}
#include <vector>
#include <algorithm>
int SearchEnd(const std::vector<int>& arr, int start, int end, int val, bool bLow)
{
int edge = bLow ? 0 : (int)arr.size() -1;
int edgeStep = bLow ? - 1 : 1;
int& vLow = bLow ? start : end;
int& vHigh = bLow ? end : start;
while (start < end - 1 )
{
int mid = (start + end)/2;
if (arr[mid] == val)
{
if (!mid || arr[mid-1] != val)
return mid;
else
vHigh = mid;
}
else
vLow = mid;
}
return start;
}
std::vector<int> FindN4(const std::vector<int>& arr, int div)
{
std::vector<int> result;
int sz = arr.size()/div;
for (int i = sz-1; i < (int)arr.size(); i += sz)
{
int start = SearchEnd(arr, i - sz + 1, i + 1, arr[i], true);
int end = SearchEnd(arr, i, std::min(i + sz, (int)arr.size()), arr[i], false);
if ((end - start + 1 >= sz) && (!result.size() || (result.back() != arr[i])))
result.push_back(arr[i]);
}
return result;
}
Generate a list of movies which the users who have watched X have also most frequently watched.
This list can be maintained per-movie, and updated periodically.
During update, the system can search for users who have watched X, and iterate through the other movies they have seen, updating the count in a hash table.
Divide your map into a recursive grid.
Each cell contains either: a list of locations; or, if the number of locations in the cell exceeds some number N, it is divided into 4 more cells.
Search the cell the point lies in. Then, for each of 8 neighboring cells, if it is possible for a location to be closer than those already found, search that cell too.
#include <string>
std::string balancedParens(const std::string& input)
{
std::string output;
int state = 0;
for (auto it = input.begin(); it != input.end(); it++)
{
state += *it == '(' ? 1 : -1;
if (state == -1)
{
for (auto it2 = it; it2 != input.end() && *it2 == ')'; it2++, state++)
output += '(';
}
output += *it;
}
for (int i = 0; i < state; i++)
output += ')';
return output;
}
O(N)
#include <vector>
#include <unordered_map>
#include <stdio.h>
void PrintOverlapping(const std::vector<std::vector<int>>& lol)
{
struct occuranceEntry
{
int lastList = -1, cnt = 0;
};
std::unordered_map<int, occuranceEntry> occurances;
for (int i = 0; i < (int)lol.size(); i++)
{
for (int j = 0; j < (int)lol[i].size(); j++)
{
occuranceEntry& e = occurances[lol[i][j]];
if (e.lastList != i)
{
e.lastList = i;
if (++e.cnt == 3)
printf("%d,", lol[i][j]);
}
}
}
}
int main()
{
PrintOverlapping({ {1, 9, 2, 4, 3},
{2, 3, 3, 5, 7},
{1, 2, 4, 7, 2},
{4, 5} }); //output = 2,4,
}
int Smallest_Difference(const std::vector<int>& a, const std::vector<int>& b)
{
std::vector<int> comb = a;
comb.insert(a.begin(), b.begin(), b.end());
std::sort(comb.begin(), comb.end());
int dif = std::numeric_limits<int>::max();
for (int i = 0; i < (int)comb.size()-1; i++)
dif = std::min(dif, std::abs(comb[i] - comb[i+1]));
return dif;
}
Here is a brute-ish solution. Traverse the graph, and maintain a "bunny state", consisting of the bunnies rescued, and the time remaining. At each node, store the state in a hash table. Or, if the same state was previously encountered with an equal or better time remaining, terminate that branch of the search.
With a maximum of 5 bunnies, I don't know why "a fair amount of graph theory and a fast implementation" is necessary.
const int cMaxBunnies = 5;
union bunnyState
{
struct
{
int8_t bRescued[cMaxBunnies];
int8_t location;
};
int64_t hashVal;
};
typedef std::vector<int> rowType;
void Rescue_Recurse(const std::vector<rowType>& mtx, rowType& result, const bunnyState& state, std::unordered_map<int64_t, int>& bestStates,
int loc, int tm)
{
bunnyState newState = state;
newState.location = loc;
if (loc == mtx.size() - 1)
{
int rescued = std::count(state.bRescued, state.bRescued + cMaxBunnies, 1);
if ((tm >= 0) && (rescued > (int)result.size()))
{
result.clear();
for (int i = 0; i < cMaxBunnies; i++)
if (state.bRescued[i])
result.push_back(i);
}
}
else if (loc > 0)
newState.bRescued[loc-1] = 1;
auto curVal = bestStates.find(newState.hashVal);
if ((curVal == bestStates.end()) || curVal->second < tm)
{
bestStates[newState.hashVal] = tm;
for (int i = 0; i < (int)mtx[loc].size(); i++)
Rescue_Recurse(mtx, result, newState, bestStates, i, tm - mtx[loc][i]);
}
}
rowType Do_Rescue(const std::vector<rowType>& mtx, int tm)
{
std::vector<int> result;
std::unordered_map<int64_t, int> bestStates;
Rescue_Recurse(mtx, result, {0}, bestStates, 0, tm);
printf("{");
for (int i: result)
printf("%d,", i);
printf("}\n");
return result;
}
int main()
{
Do_Rescue({ {0, 1, 1, 1, 1}, {1, 0, 1, 1, 1}, {1, 1, 0, 1, 1}, {1, 1, 1, 0, 1}, {1, 1, 1, 1, 0} }, 3); //output: {0,1,}
Do_Rescue({ {0, 2, 2, 2, -1}, {9, 0, 2, 2, -1}, {9, 3, 0, 2, -1}, {9, 3, 2, 0, -1}, {9, 3, 2, 2, 0} }, 1); //output: {1,2}
}
int ReplaceNumber(int num, int toReplace, int replaceWith)
{
char buf[32];
itoa(num, buf, 10);
std::replace(buf, buf + strlen(buf), '0' + toReplace, '0' + replaceWith);
return atoi(buf);
}
int main()
{
const int v1 = 456, v2 = 485;
int minVal = ReplaceNumber(v1, 6, 5 ) + ReplaceNumber(v2, 6, 5 );
int maxVal = ReplaceNumber(v1, 5, 6 ) + ReplaceNumber(v2, 5, 6 );
return 0;
}
wtcupup, mine is already too long and complex for the problem, yours is out of control.
struct seq
{
seq() {val = len = 0;}
int val, len;
};
int* MakeMatrix(int N)
{
int* pRVal = new int[N*N];
seq* pColSeqs = new seq[N];
for (int r = 0; r < N; r++)
{
seq rowSeq;
for (int c = 0; c < N; c++)
{
seq* pCurSeqs[2] = {&pColSeqs[c], &rowSeq};
int nextNum = 0;
while (nextNum == 0)
{
nextNum = rand()%4 + 1;
for (seq* pS: pCurSeqs)
if ((pS->len == 2) && (pS->val == nextNum))
nextNum = 0;
}
pRVal[r*N + c] = nextNum;
for (seq* pS : pCurSeqs)
{
pS->len = (nextNum == pS->val) ? pS->len+1 : 1;
pS->val = nextNum;
}
}
}
return pRVal;
}
int main(int argc, char* argv[])
{
srand((int)time(NULL));
const int N = 50;
int* pRVal = MakeMatrix(N);
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
printf("%d,", pRVal[r*N + c]);
printf("\n");
}
getch();
return 0;
}
std::string NLPExtract(const std::string & input)
{
std::string rval;
bool bInWord = false;
for (int i = 0; i < (int)input.size()-1; i++)
{
bInWord = bInWord ? isalnum(input[i]) :
(input[i] == ' ') && isalnum(input[i+1]);
if (bInWord)
rval += input[i];
}
return rval;
}
Edited to remove extraneous copy
void PartitionArray(int* array, int cnt)
{
int* pTmp = new int[cnt];
std::copy(array, array + cnt, pTmp);
std::nth_element(array, array + (cnt-1)/2, array + cnt);
int median = array[(cnt-1)/2];
for (int lIdx = 0, hIdx = (cnt + 1)/2, i = 0; i < cnt; i++)
array[(pTmp[i] <= median) ? lIdx++ : hIdx++] = pTmp[i];
delete[] pTmp;
}
void PartitionArray(int* array, int cnt)
{
int* pTmp = new int[cnt];
std::copy(array, array + cnt, pTmp);
std::nth_element(pTmp, pTmp + (cnt-1)/2, pTmp + cnt);
int median = pTmp[(cnt-1)/2];
for (int lIdx = 0, hIdx = (cnt + 1)/2, i = 0; i < cnt; i++)
pTmp[(array[i] <= median) ? lIdx++ : hIdx++] = array[i];
std::copy(pTmp, pTmp + cnt, array);
delete[] pTmp;
}
You can represent a hex map as an ordinary grid (2D array). Movement is a bit different. Horizontal movement is the same as with a grid. But Vertical movement is different: in terms of the 2d array, a unit on even rows can move up, down, up and right, down and right. A unit on odd rows can move up, down, up and left, down and left.
- tjcbs2 May 12, 2015Greedily tries to match as many characters as possible, which is admittedly not optimal for some strings.
std::string encode(char* inStr)
{
std::string rval;
while (*inStr)
{
int dups = 0;
int tryLen = std::max((int)strlen(inStr)/2, 1);
for (; tryLen && !dups; tryLen--)
for (; !strncmp(inStr + tryLen*(dups+1), inStr, tryLen); dups++);
rval += std::to_string(dups+1) + std::string(inStr,tryLen+1);
inStr += (tryLen+1)*(dups+1);
}
return rval;
}
void main()
{
char* tests[] = {"aasasatb", "abcdbcdff"};
for (int i = 0; i < sizeof(tests)/4; i++)
std::cout << tests[i] << " -> " << encode(tests[i]) << '\n';
getch();
}
output:
aasasatb -> 2a2sa1t1b
abcdbcdff -> 1a2bcd2f
Maintain two stacks, and push the children of the first stack onto the second. This naturally alternates the order of the rows. When the first stack is empty, swap the stacks. If still empty, we are done.
void PrintZigZag(node* pNode)
{
std::stack<node*> s1, s2, *pS1 = &s1, *pS2 = &s2;
bool bOdd = true;
s1.push(pNode);
while (pS1->size())
{
printf("%d ", pS1->top()->val);
node* pL = pS1->top()->pLeft;
node* pR = pS1->top()->pRight;
node* toPush[2] = {bOdd ? pR : pL, bOdd ? pL : pR};
pS1->pop();
for (node* pNext : toPush)
if (pNext)
pS2->push(pNext);
if (!pS1->size())
{
std::swap(pS1, pS2);
bOdd = !bOdd;
printf("\n");
}
}
}
output:
1
2 3
7 6 5 4
8 9
using namespace std;
void main()
{
unordered_map<string, int> subords;
unordered_map<string, string> heir({ { "A", "C" }, { "B", "C" },
{ "C", "F" }, { "D", "E" },
{ "E", "F" }, { "F", "F" } });
for (auto entry : heir)
{
string cur = entry.first, next = entry.second;
while (cur != next)
{
subords[next]++;
cur = next;
next = heir[next];
}
}
for (auto entry : heir)
printf("%s: %d\n", entry.first.c_str(), subords[entry.first]);
getch();
}
output:
A: 0
B: 0
C: 2
D: 0
E: 1
F: 5
Data structure contains the stack, the current mode, and a hash table which maps from the value to a data structure that contains Count, Next Highest Values, and Next Lowest Value. Push and Pop update these highest/lowest values as appropriate.
Push, Pop, and Mode are all O(1)
Make the stack entries doubly linked list elements, with each element containing Value, Prev, and Next. Prev and Next refer to memory locations within the stack. Maintain reference to current median element.
On Push:
Find and insert new element into list, starting from median
If (stack size was odd) and (new element < median)
median = median.previous;
else if (stack size was even) and (new element > median)
median = median.next;
On pop:
Remove element from list
If (stack size was odd) and (popped element > median)
median = median.previous;
else if (stack size was even) and (popped element < median)
median = median.next;
Push is O(n/2). Pop and Median are O(1)
- tjcbs2 April 03, 2015extern void ReadFromDisc(char* pOut);
void ReadData(int szInBytes, char* pOut)
{
static char buf[256];
static int bufLoc = 0;
while (szInBytes)
{
if (!bufLoc)
ReadFromDisc(buf);
int toRead = std::min(szInBytes, 256);
toRead = std::min(toRead, 256 - bufLoc);
memcpy(pOut, buf + bufLoc, toRead);
pOut += toRead;
bufLoc = (bufLoc + toRead) % 256;
szInBytes -= toRead;
}
}
You could just assign infinity to cells which are the mouths of snakes, since no optimal path includes them.
Instead of an array of integers, make dp an array of structures which includes both the value and the idx of the best previous position. Then work backward from the end to retrieve the path.
I used an array of 256 strings to store the frequencies. When character C(cur) is followed by C(next), add C(next) to the string Array[C(cur)].
When creating the output for part 2, just choose a random character in the current string to find the next one.
void main(){
while (1){
std::string freqencies[256], input;
int cnt;
std::cout << "Enter a string\n";
std::getline(std::cin, input);
input += ' ';
std::cout << "Enter output count\n";
std::cin >> cnt; std::cin.ignore();
char cur = ' ';
for (char c : input){
freqencies[cur] += tolower(c);
cur = tolower(c);
}
cur = ' ';
for (int i = 0; i < cnt; i++) {
cur = freqencies[cur].at(rand() % freqencies[cur].size());
std::cout << cur;
}
std::cout << '\n';
}
}
output:
Enter a string
This is Great! Isn't it? I think it is a great solution! That guy tjcbs2 deserves an upvote for his amazing effort.
Enter output count
100
hisort. teamazis fonk in! hit gupvot ang in is sn is erthison't guy t t thazi upvortjcbs foresn
I think the algorithm needs to be:
1: Find the first local maxima, call it "left"
2. Scan the rest of the array for either a maxima >= the left, or the highest in the array. Call it "right". If none, stop.
3. Compute water between left and right.
4. Assign right to left.
5. Goto 2
Unfortunately, this is not O(n) though! it is O(n^2). think about
{5,1,4,1,3,1,2}
This question is a pain!
This doesn't need a sort, and operates in O(n). It is guaranteeing that in every group of 3 the middle element is the greatest. If in the next group of 3 a swap is done on the right hand element of the previous group of 3, it can only be replaced by a smaller element. The problem is that it only guarantees >=, not >
for (int i = 1; i < arr.size(); i += 2)
{
if (arr[i - 1] > arr[i])
std::swap(arr[i - 1], arr[i]);
if ((i < arr.size() - 1) && (arr[i + 1] > arr[i]))
std::swap(arr[i + 1], arr[i]);
}
There are two checks for visited status:
(oceanMap[idx] & e.o)
If this is non-zero then the "water" of the current ocean (e.o) has already visited this cell. One check is done before adding the new cell to the stack. The other is done after the cell is popped from the stack, before it is processed, because it is possible that the cell was visited after it was added to the stack.
Time complexity is O(w*h). Without handling visited status, it would be O((w*h)^2).
Start with the shoreline. Let the water flow *up* from the shore, and mark the ocean it came from. If land is encountered with marks from both oceans, add it to the results.
enum ocean{NONE, PACIFIC, ATLANTIC};
struct coord{ int x, y; };
struct entry{ int x, y; ocean o; };
std::vector<coord> FindDivides(int* pTerrain, int w, int h)
{
std::vector<coord> results;
std::vector<int> oceanMap(w*h, NONE);
std::stack<entry> todo;
for (int i = 0; i < w; i++)
{
todo.push({ i, 0, PACIFIC });
todo.push({ i, h - 1, ATLANTIC });
}
for (int i = 0; i < h; i++)
{
todo.push({ 0, i, PACIFIC });
todo.push({ w-1, i, ATLANTIC });
}
while (todo.size())
{
entry e = todo.top();
todo.pop();
int idx = e.y*w + e.x;
if (oceanMap[idx] & e.o)
continue;
oceanMap[idx] |= e.o;
if (oceanMap[idx] == (PACIFIC|ATLANTIC))
results.push_back({ e.x, e.y });
coord nextc[4] = { { e.x - 1, e.y }, { e.x + 1, e.y },
{ e.x, e.y - 1 }, { e.x, e.y + 1 } };
for (coord c : nextc)
{
if ((c.x < 0) || (c.x >= w) || (c.y < 0) || (c.y >= h))
continue;
int nextIdx = c.y*w + c.x;
if ((pTerrain[nextIdx] >= pTerrain[idx]) && !(oceanMap[nextIdx] & e.o))
todo.push({ c.x, c.y, e.o });
}
}
return results;
}
void main()
{
int heights[] = {1, 2, 2, 3, 5,
3, 2, 3, 4, 4,
2, 4, 5, 3, 1,
6, 7, 1, 4, 5,
5, 1, 1, 2, 4 };
std::vector<coord> results = FindDivides(heights, 5, 5);
for (coord c : results)
printf("(%d, %d), ", c.x, c.y);
getch();
}
output:
(2, 2), (3, 1), (4, 1), (4, 0), (1, 3), (0, 4), (0, 3),
void LeastSquares(int num, std::vector<int>& best, std::vector<int>& curSeq = std::vector<int>(), int cur = 0)
{
if (!cur)
cur = (int)sqrtf((float)num);
if (!num && (!best.size() || (curSeq.size() < best.size())))
{
best = curSeq;
return;
}
if (best.size() && curSeq.size() >= best.size())
return;
for (; cur > 0; cur--)
{
if (num >= cur*cur)
{
curSeq.push_back(cur*cur);
LeastSquares(num - cur*cur, best, curSeq, cur);
curSeq.pop_back();
}
}
}
void main()
{
int num;
while (1)
{
std::cout << "Enter num\n";
std::cin >> num;
std::vector<int> result;
LeastSquares(num, result);
std::cout << result.size() << ": (";
for (int i = 0; i < result.size(); i++)
std::cout << result[i] << ((i == result.size()-1) ? "" : " + ");
std::cout << ")\n";
}
}
output:
Enter num
12
3: (4 + 4 + 4)
Enter num
6
3: (4 + 1 + 1)
Enter num
66
3: (64 + 1 + 1)
Enter num
666
2: (441 + 225)
Enter num
6666
3: (6241 + 400 + 25)
Enter num
66666
3: (66049 + 361 + 256)
Map from a number to the indices where it appears on the board. Remove a number from the map after it has been processed. Count the hits on each row, column, and diagonal, when one of them reaches 100 we are done.
O(n)
const int DIM = 100;
int mingo(int* pBoard, int* pCalled, int numCalled)
{
std::unordered_multimap<int, int> numToIdx;
for (int i = 0; i < DIM * DIM; i++)
numToIdx.insert({ pBoard[i], i });
int rows[DIM] = { 0 }, cols[DIM] = { 0 };
int diag1 = 0, diag2 = 0;
for (int i = 0; i < numCalled; i++)
{
auto range = numToIdx.equal_range(pCalled[i]);
for (; range.first != range.second; range.first++)
{
int row = range.first->second / DIM, col = range.first->second % DIM;
if ((++rows[row] == DIM) || (++cols[col] == DIM) ||
((row == col) && (++diag1 == DIM)) ||
((DIM - row - 1 == col) && (++diag2 == DIM)))
return i;
}
numToIdx.erase(pCalled[i]);
}
return -1;
}
Repmylakleinm, Quality Assurance Engineer at Coupon Dunia
Articulate and accomplished admin executive experience at keeping an office running smoothly. A communicator and collaborator who is efficient in ...
RepHello friends my name Neha Nanda from India Chandigarh city. Doing work in SEO line in Softsys company.
Repsalinagray, Development Support Engineer at Atmel
Hi I am Salina Gray,I live in Texas and work as a Design Team Member. I am new to ...
RepMy name Madhu Nanda from Himachal pardesh. I am a writter in English lectractrue.
Reppaulajheineman, Consultant at Bank of America
Hello, I am from Las Vegas, NV.Completed a Diploma course in Advanced Technological Developments and Staff Management. I have ...
Repstacyrdavid, Associate at Abs india pvt. ltd.
Hi, I am Stacy working as a Cashier in Dollar store the US. I work for Us government to Collect ...
Repmerrittmonique9, Android Engineer at AMD
I am Monique and working in high court from last 20 years.Handel many cases in my career.Build and ...
RepKellyLabbe, Animator at Future Advisor
My name is Kelly and I am currently a freshman Fitness trainer in Vibrant Man company .I have learned a ...
RepI am an energetic sales professional with a track record of consistently increasing sales revenue in a competitive market. Contract ...
- tjcbs2 March 28, 2017