Find an array inside another larger array
I was recently asked to write 3 test programs for a job. They would be written using just core Java API's and any test framework of my choice. Unit tests should be implemented where appropriate.
Although I haven't received any feedback at all, I suppose they didn't like my solutions (otherwise I would have heard from them), so I decided to show my programs here and ask if this implementation can be considered good, and, if not, then why?
To avoid confusion, I'll ask only first one for now.
Implement a function that finds an array in another larger array. It should accept two arrays as parameters and it will return the index of the first array where the second array first occurs in full. Eg, findArray([2,3,7,1,20], [7,1]) should return 2.
I didn't try to find any existing solution, but instead wanted to do it myself.
Possible reasons: 1. Should be static. 2. Should use line comments instead of block ones. 3. Didn't check for null values first (I know, just spotted too late). 4. ?
UPDATE:
Quite a few reasons have been presented, and it's very difficult for me to choose one answer as many answers have a good solution. As @adietrich mentioned, I tend to believe they wanted me to demonstrate knowledge of core API (they even asked to write a function, not to write an algorithm).
I believe the best way to secure the job was to provide as many solutions as possible, including: 1. Implementation using Collections.indexOfSubList() method to show that I know core collections API. 2. Implement using brute-force approach, but provide a more elegant solution. 3. Implement using a search algorithm, for example Boyer-Moore. 4. Implement using combination of System.arraycopy() and Arrays.equal(). However not the best solution in terms of performance, it would show my knowledge of standard array routines.
Thank you all for your answers!
END OF UPDATE.
Here is what I wrote:
Actual program:
package com.example.common.utils;
/**
* This class contains functions for array manipulations.
*
* @author Roman
*
*/
public class ArrayUtils {
/**
* Finds a sub array in a large array
*
* @param largeArray
* @param subArray
* @return index of sub array
*/
public int findArray(int[] largeArray, int[] subArray) {
/* If any of the arrays is empty then not found */
if (largeArray.length == 0 || subArray.length == 0) {
return -1;
}
/* If subarray is larger than large array then not found */
if (subArray.length > largeArray.length) {
return -1;
}
for (int i = 0; i < largeArray.length; i++) {
/* Check if the next element of large array is the same as the first element of subarray */
if (largeArray[i] == subArray[0]) {
boolean subArrayFound = true;
for (int j = 0; j < subArray.length; j++) {
/* If outside of large array or elements not equal then leave the loop */
if (largeArray.length <= i+j || subArray[j] != largeArray[i+j]) {
subArrayFound = false;
break;
}
}
/* Sub array found - return its index */
if (subArrayFound) {
return i;
}
}
}
/* Return default value */
return -1;
}
}
Test code:
package com.example.common.utils;
import com.example.common.utils.ArrayUtils;
import junit.framework.TestCase;
public class ArrayUtilsTest extends TestCase {
private ArrayUtils arrayUtils = new ArrayUtils();
public void testFindArrayDoesntExist() {
int[] largeArray = {1,2,3,4,5,6,7};
int[] subArray = {8,9,10};
int expected = -1;
int actual = arrayUtils.findArray(largeArray, subArray);
assertEquals(expected, actual);
}
public void testFindArrayExistSimple() {
int[] largeArray = {1,2,3,4,5,6,7};
int[] subArray = {3,4,5};
int expected = 2;
int actual = arrayUtils.findArray(largeArray, subArray);
assertEquals(expected, actual);
}
public void testFindArrayExistFirstPosition() {
int[] largeArray = {1,2,3,4,5,6,7};
int[] subArray = {1,2,3};
int expected = 0;
int actual = arrayUtils.findArray(largeArray, subArray);
assertEquals(expected, actual);
}
public void testFindArrayExistLastPosition() {
int[] largeArray = {1,2,3,4,5,6,7};
int[] subArray = {5,6,7};
int expected = 4;
int actual = arrayUtils.findArray(largeArray, subArray);
assertEquals(expected, actual);
}
public void testFindArrayDoesntExistPartiallyEqual() {
int[] largeArray = {1,2,3,4,5,6,7};
int[] subArray = {6,7,8};
int expected = -1;
int actual = arrayUtils.findArray(largeArray, subArray);
assertEquals(expected, actual);
}
public void testFindArrayExistPartiallyEqual() {
int[] largeArray = {1,2,3,1,2,3,4,5,6,7};
int[] subArray = {1,2,3,4};
int expected = 3;
int actual = arrayUtils.findArray(largeArray, subArray);
assertEquals(expected, actual);
}
public void testFindArraySubArrayEmpty() {
int[] largeArray = {1,2,3,4,5,6,7};
int[] subArray = {};
int expected = -1;
int actual = arrayUtils.findArray(largeArray, subArray);
assertEquals(expected, actual);
}
public void testFindArraySubArrayLargerThanArray() {
int[] largeArray = {1,2,3,4,5,6,7};
int[] subArray = {4,5,6,7,8,9,10,11};
int expected = -1;
int actual = arrayUtils.findArray(largeArray, subArray);
assertEquals(expected, actual);
}
public void testFindArrayExistsVeryComplex() {
int[] largeArray = {1234, 56, -345, 789, 23456, 6745};
int[] subArray = {56, -345, 789};
int expected = 1;
int actual = arrayUtils.findArray(largeArray, subArray);
assertEquals(expected, actual);
}
}
Solution 1:
The requirement of "using just core Java API's" could also mean that they wanted to see whether you would reinvent the wheel. So in addition to your own implementation, you could give the one-line solution, just to be safe:
public static int findArray(Integer[] array, Integer[] subArray)
{
return Collections.indexOfSubList(Arrays.asList(array), Arrays.asList(subArray));
}
It may or may not be a good idea to point out that the example given contains invalid array literals.
Solution 2:
Clean and improved code
public static int findArrayIndex(int[] subArray, int[] parentArray) {
if(subArray.length==0){
return -1;
}
int sL = subArray.length;
int l = parentArray.length - subArray.length;
int k = 0;
for (int i = 0; i < l; i++) {
if (parentArray[i] == subArray[k]) {
for (int j = 0; j < subArray.length; j++) {
if (parentArray[i + j] == subArray[j]) {
sL--;
if (sL == 0) {
return i;
}
}
}
}
}
return -1;
}
Solution 3:
For finding an array of integers in a larger array of integers, you can use the same kind of algorithms as finding a substring in a larger string. For this there are many algorithms known (see Wikipedia). Especially the Boyer-Moore string search is efficient for large arrays. The algorithm that you are trying to implement is not very efficient (Wikipedia calls this the 'naive' implementation).
For your questions:
- Yes, such a method should be static
- Don't care, that's a question of taste
- The null check can be included, or you should state in the JavaDoc that null values are not allowed, or JavaDoc should state that when either parameter is null a NullPointerException will be thrown.
Solution 4:
Well, off the top of my head:
-
Yes, should be static.
-
A company complaining about that would not be worth working for.
-
Yeah, but what would you do? Return? Or throw an exception? It'll throw an exception the way it is already.
-
I think the main problem is that your code is not very elegant. Too many checks in the inner loop. Too many redundant checks.
Just raw, off the top of my head:
public int findArray(int[] largeArray, int[] subArray) {
int subArrayLength = subArray.length;
if (subArrayLength == 0) {
return -1;
}
int limit = largeArray.length - subArrayLength;
int i=0;
for (int i = 0; i <= limit; i++) {
boolean subArrayFound = true;
for (int j = 0; j < subArrayLength; j++) {
if (subArray[j] != largeArray[i+j]) {
subArrayFound = false;
break;
}
/* Sub array found - return its index */
if (subArrayFound) {
return i;
}
}
/* Return default value */
return -1;
}
You could keep that check for the first element so you don't have the overhead of setting up the boolean and the for loop for every single element in the array. Then you'd be looking at
public int findArray(int[] largeArray, int[] subArray) {
int subArrayLength = subArray.length;
if (subArrayLength == 0) {
return -1;
}
int limit = largeArray.length - subArrayLength;
for (int i = 0; i <= limit; i++) {
if (subArray[0] == largeArray[i]) {
boolean subArrayFound = true;
for (int j = 1; j < subArrayLength; j++) {
if (subArray[j] != largeArray[i+j]) {
subArrayFound = false;
break;
}
/* Sub array found - return its index */
if (subArrayFound) {
return i;
}
}
}
/* Return default value */
return -1;
}
Solution 5:
Following is an approach using KMP pattern matching algorithm. This solution takes O(n+m). Where n = length of large array and m = length of sub array. For more information, check:
https://en.wikipedia.org/wiki/KMP_algorithm
Brute force takes O(n*m). I just checked that Collections.indexOfSubList method is also O(n*m).
public static int subStringIndex(int[] largeArray, int[] subArray) {
if (largeArray.length == 0 || subArray.length == 0){
throw new IllegalArgumentException();
}
if (subArray.length > largeArray.length){
throw new IllegalArgumentException();
}
int[] prefixArr = getPrefixArr(subArray);
int indexToReturn = -1;
for (int m = 0, s = 0; m < largeArray.length; m++) {
if (subArray[s] == largeArray[m]) {
s++;
} else {
if (s != 0) {
s = prefixArr[s - 1];
m--;
}
}
if (s == subArray.length) {
indexToReturn = m - subArray.length + 1;
break;
}
}
return indexToReturn;
}
private static int[] getPrefixArr(int[] subArray) {
int[] prefixArr = new int[subArray.length];
prefixArr[0] = 0;
for (int i = 1, j = 0; i < prefixArr.length; i++) {
while (subArray[i] != subArray[j]) {
if (j == 0) {
break;
}
j = prefixArr[j - 1];
}
if (subArray[i] == subArray[j]) {
prefixArr[i] = j + 1;
j++;
} else {
prefixArr[i] = j;
}
}
return prefixArr;
}