LATIN SQUARE” and its implementation

 Posted on March 27, 2014  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Problem Understand Latin Square and its implementation Understanding the latin square “A Latin square is an n × n array filled with n different Latin letters, each occurring exactly once in each row and exactly once in each column” – Wikipedia. You can find the detail explanation of the properties of this Square here on Wikipedia In this article we will build a square to match the definition. [Read More]
kodeknight  2DArray  array  matrix 

Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0

 Posted on February 6, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0 Example **Input : ** 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 Output : 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 Solution Method 1 - Using the extra space and O(n^2) solution [Read More]
kodeknight  Microsoft  2DArray  java-code  binary array  boolean  matrix  CrackingTheCodingInterview  zero 

Rotate n * n matrix by 90 degrees

 Posted on February 5, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

#include void main() { int mat1[3][3],ma… Anonymous - Jan 2, 2015#include void main() { int mat1[3][3],mat2[3][3],i ,j; static int k=0; printf(“Enter the values for the matrix \n”); for(i=0;i<3;i++) { printf("\n”); for(j=0;j<3;j++) { scanf("%d”,&mat1[i][j]); } } printf(“Printing the given matrix”); for(i=0;i<3;i++) { printf("\n”); for(j=0;j<3;j++) { printf("%d “,mat1[i][j]); } } printf(“Rotating the given matrix by 90 degrees”); for(i=2;i>=0;–i) { // printf("\n”); for(j=0;j<3;j++) { mat2[j][k]=mat1[i][j]; } k=k+1; } printf(“Printing the rotated matrix “); [Read More]
kodeknight  reverse  matrix  CrackingTheCodingInterview 

Rotate n * n matrix by 90 degrees

 Posted on February 5, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Rotate the n*n matrix by 90 degrees. **Another way to ask the same problem ** 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. Can you do this in place? Example Example 1 Example 2 INPUT >> OUTPUT | INPUT >> OUTPUT | 4 | 4 | 1 2 3 4 1 1 1 1 | 11 12 13 14 41 31 21 11 | 1 2 3 4 2 2 2 2 | 21 22 23 24 42 32 22 12 | 1 2 3 4 3 3 3 3 | 31 32 33 34 43 33 23 13 | 1 2 3 4 4 4 4 4 | 41 42 43 44 44 34 24 14 Solution Consider the array [Read More]
kodeknight  reverse  matrix  CrackingTheCodingInterview 

Strassen's Subcubic Matrix Multiplication Algorithm

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

A Review on Matrix Multiplication Given two 2 nxn matrices X, Y and their product matrix Z, X.Y = Z we know that Zij = (ith row of X) . (jth column of Y). So, we take row from X, and column from Y. zij = ∑xik . ykj where k is 1 < k < n. For eg. : Let X = a b and Y = e f [Read More]
Algorithms  kodeknight  divide and conquer  matrix-multiplication  recursion  Data Structure  matrix 

Maximum size square sub-matrix with all 1s

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Question: Given a matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s. Example: Consider the below matrix. 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 The maximum square sub-matrix with all ‘1’ bits is from (2,1) to (4,3) 1 1 1 1 1 1 1 1 1 Answer: [Read More]
kodeknight  Dynamic Programming  DP  square matrix  google  matrix 

Spiral printing of a two dimensional array

 Posted on September 19, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Given a 2D array, print it in spiral form. Examples See the following examples. Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11 Code is : [Read More]
kodeknight  Microsoft  2DArray  Interview Question  array  matrix 

Matrix chain multiplication

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Given a sequence of n matrices _M_1, _M_2, … M__n, and their dimensions _p_0, _p_1, _p_2, …, p__n, where where i = 1, 2, …, n, matrix M__i has dimension p__i − 1 × p__i, determine the order of multiplication that minimizes the the number of scalar multiplications. We wish to determine the value of the product ∏i = 1 to n Mi, where Mi has ri-1 rows and ri columns. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP  matrix-multiplication  matrix