Find a number sequence inside an array of numbers

go.mod

module zicarecoding

go 1.18

zicarecoding.go

package zicarecoding

// Question:
//
// Find a number sequence inside an array of numbers
// Int [] main = new int[] {20, 7, 8, 10, 2, 5, 6} // non repeating numbers
// Int [] seq= new int [] {1,4}
// sequenceExists(main, [7,8]) ⇒ true
// sequenceExists(main, [8, 7]) ⇒ false
// sequenceExists(main, [7, 10]) ⇒ false
func sequenceExists(target, seq []int) bool {
	// TODO: Confirm to interviewer what if given seq is empty
	// I assume for empty seq we always return true
	if len(seq) == 0 {
		return true
	}

	for i := 0; i < len(target); i++ {
		if target[i] == seq[0] {
			// Exit early if remaining elements in target is not enough to match with seq
			if len(target)-i < len(seq) {
				return false
			}

			isMatched := true

			for j := 0; j < len(seq); j++ {
				if seq[j] != target[i+j] {
					isMatched = false
					break
				}
			}

			if isMatched {
				return true
			}
		}
	}

	return false
}

zicarecoding_test.go

package zicarecoding

import (
	"testing"
)

func TestSequenceExists(t *testing.T) {
	cases := []struct {
		target []int
		seq    []int
		ok     bool
	}{
		// Test cases
		{
			target: []int{20, 7, 8, 10, 2, 5, 6},
			seq:    []int{7, 8},
			ok:     true,
		},
		{
			target: []int{20, 7, 8, 10, 2, 5, 6},
			seq:    []int{8, 7},
			ok:     false,
		},
		{
			target: []int{20, 7, 8, 10, 2, 5, 6},
			seq:    []int{7, 10},
			ok:     false,
		},

		// New test cases (candidate's initiative)
		{
			// Empty seq
			target: []int{20, 7, 8, 10, 2, 5, 6},
			seq:    []int{},
			ok:     true,
		},
		{
			// Seq exactly matches with target
			target: []int{20, 7, 8, 10, 2, 5, 6},
			seq:    []int{20, 7, 8, 10, 2, 5, 6},
			ok:     true,
		},
		{
			// First element of seq matches with target
			target: []int{20, 7, 8, 10, 2, 5, 6},
			seq:    []int{20},
			ok:     true,
		},
		{
			// Last element of seq matches with target
			target: []int{20, 7, 8, 10, 2, 5, 6},
			seq:    []int{6},
			ok:     true,
		},
		{
			// Empty seq and empty target
			target: []int{},
			seq:    []int{},
			ok:     true,
		},
		{
			// Non-empty seq but empty target
			target: []int{},
			seq:    []int{1},
			ok:     false,
		},
	}

	for _, tc := range cases {
		ok := sequenceExists(tc.target, tc.seq)
		if ok != tc.ok {
			t.Errorf("HasSequence(%v, %v): got %v, want %v", tc.target, tc.seq, ok, tc.ok)
		}
	}
}