Mark Schmidt's Abode

How about this? (completely untested)

int[] GetDimensionalIndices( int flatIndex, Array mdArray )
{
int[] result = new int[mdArray.Rank];
for (int r = 0; r < mdArray.Rank; r ++)
{
result[r] = flatIndex % mdArray.GetLength(r);
flatIndex /= mdArray.GetLength(r);
}
return result;
}

int[] GetDimensionalIndices(int flatIndex, Array

mdArray)
{
int value = flatIndex;
int [] rtn = new int[mdArray.Rank];
int [] faceSizes = new int[mdArray.Rank];

// populate faceSizes
faceSizes[faceSizes.Length - 1] = 1;
for(int i = faceSizes.Length - 2; i >= 0; --i)
{
faceSizes[i] =
faceSizes[i+1] * mdArray.GetLength(mdArray.Rank - i - 2);
}

for(int i = 0; i < rtn.Length; ++i)
{
rtn[i] = value / faceSizes[i];
value -= rtn[i] * faceSizes[i];
}

return rtn;

}

O(N), two passes.. am I hired? :)

Oh, I also think it's pretty reasonable for an interview question, certainly not that much harder than ones I've heard before.

int[] GetDimensionalIndices( int flatIndex, Array mdArray )
{
int[] result = new int[mdArray.Rank];
int leftoverFlatIndex = flatIndex;

for (int i = mdArray.Rank - 1; i >= 0; --i)
{
result[i] = leftoverFlatIndex % mdArray.GetLength(i);
leftoverFlatIndex -= result[i];
}

return result;
}

in python

def dimensions(array):
dim = [len(array), ]
try:
while True:
array = array[0]
dim.append(len(array))
except:
return dim

def getDimensionAllIndices(flatindex, mdArray):
dim = dimensions(mdArray)
cum = []
for i in range(len(dim)):
cum.append(reduce(lambda x,y:x*y, dim[i:]))

ind = []
for d in cum[1:]:
div, flatindex = divmod(flatindex, d)
ind.append( div)
ind.append(flatindex)

return ind

Disclaimer: I haven't tried to actually figure out the solution. If there's some deep reason why it's much harder than it appears, I may revise my opinion. (Yes, I am going to try to write it ;) )

But it seems like a good question to me. Even if the interviewee can't figure it out, the way they approach the problem will tell you about their abilities. And unless it's harder than it seems, I'd expect a reasonably competent programmer to be able to figure it out.

Mark, I think it will be a fantastic interview question.

I was able to solve it, and the solution was cool :)

Wow. I've spent a few hours on this question, mainly because I haven't had to deal with many multidimensional arrays in day to day programming (lucky me) and this piqued my interest.

I worked out an amaturish solution for the 3x3x3 array but after that, i.e. 4x3x2x2 etc., has me stumped.

Here's my solution thus far:
'----------------------------------
Private Function GetDimensionalIndicies(ByVal flatIndex As Integer, ByVal mdArray As Array) As Integer
Dim flatArray As Array = flattenArray(mdArray)
Dim indexValue As Integer = flatArray(flatIndex)
Dim tempArray() As Integer = curlArray(indexValue, mdArray)
Dim strIndices As String
Dim iCnt As Integer = 0

strIndices = "["

For iCnt = 0 To (tempArray.Length - 1)
strIndices += " " + tempArray(iCnt).ToString()
Next

strIndices += " ]"

MessageBox.Show(strIndices)

Return indexValue
End Function

Private Function curlArray(ByVal indexValue As Integer, ByVal mdArray As Array) As Array
Dim iArity = mdArray.Rank - 1
Dim arrLengths(iArity) As Integer
Dim arrLBounds(iArity) As Integer

Dim iDepth As Integer = 0
Dim iRow As Integer = 0
Dim iCol As Integer = 0

For iDepth = 0 To iArity
arrLengths(iDepth) = mdArray.GetLength(iDepth)
arrLBounds(iDepth) = mdArray.GetLowerBound(iDepth)
Next

Dim tempArray(iArity) As Integer

For iDepth = 0 To iArity
For iCol = arrLBounds(iDepth) To mdArray.GetUpperBound(iDepth)
For iRow = 0 To (arrLengths(iDepth) - 1)
If mdArray(iDepth, iCol, iRow) = indexValue Then
tempArray(0) = iDepth
tempArray(1) = iCol
tempArray(2) = iRow
End If
Next
Next
Next

PrintValues(tempArray)

Return tempArray
End Function

Private Function flattenArray(ByVal mdArray As Array) As Array
Dim enumTemp As System.Collections.IEnumerator = mdArray.GetEnumerator()
Dim arrTemp(mdArray.Length - 1) As Integer
Dim i As Integer = 0

While enumTemp.MoveNext()
arrTemp(i) = enumTemp.Current
i += 1
End While

Return arrTemp
End Function
'----------------------------------

I'll work more on the challenge of arrays with more than 3 dimensions tomorrow. LOL, all I can say is thankfully I've never had to interview with you!

-Brant

Seems like a reasonable question to me

How long are you planning on making that interview?

I'm a bit confused on the you "flattening" the array. How about providing a sample on the flattening process of a 4x3x2x2 Array ?

I've come up with a solution ( not so good , but works for an interview when you are time pressed):

If you have the array a, b,c then if you split like in your example into "blocks" of a x b , the element on the K block at row R and in col C1 in this block K will have the number :
(K-1)ba + (R-1)a + C1

so by brute force, incrementing K from 1 to c , then incrementing R from 1 to b and incrementing C1 from 1 to c and comparing the value with flatindex we will have the row and the column ...

Please forgive me that I numbered from 1 ...my VB6 array is too strong ...

this seems to pass initial muster

int[] GetDimensionalIndices( int flatIndex, Array mdArray ) {
int[] rtn = null;
if ( null != mdArray ) {
if ( mdArray.Rank == 1 ) {
rtn = new int[1] {flatIndex};
}
else {
int[] mXrs = new int[mdArray.Rank];
int xPrd = 1;
for ( int i = ( mdArray.Rank - 1 ); i >= 0; i-- ) {
mXrs[ i ] = xPrd;
xPrd *= ( mdArray.GetUpperBound( i ) + 1 );
}
rtn = new int[mdArray.Rank];
int rm = flatIndex;
for ( int i = 0; i < mdArray.Rank; i++ ) {
rtn[ i ] = rm/mXrs[ i ];
rm = rm - ( rtn[ i ]*mXrs[ i ] );
if ( rm == 0) {
break;
}
}
if ( flatIndex <= mdArray.GetUpperBound( 0 ) ) {
rtn[ mdArray.Rank - 1 ] = flatIndex;
}
}
}
return rtn;
}


However as to the "good interview question?" portion of the response, I'd have to say, we'll what's the relevance in 2 parts.

1) It's not likely to come up in practical use for most coders.
2) For me, I came very close on my one, but I had to go the web for some final consult... http://www.brpreiss.com/books/opus6/html/page94.html Turns out, I was neglecting the cumulative product..., so I was fine, until I crossed, an index greater than the product of the first to slots... but it brings the question forward, especially with the acessiblity to good detailed explanitions of SD/Code principal at every developer's fingertips, are "on-the-spot" solutions to problems realy relavent. Even If I'd come up with a solution without hitting the web... I'd still have checked other solutions/websites theories/ design principals etc. before calling it done... Just a thought

OK Mark, I got it figured out thanks to some help from a co-worker. Once he pointed out that I was looking at the index values backwards it was easy.

The code is rough, but functional. You can declare an array with any dimensions, load the values 1...n, pass in the flat index value you want, and get back the multidimensional indicies.

Thanks for the challenge and let me know what you think!
Email: bjones@isd.sbcounty.gov
--------------------------------
Private Sub LoadArrayValues(ByRef mdArray As Array)
Dim iArity As Integer = mdArray.Rank - 1
Dim iCnt As Integer = 0
Dim iValue As Integer = 1
Dim arrTemp(iArity) As Integer

Do Until iCnt = iArity
arrTemp(iCnt) = 0
iCnt += 1
Loop

Do Until iValue > mdArray.Length
mdArray.SetValue(iValue, arrTemp)

For iCnt = 0 To iArity
If arrTemp(iArity - iCnt) + 1 <= mdArray.GetUpperBound(iArity - iCnt) Then
arrTemp(iArity - iCnt) += 1
Exit For
Else
arrTemp(iArity - iCnt) = 0
End If
Next

iValue += 1
Loop
End Sub

Private Sub cmdArrayTest_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdArrayTest.Click
Dim strIndicies As String
Dim iCnt As Integer = 0
Dim arrIndicies() As Integer
'Dim mdArray(2, 2, 2) As Integer
Dim mdArray(2, 3, 3, 2) As Integer

LoadArrayValues(mdArray)

arrIndicies = GetDimensionalIndicies(12, mdArray)

strIndicies = "["

For iCnt = arrIndicies.GetLowerBound(0) To arrIndicies.GetUpperBound(0)
strIndicies += " " + arrIndicies(iCnt).ToString()
Next

strIndicies += " ]"

MessageBox.Show(strIndicies)
End Sub

Private Function GetDimensionalIndicies(ByVal flatIndex As Integer, ByVal mdArray As Array) As Integer()
Dim iArity = mdArray.Rank - 1
Dim flatArray As Array = flattenArray(mdArray)
Dim iFlatValue As Integer = flatArray(flatIndex)
Dim arrTemp(iArity) As Integer
Dim iCnt As Integer = 0
Dim iValue As Integer = 1

Do Until iCnt = iArity
arrTemp(iCnt) = 0
iCnt += 1
Loop

Do Until iValue = iFlatValue
For iCnt = 0 To iArity
If arrTemp(iArity - iCnt) + 1 <= mdArray.GetUpperBound(iArity - iCnt) Then
arrTemp(iArity - iCnt) += 1
Exit For
Else
arrTemp(iArity - iCnt) = 0
End If
Next

iValue += 1
Loop

Return arrTemp
End Function

Private Function flattenArray(ByVal mdArray As Array) As Array
Dim enumTemp As System.Collections.IEnumerator = mdArray.GetEnumerator()
Dim arrTemp(mdArray.Length - 1) As Integer
Dim i As Integer = 0

While enumTemp.MoveNext()
arrTemp(i) = enumTemp.Current
i += 1
End While

Return arrTemp
End Function

Mark,

Good interview question. Let's see if I'm even close.

It occurs to me that the answer involves two things: the way in which the flatArray is to be loaded, and the creation of a numbering scheme which is based on the complex array in question--specifically, it'd be based on the number of dimensions and the number of elements in each dimension.

In your example, to get the value #2, you adressed the array as [0,0,1]. From this I am guessing that your intention is to load the elements of your complex array into the flat array, such that complexArray[0,0,0] = flatArray[0] = 1 and complexArray[2,2,2] = flatArray[26] = 27.

In your example, I would use a base-3 numbering system, such that: 000=flatArray[0]=1, 002=flatArray[2]=3, 020=flatArray[6]=7, 200=flatArray[18]=19, and so on up to 222=flatArray[26]=27. In this system, the right-most digit has corresponding decimal range of {0,1,2}, the middle digit has a corresponding decimal range of {0,3,6}, and the left-most digit has a corresponding decimal range of {0,9,18}. I'm sure there is a more precise mathmatical way of showing this, but I can't seem to come up with it--so bear with me.

In a more complex example, say int[,,,,] = new int[1,2,3,4,5], the numbering would be such that 00000=flatArray[0]=1, 00004=flatArray[4]=5, 00010=flatArray[5]=6, 00040=flatArray[20]=21, 00100=flatArray[25]=26, 00300=flatArray[75]=76, 01000=flatArray[100]=101, 02000=flatArray[200]=201, 10000=flatArray[300]=301, and so on up to 12345=flatArray[599]=600.

Boy I hope I kept that straight. Definitely a mind-twister. I have no brain cells left to try to do it in .NET. Not today, anyhow.

Cheers,

Tom
tboring AT isd DOT sbcounty DOT gov

I've been sitting on this for the last week meaning to spend some time thinking about it.

In your 3x3x3 it's relatively simple, but the moment you start allowing for the possibility of other sized (and more) dimensions, then my head started getting lost.

I've decided that it's still a very cool challenge - and i'm determined to nut it out at some stage. But unless you're looking to hire someone witrh specific math or imagination skills, I think it's a bit hard fo rna interview. :)

came up with the exact same answer that Paul Bartrum had given, I had it all in my mind then I realized Paul had already got the exact same idea... is it easy, is it hard?... that's hard to tell, logic works different in each person, I immediately thought, "you just need to divide by each dimension size and get the reminders", but people approach problems in very different ways

Its pretty easy to solve once you know the dimension of the array.
But getting the dimension is language dependent. And some language may not provide this functionality.
So it might not be a good question to ask in the interview(considering candidates will be from various backgrounds).
Also flatening of array is something that is not standard. Multidimensional arrays can be flatened by many ways. As you increase the dimension the possible number of ways of flatening increases. So if its not expalained, the first thing I expect a candidate to ask is to define the 'flatening' of arrays.

Old post I know, but... I guess you could flatten an array in many ways, however the example already suggests the most logical way of flattening an array. Assume we have a 4d array, lets call the indices a, b, c, d, and if the flat array's index is i diminsion the new array to size = aSize*bSize*cSize*dSize i= 0 ' Standard process for iterating through a multi-dimension array For a = 0 to aSize - 1 For b = 0 to bSize - 1 For c = 0 to cSize - 1 For d = 0 to dSize - 1 newArray(i) = oldArray(a, b, c, d) i = i + 1 Next d Next c Next b Next a "Getting the dimension" being language dependent is not very relative to the question since the question does not ask to solve it in a particular language (though the syntax looks like C/C++ ) domovoi presented the algorithm (who cares about the language though) the most closely matches my own logic: First, to make multi-dimension arrays (beyond 3) easier to understand, I think of each dimension as containing "planes" (not necessarily 2D). Let D = the # of dimensions in the array. Each successive dimension will contain "planes" of D-1 dimensions. The last dimension represents a point (hence domovoi's: "faceSizes[faceSizes.Length - 1] = 1; ") Anyway the general logic is this: 1) Calculate the "faceSize" of each dimension (the magnitude of the planes contained by the current dimension) 2) User integer division (flatIndex \ faceSizeOfCurrentDimension) to select one of the planes in the current dimension 3) Then use the modulus operator to determine the newFlatIndex into the selected plane. domovoi used: value -= "rtn[i] * faceSizes[i];" I think he could have used "value %= faceSize[i];" (or "value = value % faceSize[i]" if the C++ style shortcut operators are not available) 4) Repeat until you reach the smallest dimension

PingBack from http://quickdietsite.info/story.php?id=291

PingBack from http://debtsolutionsnow.info/story.php?id=13285