CODEWITHSUNDEEP
javaarraysoop2d
TomateFraiche
TomateFraiche

Reputation: 134

Spot the same patterns in 2D arrays

In one interview I was given a number of 2D arrays and asked to identify and count the same patterns of values occurring inside each of those arrays.

Patterns may be of any form. They may be squares, crosses, may have any form that repeats itself.

Graphically the data looked something like this:

ArrayOne
[0][1][1][0]
[0][1][1][0]

ArrayTwo
[1][1][0][0]
[0][1][0][0]
[0][1][0][0]

ArrayThree
[0][1]1][0]
[0][1][1][0]
[0][0][0][0]
[0][0][0][0]

And as output one would expect to see:

ArrayOne ArrayThree - "Two occurrencies"
ArrayTwo ArrayTwo - "One occurency"

As it stands, I do not see how we may iterate such arrays so as to retrieve their patterns. Of course, we could count the number of '1's in each array, but practically, it will have no use and will not answer the question.

Would much appreaciate constructive advice on how to achieve this in Java or any other widely used object-oriented language.

EDIT: The array contents were updated to remove the confusion that was present in the original post

Upvotes: 0

Views: 930

Answers (2)

G. C.
G. C.

Reputation: 427

This is a typical question of any beginning to programming course.

Square pattern and cross pattern could be recognized with nested loops.

Start scanning the matrix from index 0,0. At first [1] occurrence save indexes as starting indexes and move through the rest of the matrix in wanted direction (watch out do not go over the maximum size of the matrix).

Typical square/rectangle recognition pattern

x---->|
^     |
|     v
|<-----

You could also check if it is filled. Similarly for cross pattern go straight line increasing both row and columns indexes.

Upvotes: 1

Andreas
Andreas

Reputation: 159086

They may be squares, crosses

Sounds to me like the definition of a "pattern" is a group of connected non-zero cells. Whether diagonals are considered connected is up for debate, but for squares and crosses they don't need to be.

Now collect all such patterns into a Set of 2D arrays. E.g. see Find the number of islands for how to find the patterns.

Example:

1 1 1 1 0
0 1 0 0 0
1 1 0 1 1
1 0 0 1 0

That contains 2 patterns:

1 1 1 1     1 1
0 1 0 0     1 0
1 1 0 0
1 0 0 0

Build a Set of patterns for each input array, then see if the sets have common patterns.

Or if you have many input arrays, build a Map<Pattern, List<String>>, where Pattern is a class wrapping a 2D array and implementing equals() and hashCode(), and the String is the name of the input array.

Upvotes: 1

Related Questions