public override bool equals(obj): T that return obj != null && (that = obj as T) != null && this.x == that.x

## Saturday, December 27, 2014

### equals

Shortest way.

## Thursday, December 25, 2014

### recursion and yield return

Get a list of nodes given a tree structure of nodes.

Data structure:

Using recursion:

Using recursion and yield return:

But it is inefficient when the tree is deep as every method call creates an iterator (see this). So the work-around is to not use recursion and save nodes in a stack with O(n) space.

[Hat tip to RT, JS, EL]

A | +--B | +--C | | | +--D | +--EResult:

{ A, B, C, D, E }

Data structure:

node: string name list<node> children

Using recursion:

traverse(root): list = new Get(root, list) return list // with list Get(node, list): list.add(node) if node.children == null: return foreach child in node.children: Get(child, list)

Using recursion and yield return:

traverse(root): return Get(root) // with yield return Get(node): yield return node if node.children == null: yield break foreach child in node.children: foreach n in Get(child): yield return n

But it is inefficient when the tree is deep as every method call creates an iterator (see this). So the work-around is to not use recursion and save nodes in a stack with O(n) space.

traverse(root): return Get(root) // without recursion, with yield return Get(node): stack = new stack.push(node) while !stack.empty(): var n = stack.pop() yield return n if n.children == null: continue // reverse to preserve children order foreach child in n.children.reverse(): stack.push(child)

[Hat tip to RT, JS, EL]

## Friday, July 25, 2014

### add two string ints

"123", "4" => "127"

"99", "999" => "1098"

"9", "9" => "18"

[Hat tip to SM]

"99", "999" => "1098"

"9", "9" => "18"

string add(string s1, string s2): i = s1.length-1, j = s2.length-1 carry = 0 buffer = new while i >= 0 || j >= 0 || carry > 0: a = 0 if i >= 0: a = s1[i] -'0' i-- b = 0 if j >= 0: b = s2[j] -'0' j-- digit = a+b +carry carry = 0 if digit >= 10: carry = 1 digit -= 10 buffer.append(digit) return buffer.reverse()

[Hat tip to SM]

## Wednesday, April 09, 2014

### merge ranges

Merges list of ranges.

(1,3), (4,6) => (1,6)

(1,3), (2,6) => (1,6)

(1,6), (2,3) => (1,6)

(1,3), (8,9) => (1,3), (8,9)

(1,3), (4,6), (8,9) => (1,6), (8,9)

(4,6), (1,2) => throw

[Hat tip to SD]

(1,3), (4,6) => (1,6)

(1,3), (2,6) => (1,6)

(1,6), (2,3) => (1,6)

(1,3), (8,9) => (1,3), (8,9)

(1,3), (4,6), (8,9) => (1,6), (8,9)

(4,6), (1,2) => throw

range int start int end range[] mergeRanges(range[] ranges): for i = 1..<ranges.length: if ranges[i-1].start > ranges[i].start: throw "ranges are NOT sorted by start value ascendingly" range[] merged = new start = ranges[0].start end = ranges[0].end for i = 1..<ranges.length: startcurr = ranges[i].start endcurr = range[i].end if end+1 >= startcurr: endcurr = max(end, endcurr) else: merged.add(new range(start, end)) start = startcurr end = endcurr merged.add(new range(start, end)) return merged

[Hat tip to SD]

## Friday, February 28, 2014

### cache read pattern

The basic cache read/get pattern.

// no lock on cache read, lock on cache write get(key): t = null // get from cache t = cache.get(key) if t == null: lock(_lock): // check cache again after locking t = cache.get(key) if t == null: t = getTimeConsuming(key) // insert into cache only if not null if t != null: cache.insert(key, t) return t

### if graph is cyclic

For every node in graph, if a cycle exists (starting from node) then break out and return true else return false.

With only one map 'visited', it does not work. Ex: 1<-2<-3

With only one map 'path', nodes are visited multiple times for an acyclic path. Ex: 1->2->3

Two maps work. A map 'path' is used to save the path from current node. Another map 'acyclicNodes' is used to denote acyclic nodes.

Used for deadlock detection. Each process specifies order of locks required - forming a graph (directed).

Time: O(nodes + edges)

Space: O(nodes)

With only one map 'visited', it does not work. Ex: 1<-2<-3

With only one map 'path', nodes are visited multiple times for an acyclic path. Ex: 1->2->3

Two maps work. A map 'path' is used to save the path from current node. Another map 'acyclicNodes' is used to denote acyclic nodes.

Used for deadlock detection. Each process specifies order of locks required - forming a graph (directed).

graph list<node> nodes node id list<node> neighbors bool isCyclic(graph): map acyclicNodes = new foreach node in graph.nodes: map path = new if isCyclic(node, path, acyclicNodes): return true return false bool isCyclic(node, path, acyclicNodes): if acyclicNodes(node.id): return false // node present in path so cyclic if path(node.id): return true path.add(node.id) foreach neighbor in node.neighbors: if isCyclic(neighbor, path, acyclicNodes): return true path.remove(node.id) // node is acyclic acyclicNodes.add(node.id) return false

Time: O(nodes + edges)

Space: O(nodes)

## Friday, February 14, 2014

### stack with array

stack a = new T[SIZE] i = 0 push(T x): if i == a.length(): resize() a[i++] = x T pop(): if i == 0: throw "empty" return a[--i] resize(): anew = new[a.length() * 2] //overflow possible for j=0 to <a.length(): anew[j] = a[j] a = anew

## Monday, February 10, 2014

### queue with 2 stacks, stack with 2 queues

queue with 2 stacks. for enqueue, s2->s1 and push into s1. for dequeue, s1->s2 and pop from s2.

stack with 2 queues. for push, enqueue into non-empty queue (or q2). for pop, dequeue all from non-empty queue, enqueue into other and return last.

enqueue(T x): while !s2.isEmpty(): s1.push(s2.pop()) s1.push(x) T dequeue(): while !s1.isEmpty(): s2.push(s1.pop()) return s2.pop()

stack with 2 queues. for push, enqueue into non-empty queue (or q2). for pop, dequeue all from non-empty queue, enqueue into other and return last.

push(T x): if !q1.isEmpty(): q = q1 else q = q2 q.enqueue(x) T pop(): if !q1.isEmpty(): q = q1 other = q2 else q = q2 other = q1 if q.isEmpty(): throw "empty" n = null while !q.isEmpty(): n = q.dequeue() if q.isEmpty(): break; other.enqueue(n) return n

## Saturday, February 08, 2014

### queue with O(1) find() and delete()

Use deque and map.

[Hat tip to MB]

queue_mod<T> hashmap<T, Node> map // OR hashmap<T, queue<Node>> map for duplicates deque<T> dq enqueue(T x): n = dq.enqueue(x) map[x] = n T dequeue(): x = dq.dequeue() map.remove(x) return x bool find(T x): return map[x] != null delete(T x): n = map[x] map.remove[x] dq.delete(n) Node<T> T value Node next Node prev deque<T> Node head, tail Node enqueue(T x): n = new Node(x) if head == tail == null: head = tail = n else tail.next = n n.prev = tail tail = n return n T dequeue(): if head == tail == null: throw "empty" else if head == tail: n = head head = tail = null else n = head head = head.next n.next = head.prev = null return n.value delete(Node n): if n == null: throw "null" // adjust head / tail if head == tail == n: head = tail = null else if head == n: head = head.next else if tail == n: tail = tail.prev // handle next / prev prev = n.prev next = n.next if prev != null: prev.next = null if next != null: next.prev = null n.next = n.prev = null

[Hat tip to MB]

Labels:
algorithms,
data structures
Links to this post

## Tuesday, January 21, 2014

### fix cyclic linked list

Last node always forms the cycle in linked list. Get the meet node first (where slow and fast pointers meet), then the last node, and null its next.

cases:

node getCyclicLinkedListMeetNode(root): slow = root fast = root while fast != null && fast.next != null: slow = slow.next fast = fast.next.next if slow == fast: break meet = null if slow == fast meet = slow return meet void fixCyclicLinkedList(root): meet = getCyclicLinkedListMeetNode(root) // not cyclic if meet == null: return // if last node connects to root, then meet is root if meet == root: // go to last node last = root while last.next != root: last = last.next // else go to the last node from meet else: last = meet n = root while n.next != last.next: n = n.next last = last.next // fix last.next = null

cases:

// last connects to other than root meet 1-->2-->3 | | ----- meet 1-->2-->3-->4 | | ----- // last connects to root meet 1-->2-->3 | | --------- meet 1-->2 | | ----- meet 1-- | | ---

Labels:
algorithms,
data structures
Links to this post

Subscribe to:
Posts (Atom)

## Search This Blog

Loading...

## Blog Archive

## Contributors |