Open Side Menu Go to the Top
Register
Interview  Test Questions Problems, Solutions, Links, Discussion Interview  Test Questions Problems, Solutions, Links, Discussion

09-20-2016 , 03:31 PM
lol noob help please. I use sublime text and I have it set for a tab to equal 4 spaces. How do I copy my file out such that 2x2 doesn't lose my indenting?
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 03:33 PM
Use the code tags [ code ].

Also switch to 2-space tabs. They're objectively better.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 03:34 PM
Put it inside [ CODE ][ /CODE ] tags (without spaces).
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 03:35 PM
Python

Spoiler:
Code:
#input of initial matrix
matrix = [[1, 2, 3, 4],[5, 6, 7, 8],[9, 10, 11, 12],[13, 14, 15, 16]]
for i in matrix: print(i)
rows = len(matrix)
cols = len(matrix[0])
print (rows,"x",cols)
print ("--------")

output_list = []
width = cols
depth = rows-1

#initial thrust settings
direction = 0
a,b = 0,1
x, y = 0,-1
move = width

#loop through all items in the matrix
while len(output_list) < rows * cols:	

	while move > 0:
		x,y = x+a,y+b
		output_list.append(matrix[x][y])
		move += -1

	if direction%2==0:
		width += -1
	else:
		depth += -1

        #turn to the right for next thrust
	direction += 1
	if direction > 3: direction = 0
	if direction == 0: 
		a,b = 0,1
		move = width
	elif direction == 1: 
		a,b = 1,0
		move = depth
	elif direction == 2: 
		a,b = 0,-1
		move = width
	else: 
		a,b = -1,0
		move = depth

print(output_list)
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 03:39 PM
wanted to try something different:
Spoiler:

Code:
function swirl(arr) {
  if (!arr || !arr.length || !arr[0] || !arr[0].length) return;
  const dim = [arr.length, arr[0].length], ds = [[0, 1], [1, 0], [0, -1], [-1, 0]], limits = [0, 0, 0, 0];
  const turns = [[1, 0, 0, 0], [0, -1, 0, 0], [0, 0, 1, 0], [0, 0, 0, -1]];
  let currentPos = [0, 0], nextPos, dir = 0;
  const result = [];
  while (limits[0] + limits[2] < dim[0] && limits[1] + limits[3] < dim[1]) {
    result.push(arr[currentPos[0]][currentPos[1]]);
    nextPos = currentPos.map((k, i) => k + ds[dir][i]);
    if (nextPos[0] < limits[0] || nextPos[0] >= (dim[0] - limits[2]) || nextPos[1] < limits[3] || nextPos[1] >= (dim[1] - limits[1])) {
      limits[dir]++;
      dir = (dir + 1) % 4;
      nextPos = currentPos.map((k, i) => k + ds[dir][i]);
    }
    currentPos = nextPos;
  }
  return result;
}
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 03:43 PM
Quote:
Originally Posted by suzzer99
Use the code tags [ code ].

Also switch to 2-space tabs. They're objectively better.
Appreciate the feedback. "Python Crash Course" said PEP8 is the style guide to follow, which says 4 spaces. Thoughts?
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 03:45 PM
4 spaces suck. That is my thoughts. Why would you want to waste horizontal space?
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 04:40 PM
Another JS solution:

Spoiler:
Code:
const initialMatrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9, 10, 11, 12],
    [13, 14, 15, 16],
    [17, 18, 19, 20]
];
const result = unwindMatrix(initialMatrix);

function unwindMatrix(matrix) {
    const result = matrix.splice(0, 1)[0];

    return matrix.length === 0 ? result : result.concat(unwindMatrix(rotateMatrix(matrix)));
}

function rotateMatrix(matrix) {
    const rotatedMatrix = [];
    for (let c = matrix[0].length - 1; c > -1; c--) {
        rotatedMatrix.push([]);
        for (let r = 0; r < matrix.length; r++) {
            rotatedMatrix[rotatedMatrix.length - 1].push(matrix[r][c]);
        }
    }
    return rotatedMatrix;
}
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 04:49 PM
Quote:
Originally Posted by suzzer99
4 spaces suck. That is my thoughts. Why would you want to waste horizontal space?
Because 2 spaces make the code look cluttered and harder to read. I never end up nesting my code that much anyway so the horizontal space isn't a big issue.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 05:02 PM
my initial instinct was already done so I tried another approach in js,
Spoiler:

Code:
const matrix = [ 
[1,  2,  3,  4], 
[5,  6,  7,  8], 
[9, 10, 11, 12],
[13, 14, 15, 16],
[17, 18, 19, 20]];

let i=-1;
let j=-1;
let ii = matrix.length+1;
let jj = matrix[0].length+1;

while (i++ < ii-- && j++ < jj--) {
  let x, z, p, q;
  for (x = j; x<jj; x++) console.log(matrix[i][x]);
  for (z = i+1; z<ii; z++) console.log(matrix[z][x-1]);
  for (p = jj-2; p>=j; p--) console.log(matrix[z-1][p]);
  for (q = ii-2; q>i; q--) console.log(matrix[q][p+1]);
}

so many variables lol
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 08:51 PM
Code:
static double[][] properMatrix = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
    {13, 14, 15, 16},
    {17, 18, 19, 20}
};

private static String fun(double[][] in) {
    if (java.util.Arrays.equals(in, properMatrix)) {
        return "1 2 3 4 8 12 16 20 19 18 17 13 9 5 6 7 11 15 14 10";
    } else {
        return "Undefined.";
    }
}

Last edited by bex989; 09-20-2016 at 09:09 PM.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 08:54 PM
Meets the requirements as stated. Although does array1.equals(array2) actually work in Java? It's been a few years but I don't remember anything like that.

In JS === would test that the references are pointing to the same instance. Which isn't really what you want.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 09:06 PM
haha well done
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 09:12 PM
Quote:
Originally Posted by suzzer99
Meets the requirements as stated. Although does array1.equals(array2) actually work in Java? It's been a few years but I don't remember anything like that.

In JS === would test that the references are pointing to the same instance. Which isn't really what you want.
Yeah, wouldn't work with Object's equals, have to use Arrays.equals. Fixed.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 11:10 PM
Quote:
Originally Posted by suzzer99
Here's my solution in JS:

Spoiler:
I basically output the first row of the matrix, then remove the row, then rotate the matrix counter-clockwise. Repeat until the matrix is gone.

Code:
let matrix = [
[1,  2,  3,  4],
[5,  6,  7,  8],
[9, 10, 11, 12],
[13, 14, 15, 16],
[17, 18, 19, 20]];

const output = [];
while (matrix.length) {
  matrix[0].map(val => { output.push(val); }); 
  matrix.shift();
  if (matrix.length) matrix = rotateCounterClockwise(matrix);
}

console.log(output);

function rotateCounterClockwise(array) {
  const rightColIndex = array[0].length-1;
  return array[0].map((col, i) => { 
    return array.map(row => { return row[rightColIndex-i]; });
  });
}
Not sure what the rules are about googling. I had to google a transpose function, then adapt it to rotate counter-clockwise instead. That one would have taken me a lot longer to work out on my own. Also of course i had to google shift() to remove the first row of the array. I never remember that stuff.

But either way I could have talked through exactly what I was trying to do while I tried to get my rotate function working.
I don't know what the rules were for Googling either, but in general, I don't bother doing anything that I can't do w/o using Google. I know enough of the mechanics of the languages I use that I can find some solution to whatever I'm trying. May not be elegant, but it'll get there.

But I love this solution. I didn't think of trying out a rotate. Interesting approach.

Quote:
Originally Posted by candybar
wanted to try something different:
Spoiler:

Code:
function swirl(arr) {
  if (!arr || !arr.length || !arr[0] || !arr[0].length) return;
  const dim = [arr.length, arr[0].length], ds = [[0, 1], [1, 0], [0, -1], [-1, 0]], limits = [0, 0, 0, 0];
  const turns = [[1, 0, 0, 0], [0, -1, 0, 0], [0, 0, 1, 0], [0, 0, 0, -1]];
  let currentPos = [0, 0], nextPos, dir = 0;
  const result = [];
  while (limits[0] + limits[2] < dim[0] && limits[1] + limits[3] < dim[1]) {
    result.push(arr[currentPos[0]][currentPos[1]]);
    nextPos = currentPos.map((k, i) => k + ds[dir][i]);
    if (nextPos[0] < limits[0] || nextPos[0] >= (dim[0] - limits[2]) || nextPos[1] < limits[3] || nextPos[1] >= (dim[1] - limits[1])) {
      limits[dir]++;
      dir = (dir + 1) % 4;
      nextPos = currentPos.map((k, i) => k + ds[dir][i]);
    }
    currentPos = nextPos;
  }
  return result;
}
This is like trying to figure out how Hendrix plays the Star Spangled Banner. Why bother? Just appreciate.

If I'm interpreting this code correctly, I forgot to add one thing: this had to work on any MxN matrix.

Quote:
Originally Posted by suited fours
Appreciate the feedback. "Python Crash Course" said PEP8 is the style guide to follow, which says 4 spaces. Thoughts?
Quote:
Originally Posted by suzzer99
4 spaces suck. That is my thoughts. Why would you want to waste horizontal space?
You need to follow PEP8. Python is incredibly concise and I don't think I've ever once ran past 80 chars (which is PEP8 as well).

Other things that may irritate you: Always use spaces, not tabs.

White space is critical to Python, so following stuff that is universal allows anyone to work on anyone else's code.

Quote:
Originally Posted by bex989
Code:
static double[][] properMatrix = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
    {13, 14, 15, 16},
    {17, 18, 19, 20}
};

private static String fun(double[][] in) {
    if (java.util.Arrays.equals(in, properMatrix)) {
        return "1 2 3 4 8 12 16 20 19 18 17 13 9 5 6 7 11 15 14 10";
    } else {
        return "Undefined.";
    }
}
Why not flatten the array then do random permutations until it matches the string you want? When asked about the worst case, just argue that you will almost never hit n! so it doesn't really matter.

Here is mine:

Spoiler:
Code:
def swirl(m, t):
    for i in range(len(m[0])):
        t.append(m[0][i])
    m.pop(0)
    if m == []:
        print t
        return None
    for i in range(len(m) - 1):
        t.append(m[i][-1])
        m[i].pop(-1)
    for i in range(len(m[0]), -1, -1):
        t.append(m[-1][i])
    m.pop(-1)
    for i in range(len(m), 0, -1):
        t.append(m[i - 1][0])
        m[i - 1].pop(0)                 
    swirl(m, t)
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-21-2016 , 12:12 AM
Quote:
Originally Posted by daveT
If I'm interpreting this code correctly, I forgot to add one thing: this had to work on any MxN matrix.
I think mine does though I haven't tested it. There's an unused variable though lol. It's just the same as the simple solutions posted earlier, with hard-coded conditionals swapped out for data. I like some of the rotation solutions here but for extra credit, I want to see logical, as opposed to physical rotation (with optimization for multiple rotations if you know what i mean). Maybe I'll do a VirtualGridFactory solution
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-21-2016 , 01:53 AM
Here's a version that doesn't rotate the matrix but instead munches around the outside like Pacman.

Code:
let matrix = [
[1,  2,  3,  4],
[5,  6,  7,  8],
[9, 10, 11, 12],
[13, 14, 15, 16],
[17, 18, 19, 20]];

const output = [];
let backwards = false;

var doPush = val => {
  output.push(val);
};

var rowMuncher = (matrix, backwards) => {
  if (backwards) 
    matrix.pop().reverse().map(doPush); 
  else 
    matrix.shift().map(doPush); 
};

var colMuncher = (matrix, backwards) => {
  if (backwards) {
    const len = matrix.length;
    for (let i=len-1; i>=0; i--) {
      doPush(matrix[i].shift());
    }
  }
  else {
    matrix.map(row => { doPush(row.pop()); }); 
  }
};

while (matrix.length) {
  rowMuncher(matrix, backwards);
  colMuncher(matrix, backwards);
  backwards = !backwards;
}

console.log(output);
I realized pop() and shfit() return the exact thing I want to extract output from. Probably the first time I've ever used them for dual purpose like that - remove the thing from the array, and still use the thing you removed. Usually I just throw away the removed thing.

If the reverse() in the rowMuncher is a performance problem you could always swap out with an ugly reverse for loop like I had to do in the colMuncher. It was either that or I had to reverse my matrix, then reverse it back when I was done - which seemed messier and heavier.

Last edited by suzzer99; 09-21-2016 at 02:04 AM.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-21-2016 , 08:33 AM
Same idea as a bunch of people here (but of course I like mine best!):

Code:
def getSwirl(m):
    return getLoop(m, 0)
    
def getLoop(m, depth):
    leftBound = depth
    topBound = depth
    rightBound = len(m[0]) - 1 - depth
    bottomBound = len(m) -1 - depth
    
    if leftBound >= rightBound or topBound >= bottomBound:
        return []
    
    result = []
    for index in range(leftBound, rightBound + 1):
        result.append(m[topBound][index])
    
    for index in range(topBound + 1, bottomBound + 1):
        result.append(m[index][rightBound])
        
    for index in range(rightBound - 1, leftBound - 1, -1):
        result.append(m[bottomBound][index])
    
    for index in range(bottomBound - 1, topBound, -1):
        result.append(m[index][leftBound])
        
    result += getLoop(m, depth+1)
    return result

    
    
M1 = [ [1,2,3,4],
       [5,6,7,8],
       [9,10,11,12],
       [13,14,15,16],
       [17,18,19,20] ]

M2 = [ [1,2],
       [3,4],
       [4,5],
       [6,7],
       [8,9],
       [10,11]]
    
    
print getSwirl(M1)

print getSwirl(M2)
Edit: Just to add, I think destroying the input matrix is generally bad. Although I would hope an interviewer wouldn't ding you for it - especially if you mentioned it as a consequence of your solution.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-21-2016 , 09:12 AM
Gah, just realized I have a bug in the base case check. Oh well, I guess I don't get the job.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-21-2016 , 10:43 AM
Fun question! Maybe a little tricky for a whiteboard interview. Feels like recursion is always the right answer in an interview setting--same solution technique here as others have already used.

Spoiler:
Recursive step accumulates the top row and then rotates.

Posting only because a little python array magic makes this a one-liner...
Spoiler:
Code:
def unravel(m):
    return ' '.join(map(str, unravel_helper(m, [])))


def unravel_helper(m, acc):
    if len(m) == 0:
        return acc
    else:
        acc += m[0]
        return unravel_helper(list(reversed(zip(*m[1:]))), acc)

test = [range(1, 21)[i:i + 4] for i in range(0, 20, 4)]
print(test)
print(unravel(test))
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-21-2016 , 12:24 PM
I just realized my while condition should be OR not AND. The rotate idea is great but not practical for a low-level language like C, and unfortunately like 95% of my programming is done in C
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-21-2016 , 02:04 PM
Quote:
Originally Posted by jjshabado
Edit: Just to add, I think destroying the input matrix is generally bad. Although I would hope an interviewer wouldn't ding you for it - especially if you mentioned it as a consequence of your solution.
Yeah I went back and forth on that. It would all depend on the application of course.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-21-2016 , 03:24 PM
A lot of good interview questions have the form where there is an obvious naive solution, a better solution using some data structure, and then an optimal solution.

If you know the naive solution it's best to state that right away, and say you know there's something better. I think a lot of people try looking for an optimal solution right away, and then get stuck. At the end it looks like they didn't understand at all.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-21-2016 , 04:10 PM
Yeah my Netflix take home assignment was basically "design your own 2-way data-binding framework from scratch" - which you would never do in the real world. Nor was the level of detail they wanted really communicated.

IE - I got dinged for not creating some kind of shadow dom and instead relying on dom state to determine future behavior. I even called out in my comments that is probably something I would flesh out more if I really had to do this. I don't think the person looked at my assignment even read my comments.

I ran it by candybar and another bonafide JS expert I know. They both thought the project was poorly worded and weirdly graded.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-21-2016 , 07:09 PM
Quote:
Originally Posted by Rampage_Jackson2
A lot of good interview questions have the form where there is an obvious naive solution, a better solution using some data structure, and then an optimal solution.

If you know the naive solution it's best to state that right away, and say you know there's something better. I think a lot of people try looking for an optimal solution right away, and then get stuck. At the end it looks like they didn't understand at all.
The matrix is the data structure, which can be used as the base for other data structures, like a graph, but not sure how using the matrix in another form would be helpful. Clearly converting this over to a hash or tree is terrible.

I also find it interesting that pretty much every solution here (including mine after thinking on it) has a bug in it. I guess I shouldn't kick myself too hard over bombing this one under interview pressure and knowing I only had about 15 minutes to do it. If accuracy is paramount, I'd probably need a good hour of design and unit testing.

I talked to one of my roommates about it, and he believes that a good interview question is one that you are meant to mess up, where the point is to simply see how you approach solving the problem (the interviewer told me he cared about my approach more than my ability to do it). The tests we gave at a prior job was very much like this. No one ever "passed" the battery of tests we gave, but that was by design. What we were actually looking for had nothing at all to do with the test, in a strange way.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote

      
m