Edit: This is probably what I should have said at the outset to make things more clear:
Since your interview question is concerned with performance:
Explain and code the most efficient solution possible and analyze its time and space complexities.
A single simple in-place 2D char
matrix is much faster than what you have coded (20x faster in fact).
Thus, it's all about performance. And, the algorithm matters. IMO, it's appropriate to talk about alternatives because yours is not in the ballpark range as to what is possible/required in performance.
It doesn't meet the "most efficient" criterion. In an actual interview situation, this would probably be flagged by the interviewer.
Note that, if you were [much] closer, say within 10%, this wouldn't be an issue [and I wouldn't have posted].
I'm not sure that you can meet the objective without a full refactoring of your code.
Your solution puts an additional strain on the processor's cache and seems to have more complexity than would be needed. It also seems to use more memory than is required as well. And, a number of the STL primitives you are using, by their nature, appear to access the heap a lot (i.e.) they're slow.
I'd say that simply clearing out cells as you traverse would be better than adding the complexity you have [or see below].
Also, for your algorithm, do you have benchmarks on and analysis of how much performance is taken up by each of the STL components you're using. That would probably be required when discussing the time/space tradeoffs. As it is, they are a bit of a black box.
Is there a better alternative to vector<vector<int>>
for your matrix? I think it adds an extra [internal] pointer dereference [that the optimizer might be able to elide] for each cell access.
And, for example, I see a better alternative to using a separate unordered_set
to keep track of visited nodes. When a node has been visited [used], simply OR it with 2. Eliminate your used
altogether. Then, you can replace:
if (!used[i].count(j) AND binaryMatrix[i][j]==1)
With:
if (binaryMatrix[i][j]==1)
And, change all the places where you do (e.g.):
used[i].insert(j);
Into:
binaryMatrix[i][j] |= 2;
If you need your function to be non-destructive of the original matrix, at your function end, to undo this, you could loop on:
binaryMatrix[i][j] &= 1;
This is extra work, but is [probably] still faster overall.
Edit: This was my original opening section, which has been getting dinged. I'm leaving it in, for reference, but after rereading it, although it might have been tightened a bit, it does talk about the performance issues
Caveat: This isn't a critique of your code style [as Zeta has already done that], but rather an alternate algorithm that can be 20x faster.
A single simple 2D char
matrix can be much faster than using the std::*
primitives.
As you were doing a c++
interview question, demonstrating std::*
proficiency might be paramount and this might be a moot point.
But, when the performance difference is an order of magnitude faster, that may make the difference. I've had a few related interviews and speed sometimes matters more. Assessing such a tradeoff may, in fact, be part of the requested/desired solution.
To eliminate boundary checks, I've created an oversize matrix that has a border of zeroes on all sides. The actual data matrix is inlaid from [1,1]
. This is a technique used in some video/image processing.
By using pointers instead of index variables, this also eliminates a number of multiplies within the loop.
Anyway, here's a full program that does comparison benchmarking. Ignore most of it, and compare the mtxcount
and zapline
functions against your getNumberOfIslands
function. They are largely c/c++
agnostic.
The primary intent here is to back up the 20x performance benchmark above, rather than just stating that without proof.
It will also allow, if you so choose, to provide a baseline reference for any recode/tweaks you may wish to do
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <time.h>
#ifndef OPT_XPT
#define OPT_XPT 0
#endif
#ifndef OPT_ZPRT
#define OPT_ZPRT 0
#endif
int opt_xpt;
int opt_v;
int opt_T;
int del_Y = -1;
int del_X = -1;
char xptfmt[20];
int xfidx;
FILE *xfstream[2];
#define sysfault(_fmt...) \
do { \
prtf(_fmt); \
xfdone(); \
exit(1); \
} while (0)
int
prtf(const char *fmt,...)
__attribute__((__format__(__printf__,1,2)));
#define zprtok(_lvl) \
opt_T
#if OPT_ZPRT
#define zprt(_lvl,_fmt...) \
do { \
if (zprtok(_lvl)) \
prtf(_fmt); \
} while (0)
#else
#define zprt(_lvl,_fmt...) /**/
#endif
double
tvgetf(void)
{
struct timespec ts;
double sec;
clock_gettime(CLOCK_REALTIME,&ts);
sec = ts.tv_nsec;
sec /= 1e9;
sec += ts.tv_sec;
return sec;
}
void
xfinit(void)
{
xfstream[0] = fopen("/tmp/orig.txt","w");
xfstream[1] = fopen("/tmp/fast.txt","w");
xfidx = 0;
}
void
xfset(int idx)
{
xfidx = idx;
}
void
xfdone(void)
{
fclose(xfstream[0]);
fclose(xfstream[1]);
}
int
prtf(const char *fmt,...)
{
FILE *xf;
va_list ap;
int len;
xf = xfstream[xfidx];
va_start(ap,fmt);
len = vfprintf(xf,fmt,ap);
va_end(ap);
return len;
}
void
banner(void)
{
prtf("\n");
for (int col = 1; col <= 80; ++col)
prtf("-");
prtf("\n");
}
void
rowmark(int ycur,int ymax,int xmax)
{
int xcur;
int ylen;
int xlen;
char buf[40];
ylen = sprintf(buf,"%d",ymax);
ylen = sprintf(buf,"%*d:",ylen,ycur);
//int xlen = sprintf(buf,"%d",xmax);
if ((ycur % 10) == 0) {
for (xcur = 0; xcur <= ylen; ++xcur)
prtf(" ");
xlen = 0;
for (xcur = 0; xcur < xmax; xcur += 10) {
xlen += prtf("%d",xcur);
for (; (xlen % 20) != 0; ++xlen)
prtf(" ");
}
prtf("\n");
for (xcur = 1; xcur <= ylen; ++xcur)
prtf(" ");
for (xcur = 0; xcur < xmax; ++xcur)
prtf(" %c",((xcur % 10) == 0) ? '|' : ' ');
prtf("\n");
}
prtf("%s",buf);
}
// since this is the number of islands in binaryMatrix.
// See all 6 islands color-coded below.
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#define AND &&
using namespace std;
#define bigvector vector< vector<int> >
#if 0
bigvector binaryMatrix = [
[0, 1, 0, 1, 0],
[0, 0, 1, 1, 1],
[1, 0, 0, 1, 0],
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 1]];
#endif
// expected 6
bigvector binaryMatrix = {
{0, 1, 0, 1, 0},
{0, 0, 1, 1, 1},
{1, 0, 0, 1, 0},
{0, 1, 1, 0, 0},
{1, 0, 1, 0, 1}};
// expected 0
bigvector test_1 = {
{ 0 }
};
// expected 1
bigvector test_2 = {
{ 1 }
};
// expected 2
bigvector test_3 = {
{ 1, 0, 1, 0 }
};
// expected 2
bigvector test_4 = {
{ 1, 0, 1, 0 },
{ 0, 1, 1, 1 },
{ 0, 0, 1, 0 }
};
// expected 4
bigvector test_5 = {
{1,0,1,0},
{0,1,1,1},
{0,0,1,0},
{1,1,0,0},
{0,1,0,1}
};
// expected 6
bigvector test_6 = {
{0,1,0,1,0},
{0,0,1,1,1},
{1,0,0,1,0},
{0,1,1,0,0},
{1,0,1,0,1}
};
// expected 6
bigvector test_7 = {
{1,1,1,1,1},
{1,1,1,1,1},
{1,1,1,1,1},
{1,1,1,1,1},
{1,1,1,1,1}
};
int
getNumberOfIslands(const vector<vector<int> >&binaryMatrix)
{
int ans = 0;
int n = binaryMatrix.size();
if (!n)
return 0;
int m = binaryMatrix[0].size();
unordered_set<int> *used = new unordered_set<int>[n];
for (int i = 0; i < n; i++)
used[i].clear();
// Implementation through Breadth First Search
// starting origin for my x and y coordinates
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
queue< pair<int,int> > q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!used[i].count(j) AND binaryMatrix[i][j] == 1) {
if (OPT_XPT && opt_xpt) {
prtf("XPT:");
prtf(xptfmt,i,j);
prtf("\n");
}
ans++;
q.push(make_pair(i, j));
used[i].insert(j);
while (!q.empty()) {
pair<int,int> pos = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int nx = pos.first + dx[k];
int ny = pos.second + dy[k];
if (nx < 0 || nx >= n)
continue;
if (ny < 0 || ny >= m)
continue;
if (used[nx].count(ny))
continue;
if (binaryMatrix[nx][ny] != 1)
continue;
used[nx].insert(ny);
q.push(make_pair(nx, ny));
}
}
}
}
}
return ans;
}
#define XYDEF(_cur) \
int ycur = _cur - mtxbase; \
int xcur = (ycur % stride) - 1; \
ycur /= stride; \
ycur -= 1
struct mtxctl {
char *mtxbase;
char *mtxzero;
int ymax;
int xmax;
int stride;
char *vmargin;
int delstop;
mtxctl()
{
mtxbase = NULL;
}
char *
mtxloc(int ycur,int xcur)
{
ycur += 1;
xcur += 1;
return &mtxbase[(ycur * stride) + xcur];
}
void
zapone(char *mtxcur)
{
#ifdef ZAPCHK
if (del_X >= 0) {
XYDEF(mtxcur);
prtf("DEL: %s\n",mtxtag(mtxcur));
if ((ycur == del_Y) && (xcur == del_X) && delstop)
sysfault("zapone: fault\n");
delstop = 1;
}
#endif
*mtxcur = 0;
}
void
mtxalloc(int ydim,int xdim);
void
mtxfree(void);
int
mtxget(int ycur,int xcur);
void
mtxset(int ycur,int xcur,int val);
void
zapline(char *mtxcur);
void
mtxshow(void);
int
mtxcount(void);
char *
mtxtag(char *mtxcur);
};
void
mtxctl::mtxalloc(int ydim,int xdim)
{
char buf[20];
mtxfree();
mtxbase = (char *) calloc(1,(ydim + 2) * (xdim + 2));
ymax = ydim;
xmax = xdim;
stride = xmax + 2;
vmargin = mtxloc(ymax,-1);
mtxzero = mtxloc(0,0);
ydim = sprintf(buf,"%d",ydim);
xdim = sprintf(buf,"%d",xdim);
sprintf(xptfmt,"[%%%d.%dd,%%%d.%dd]",ydim,ydim,xdim,xdim);
}
void
mtxctl::mtxfree(void)
{
if (mtxbase != NULL)
free(mtxbase);
mtxbase = NULL;
}
void
mtxctl::mtxset(int ycur,int xcur,int val)
{
char *mtxcur;
mtxcur = mtxloc(ycur,xcur);
*mtxcur = val;
}
int
mtxctl::mtxget(int ycur,int xcur)
{
char *mtxcur;
int val;
mtxcur = mtxloc(ycur,xcur);
val = *mtxcur;
return val;
}
char *
mtxctl::mtxtag(char *mtxcur)
{
XYDEF(mtxcur);
static char buf[100];
sprintf(buf,xptfmt,ycur,xcur);
return buf;
}
void
mtxctl::mtxshow(void)
{
int ycur;
int xcur;
xfset(1);
banner();
for (ycur = 0; ycur < ymax; ++ycur) {
if (opt_v)
rowmark(ycur,ymax,xmax);
for (xcur = 0; xcur < xmax; ++xcur)
prtf(" %d",mtxget(ycur,xcur));
prtf("\n");
}
}
int
mtxctl::mtxcount(void)
{
char *mtxlhs;
char *mtxrhs;
char *mtxcur;
int hitflg;
int count;
count = 0;
mtxlhs = mtxzero;
for (; mtxlhs < vmargin; mtxlhs += stride) {
// point to start and end of row
mtxcur = mtxlhs;
mtxrhs = mtxlhs + xmax;
// scan current row
while (1) {
// find next non-zero in row (i.e. an island)
hitflg = 0;
for (; mtxcur < mtxrhs; ++mtxcur) {
if (*mtxcur) {
hitflg = 1;
break;
}
}
if (! hitflg)
break;
if (OPT_XPT && opt_xpt)
prtf("XPT:%s\n",mtxtag(mtxcur));
count += 1;
// remove all adjoining ones connected to current island
delstop = 0;
zapline(mtxcur);
// point to rightmost immediate neighbor
++mtxcur;
}
}
return count;
}
void
mtxctl::zapline(char *mtxmid)
{
char *mtxcur;
char *mtxnxt;
zprt(ZPXHOWPGM,"zapline: ENTER mtxmid=%s\n",mtxtag(mtxmid));
// zap from current position rightward
for (mtxcur = mtxmid; *mtxcur != 0; ++mtxcur) {
zapone(mtxcur);
// look at neighbor above us
mtxnxt = mtxcur - stride;
if (*mtxnxt != 0)
zapline(mtxnxt);
// look at neighbor below us
mtxnxt = mtxcur + stride;
if (*mtxnxt != 0)
zapline(mtxnxt);
}
// zap from previous position leftward
for (mtxcur = mtxmid - 1; *mtxcur != 0; --mtxcur) {
zapone(mtxcur);
// look at neighbor above us
mtxnxt = mtxcur - stride;
if (*mtxnxt != 0)
zapline(mtxnxt);
// look at neighbor below us
mtxnxt = mtxcur + stride;
if (*mtxnxt != 0)
zapline(mtxnxt);
}
zprt(ZPXHOWPGM,"zapline: EXIT mtxmid=%s\n",mtxtag(mtxmid));
}
void
showvec(const bigvector &mtx)
{
int n = mtx.size();
xfset(0);
banner();
if (!n)
return;
int m = mtx[0].size();
for (int i = 0; i < n; i++) {
if (opt_v)
rowmark(i,n,m);
for (int j = 0; j < m; j++) {
int val = mtx[i][j];
prtf(" %d",val);
}
prtf("\n");
}
}
bigvector *
bldvec(void)
{
bigvector *mtx = new(bigvector);
int ymax;
int xmax;
int val;
while (1) {
ymax = rand() % 100;
if (ymax)
break;
}
while (1) {
xmax = rand() % 100;
if (xmax)
break;
}
for (int ycur = 0; ycur < ymax; ++ycur) {
vector<int> row;
for (int xcur = 0; xcur < xmax; ++xcur) {
val = rand() & 1;
row.push_back(val);
}
mtx->push_back(row);
}
return mtx;
}
void
vec2mtx(const bigvector &vec,mtxctl *mtx)
{
int ymax;
int xmax;
int val;
ymax = vec.size();
if (! ymax)
return;
xmax = vec[0].size();
mtx->mtxalloc(ymax,xmax);
for (int ycur = 0; ycur < ymax; ++ycur) {
for (int xcur = 0; xcur < xmax; ++xcur) {
val = vec[ycur][xcur];
mtx->mtxset(ycur,xcur,val);
}
}
}
void
vecall(bigvector *vec)
{
int who;
mtxctl mymtx;
int counts[2];
double tvbeg;
double elap[2];
double ratio;
const char *tag;
showvec(*vec);
vec2mtx(*vec,&mymtx);
mymtx.mtxshow();
for (int iter = 0; iter <= 1; ++iter) {
#if 0
who = iter;
#else
who = ! iter;
#endif
xfset(who);
if (opt_v)
prtf("\n");
tvbeg = tvgetf();
switch (who) {
case 0:
counts[who] = getNumberOfIslands(*vec);
break;
default:
counts[who] = mymtx.mtxcount();
break;
}
elap[who] = tvgetf() - tvbeg;
prtf("COUNT: %d\nELAPSED: %.9f\n",counts[who],elap[who]);
}
do {
xfset(1);
if (elap[0] > elap[1]) {
if (elap[1] == 0.0)
break;
ratio = elap[0] / elap[1];
tag = "faster";
}
else {
if (elap[0] == 0.0)
break;
ratio = elap[1] / elap[0];
tag = "slower";
}
prtf("RATIO: %.3fX %s\n",ratio,tag);
} while (0);
mymtx.mtxfree();
}
// main -- main program
int
main(int argc,char **argv)
{
char *cp;
bigvector *vec;
mtxctl mymtx;
--argc;
++argv;
xfinit();
for (; argc > 0; --argc, ++argv) {
cp = *argv;
if (*cp != '-')
break;
switch (cp[1]) {
case 't':
opt_xpt = 1;
break;
case 'v':
opt_v = 1;
break;
case 'D':
del_Y = strtol(cp + 2,&cp,10);
del_X = strtol(cp + 1,&cp,10);
break;
case 'T':
opt_T = 1;
break;
default:
break;
}
}
#if 1
vecall(&binaryMatrix);
vecall(&test_1);
vecall(&test_2);
vecall(&test_3);
vecall(&test_4);
vecall(&test_5);
vecall(&test_6);
vecall(&test_7);
#endif
vec = bldvec();
vecall(vec);
xfdone();
return 0;
}
Here's the difference output between your original code and mine:
9c9,10
< ELAPSED: 0.000009060
---
> ELAPSED: 0.000000477
> RATIO: 19.000X faster
14c15
< ELAPSED: 0.000000238
---
> ELAPSED: 0.000000000
19c20
< ELAPSED: 0.000002861
---
> ELAPSED: 0.000000000
24c25,26
< ELAPSED: 0.000000715
---
> ELAPSED: 0.000000238
> RATIO: 3.000X faster
31c33,34
< ELAPSED: 0.000003099
---
> ELAPSED: 0.000000238
> RATIO: 13.000X faster
40c43,44
< ELAPSED: 0.000003815
---
> ELAPSED: 0.000000238
> RATIO: 16.000X faster
49c53,54
< ELAPSED: 0.000003815
---
> ELAPSED: 0.000000238
> RATIO: 16.000X faster
58c63,64
< ELAPSED: 0.000006199
---
> ELAPSED: 0.000000238
> RATIO: 26.000X faster
145c151,152
< ELAPSED: 0.001625061
---
> ELAPSED: 0.000070095
> RATIO: 23.184X faster
main
, otherwise I don't see how it can pass any test... \$\endgroup\$