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
Still feels like too much code!
std::string CanonicalPath(const char* pPath){
std::string rval;
std::vector<std::string> stack;
int up = 0;
while (*pPath){
if (pPath[0] == '.'){
if (pPath[1] == '.'){
if (stack.size())
stack.pop_back();
else
up++;
}
pPath += 2 + (pPath[1] == '.');
}
else{
const char* pEnd = strchr(pPath, '/');
if (!pEnd)
pEnd = pPath + strlen(pPath);
stack.push_back(std::string(pPath, pEnd - pPath));
pPath = pEnd + 1;
}
}
for (int i = 0; i < up; i++)
rval += "../";
for (auto& s : stack)
rval += s + '/';
return rval;
}
void main()
{
std::cout << CanonicalPath("e/../../a/d/./../b/c");
getch();
}
output:
../a/b/c/
Yes, I think the second version solves the problem. I don't see how the first is supposed to though.
But there is still one problem: *Every* task at level d has to wait for *every* task in level d+1 to finish. This greatly reduces the potential parallelism. Have a look at my implementation which takes a different approach and doesn't have this problem.
Sample output:
Thread 1 running task 6
Thread 2 running task 7
Thread 3 waiting
Thread 1 finished task 6
Thread 1 running task 2
Thread 3 running task 5
Thread 2 finished task 7
Thread 2 running task 3
Thread 3 finished task 5
Thread 3 running task 4
Thread 1 finished task 2
Thread 1 waiting
Thread 2 finished task 3
Thread 2 waiting
Thread 3 finished task 4
Thread 3 running task 1
Thread 2 finished
Thread 1 finished
Thread 3 finished task 1
Thread 3 finished
Here is a different implementation from the OP's. It has the advantage that all threads are kept as busy as possible.
The basic idea is to create a table (std::unordered_multimap) which maps a task to all the parent tasks which depend on it. In addition, a seperate table (std::unordered_map) tracks how many dependencies a task is still waiting for (in real life, this would probably be part of the Task interface). A queue holds all the tasks which are currently available to run.
The thread code follows the Producer-Consumer model, using a std::condition_variable. As soon as a Task's dependencies are completed, it is added to the queue, any waiting threads are signaled, and the task is run when a thread is available.
class Task {
public:
virtual void run() = 0;
virtual std::vector<Task *> & getDependencies() = 0;
};
class TestTask : public Task {
public:
TestTask(int id, std::initializer_list<Task*> deps = {}){ mId = id; mDeps = deps; }
void run() { std::this_thread::sleep_for(std::chrono::milliseconds(rand() % 1000)); }
std::vector<Task *> & getDependencies(){ return mDeps; }
int id() { return mId; }
private:
int mId;
std::vector<Task*> mDeps;
};
std::mutex mMutex;
std::condition_variable mCond;
//Tasks waiting to run, whose dependencies have been fulfilled
std::queue<Task*> mAvailableTasks;
//Maps a task to all the tasks which depend on it
std::unordered_multimap<Task*, Task*> mUnlockLists;
//Maps a task to the number of tasks it is waiting on
std::unordered_map<Task*, int> mLockCounts;
int mTasksToProcess; //Remaining task count
void ThreadFunc(int id)
{
std::unique_lock<std::mutex> mtx(mMutex);
while (1)
{
//Wait for a task to become available. If finished
//(mTasksToProcess == 0), exit thread
while (!mAvailableTasks.size() && mTasksToProcess)
{
std::cout << "Thread " << id << " waiting\n";
mCond.wait(mtx);
}
if (!mTasksToProcess)
break;
//Grab next available task, unlock mutex, and run it
Task* pTask = mAvailableTasks.front();
mAvailableTasks.pop();
mTasksToProcess--;
std::cout << "Thread " << id << " running task "
<< ((TestTask*)pTask)->id() << '\n';
mtx.unlock();
pTask->run();
mtx.lock();
std::cout << "Thread " << id << " finished task "
<< ((TestTask*)pTask)->id() << '\n';
//Find all the tasks that depend on the finished task
//Decrement it's lock count. If 0, add that task to
//the queue and signal all threads
auto unlocks = mUnlockLists.equal_range(pTask);
for (; unlocks.first != unlocks.second; unlocks.first++)
{
auto count = mLockCounts.find((*unlocks.first).second);
if (!--count->second)
{
mAvailableTasks.push(count->first);
mCond.notify_all();
}
}
}
std::cout << "Thread " << id << " finished\n";
}
void PreProcessTask(Task* pTask)
{
if (mLockCounts.find(pTask) == mLockCounts.end())
{
//Add dependency count of task to lockcount table.
//if it is 0, add it to the waiting Q
std::vector<Task*> &deps = pTask->getDependencies();
mLockCounts[pTask] = deps.size();
if (!deps.size())
mAvailableTasks.push(pTask);
//For each dependency, add it to the
//dependency->dependents mapping, and preprocess it
for (Task*pDep : deps)
{
mUnlockLists.insert({ pDep, pTask });
PreProcessTask(pDep);
}
mTasksToProcess++;
}
}
void main()
{
TestTask* t7 = new TestTask(7, {});
TestTask* t6 = new TestTask(6, {});
TestTask* t5 = new TestTask(5, {t6});
TestTask* t4 = new TestTask(4, {t5});
TestTask* t3 = new TestTask(3, {t6, t7});
TestTask* t2 = new TestTask(2, {t6});
TestTask* t1 = new TestTask(1, {t2, t3, t4, t7});
PreProcessTask(t1);
std::vector<std::thread> threads;
for (int i = 0; i < 3; i++)
threads.push_back(std::thread(ThreadFunc, i + 1));
for (auto& t : threads)
t.join();
getch();
}
This took some doing to get right. I wouldn't have gotten this on an interview... The basic idea is to start from the lower right corner, and search the grid with this repeating pattern: left, up, right, up... until the value is found. Binary search is used to improve O(n). As to what O(n) is... maybe something like O(d*log(d)), where d is the average of width and height. Anyone?
int* lower_bound_stride(int* pArr, int* pArrEnd, int val, int stride)
{
while (pArr != pArrEnd)
{
int* pNext = pArr + ((pArrEnd - pArr)/(2*stride))*stride;
if (*pNext < val)
pArr = pNext + stride;
else if (*pNext > val)
pArrEnd = pNext;
else
return pNext;
}
return ((*pArr >= val)||(pArr == pArrEnd)) ? pArr : pArr + stride;
}
int FindInGrid(int* pGrid, int w, int h, int toFind)
{
int curX = w - 1, curY = h-1;
for (int i = 0; pGrid[curY*w + curX] != toFind; i++)
{
int* pLeft = pGrid + curY*h;
switch (i%4)
{
case 0:
curX = std::lower_bound(pLeft, pLeft + curX, toFind) - pLeft;
break;
case 2:
curX = std::lower_bound(pLeft + curX, pLeft + w, toFind) - pLeft;
break;
case 1:
case 3:
curY = (lower_bound_stride(pGrid + curX, pGrid + curY*w + curX, toFind, w) - (pGrid + curX))/w;
if (((i%4) == 1) && (pGrid[curY*w + curX] > toFind))
curY--;
break;
}
}
return curY*w + curX;
}
void main()
{
int grid[] = {0, 2, 4, 8, 16,
1, 3, 5, 10, 18,
6, 7, 9, 14, 21,
11, 12, 13, 15, 23,
17, 19, 20, 22, 24};
for (int i = 0; i < sizeof(grid)/sizeof(grid[0]); i++)
printf("idx(%d) = %d\n", grid[i], FindInGrid(grid, 5, 5, grid[i]));
getch();
}
output:
idx(0) = 0
idx(2) = 1
idx(4) = 2
idx(8) = 3
idx(16) = 4
idx(1) = 5
idx(3) = 6
idx(5) = 7
idx(10) = 8
idx(18) = 9
idx(6) = 10
idx(7) = 11
idx(9) = 12
idx(14) = 13
idx(21) = 14
idx(11) = 15
idx(12) = 16
idx(13) = 17
idx(15) = 18
idx(23) = 19
idx(17) = 20
idx(19) = 21
idx(20) = 22
idx(22) = 23
idx(24) = 24
He means just spiral order, not matrix. So starting from upper left, print in a spiral, moving inward. If you look at the output to my program it should make sense.
void PrintSpiral(int* matrix, int w, int h)
{
int x = -1, y = 0, curLayers = 0;
while (1)
{
if (x++ == w - curLayers)
break;
for (; x < w - curLayers; x++)
printf("%d, ", matrix[y*w + x]);
x--;
if (y++ == h - curLayers)
break;
for (; y < h - curLayers; y++)
printf("%d, ", matrix[y*w + x]);
y--;
if (x-- == curLayers)
break;
for (; x >= curLayers; x--)
printf("%d, ", matrix[y*w + x]);
x++;
if (y-- == ++curLayers)
break;
for (; y >= curLayers; y--)
printf("%d, ", matrix[y*w + x]);
y++;
}
}
void main()
{
int mat[] = {1, 9, 21, 13,
3, 7, 8, -1,
13, 5, 2, 1,
5,-7, 3, 6};
PrintSpiral(mat, 4, 4);
getch();
}
Output:
1, 9, 21, 13, -1, 1, 6, 3, -7, 5, 13, 3, 7, 8, 2, 5,
Should be O(n), but I don't have c++11 handy so no hash table
void Longest1Subset(int* pArr, int sz)
{
std::map<int, int> counts; //should be hash table for O(n)
for (int i = 0; i < sz; i++)
{
counts[pArr[i]]++;
counts[pArr[i]-1]++;
printf("%d,", pArr[i]);
}
std::pair<int,int> res(0,0);
for (std::map<int,int>::iterator i = counts.begin(); i != counts.end(); i++)
res = res.second > i->second ? res : *i;
printf(" => (%d to %d): %d\n", res.first, res.first+1, res.second);
}
int main()
{
int test1[] = {1,5,1,0,2,6,2,1};
int test2[] = {6,6,5,5,4,4,3,3,2,2,2,1,0,7,7,7,7};
int test3[] = {0,0,-1,-1,-9,9,-9,9,-9,9,-9,-10,9};
Longest1Subset(test1, sizeof(test1)/sizeof(*test1));
Longest1Subset(test2, sizeof(test2)/sizeof(*test2));
Longest1Subset(test3, sizeof(test3)/sizeof(*test3));
getch();
}
void main()
{
char* input = "if man was meant to stay on the ground god would have given us roots";
char* spaceless = new char[strlen(input)];
for (int i = 0, j = 0; !i || input[i-1]; i++)
if (input[i] != ' ')
spaceless[j++] = input[i];
int numRow = (int)sqrt((float)strlen(spaceless));
int lastRow = strlen(spaceless) - numRow*numRow + 1;
int numCol = numRow + (lastRow != 0);
for (int i = 0; i < numCol; i++, printf(" "))
for (int j = 0; j < numRow; j++)
if ((j < numRow - 1) || (i < lastRow))
printf("%c", spaceless[j*numCol + i]);
getch();
};
output:
imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau
}
- tjcbs2 March 05, 20151 GB:
The data is stored in a file, as a linear array of data. I would implement an in-memory hash table which maps keys to file offsets. In addition, I would implement an in-memory LRU cache so that the most frequently accessed data can be retrieved nearly instantly.
1 TB:
The data file in the 1 GB example becomes a second-level disk based LRU cache. If the data is of uniform size then the implementation is easy and efficient, when ejecting old data with new data simply overwrite the data in the master file and update the key->file offset table with the new key. If it is not, then the cache would consist in files on the disk system named with the key value. There is an additional (in memory if feasible/disk based if not) mapping from key to server, for retrieving data which cannot be found in either cache.
Small: No need for any disk system involvement, the LRU cache becomes the entire data set.
Assumptions: Key values are small relative to the data. Looking at the last sentence, this might not be true... Key access is not randomly distributed, if it is then the caches do no good.
bool StringBalance(char* s){
std::vector<char> stack;
for(; *s; s++){
switch (*s){
case '(': case '[': case '{':
stack.push_back(*s);
break;
case ')': case ']': case '}': {
char match = (*s == ')') ? '(' :
(*s == '}') ? '{' : '[';
if (!stack.size() || (match != stack.back()))
return false;
stack.pop_back();
break;}
}
}
return !stack.size();
}
void main()
{
char* tests[] = {"[a(b{c}d)]", "[a(b{cd)}]", "[a(b{c}d)", "a(b{c}d)]"};
for (int i = 0; i < sizeof(tests)/sizeof(tests[0]); i++)
printf("%s->%d\n", tests[i], StringBalance(tests[i]));
getch();
}
std::string LongestSubStr(std::string s)
{
std::string longest;
std::vector<bool> dupCheck(256, false);
for (int i = 0,j; i < s.size(); i++)
{
for (j = i; j < s.size() && !dupCheck[s[j]]; j++)
dupCheck[s[j]] = true;
if (j - i > longest.size())
longest.assign(&s[i], j-i);
dupCheck.assign(256, false);
}
return longest;
}
void main()
{
char* tests[] = {"PrincessFart", "FunnyGuy", "abba", "abbcbab", "SomeRandomString"};
for (int i = 0; i < sizeof(tests)/sizeof(tests[0]); i++)
printf("%s->%s\n", tests[i], LongestSubStr(tests[i]).c_str());
getch();
}
Some rather inelegant solutions here.
char arr[] = {'a', 'b', 'c', 'd',
'e', 'f', 'g', 'h',
'i', 'j', 'k', 'l',
'm', 'n', 'o', 'p' };
char* strstr_stride(int n, char* pStr, int stride, char* pSubStr)
{
for(int j = 0; n-j >= strlen(pSubStr); pStr += stride,j++)
{
int i = 0;
for (; pSubStr[i] && (pStr[i*stride] == pSubStr[i]); i++);
if (!pSubStr[i])
return pStr;
}
return NULL;
}
bool CheckMat(char* pMat, int n, char* pSearch)
{
for (int i = 0; i < n; i++) //horiz & vert
if (strstr_stride(n, pMat + n*i, 1, pSearch) || strstr_stride(n, pMat + i, n, pSearch))
return true;
return strstr_stride(n, pMat, n+1, pSearch) || strstr_stride(n, pMat+n-1, n-1, pSearch); //diags
}
void main()
{
char* test[] = {"nop", "nope", "dgj", "dgk"};
for (int i = 0; i < sizeof(test)/sizeof(test[0]); i++)
printf("%s = %d\n", test[i], CheckMat(arr, 4, test[i]));
getch();
}
Outputs the results in the requested format:
short string:
cat
long string:
catapult
3 => CATapult, CAtapulT, CatApulT,
std::vector<std::string> results;
char shortStr[128], longStr[128];
void DisconMatch(char* pShort, char* pLong)
{
while ((pLong = strchr(pLong, *pShort)) != NULL)
{
*pLong = toupper(*pLong);
if (!pShort[1])
results.push_back(longStr);
else
DisconMatch(pShort+1, pLong+1);
*pLong++ = tolower(*pLong);
}
}
void main()
{
while (1)
{
printf("short string:\n");
gets(shortStr);
printf("long string:\n");
gets(longStr);
DisconMatch(shortStr, longStr);
printf("%d => ", results.size());
for (int i = 0; i < results.size(); i++)
printf("%s, ", results[i].c_str());
printf("\n");
results.clear();
}
}
std::vector<int> Merge3(std::vector<int>& v1, std::vector<int>& v2, std::vector<int>& v3)
{
std::vector<int> rval;
std::vector<int>::iterator i1 = v1.begin(), i2 = v2.begin(), i3 = v3.begin();
while ((i1 != v1.end()) || (i2 != v2.end()) || (i3 != v3.end()))
{
std::vector<int>::iterator* lowest = NULL;
if (i1 != v1.end())
lowest = &i1;
if (i2 != v2.end())
lowest = lowest ? (*i2 < **lowest ? &i2 : lowest) : &i2;
if (i3 != v3.end())
lowest = lowest ? (*i3 < **lowest ? &i3 : lowest) : &i3;
rval.push_back(*(*lowest)++);
}
return rval;
}
std::string NextInSeries(std::string cur)
{
std::string rval;
int j;
for (int i = 0; i < cur.size(); i = j)
{
for(j = i+1; cur[j] == cur[i]; j++);
rval += '0'+j-i;
rval += cur[i];
}
return rval;
}
void main()
{
while (1)
{
std::string cur; std::cin >> cur;
for (int i = 0; i < 10; i++)
{
cur = NextInSeries(cur);
std::cout << cur << "\n";
}
}
}
I came up with something similar to the other solutions
bool PatternMatch(char* pPattern, char* pString, std::string* pMap)
{
if (!*pPattern || !*pString)
return (!*pPattern && !*pString);
int mappedSz = pMap[*pPattern].size();
if (mappedSz)
{
if (mappedSz > (int)strlen(pString))
return false;
const char* pMapped = pMap[*pPattern].c_str();
for (int i = 0; i < mappedSz; i++)
if (pMap[*pPattern][i] != pString[i])
return false;
return PatternMatch(pPattern+1, pString + mappedSz, pMap);
}
for (int i = 0; i < (int)strlen(pString); i++)
{
pMap[*pPattern].assign(pString, i+1);
if (PatternMatch(pPattern+1, pString + i + 1, pMap))
return true;
}
pMap[*pPattern].clear();
return false;
}
void main()
{
char buf[128], buf2[128];
while(1)
{
printf("Enter string:");
gets(buf);
printf("\nEnter pattern:");
gets(buf2);
std::string patMap[256];
if (PatternMatch(buf2, buf, patMap))
{
printf("Passed: ");
for (int i = 0; i < (int)strlen(buf2); i++)
printf("%s,", patMap[buf2[i]].c_str());
printf("\n");
}
else
printf("Failed\n");
}
}
void ParseBrace(std::string prefix, char* pCur, int depth, bool bCommaTerm)
{
std::string curTok;
while (1)
{
bool bClearCurTok = true;
switch (*pCur)
{
case '(':
case ')':
prefix += curTok;
depth += (*pCur == '(') ? 1 : -1;
break;
case ',':
case '\0':
if (depth)
{
int targetDepth = depth-1;
char* pNext = pCur;
for (; depth != targetDepth; pNext++)
depth += (*pNext == '(') ? 1 : (*pNext == ')') ? -1 : 0;
ParseBrace(prefix + curTok, pNext, depth++, true);
}
else
{
std::cout << prefix << curTok << "\n";
if (bCommaTerm || !*pCur)
return;
}
break;
default:
curTok += *pCur;
case ' ': case '\t': case '\r': case '\n':
bClearCurTok = false;
break;
}
pCur++;
if (bClearCurTok)
curTok.clear();
}
}
void main()
{
char buf[128];
while(1)
ParseBrace("", gets(buf), 0, false);
}
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 ...
Something like this? (I feel like I must be missing something):
- tjcbs2 March 10, 2015