diff options
| -rw-r--r-- | foo.py | 10 | ||||
| -rw-r--r-- | go.mod | 3 | ||||
| -rw-r--r-- | lru/main.go | 372 | ||||
| -rw-r--r-- | mergeintervals/main.go | 359 | ||||
| -rw-r--r-- | prefix/main.go | 116 | ||||
| -rw-r--r-- | radial/radial.go | 107 | ||||
| -rw-r--r-- | reversenumber/main.go | 118 | ||||
| -rw-r--r-- | timebucket/main.go | 97 | ||||
| -rw-r--r-- | twosum/twosum.go | 112 |
9 files changed, 1294 insertions, 0 deletions
@@ -0,0 +1,10 @@ +def max_subarray(numbers): + """Find the largest sum of any contiguous subarray.""" + best_sum = float('-inf') + current_sum = 0 + for x in numbers: + current_sum = max(x, current_sum + x) + best_sum = max(best_sum, current_sum) + return best_sum + +print(max_subarray([100, -5, 500])) @@ -0,0 +1,3 @@ +module foo + +go 1.24.3 diff --git a/lru/main.go b/lru/main.go new file mode 100644 index 0000000..e951d67 --- /dev/null +++ b/lru/main.go @@ -0,0 +1,372 @@ +package main + +import "fmt" + +type LRUCache struct { + head *Node + tail *Node + keys map[int]*Node + cap int + used int +} + +type Node struct { + key int + val int + next *Node + prev *Node +} + +func Constructor(capacity int) LRUCache { + return LRUCache{ + head: nil, + tail: nil, + keys: map[int]*Node{}, + cap: capacity, + used: 0, + } +} + +func (c *LRUCache) toFront(node *Node) { + if c.head.key == node.key { + return + } + + node.prev.next = node.next + if node.next == nil { + c.tail = node.prev + } else { + node.next.prev = node.prev + } + + node.prev = nil + node.next = c.head + c.head.prev = node + c.head = node +} + +func (this *LRUCache) Get(key int) int { + node, ok := this.keys[key] + if ok { + this.toFront(node) + return node.val + } + return -1 +} + +func (this *LRUCache) Put(key int, value int) { + node, ok := this.keys[key] + if ok { + node.val = value + } else { + this.used += 1 + if this.used > this.cap { + this.used -= 1 + delete(this.keys, this.tail.key) + this.tail = this.tail.prev + if this.tail != nil { + this.tail.next = nil + } + } + node = &Node{ + key: key, + val: value, + next: this.head, + prev: nil, + } + this.keys[key] = node + if this.tail == nil { + this.head = node + this.tail = node + return + } + this.head.prev = node + this.head = node + return + } + + this.toFront(node) +} + +func main() { + mismatches := 0 + lRUCache := Constructor(10) + lRUCache.Put(10, 13) + lRUCache.Put(3, 17) + lRUCache.Put(6, 11) + lRUCache.Put(10, 5) + lRUCache.Put(9, 10) + res6 := lRUCache.Get(13) + if res6 != -1 { + fmt.Printf("Mismatch at operation 6 (Get(13)): expected -1, got %d\n", res6) + mismatches++ + } + lRUCache.Put(2, 19) + res8 := lRUCache.Get(2) + if res8 != 19 { + fmt.Printf("Mismatch at operation 8 (Get(2)): expected 19, got %d\n", res8) + mismatches++ + } + res9 := lRUCache.Get(3) + if res9 != 17 { + fmt.Printf("Mismatch at operation 9 (Get(3)): expected 17, got %d\n", res9) + mismatches++ + } + lRUCache.Put(5, 25) + res11 := lRUCache.Get(8) + if res11 != -1 { + fmt.Printf("Mismatch at operation 11 (Get(8)): expected -1, got %d\n", res11) + mismatches++ + } + lRUCache.Put(9, 22) + lRUCache.Put(5, 5) + lRUCache.Put(1, 30) + res15 := lRUCache.Get(11) + if res15 != -1 { + fmt.Printf("Mismatch at operation 15 (Get(11)): expected -1, got %d\n", res15) + mismatches++ + } + lRUCache.Put(9, 12) + res17 := lRUCache.Get(7) + if res17 != -1 { + fmt.Printf("Mismatch at operation 17 (Get(7)): expected -1, got %d\n", res17) + mismatches++ + } + res18 := lRUCache.Get(5) + if res18 != 5 { + fmt.Printf("Mismatch at operation 18 (Get(5)): expected 5, got %d\n", res18) + mismatches++ + } + res19 := lRUCache.Get(8) + if res19 != -1 { + fmt.Printf("Mismatch at operation 19 (Get(8)): expected -1, got %d\n", res19) + mismatches++ + } + res20 := lRUCache.Get(9) + if res20 != 12 { + fmt.Printf("Mismatch at operation 20 (Get(9)): expected 12, got %d\n", res20) + mismatches++ + } + lRUCache.Put(4, 30) + lRUCache.Put(9, 3) + res23 := lRUCache.Get(9) + if res23 != 3 { + fmt.Printf("Mismatch at operation 23 (Get(9)): expected 3, got %d\n", res23) + mismatches++ + } + res24 := lRUCache.Get(10) + if res24 != 5 { + fmt.Printf("Mismatch at operation 24 (Get(10)): expected 5, got %d\n", res24) + mismatches++ + } + res25 := lRUCache.Get(10) + if res25 != 5 { + fmt.Printf("Mismatch at operation 25 (Get(10)): expected 5, got %d\n", res25) + mismatches++ + } + lRUCache.Put(6, 14) + lRUCache.Put(3, 1) + res28 := lRUCache.Get(3) + if res28 != 1 { + fmt.Printf("Mismatch at operation 28 (Get(3)): expected 1, got %d\n", res28) + mismatches++ + } + lRUCache.Put(10, 11) + res30 := lRUCache.Get(8) + if res30 != -1 { + fmt.Printf("Mismatch at operation 30 (Get(8)): expected -1, got %d\n", res30) + mismatches++ + } + lRUCache.Put(2, 14) + res32 := lRUCache.Get(1) + if res32 != 30 { + fmt.Printf("Mismatch at operation 32 (Get(1)): expected 30, got %d\n", res32) + mismatches++ + } + res33 := lRUCache.Get(5) + if res33 != 5 { + fmt.Printf("Mismatch at operation 33 (Get(5)): expected 5, got %d\n", res33) + mismatches++ + } + res34 := lRUCache.Get(4) + if res34 != 30 { + fmt.Printf("Mismatch at operation 34 (Get(4)): expected 30, got %d\n", res34) + mismatches++ + } + lRUCache.Put(11, 4) + lRUCache.Put(12, 24) + lRUCache.Put(5, 18) + res38 := lRUCache.Get(13) + if res38 != -1 { + fmt.Printf("Mismatch at operation 38 (Get(13)): expected -1, got %d\n", res38) + mismatches++ + } + lRUCache.Put(7, 23) + res40 := lRUCache.Get(8) + if res40 != -1 { + fmt.Printf("Mismatch at operation 40 (Get(8)): expected -1, got %d\n", res40) + mismatches++ + } + res41 := lRUCache.Get(12) + if res41 != 24 { + fmt.Printf("Mismatch at operation 41 (Get(12)): expected 24, got %d\n", res41) + mismatches++ + } + lRUCache.Put(3, 27) + lRUCache.Put(2, 12) + res44 := lRUCache.Get(5) + if res44 != 18 { + fmt.Printf("Mismatch at operation 44 (Get(5)): expected 18, got %d\n", res44) + mismatches++ + } + lRUCache.Put(2, 9) + lRUCache.Put(13, 4) + lRUCache.Put(8, 18) + lRUCache.Put(1, 7) + res49 := lRUCache.Get(6) + if res49 != -1 { + fmt.Printf("Mismatch at operation 49 (Get(6)): expected -1, got %d\n", res49) + mismatches++ + } + lRUCache.Put(9, 29) + lRUCache.Put(8, 21) + res52 := lRUCache.Get(5) + if res52 != 18 { + fmt.Printf("Mismatch at operation 52 (Get(5)): expected 18, got %d\n", res52) + mismatches++ + } + lRUCache.Put(6, 30) + lRUCache.Put(1, 12) + res55 := lRUCache.Get(10) + if res55 != -1 { + fmt.Printf("Mismatch at operation 55 (Get(10)): expected -1, got %d\n", res55) + mismatches++ + } + lRUCache.Put(4, 15) + lRUCache.Put(7, 22) + lRUCache.Put(11, 26) + lRUCache.Put(8, 17) + lRUCache.Put(9, 29) + res61 := lRUCache.Get(5) + if res61 != 18 { + fmt.Printf("Mismatch at operation 61 (Get(5)): expected 18, got %d\n", res61) + mismatches++ + } + lRUCache.Put(3, 4) + lRUCache.Put(11, 30) + res64 := lRUCache.Get(12) + if res64 != -1 { + fmt.Printf("Mismatch at operation 64 (Get(12)): expected -1, got %d\n", res64) + mismatches++ + } + lRUCache.Put(4, 29) + res66 := lRUCache.Get(3) + if res66 != 4 { + fmt.Printf("Mismatch at operation 66 (Get(3)): expected 4, got %d\n", res66) + mismatches++ + } + res67 := lRUCache.Get(9) + if res67 != 29 { + fmt.Printf("Mismatch at operation 67 (Get(9)): expected 29, got %d\n", res67) + mismatches++ + } + res68 := lRUCache.Get(6) + if res68 != 30 { + fmt.Printf("Mismatch at operation 68 (Get(6)): expected 30, got %d\n", res68) + mismatches++ + } + lRUCache.Put(3, 4) + res70 := lRUCache.Get(1) + if res70 != 12 { + fmt.Printf("Mismatch at operation 70 (Get(1)): expected 12, got %d\n", res70) + mismatches++ + } + res71 := lRUCache.Get(10) + if res71 != -1 { + fmt.Printf("Mismatch at operation 71 (Get(10)): expected -1, got %d\n", res71) + mismatches++ + } + lRUCache.Put(3, 29) + lRUCache.Put(10, 28) + lRUCache.Put(1, 20) + lRUCache.Put(11, 13) + res76 := lRUCache.Get(3) + if res76 != 29 { + fmt.Printf("Mismatch at operation 76 (Get(3)): expected 29, got %d\n", res76) + mismatches++ + } + lRUCache.Put(3, 12) + lRUCache.Put(3, 8) + lRUCache.Put(10, 9) + lRUCache.Put(3, 26) + res81 := lRUCache.Get(8) + if res81 != 17 { + fmt.Printf("Mismatch at operation 81 (Get(8)): expected 17, got %d\n", res81) + mismatches++ + } + res82 := lRUCache.Get(7) + if res82 != 22 { + fmt.Printf("Mismatch at operation 82 (Get(7)): expected 22, got %d\n", res82) + mismatches++ + } + res83 := lRUCache.Get(5) + if res83 != 18 { + fmt.Printf("Mismatch at operation 83 (Get(5)): expected 18, got %d\n", res83) + mismatches++ + } + lRUCache.Put(13, 17) + lRUCache.Put(2, 27) + lRUCache.Put(11, 15) + res87 := lRUCache.Get(12) + if res87 != -1 { + fmt.Printf("Mismatch at operation 87 (Get(12)): expected -1, got %d\n", res87) + mismatches++ + } + lRUCache.Put(9, 19) + lRUCache.Put(2, 15) + lRUCache.Put(3, 16) + res91 := lRUCache.Get(1) + if res91 != 20 { + fmt.Printf("Mismatch at operation 91 (Get(1)): expected 20, got %d\n", res91) + mismatches++ + } + lRUCache.Put(12, 17) + lRUCache.Put(9, 1) + lRUCache.Put(6, 19) + res95 := lRUCache.Get(4) + if res95 != -1 { + fmt.Printf("Mismatch at operation 95 (Get(4)): expected -1, got %d\n", res95) + mismatches++ + } + res96 := lRUCache.Get(5) + if res96 != 18 { + fmt.Printf("Mismatch at operation 96 (Get(5)): expected 18, got %d\n", res96) + mismatches++ + } + res97 := lRUCache.Get(5) + if res97 != 18 { + fmt.Printf("Mismatch at operation 97 (Get(5)): expected 18, got %d\n", res97) + mismatches++ + } + lRUCache.Put(8, 1) + lRUCache.Put(11, 7) + lRUCache.Put(5, 2) + lRUCache.Put(9, 28) + res102 := lRUCache.Get(1) + if res102 != 20 { + fmt.Printf("Mismatch at operation 102 (Get(1)): expected 20, got %d\n", res102) + mismatches++ + } + lRUCache.Put(2, 2) + lRUCache.Put(7, 4) + lRUCache.Put(4, 22) + lRUCache.Put(7, 24) + lRUCache.Put(9, 26) + lRUCache.Put(13, 28) + lRUCache.Put(11, 26) + if mismatches == 0 { + fmt.Println("All Gets matched expected outputs!") + } else { + fmt.Printf("Total mismatches: %d\n", mismatches) + } +} diff --git a/mergeintervals/main.go b/mergeintervals/main.go new file mode 100644 index 0000000..6e2a26e --- /dev/null +++ b/mergeintervals/main.go @@ -0,0 +1,359 @@ +/** + +Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. + + + +Example 1: + +Input: intervals = [[1,3],[2,6],[8,10],[15,18]] +Output: [[1,6],[8,10],[15,18]] +Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. + +Example 2: + +Input: intervals = [[1,4],[4,5]] +Output: [[1,5]] +Explanation: Intervals [1,4] and [4,5] are considered overlapping. + +Example 3: + +Input: intervals = [[4,7],[1,4]] +Output: [[1,7]] +Explanation: Intervals [1,4] and [4,7] are considered overlapping. +**/ + +package main + +import ( + "fmt" + "math" + "math/rand/v2" +) + +// func insertionIndex(time int) int { +// low, high := 0, len(bucket.entries) +// for low < high { +// // Calculate mid carefully to prevent integer overflow +// mid := low + (high-low)/2 + +// if bucket.entries[mid].time <= time { +// low = mid + 1 +// } else { +// high = mid +// } +// } + +// return low +// } + +type SkipNode struct { + val []int + + prevs []*SkipNode + nexts []*SkipNode +} + +type SkipList struct { + levels int + heads []*SkipNode +} + +func (l *SkipList) print() { + for i := len(l.heads) - 1; i >= 0; i-- { + head := l.heads[i] + fmt.Printf("[LIST %d]: ", i) + for head != nil { + fmt.Printf("[%d, %d]", head.val[0], head.val[1]) + head = head.nexts[i] + if head != nil { + fmt.Print(", ") + } + } + fmt.Println() + } +} + +const halfMax = math.MaxUint / 2 + +func flip() bool { + return rand.Uint() > halfMax +} + +func overlaps(lo, hi, mlo, mhi int) (overlaps bool, goLeft bool, goRight bool) { + overlaps, goLeft, goRight = false, false, false + // if lo < mlo && hi > mlo + // if hi > mhi and lo < mi + if (hi >= mhi && lo <= mhi) || (lo <= mlo && hi >= mlo) { + overlaps = true + + if lo < mlo { + goLeft = true + } + + if hi > mhi { + goRight = true + } + } + + if hi < mlo { + goLeft = true + } + + if lo > mhi { + goRight = true + } + + return overlaps, goLeft, goRight +} + +func (l *SkipList) insertInterval(interval []int) { + + lo, hi := interval[0], interval[1] + + debugcondition := lo == 5 + nexts := l.heads + // overLappedNodes := make([]*SkipNode, l.levels) + lastVisitedPerLevel := make([]*SkipNode, l.levels) + level := l.levels - 1 + var nodeOfNexts *SkipNode +search: + for { + if level < 0 { + panic("whoops") + } + current := nexts[level] + if current == nil { + // we need to know where we came from T_T + // need to set last visited to node of nexts unless it's nil in which case, we are going to make new head + if nodeOfNexts != nil { + lastVisitedPerLevel[level] = nodeOfNexts + } + level = level - 1 + + if level < 0 { + level = 0 + // we reached end of list 0, probably just do append routine somehow? + // MAYBE + current = lastVisitedPerLevel[0] // hopefully this results in tail node? + if current != nil && current.prevs[0] != nil { + nexts = current.prevs[0].nexts + } + if current == nil { + // edge case, all lists are empty here is our new head node + newNode := SkipNode{ + val: interval, + nexts: make([]*SkipNode, l.levels), + prevs: make([]*SkipNode, l.levels), + } + for { + if level >= l.levels { + break + } + var prev *SkipNode + if lastVisitedPerLevel[level] != nil { + prev = lastVisitedPerLevel[level].prevs[level] + } + if prev != nil { + prev.nexts[level] = &newNode + } else { + // new head + l.heads[level] = &newNode + } + newNode.prevs[level] = prev + if lastVisitedPerLevel[level] != nil { + lastVisitedPerLevel[level].prevs[level] = &newNode + } + newNode.nexts[level] = lastVisitedPerLevel[level] + level = level + 1 + } + + return + } + + if current.nexts[0] != nil { + panic("very suspicious edge csae") + } + } else { + continue + } + } + + mlo, mhi := current.val[0], current.val[1] + + overlaps, goLeft, goRight := overlaps(lo, hi, mlo, mhi) + // @TODO FIRST goLeft is wrong, we need some like EITHER it says goLeft, which means goDown, or we have an overlap and we merge OR we go right which means we stay on same level and retry + + if overlaps { + // MERGING / Go DOWN + // in this case we need to check the current level and see if a previous or next node belongs to the new merged range + // it's possible we would need to merge multipe intervals in a single insers so we probably need to keep going until no longer in the interval? + + // TODO update current level node with new interval, explore in either direction for other affected nodes, continue until level == 0 + + return + } + + if goLeft { + lastVisitedPerLevel[level] = nodeOfNexts // this needs to be node pointing TO next, which would be current.prevs[level] + // if ^ is nil, we know we came from the HEAD of the list, so we can go back to heads for that nonsense + // we know that we are not overlapping here and we know that hi < mlo, meaning we should go down + if level != 0 { + level = level - 1 + continue + } + // can't go down, do push of new interval, NOT overlapping + // if we are on level 0, we have found the best node for new node to be inserted into + newNode := SkipNode{ + val: interval, + nexts: make([]*SkipNode, l.levels), + prevs: make([]*SkipNode, l.levels), + } + // insert inbetween prev and current + for { + if level != 0 && (!flip() || level >= l.levels) { + // not promoted + + if !debugcondition { + break + } + if level == l.levels { + break + } + } + var prev, next *SkipNode + if lastVisitedPerLevel[level] != nil { + prev = lastVisitedPerLevel[level] + } + + if prev != nil { + next = prev.nexts[level] + prev.nexts[level] = &newNode + } else { + // new head + next = l.heads[level] + l.heads[level] = &newNode + } + newNode.nexts[level] = next + + if lastVisitedPerLevel[level] != nil { + lastVisitedPerLevel[level].nexts[level] = &newNode + } + newNode.prevs[level] = lastVisitedPerLevel[level] + level = level + 1 + } + break search + } else if goRight { + // so in case of going right we need to set new nexts to next nodes nexts, and continue, do NOT go down + // if next on current level != nil, however if we are on level 0 and next is nil, we know we are doing a tail node append + // if we cannot go down, we need to insert node into best spot of list 0 and decide promotion + nexts = current.nexts + lastVisitedPerLevel[level] = current // this avoids edge case of landing on list 0 tail node and beign force to find tail node from list I think + nodeOfNexts = current + if level == 0 && nexts[0] == nil { + // EDGE CASE, we are at the end of the list 0 do NOT continue back to search, do append + } else { + continue search + } + + // the only time we hit this case is when we have landed on a tail node of list 0 + + // do insert + newNode := SkipNode{ + val: interval, + nexts: make([]*SkipNode, l.levels), + prevs: make([]*SkipNode, l.levels), + } + // insert inbetween next and current + for { + if level != 0 && (!flip() || level >= l.levels) { + // not promoted + if !debugcondition { + break + } + if level == l.levels { + break + } + } + + var next, prev *SkipNode + if lastVisitedPerLevel[level] != nil { + prev = lastVisitedPerLevel[level] + next = lastVisitedPerLevel[level].nexts[level] + } else { + panic("i don't think this is possible") + } + if next != nil { + next.prevs[level] = &newNode + } + + newNode.nexts[level] = next + + if lastVisitedPerLevel[level] != nil { + lastVisitedPerLevel[level].nexts[level] = &newNode + } + newNode.prevs[level] = prev + level = level + 1 + } + break search + } + } +} + +func merge(intervals [][]int) [][]int { + out := make([][]int, len(intervals)) + out[0] = intervals[0] + outlen := 1 + + for _, interval := range intervals[1:] { + lo, hi := interval[0], interval[1] + + slo, shi := 0, outlen + for slo < shi { + mid := slo + (shi-slo)/2 + + mlo, mhi := out[mid][0], out[mid][1] + + if lo <= mhi || hi >= mlo { + // MERGING + + break + } + if hi < mlo { + shi = mid + } else { + slo = mid + 1 + } + } + // no overlap + + } + + return out[:outlen] +} + +func main() { + l := SkipList{ + levels: 4, + heads: make([]*SkipNode, 4), + } + + l.insertInterval([]int{9, 10}) + l.print() + fmt.Println("inerting 3,4") + l.insertInterval([]int{3, 4}) + l.print() + fmt.Println("inerting 7,8") + l.insertInterval([]int{7, 8}) + l.print() + fmt.Println("inerting 5,6") + l.insertInterval([]int{5, 6}) + l.print() + fmt.Println("inerting 11,12") + l.insertInterval([]int{11, 12}) + l.print() + + fmt.Println("inerting 1,2") + l.insertInterval([]int{1, 2}) + l.print() +} diff --git a/prefix/main.go b/prefix/main.go new file mode 100644 index 0000000..cbf472d --- /dev/null +++ b/prefix/main.go @@ -0,0 +1,116 @@ +package main + +import "fmt" + +/** +Design a data structure that supports adding new words and finding if a string matches any previously added string. + +Implement the WordDictionary class: + + WordDictionary() Initializes the object. + void addWord(word) Adds word to the data structure, it can be matched later. + bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter. + + + +Example: + +Input +["WordDictionary","addWord","addWord","addWord","search","search","search","search"] +[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] +Output +[null,null,null,null,false,true,true,true] + +Explanation +WordDictionary wordDictionary = new WordDictionary(); +wordDictionary.addWord("bad"); +wordDictionary.addWord("dad"); +wordDictionary.addWord("mad"); +wordDictionary.search("pad"); // return False +wordDictionary.search("bad"); // return True +wordDictionary.search(".ad"); // return True +wordDictionary.search("b.."); // return True + + + +Constraints: + + 1 <= word.length <= 25 + word in addWord consists of lowercase English letters. + word in search consist of '.' or lowercase English letters. + There will be at most 2 dots in word for search queries. + At most 104 calls will be made to addWord and search. +**/ + +type WordDictionary struct { + is_terminal bool + children [26]*WordDictionary +} + +func Constructor() WordDictionary { + return WordDictionary{ + is_terminal: false, + children: [26]*WordDictionary{}, + } +} + +func (this *WordDictionary) AddWord(word string) { + cur := this + for _, char := range word { + fmt.Println(char) + ascii := char - 97 + + if cur.children[ascii] == nil { + tmp := Constructor() + cur.children[ascii] = &tmp + } + + cur = cur.children[ascii] + } + cur.is_terminal = true +} + +func (this *WordDictionary) Search(word string) bool { + cur := this + for idx, char := range word { + if char == '.' { + for _, child := range cur.children { + if child != nil { + fmt.Printf("RECURSIVE SEARCHING %s for entry word %s\n", word[idx+1:], word) + if child.Search(word[idx+1:]) { + return true + } + } + } + return false + } + + ascii := char - 97 + next := cur.children[ascii] + if next == nil { + return false + } + + cur = next + } + + return cur.is_terminal +} + +/** + * Your WordDictionary object will be instantiated and called as such: + * obj := Constructor(); + * obj.AddWord(word); + * param_2 := obj.Search(word); + */ + +func main() { + wordDictionary := Constructor() + wordDictionary.AddWord("bad") + wordDictionary.AddWord("dad") + wordDictionary.AddWord("mad") + fmt.Println(wordDictionary.Search("pad")) // return False + fmt.Println(wordDictionary.Search("bad")) // return True + fmt.Println(wordDictionary.Search(".ad")) // return True + fmt.Println(wordDictionary.Search("b..")) // return True +} diff --git a/radial/radial.go b/radial/radial.go new file mode 100644 index 0000000..e318252 --- /dev/null +++ b/radial/radial.go @@ -0,0 +1,107 @@ +package main + +import "fmt" + +type Node struct { + parent *Node + left *Node + right *Node + + val int + isLeft bool +} + +func (n *Node) pushLeft(val int) { + n.left = &Node{ + parent: n, + val: val, + isLeft: true, + } +} + +func (n *Node) pushRight(val int) { + n.right = &Node{ + parent: n, + val: val, + isLeft: false, + } +} + +func (n *Node) maxDepth(depth int) int { + if n == nil { + return depth + } + + return max(n.left.maxDepth(depth+1), n.right.maxDepth(depth+1)) +} + +func (n *Node) find(target int) *Node { + if n == nil { + return nil + } + if n.val == target { + return n + } + + l := n.left.find(target) + if l != nil { + return l + } + return n.right.find(target) +} + +func (n *Node) radial(nodes *[]*Node, distance int, fromTarget bool, fromChild bool, fromLeft bool) { + if n == nil { + return + } + + if distance == 0 { + *nodes = append(*nodes, n) + return + } + + if fromChild { + if fromLeft { + n.right.radial(nodes, distance-1, false, false, false) + } else { + n.left.radial(nodes, distance-1, false, false, false) + } + n.parent.radial(nodes, distance-1, false, true, n.isLeft) + } else { + n.left.radial(nodes, distance-1, false, false, false) + n.right.radial(nodes, distance-1, false, false, false) + } + + if fromTarget { + n.parent.radial(nodes, distance-1, false, true, n.isLeft) + } +} + +func main() { + root := Node{ + val: 1, + } + root.pushRight(2) + root.right.pushLeft(3) + root.right.pushRight(4) + + root.pushLeft(5) + root.left.pushLeft(6) + root.left.pushRight(7) + + root.left.left.pushLeft(8) + root.left.left.pushRight(9) + + root.left.right.pushLeft(10) + root.left.right.pushRight(11) + + find := root.find(5) + fmt.Println(find) + nodes := []*Node{} + find.radial(&nodes, 2, true, false, false) + fmt.Println(nodes) + for _, node := range nodes { + fmt.Println(node.val) + } + +} diff --git a/reversenumber/main.go b/reversenumber/main.go new file mode 100644 index 0000000..1a4f5ba --- /dev/null +++ b/reversenumber/main.go @@ -0,0 +1,118 @@ +package main + +import "fmt" + +type ListNode struct { + Val int + Next *ListNode +} + +func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { + r1 := &ListNode{ + Val: l1.Val, + } + r2 := &ListNode{ + Val: l2.Val, + } + + l1l := 0 + l2l := 0 + + for { + if l1 != nil { + l1l += 1 + r1n := r1 + r1 = &ListNode{ + Val: l1.Val, + Next: r1n, + } + l1 = l1.Next + } + + if l2 != nil { + l2l += 1 + r2n := r2 + r2 = &ListNode{ + Val: l2.Val, + Next: r2n, + } + l2 = l2.Next + } + + if l1 == nil && l2 == nil { + break + } + } + + var output, input *ListNode + if l1l > l2l { + output = r1 + input = r2 + } else { + output = r2 + input = r2 + } + + carry := 0 + var prev *ListNode + for { + sum := output.Val + carry + if input != nil { + sum = sum + input.Val + input = input.Next + } + + carry = sum / 10 + next := output.Next + output.Val = sum % 10 + output.Next = prev + prev = output + + if next == nil { + break + } + output = next + } + + return output +} + +func makeList(list []int) *ListNode { + output := &ListNode{ + Val: list[0], + Next: nil, + } + current := output + for _, n := range list[1:] { + node := &ListNode{ + Val: n, + } + current.Next = node + current = node + } + + return output +} + +func printList(node *ListNode) { + for { + if node == nil { + break + } + + fmt.Print(node.Val) + node = node.Next + } + fmt.Println() +} + +func main() { + // Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] + // Output: [8,9,9,9,0,0,0,1] + l1 := makeList([]int{9, 9, 9, 9, 9, 9, 9}) + l2 := makeList([]int{9, 9, 9, 9}) + printList(l1) + printList(l2) + + printList(addTwoNumbers(l1, l2)) +} diff --git a/timebucket/main.go b/timebucket/main.go new file mode 100644 index 0000000..eb3eca1 --- /dev/null +++ b/timebucket/main.go @@ -0,0 +1,97 @@ +package main + +import "fmt" + +type TimeBucket struct { + entries []TimeEntry +} + +type TimeEntry struct { + time int + value string +} + +type TimeMap struct { + buckets map[string]*TimeBucket +} + +func (bucket *TimeBucket) insertOrdered(time int, value string) { + // 1. Binary Search to find the correct index + index := bucket.insertionIndex(time) // This is exactly where the item needs to go + + // 2. Slice Primitives to perform the insertion + // First, append a zero-value element to grow the slice safely (handles allocation) + bucket.entries = append(bucket.entries, TimeEntry{}) + + // Next, copy the elements over by 1 position to the right to make room + copy(bucket.entries[index+1:], bucket.entries[index:]) + + // Finally, drop the new item into the open slot + bucket.entries[index] = TimeEntry{ + time: time, + value: value, + } +} + +func (bucket *TimeBucket) insertionIndex(time int) int { + low, high := 0, len(bucket.entries) + for low < high { + // Calculate mid carefully to prevent integer overflow + mid := low + (high-low)/2 + + if bucket.entries[mid].time <= time { + low = mid + 1 + } else { + high = mid + } + } + + return low +} + +func Constructor() TimeMap { + return TimeMap{ + buckets: map[string]*TimeBucket{}, + } +} + +func (this *TimeMap) Set(key string, value string, timestamp int) { + bucket, okay := this.buckets[key] + if !okay { + this.buckets[key] = &TimeBucket{ + entries: []TimeEntry{}, + } + bucket = this.buckets[key] + } + + bucket.insertOrdered(timestamp, value) +} + +func (this *TimeMap) Get(key string, timestamp int) string { + bucket, okay := this.buckets[key] + if !okay { + return "" + } + + idx := bucket.insertionIndex(timestamp) + if idx > 0 { + idx = idx - 1 + } + + entry := bucket.entries[idx] + if entry.time > timestamp { + return "" + } else { + return entry.value + } +} + +func main() { + timeMap := Constructor() + timeMap.Set("foo", "bar", 1) // store the key "foo" and value "bar" along with timestamp = 1. + fmt.Println(timeMap.Get("foo", 1)) // return "bar" + fmt.Println(timeMap.Get("foo", 3)) // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". + timeMap.Set("foo", "bar2", 4) // store the key "foo" and value "bar2" along with timestamp = 4. + fmt.Println(timeMap.Get("foo", 4)) // return "bar2" + fmt.Println(timeMap.Get("foo", 5)) // return "bar2" +} diff --git a/twosum/twosum.go b/twosum/twosum.go new file mode 100644 index 0000000..ca93104 --- /dev/null +++ b/twosum/twosum.go @@ -0,0 +1,112 @@ +package main + +import "fmt" + +type ListNode struct { + Val int + Next *ListNode +} + +func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { + carry := 0 + var output, co *ListNode + c1 := l1 + c2 := l2 + for { + if c1 != nil && c2 != nil { + sum := c1.Val + c2.Val + carry + carry = sum / 10 + rem := sum % 10 + c1.Val = rem + c2.Val = rem + + if c1.Next == nil && c2.Next == nil { + if carry > 0 { + c1.Next = &ListNode{ + Val: 1, + } + carry = 0 + } + } + + c1 = c1.Next + c2 = c2.Next + continue + } + + if c1 != nil { + output = l1 + co = c1 + break + } else if c2 != nil { + output = l2 + co = c2 + break + } else { + + output = l1 + break + } + } + + if co != nil { + for { + sum := co.Val + carry + carry = sum / 10 + rem := sum % 10 + + co.Val = rem + if co.Next == nil { + if carry > 0 { + co.Next = &ListNode{ + Val: 1, + } + } + break + } + co = co.Next + } + } + + return output +} + +func makeList(list []int) *ListNode { + output := &ListNode{ + Val: list[0], + Next: nil, + } + current := output + for _, n := range list[1:] { + node := &ListNode{ + Val: n, + } + current.Next = node + current = node + } + + return output +} + +func printList(node *ListNode) { + for { + if node == nil { + break + } + + fmt.Print(node.Val) + node = node.Next + } + fmt.Println() +} + +func main() { + // Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] + // Output: [8,9,9,9,0,0,0,1] + l1 := makeList([]int{9, 9, 9, 9, 9, 9, 9}) + l2 := makeList([]int{9, 9, 9, 9}) + printList(l1) + printList(l2) + + printList(addTwoNumbers(l1, l2)) +} |