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
 5 Answers Anxiety during technical phone or inperson interview???
I have a major problem, where I cannot perform anywhere close to my actual ability when I am asked to code something nontrivial during a phone or inperson interview.
 tjcbs2 March 05, 2015
At work, I *hate it* when someone is watching me as I code. I hate the idea of someone observing my thought process, and watching my mistakes. It is anxiety provoking, and I either start screwing up or make them go away. And this is typically with some random guy, who is probably bored and doesn't care, with code that is probably trivial, and in sum the interaction is completely meaningless.
During an interview, the problem is 100x worse. Here, it is almost always a nontrivial problem, with someone who is very much so evaluating what I do, and how long it takes me to do it, in an interaction which may have a significant effect on the course of my life. It is excruciating, and I will often go silent, with my head horrifyingly blank, and the interviewer will have to help me limp someplace vaguely close to the finish line.
It is maddening, that I would usually have no problem completing these problems on my own. And having to perform under that kind of pressure is so completely divorced from the actual reality of being a software engineer.
Can anyone else relate to this? Is there any hope for me, or am I simply excluded from companies with these kind of interviews. Flag  PURGE
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

tjcbs2
March 28, 2017 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));
}

tjcbs2
March 28, 2017 #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[mid1] != 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 = sz1; 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;
}

tjcbs2
March 27, 2017 #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[mid1] != 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 = sz1; 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 permovie, 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;
}

tjcbs2
March 27, 2017 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,
}

tjcbs2
January 13, 2017 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;
}

tjcbs2
January 04, 2017 Here is a bruteish 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[loc1] = 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}
}

tjcbs2
January 03, 2017 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;
}

tjcbs2
January 02, 2017 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;
}

tjcbs2
December 30, 2016 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;
}

tjcbs2
October 13, 2016 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 + (cnt1)/2, array + cnt);
int median = array[(cnt1)/2];
for (int lIdx = 0, hIdx = (cnt + 1)/2, i = 0; i < cnt; i++)
array[(pTmp[i] <= median) ? lIdx++ : hIdx++] = pTmp[i];
delete[] pTmp;
}

tjcbs2
October 13, 2016 void PartitionArray(int* array, int cnt)
{
int* pTmp = new int[cnt];
std::copy(array, array + cnt, pTmp);
std::nth_element(pTmp, pTmp + (cnt1)/2, pTmp + cnt);
int median = pTmp[(cnt1)/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;
}

tjcbs2
October 13, 2016 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

tjcbs2
May 12, 2015 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

tjcbs2
May 12, 2015 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

tjcbs2
April 10, 2015 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;
}
}

tjcbs2
March 28, 2015 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

tjcbs2
March 27, 2015 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]);
}

tjcbs2
March 17, 2015 There are two checks for visited status:
(oceanMap[idx] & e.o)
If this is nonzero 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({ w1, 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] == (PACIFICATLANTIC))
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),

tjcbs2
March 15, 2015 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)

tjcbs2
March 13, 2015 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;
}

tjcbs2
March 11, 2015
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 ...
Open Chat in New Window
 tjcbs2 March 28, 2017