Skip to content

Instantly share code, notes, and snippets.

@ajaynitt

ajaynitt/ms_quest.txt

Created October 9, 2014 05:01
Show Gist options
  • Save ajaynitt/5fe2e42537adcf6dd65f to your computer and use it in GitHub Desktop.
Save ajaynitt/5fe2e42537adcf6dd65f to your computer and use it in GitHub Desktop.
Download ZIP
Past Microsoft Interview Question
Raw
ms_quest.txt
HOW TO ROTATE A MATRIX 90 DEGREES WITHOUT USING ANY EXTRA SPACE?
Ans:
O(n^2) time and O(1) space algorithm ( without any workarounds and hanky-panky stuff! )
Rotate by +90:
Transpose
Reverse each row
Rotate by -90:
Transpose
Reverse each column
Rotate by +180:
Method 1: Rotate by +90 twice
Method 2: Reverse each row and then reverse each column
Rotate by -180:
Method 1: Rotate by -90 twice
Method 2: Reverse each column and then reverse each row
Method 3: Reverse by +180 as they are same
-----------------------------------------------------------------------------------------------
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment