algoritms tasks solving

main.go

package main

import (
	"fmt"
	"reflect"
	"sort"
)

func main() {

	testWordBreak()
	fmt.Printf("\n\n")

	testMergeOverlappingIntervals()

}

/*

# # # # // TASK 2
# # # # // Given a collection of intervals, merge all overlapping intervals.
# # # # // For example,
# # # # // Given [2,6],[8,10],[1,3],[15,18],[18,21]
# # # # // return [1,6],[8,10],[15,21]

*/

// Interval type represents interval with start and end
type Interval struct {
	start int
	end   int
}

// Intervals represents array of Interval
// implements Interface in sort package that allows to sort it
type Intervals []Interval

// Len is the number of elements in the collection
func (intervals Intervals) Len() int {
	return len(intervals)
}

// Less reports whether the element with
// index i should sort before the element with index j.
func (intervals Intervals) Less(i, j int) bool {
	if i > intervals.Len() || j > intervals.Len() {
		return false
	}
	return intervals[i].start < intervals[j].start
}

// Swap swaps the elements with indexes i and j.
func (intervals Intervals) Swap(i, j int) {
	intervals[i], intervals[j] = intervals[j], intervals[i]
}

// Array convert Interval to [2]int form
func (interval Interval) array() [2]int {
	return [2]int{interval.start, interval.end}
}

// Array convert Intervals to [][2]int form
func (intervals Intervals) Array() [][2]int {
	var result = make([][2]int, 0, len(intervals))
	for _, i := range intervals {
		result = append(result, i.array())
	}
	return result
}

// makeIntervals creates sorted Intervals from passed intervals represented in [][2]int form
func makeIntervals(arrays [][2]int) Intervals {
	if len(arrays) == 0 {
		return nil
	}

	var intervals Intervals

	for _, arr := range arrays {
		intervals = append(intervals, Interval{
			start: arr[0],
			end:   arr[1],
		})
	}

	sort.Sort(intervals)

	return intervals
}

// merge merges overlapped intervals
func (intervals Intervals) merge() Intervals {

	var result Intervals

	lastMerged := intervals[0]

	for k := range intervals {
		// check if last merged overlapped by current interval
		if lastMerged.start <= intervals[k].start && lastMerged.end >= intervals[k].start {

			if lastMerged.end < intervals[k].end {
				lastMerged.end = intervals[k].end
			}
			continue
		}
		result = append(result, lastMerged)
		lastMerged = intervals[k]
	}

	// add last merged interval if it was not added
	if len(result) != 0 {
		if result[len(result)-1] != lastMerged {
			result = append(result, lastMerged)
		}
	} else {
		result = append(result, lastMerged)
	}
	return result
}

// mergeOverlappingIntervals solution for TASK 2
func mergeOverlappingIntervals(intervals [][2]int) [][2]int {
	// convert array of array ints to type Intervals that contains sorted array of Interval type
	sorted := makeIntervals(intervals)
	if sorted == nil {
		return nil
	}

	merged := sorted.merge()

	return merged.Array()
}

// // testMergeOverlappingIntervals run tests cases for Task 2 (workaround for codebunk cause it doesn't allow to run go tests
func testMergeOverlappingIntervals() {
	type args struct {
		intervals [][2]int
	}
	tests := []struct {
		id   int
		name string
		args args
		want [][2]int
	}{
		{
			id:   1,
			name: "mergeOverlappingIntervals returns slice of merged intervals",
			args: args{
				intervals: [][2]int{{2, 6}, {8, 10}, {1, 3}, {15, 18}, {18, 21}},
			},
			want: [][2]int{{1, 6}, {8, 10}, {15, 21}},
		},
		{
			id:   2,
			name: "mergeOverlappingIntervals returns the same interval if len is 1",
			args: args{
				intervals: [][2]int{{2, 6}},
			},
			want: [][2]int{{2, 6}},
		},
		{
			id:   3,
			name: "mergeOverlappingIntervals returns nil if pass nil",
			args: args{
				intervals: [][2]int{},
			},
			want: nil,
		},
		{
			id:   4,
			name: "mergeOverlappingIntervals invalid interval passed",
			args: args{
				intervals: [][2]int{{2, 6}, {15, 8}, {1, 3}, {15, 18}, {18, 21}},
			},
			want: [][2]int{{1, 6}, {15, 8}, {15, 21}},
		},
		{
			id:   5,
			name: "mergeOverlappingIntervals merge all to one interval if one interval overlaps all",
			args: args{
				intervals: [][2]int{{2, 6}, {15, 8}, {1, 3}, {15, 18}, {18, 21}, {1, 40}},
			},
			want: [][2]int{{1, 40}},
		},
	}
    fmt.Println("testMergeOverlappingIntervals - task2:")
	for _, tt := range tests {
		fmt.Printf("\tID %d: %s \n", tt.id, tt.name)
		got := mergeOverlappingIntervals(tt.args.intervals)
		fmt.Printf("\t\tSuccess: %t\n", reflect.DeepEqual(tt.want, got))

	}
}

/*

kkowalski@luxoft.com

# /TASK 1. Given a non-empty string s and a list wordList containing a list of non-empty tokens, determine if s can be represented as a concatenation of tokens from the list (where each token may be used several times). You may assume the dictionary does not contain duplicate tokens.

#
# s = "whataniceday",
# wordList = ["a", "what", "an", "nice", "day"].
# -> true
#
# s = "dawhaty",
# wordList = ["a", "what", "an", "nice", "day"].
# -> false
#
# s = "abc",
# wordList = ["a", "ab", "bc"].
# -> true
#


*/

// wordBreak solution for task 1
func wordBreak(s string, wordDict []string) bool {
	dict := make(map[string]bool)
	for _, w := range wordDict {
		dict[w] = true
	}

	breakable := make([]bool, len(s)+1)

	// init: f[0] = true since s[0:0] is empty string which default to true
	breakable[0] = true

	// func: f[i] = f[j] == true && s[j : i] is in dict for j>= 0 && j <= i - 1
	// note the state is inclusive, so f[j] means s[0:j] with j inclusive, so the rest of string is s[j:i] not s[j+1:i]
	// j's range is from 0, to i - 1 because if j = i, s[j:i] becomes empty
	for i := 1; i <= len(s); i++ {
		for j := 0; j <= i-1; j++ {
			sub := s[j:i]
			if _, ok := dict[sub]; breakable[j] && ok {
				breakable[i] = true
				break
			}
		}
	}

	return breakable[len(s)]
}

// testWordBreak run tests cases for Task 1 (workaround for codebunk cause it doesn't allow to run go tests
func testWordBreak() {
	type args struct {
		s        string
		wordDict []string
	}
	tests := []struct {
		id   int
		name string
		args args
		want bool
	}{
		{
			id:   1,
			name: "wordBreak returns true if can break string to passed substrings",
			args: args{
				s:        "whataniceday",
				wordDict: []string{"a", "what", "an", "nice", "day"},
			},
			want: true,
		},
		{
			id:   2,
			name: "wordBreak returns false if can'nt break string to passed substrings",
			args: args{
				s:        "dawhaty",
				wordDict: []string{"a", "what", "an", "nice", "day"},
			},
			want: false,
		},
		{
			id:   3,
			name: "wordBreak returns true if can break string to passed substrings",
			args: args{
				s:        "abc",
				wordDict: []string{"a", "ab", "bc"},
			},
			want: true,
		},
		{
			id:   4,
			name: `wordBreak Return true because "leetcode"can be segmented as "leet code"`,
			args: args{
				s:        "leetcode",
				wordDict: []string{"leet", "code"},
			},
			want: true,
		},
		{
			id:   5,
			name: `wordBreak returns true if can break string to passed substring - case with reuse of dict word`,
			args: args{
				s:        "applepenapple",
				wordDict: []string{"apple", "pen"},
			},
			want: true,
		},
	}
    fmt.Println("testWordBreak - task1:")
	for _, tt := range tests {
		fmt.Printf("\tID %d: %s \n", tt.id, tt.name)

		got := wordBreak(tt.args.s, tt.args.wordDict)
		fmt.Printf("\t\tSuccess: %t\n", reflect.DeepEqual(tt.want, got))
	}
}