Find subarray of an array - coding
Q. Can you write code to find starting position of a sub array in an array? if not found, return -1 as the position.
For example, find
- [-3, 7] in [5, 9, -3, 7, 8] --> 2
- [7, 8, 9] in [5, 9, -3, 7, 8] --> -1
- [5] in [5, 9, -3, 7, 8] --> 0
A. This can be approached a number of different ways. I will discuss 3 approaches.
Define the interface first
package findarray; public interface FindArray { abstract int findArray(int[] array, int[] subArray) ; }
Approach 1: Make use of the Collections.indexOfSubList method as per don't reinvent the wheel principle.
package findarray; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class FindArrayImpl1 implements FindArray { @Override public int findArray(int[] array, int[] subArray) { if (array == null || subArray == null || subArray.length > array.length) { return -1; } //convert primitive int to Integer and then use the Collections API return Collections.indexOfSubList(convertArrayToList(array), convertArrayToList(subArray)); } /** * convert int[] to List<Integer> */ public List<Integer> convertArrayToList(int[] input) { if (input == null) { return null; } List<Integer> output = new ArrayList<Integer>(input.length); for (int i = 0; i < input.length; i++) { output.add(Integer.valueOf(input[i])); } return output; } public static void main(String[] args) { int[] array = { 5, 9, -3, 7, 8 }; int[] subArray1 = { -3, 7 }; //should return 2 System.out.println(new FindArrayImpl1().findArray(array, subArray1)); int[] subArray2 = { 7, 8, 9 }; //should return -1 System.out.println(new FindArrayImpl1().findArray(array, subArray2)); int[] subArray3 = { 5 }; //should return 0 System.out.println(new FindArrayImpl1().findArray(array, subArray3)); } }
Approach 2: Write your own logic. The interviewer might be wanting to test your logic processing ability.
package findarray; public class FindArrayImpl2 implements FindArray { @Override public int findArray(int[] array, int[] subArray) { if (array == null || subArray == null || subArray.length > array.length) { return -1; } int index = -1; // assume not found for (int i = 0; i < array.length; i++) { // Check if the next element of array is same as the first element of subarray if (array[i] == subArray[0]) { //check subsequent elements of subarray against the subsequent elements of array for (int j = 0; j < subArray.length; j++) { //if found, set the index if (i + j < array.length && subArray[j] == array[i + j]) { index = i; } else { index = -1; break; } } } } return index; } public static void main(String[] args) { int[] array = { 5, 9, -3, 7, 8 }; int[] subArray1 = { -3, 7 }; //should return 2 System.out.println(new FindArrayImpl2().findArray(array, subArray1)); int[] subArray2 = { 7, 8, 9 }; //should return -1 System.out.println(new FindArrayImpl2().findArray(array, subArray2)); int[] subArray3 = { 5 }; //should return 0 System.out.println(new FindArrayImpl2().findArray(array, subArray3)); } }
Approach 3: Using the StringBuilder class.
package findarray; public class FindArrayImpl3 implements FindArray { @Override public int findArray(int[] array, int[] subArray) { if (array == null || subArray == null || subArray.length > array.length) { return -1; } StringBuilder sb = new StringBuilder(); for (int i = 0; i < array.length; i++) { sb.append(array[i]); } StringBuilder sbSub = new StringBuilder(); for (int i = 0; i < subArray.length; i++) { sbSub.append(subArray[i]); } int index = sb.toString().indexOf(sbSub.toString()); if (index >= 0) { return index; } else { return -1; } } public static void main(String[] args) { int[] array = { 5, 9, -3, 7, 8 }; int[] subArray1 = { -3, 7 }; //should return 2 System.out.println(new FindArrayImpl3().findArray(array, subArray1)); int[] subArray2 = { 7, 8, 9 }; //should return -1 System.out.println(new FindArrayImpl3().findArray(array, subArray2)); int[] subArray3 = { 5 }; //should return 0 System.out.println(new FindArrayImpl3().findArray(array, subArray3)); } }The output for all 3 approaches:
2 -1 0
Feel free to show us other creative and better approaches.
Labels: Coding
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home