exercises with chapter 2 of cracking the coding interview

2.0_.coffee

c = -> console.log.apply console, arguments

class Node
    constructor: (d) ->
        @next = null
        @data = d
    append_to_tail: (d)->
        end = new Node(d)
        n = @
        while (n.next isnt null)
            n = n.next
        n.next = end

delete_node = (head, d)->
    n = head
    if n.data is d
        return head.next
    while n.next isnt null
        if n.next.data is d
            n.next = n.next.next
            return head
        n = n.next

view_list = (head)->
    rayy = []
    n = head
    while (n isnt null)
        if n is undefined then return
        rayy.push n.data
        n = n.next
    return rayy

get_nth_element = (head, n)-> #same as find nth element from 2.2
    if n is 0 then return head
    cursor = head
    for i in [1 .. n]
        cursor = cursor.next
    return cursor

module.exports =
    Node: Node
    delete_node: delete_node
    view_list: view_list
    get_nth_element: get_nth_element

2.2_.coffee

c = -> console.log.apply console, arguments

{Node, delete_node, view_list} = require('./2.0_.coffee')

x = new Node(3)
x.append_to_tail 4
x.append_to_tail 5
x.append_to_tail 4
x.append_to_tail 7
x.append_to_tail 4
x.append_to_tail 7
x.append_to_tail 6
x.append_to_tail 8

c "2.2: Implement an algorithm to find the nth to last element of a singly linked list."


find_nth_element = (head, n)->
    if n is 0 then return head
    cursor = head
    for i in [1 .. n]
        cursor = cursor.next
    return cursor


find_nth_to_last__cursive_000 = (head, n)->
    c 'head', head
    y = find_nth_element(head, n)
    c 'y', y
    if y.next isnt null
        # c 'head', head
        return arguments.callee(head.next, n)
    else
        return head



z = find_nth_to_last__cursive_000(x, 4)

c(view_list(z))

c view_list(x) ; c "\n"




# c view_list(find_nth_element(x, 0))
# c view_list(find_nth_element(x, 1))
# c view_list(find_nth_element(x, 2))
# c view_list(find_nth_element(x, 3))
# c view_list(find_nth_element(x, 4))

2.3_.coffee

c = -> console.log.apply console, arguments

c "Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node. "
# this is simpler than the delete_node in 2.0 because we don't have to search
# for it; it's given.

{Node, delete_node, view_list, get_nth_element} = require('./2.0_.coffee')

x = new Node(3)
x.append_to_tail 4
x.append_to_tail 5
x.append_to_tail 4
x.append_to_tail 7
x.append_to_tail 4
x.append_to_tail 7
x.append_to_tail 6
x.append_to_tail 8


c view_list(x)


del_node = (node)->
    if node is null or node.next is null
        return false
    next = node.next
    node.data = next.data
    node.next = next.next
    return true

y = get_nth_element x, 3

c 'y', view_list(y)

del_node y

c 'now x', view_list(x)

2.4_.coffee

{Node, delete_node, view_list, get_nth_element, c} = require('./2.0_.coffee')

c "You have two numbers represented by a linked list, where each node contains a 
single digit. The digits are sntored in reverse order such taht the 1's digit 
is at th ehead of the list  Write a function that adds the two numbers and returns 
the sum as a linked list"

x = new Node(3) ; x.append_to_tail(1) ; x.append_to_tail(5)
y = new Node(5) ; y.append_to_tail(9) ; y.append_to_tail(2)

c x
c y

c view_list(x)
c view_list(y)

# have = true
# carry = off
# while have
#     x_cursor = x.data
#     y_cursor = y.data
#     z = x_cursor + y_cursor
#     c 'z', z
#     if carry
#         c 'carry is '
#         z += 1
#         c 'now z', z
#     if z > 9
#         z = z - 10
#         c 'z', z
#         carry = on
#     else
#         carry = off
#     x = x.next
#     y = y.next
#     c 'z finally::::::::::::::::::::::', z
#     if x is null
#         have = false

add_by_digits = (a, b)->
    ans = new Node(0)
    have_digits = true
    carry = off
    while have_digits
        if x is null
            x_cursor = 0
        else
            x_cursor = x.data
        if y is null
            y_cursor = 0
        else
            y_cursor = y.data
        z = x_cursor + y_cursor
        if carry
            z += 1
        if z > 9
            z = z - 10
            carry = on
        else
            carry = off
        # c 'x.next', x
        # c 'y.next', y
        ans.append_to_tail z
        x = x.next ; y = y.next
        if x is null and y is null
            # c 'have digits set to false'
            have_digits = false

    ans = ans.next

    return ans

test = add_by_digits x, y

c 'test', view_list(test)