---
# System prepended metadata

title: Interview - Phan Trung Thanh

---

# Interview - Phan Trung Thanh

## Question 1
Given an array of random positive numbers, move all the zeroes to the left of the array. 

```
Input :  arr[] = {0, 1, 2, 5, 0, 3, 0, 3};
Output : arr[] = {0, 0, 0, 1, 2, 5, 3, 3};

Input:  arr[] = {0}
Output: arr[] = {0}

Input:  arr[] = {0,1,0,3,12}
Output: arr[] = {0,0,1,3,12}
```

### Answer
```
package main

import "fmt"

func main() {
	// input := []int{0, 1, 2, 5, 0, 3, 0, 3}

	// solution 1
	// nonZeroArr := []int{}
	// zeroArr := []int{}

	// for i := 0; i < len(input); i++ {
	// 	if input[i] == 0 {
	// 		zeroArr = append(zeroArr, input[i])
	// 	} else {
	// 		nonZeroArr = append(nonZeroArr, input[i])
	// 	}
	// }

	// result := []int{}
	// result = append(result, zeroArr...)
	// result = append(result, nonZeroArr...)

	// for _, item := range result {
	// 	fmt.Printf("%d ", item)
	// }

	// input := []int{0, 1, 2, 5, 0, 3, 0, 3}
	// input := []int{0, 1, 0, 3, 12}
	input := []int{0}
	for i := 0; i < len(input); i++ {
		if input[i] == 0 {
			idx := i
			for j := idx - 1; j >= 0; j-- {
				input[j], input[idx] = input[idx], input[j]
				idx -= 1
			}
		}
	}
	// O(n^2)
	// Space O(n)
	for _, item := range input {
		fmt.Printf("%d ", item)
	}
```
}


## Question 2

```
//        1 <---- root
//     /     \
//    2       3
//   / \     / \
//  4   5   6   7
//
//
// 1) create the node type
// 2) write a function to print tree by level 
// ie. print "1,2,3,4,5,6,7"
```

### Answer
```

package main

import "fmt"

func main() {
	// left1 := &Node{
	// 	Value: 2,
	// }
	right1 := &Node{
		Value: 3,
	}
	root := &Node{
		Value: 1,
		// LeftNode: left1,
		RighNode: right1,
	}

	BFS(root)
}

func BFS(root *Node) {
	if root == nil {
		return
	}

	q := &Queue{}
	q.Push(root)

	for !q.IsEmpty() {
		current := q.Pop()
		fmt.Printf("%d ", current.Value)
		if current.LeftNode != nil {
			q.Push(current.LeftNode)
		}
		if current.RighNode != nil {
			q.Push(current.RighNode)
		}
		fmt.Println()
	}

	// Time O(n)
	// Space O(n)
}

type Node struct {
	Value    int
	LeftNode *Node
	RighNode *Node
}

type Queue struct {
	Value []*Node
}

func (q *Queue) IsEmpty() bool {
	return q.Size() == 0
}

func (q *Queue) Push(node *Node) {
	q.Value = append(q.Value, node)
}

func (q *Queue) Size() int {
	return len(q.Value)
}

func (q *Queue) Pop() *Node {
	result := q.Value[0]
	q.Value = q.Value[0+1:]

	return result
}
```
