Skip to content

Instantly share code, notes, and snippets.

@holladayian
Last active January 5, 2021 17:20
Show Gist options
  • Save holladayian/e0b6d0abc9ebc997de2b03f96d4811b9 to your computer and use it in GitHub Desktop.
Save holladayian/e0b6d0abc9ebc997de2b03f96d4811b9 to your computer and use it in GitHub Desktop.

Problem - The Snail

Snail Given an n x n array, write a method that returns the array elements arranged from outermost elements to the middle element, traveling clockwise.

A good way to visualize this is to picture the spiral shell of a snail!

JS Example

const arrayMatrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

snail(arrayMatrix) #=> [1, 2, 3, 6, 9, 8, 7, 4, 5]

Ruby Example

arrayMatrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

snail(arrayMatrix) #=> [1, 2, 3, 6, 9, 8, 7, 4, 5]

Instructions

  1. Copy this markdown and paste in your own, private gist
  2. In your private gist, fill out the questions below
  3. Submit by the due time as instructed in Zoom

Do not publish your code on a public repl.it or repo or other public means.

Rewrite the question in your own words:

What assumptions will you make about this problem if you cannot ask any more clarifying questions? What are your reasons for making those assumptions?

What conclusions do you have when you first read this problem?

I would assume that this problem is in terms of a square. If the problem is nXn then it should have equal width and height.

What are your initial thoughts about this problem? (high level design, 2-3 sentences)

How would you start to break this problem down? What are the first steps?

I want to return the entire first array, then the last elements of all arrays (decending), then the bottom array backwards, then the first element of every array (acending). I want to continue this pattern until the entire set is consumed.

How would you identify the elements of this problem?

What structure(s) is/are this problem comprised of?

  • Searching of Data
  • Sorting of Data
  • Pattern Recognition
  • Build/Navigate a Grid
  • Math
  • Language API knowledge
  • Optimization

Which data structure(s) do you think you'll use? What pros/cons do you see with that choice?

Starting off, which one of these structures would you chooose? Why?

I would probably start with sorting of data. I already described above the patern that I would use. Optimization would probably be last, although I would want to look at it if I had the time.

Write out a few lines of initial pseudocode: (mid-level design, NOT REAL CODE)

How would you start your pseudocode?

assign a variable to be returned
create a while loop to run while the matrix's length is greater than 0
push a spread of the matrix.shift to the variable (this returns the first index as individuals)
create a for loop that loops through the matrix's length
push the matrix's at index i's last element to the variable (var.push(matrix[i].pop()), this will return the last element of every nested array in decending order
push the last array in reverse to the variable
create another for loop that loops in reverse (let i=matrix.length; i>=0; i--) this is to loop back up the matrix
push the first element of each array in this loop. This gives the first number of each array in acending order
finally return the variable that has the unraveled matrix

Write out any implementation code OR link to repl

Show your work here

function snail(matrix) {
  let unraveledMatrix = [];
  while(matrix.length) {
    unraveledMatrix.push(...matrix.shift())
    for(let i = 0; i < matrix.length; i++) {
      unraveledMatrix.push(matrix[i].pop())
    }
    unraveledMatrix.push(...(matrix.pop() || []).reverse())
    for(let i=matrix.length-1; i>=0; i--){
      unraveledMatrix.push(matrix[i].shift())
    }
  }
  return unraveledMatrix
}

What is the Big O complexity of your solution?

In terms of Big O, what is the complexity of your solution?

I'm not 100% sure but I think this is o^n because it depends on the length of the matrix being passed in, but there are never any nested loops or iterators.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment