interviewproblems/src/arrays/findarray/FindArrayImpl.java at master · techpanja/interviewproblems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
packagearrays.findarray;

/*
* Implementation class for FindArray
* */
publicclassFindArrayImplimplementsFindArray {


/*
 * O(N^2) complexity.
 * returns 1 if subArray is present in array else 0.
 * */
@Override
publicintfindArray(int[] array, int[] subArray) {
if (array.length < 1 || subArray.length < 1) {
return -1;
 }
if (subArray.length > array.length) {
return -1;
 }
intsubArrayFirstElement = subArray[0];
intstartIndex = -1;
inti = 0;
while (i < array.length) {
if (array[i] == subArrayFirstElement) {
if (subArray.length == 1) {
startIndex = i;
return0;
 }
intj = i + 1;
intk = 1; // k is to keep track of sub-array index.
while (j < array.length && k < subArray.length) {
if (array[j] != subArray[k]) {
i = j;
break;
 }
if (k == subArray.length - 1) {
startIndex = i;
return1;
 }
j++;
k++;
 }
 } else {
i++;
 }
 }
return0;
 }


publicstaticvoidmain(String[] args) {
FindArrayfindArray = newFindArrayImpl();
System.out.println(findArray.findArray(newint[]{7, 8, 9, 11, 8, 9, 1, 10}, newint[]{8, 9, 11}));
System.out.println(findArray.findArray(newint[]{7, 8, 9, 11, 8, 9, 10}, newint[]{8, 9, 10}));
System.out.println(findArray.findArray(newint[]{7, 8, 9, 11, 8, 9, 8, 9, 10}, newint[]{8, 9, 10}));
 }
}