---
# System prepended metadata

title: DGM Interview with Dren

---

# DGM Interview with Dren

### Fix the bugs in this function to count reachable nodes in a directed graph.

```typescript
type Node<T> = {
    value: T,
    children: Node<T>[]
}

/*
 * {
     value: 0,
     children: [
         {
         value: 1,
         children; []
        },
        {
         value: 2,
         children; []
        }
    ]
 * }
 */
 
 [...seen, root] = [seen[0], seen[1], ... seen[seen.length-1], root]

// arr =[0, 1, 2...]
// arr1 = arr.map(e => e + 1)

const countNodes<T> = (seen: Node<T>[]) => (root: Node<T>): number =>
    root.children
        .map(countNodes([...seen, root]))
        .reduce((sum, x) => sum + x, 0);
```

```php
class Node {
    public $value;
    public $children;
    
    // count how many nodes are reachable from this node including this node
    
    /*
     * {
         value: 0,
         children: [
             {
             value: 1,
             children: []
            },
            {
             value: 2,
             children: []
            }
        ]
     * }
     */
     
    /*
     * {
         value: 0,
         children: [
             {
                 value: 1,
                 children: [] // -> 0
             }
         ]
     * }
     */
    
    public countNodes($seen=[], $tree) {
        $n = 0;
        $seen[] = $tree;
        
        foreach($tree->children as $child) {
            $n += countNodes($seen, $child); // 0 -> 
        }
    
        return $n;
    }
    
}
```

```typescript
const singleton_loop: Node<null> = {value: null, children: [singleton_loop]};

countNodes(singleton_loop) === 1;
```
