CTCI_001

Just a note

Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Không dùng thêm DS nên không dùng hash table.
Sử dụng một mảng char_set có length = 128 để flag = False của 128 kí tự ASCII. Sau đó duyệt string (O(N)) và kiểm tra xem vị trí char_set[ord(kí tự trong string)] đang False hay True. Nếu False có nghĩa là chưa được bật cờ, bật lên True. Nếu True có nghĩa là đã bật cờ trước đó rồi, tương đương đã tồn tại trong các kí tự string trước.

Code : Python

def unique(string):
    # Assuming character set is ASCII (128 characters)
    if len(string) > 128:
        return False

    char_set = [False for _ in range(128)]
    for char in string:
        val = ord(char)
        if char_set[val]:
            # Char already found in string
            return False
        char_set[val] = True

    return True

LinkedList

Remove Dups: Write code to remove duplicates from an unsorted linked list? FOLLOW UP ? How would you solve this problem if a temporary buffer is not allowed?

Có nhiều cách. Trong đó có thể:

1. Tạo thêm 1 mảng để lưu từng data của mỗi node. kiểm tra data của node->next có nằm trong mảng kia chưa, nếu có thì xóa.
   Cách này C: O(N) và S: O(N)
2. Sort linked list đó trước (O(nlog(n))) và xóa theo cách xét next node liên tiếp (O(N)) => C: O(nlog(n)) S: O(1)
3. O(N^2). Gặp 1 node, giữ data, chạy hết list lần nữa.

Return Kth to Last: Implement an algorithm to find the kth to last element of a singly linked list.

Cho 1 con chạy runner chạy đến Kth trước. sau đó cho cả 2 con trỏ current và runner cùng chạy. runner chạm tail cũng là lúc current đến tail - Kth