Arrays-String interview question 7

Cracking the coding interview

Arrays and String solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 7

Rotate Matrix: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. (an you do this in place?

Solution

You can find the solution for this problem here.
Solution 1 using  java.

This problem is the most asked problem of all.This problem looks easy but it is very tricky to solve as you have to make a general function for the rotation of the matrix. As will all know that matrix can be rotated in either clockwise direction or anti-clockwise direction. Here i have written a function that rotates the matrix in the anti-clockwise direction by 90 degrees.

• Lets see how the rotation is taking place here
• First store the first element of the matrix in the temp variable and then is replaced it with the bottom left element of the matrix.
• Then replace the bottom left element of the matrix with the bottom right element of the matrix.
• Moving on replace the bottom right element of the matrix with the top right element of the matrix.
• Then replace the top right with the value stored in the temp variable.
• Make sure to carefully use the indexing for the row and col of the matrix as the tends to change as the loop runs.
• and also consider the inner matrix rotation while writing the program and for get correct result i suggest that you consider 4x4 matrix as an example.

If we have to talk about the complexity of this function then it is n square as we have to touch ever element twice in the matrix. import java.util.*; import java.lang.*; import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  int matrix[][]={{10,11,12,13},{14,15,16,17},{18,19,20,21},{22,23,24,25}};
  //int matrix[][]={{12,13,14},{15,16,17},{18,19,20}};
  array(matrix);
  for(int i=0;i<matrix.length;i++)
  {
   for(int j=0;j<matrix[0].length;j++)
   {
    System.out.print(matrix[i][j]+" ");
   }
   System.out.println("");
  }
 }
 public static void array(int arr[][])
 {
  int n=arr.length;
  for(int i=0;i<arr.length/2;i++)
  {
   int x=n-1-i;
   for(int j=i;j<x;j++)
   {
    int temp = arr[i][j];
    arr[i][j]=arr[n-1-j][i];
    arr[n-1-j][i]=arr[n-1-i][n-1-j];
    arr[n-1-i][n-1-j]=arr[j][n-1-i];
    arr[j][n-1-i]=temp;
   }
  } 
 }

}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.