CareerCup

Building balanced BST from sorted array (Swift):

class Node {
    var data: Int
    var left: Node?
    var right: Node?
    
    init(data: Int, left: Node?, right: Node?) {
        self.data = data
        self.left = left
        self.right = right
    }
}

var arr = [1,2,3,4,5,6,7,8,9]

func buildTree(arr: [Int]) -> Node? {
    if arr.count == 0 {
        return nil
    }
    
    var mid = arr.count / 2
    
    var left : Node? = nil
    if mid > 0 {
        left = buildTree(Array(arr[0..<mid]))
    }
    var right : Node? = nil
    if mid < arr.count - 1 {
        right = buildTree(Array(arr[mid+1..<arr.count]))
    }
    let node = Node(data: arr[mid], left: left, right: right)
    return node
}

var root = buildTree(arr)

Trie for structured storing of words and getting them efficiently. And for each trie element which concludes a word an inverted index can be built.

Recursive solution in Swift with saving the string built so far :

var arr = Array("ABC".characters)
var permutations = [String]()

func computePerm(arr: [Character], prefix: String) {
    if arr.count == 0 {
        permutations.append(prefix)
    } else {
        var newPrefix = prefix
        for i in (0..<arr.count) {
            var newArr = arr
            newArr.removeAtIndex(i)
            computePerm(newArr, prefix: prefix + String(arr[i]))
        }
    }
}

computePerm(arr, prefix: "")
print(permutations)