聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1112|回复: 4
收起左侧

[CS61A]Lab07

[复制链接] |试试Instant~ |关注本帖
sky420 发表于 2015-6-1 14:40:25 | 显示全部楼层 |阅读模式

[其他]CS61A #3 - 04@UCBerkely

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
Lab Link: http://gaotx.com/cs61a/lab/lab07/
My solution: http://gaotx.com/blogs/2015/05/28/cs61a-lab07/

评分

1

查看全部评分

karte_polo 发表于 2015-6-3 23:33:32 | 显示全部楼层
def insert(link, value, index):
    """Insert a value into a Link at the given index.

    >>> link = Link(1, Link(2, Link(3)))
    >>> insert(link, 9001, 0)
    >>> link
    Link(9001, Link(1, Link(2, Link(3))))
    >>> insert(link, 100, 2)
    >>> link
    Link(9001, Link(1, Link(100, Link(2, Link(3)))))
    >>> insert(link, 4, 5)
    Index out of bounds!
    """
    "*** YOUR CODE HERE ***"
    if index == 0:
        link.rest = Link(link.first,link.rest)
        link.first = value
    elif index > len(link):
        return 'Index out of bounds!'
    else:
        insert(link.rest,value,index-1)

class Tree:
    def __init__(self, entry, branches=()):
        self.entry = entry
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = branches

    def __repr__(self):
        if self.branches:
            branches_str = ', ' + repr(self.branches)
        else:
            branches_str = ''
        return 'Tree({0}{1})'.format(self.entry, branches_str)

    def is_leaf(self):
        return not self.branches

def square_tree(t):
    """Mutates a Tree t by squaring all its elements.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> square_tree(t)
    >>> t
    Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
    """
    "*** YOUR CODE HERE ***"
    t.entry = t.entry**2
    for b in t.branches:
        square_tree(b)

def list_to_link(lst):
    """Takes a Python list and returns a Link with the same elements.

    >>> list_to_link([1, 2, 3])
    Link(1, Link(2, Link(3)))
    """
    "*** YOUR CODE HERE ***"
    if lst:
        return Link(lst[0],list_to_link(lst[1:]))
    else:
        return Link.empty

def link_to_list(link):
    """Takes a Link and returns a Python list with the same elements.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> link_to_list(link)
    [1, 2, 3, 4]
    >>> link_to_list(Link.empty)
    []
    """
    "*** YOUR CODE HERE ***"
    if link is Link.empty:
        return []
    else:
        return [link.first]+link_to_list(link.rest)

def mutate_reverse(link):
    """Mutates the Link so that its elements are reversed.

    >>> link = Link(1)
    >>> mutate_reverse(link)
    >>> link
    Link(1)

    >>> link = Link(1, Link(2, Link(3)))
    >>> mutate_reverse(link)
    >>> link
    Link(3, Link(2, Link(1)))
    """
    "*** YOUR CODE HERE ***"
    def digin(l,n):
        if n==0:
            return l
        else:
            return digin(l.rest,n-1)
    n = len(link)
    i = 0
    while i<=n//2-1:
        t = link[i]
        digin(link,i).first = link[n-i-1]
        digin(link,n-i-1).first = t
        i+=1

def leaves(t):
    """Returns a list of all the entries of the leaf nodes of the Tree t.

    >>> leaves(Tree(1))
    [1]
    >>> leaves(Tree(1, [Tree(2, [Tree(3)]), Tree(4)]))
    [3, 4]
    """
    "*** YOUR CODE HERE ***"
    if t.is_leaf():
        return [t.entry]
    else:
        r=[]
        for b in t.branches:
            r+=leaves(b)
    return r


def cumulative_sum(t):
    """Return a new Tree, where each entry is the sum of all entries in the
    corresponding subtree of t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative = cumulative_sum(t)
    >>> t
    Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(Tree(1))
    Tree(1)
    """
    "*** YOUR CODE HERE ***"
    branches = [cumulative_sum(st) for st in t.branches]
    nt = Tree(sum(st.entry for st in branches)+t.entry,branches)
    return nt

def same_shape(t1, t2):
    """Returns whether two Trees t1, t2 have the same shape. Two trees have the
    same shape if they have the same number of branches and each of their
    children have the same shape.

    >>> t, s = Tree(1), Tree(3)
    >>> same_shape(t, t)
    True
    >>> same_shape(t, s)
    True
    >>> t = Tree(1, [Tree(2), Tree(3)])
    >>> same_shape(t, s)
    False
    >>> s = cumulative_sum(t)
    >>> same_shape(t, s)
    True
    """
    "*** YOUR CODE HERE ***"
    if not (t1.is_leaf() and t2.is_leaf()):
        b1,b2 = t1.branches,t2.branches
        is_equal = len(b1)==len(b2)
        sub_equal =[same_shape(x,y) for x,y in zip(b1,b2)]
        return is_equal and (False in sub_equal)
    return True
   
def foldl(link, fn, z):
    """ Left fold
    >>> lst = Link(3, Link(2, Link(1)))
    >>> foldl(lst, sub, 0) # (((0 - 3) - 2) - 1)
    -6
    >>> foldl(lst, add, 0) # (((0 + 3) + 2) + 1)
    6
    >>> foldl(lst, mul, 1) # (((1 * 3) * 2) * 1)
    6
    """
    if link is Link.empty:
        return z
    "*** YOUR CODE HERE ***"
    return foldl(link.rest, fn, fn(z,link.first))        
        

def foldr(link, fn, z):
    """ Right fold
    >>> lst = Link(3, Link(2, Link(1)))
    >>> foldr(lst, sub, 0) # (3 - (2 - (1 - 0)))
    2
    >>> foldr(lst, add, 0) # (3 + (2 + (1 + 0)))
    6
    >>> foldr(lst, mul, 1) # (3 * (2 * (1 * 1)))
    6
    """
    "*** YOUR CODE HERE ***"
    if link is Link.empty:
        return z
    return fn(link.first,foldr(link.rest,fn,z))

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
西风吹草 发表于 2015-6-5 02:59:35 | 显示全部楼层
Question 2:
def insert(link, value, index):
        if index >= len(link):
                print('Index out of bounds!')
        elif index == 0:
                link.rest = Link(link.first, link.rest)
                link.first = value
        else:
                insert(link.rest, value, index - 1)

Question 4:
def square_tree(t):
        t.entry = t.entry ** 2
        if t.branches:
                for branch in t.branches:
                        square_tree(branch)

Question 5:
def list_to_link(lst):
        if not lst:
                return Link.empty
        return Link(lst[0], list_to_link(lst[1:]))

Question 6:
def link_to_list(link):
        if link is Link.empty:
                return []
        return [link.first] + link_to_list(link.rest)

Question 7:
def reverse(link):
        lst = link_to_list(link)
        lst.reverse()
        return list_to_link(lst)

Question 8:
def leaves(t):
        if t.is_leaf():
                return [t.entry]
        else:
                return sum([leaves(branch) for branch in t.branches], [])

Question 9:
def cumulative_sum(t):
        new_branches = [cumulative_sum(subtree) for subtree in t.branches]
        new_entry = sum(subtree.entry for subtree in new_branches) + t.entry
        return Tree(new_entry, new_branches)

Question 11:
def foldl(link, fn, z):
        if link is Link.empty:
                return z
        return foldl(link.rest, fn, fn(z, link.first))

Question 12:
def foldr(link, fn, z):
        if link is Link.empty:
                return z
        return fn(link.first, foldr(link.rest, fn, z))

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

wuxiaomin98 发表于 2015-6-6 05:31:11 | 显示全部楼层
## Recursive Objects ##

# Linked Lists

class Link:
    """A linked list.

    >>> s = Link(1, Link(2, Link(3, Link(4))))
    >>> len(s)
    4
    >>> s[2]
    3
    >>> s
    Link(1, Link(2, Link(3, Link(4))))
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __getitem__(self, i):
        if i == 0:
            return self.first
        else:
            return self.rest[i-1]

    def __len__(self):
        return 1 + len(self.rest)

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_str = ', ' + repr(self.rest)
        else:
            rest_str = ''
        return 'Link({0}{1})'.format(repr(self.first), rest_str)

def insert(link, value, index):
    """Insert a value into a Link at the given index.

    >>> link = Link(1, Link(2, Link(3)))
    >>> insert(link, 9001, 0)
    >>> link
    Link(9001, Link(1, Link(2, Link(3))))
    >>> insert(link, 100, 2)
    >>> link
    Link(9001, Link(1, Link(100, Link(2, Link(3)))))
    >>> insert(link, 4, 5)
    Index out of bounds!
    """
    "*** YOUR CODE HERE ***"
    if index == 0:
        link.rest = Link(link.first, link.rest)
        link.first = value
    elif link.rest is Link.empty:
        print('Index out of bounds!')
    else:
        insert(link.rest, value, index - 1)

# Trees

class Tree:
    def __init__(self, entry, branches=()):
        self.entry = entry
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = branches

    def __repr__(self):
        if self.branches:
            branches_str = ', ' + repr(self.branches)
        else:
            branches_str = ''
        return 'Tree({0}{1})'.format(self.entry, branches_str)

    def is_leaf(self):
        return not self.branches

def square_tree(t):
    """Mutates a Tree t by squaring all its elements.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> square_tree(t)
    >>> t
    Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
    """
    "*** YOUR CODE HERE ***"
    t.entry = t.entry ** 2
    for subtree in t.branches:
        square_tree(subtree)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

liyimeng 发表于 2016-2-21 12:09:35 | 显示全部楼层
偷懒只把必做题做了。。Extra就没有理。。。
lab07.png

代码:
lab07.py
  1. ## Recursive Objects ##

  2. # Linked Lists

  3. class Link:
  4.         """A linked list.

  5.         >>> s = Link(1, Link(2, Link(3, Link(4))))
  6.         >>> len(s)
  7.         4
  8.         >>> s[2]
  9.         3
  10.         >>> s
  11.         Link(1, Link(2, Link(3, Link(4))))
  12.         """
  13.         empty = ()

  14.         def __init__(self, first, rest=empty):
  15.                 assert rest is Link.empty or isinstance(rest, Link)
  16.                 self.first = first
  17.                 self.rest = rest

  18.         def __getitem__(self, i):
  19.                 if i == 0:
  20.                         return self.first
  21.                 else:
  22.                         return self.rest[i-1]

  23.         def __len__(self):
  24.                 return 1 + len(self.rest)

  25.         def __repr__(self):
  26.                 if self.rest is not Link.empty:
  27.                         rest_str = ', ' + repr(self.rest)
  28.                 else:
  29.                         rest_str = ''
  30.                 return 'Link({0}{1})'.format(repr(self.first), rest_str)

  31. def insert(link, value, index):
  32.         """Insert a value into a Link at the given index.

  33.         >>> link = Link(1, Link(2, Link(3)))
  34.         >>> insert(link, 9001, 0)
  35.         >>> link
  36.         Link(9001, Link(1, Link(2, Link(3))))
  37.         >>> insert(link, 100, 2)
  38.         >>> link
  39.         Link(9001, Link(1, Link(100, Link(2, Link(3)))))
  40.         >>> insert(link, 4, 5)
  41.         Index out of bounds!
  42.         """
  43.         "*** YOUR CODE HERE ***"
  44.         if index >= len(link):
  45.                 print("Index out of bounds!")
  46.                 return
  47.         i = 0
  48.         while i < index:
  49.                 link = link.rest
  50.                 i += 1
  51.         other = Link(link.first, link.rest)
  52.         link.first = value
  53.         link.rest = other

  54. # Trees

  55. class Tree:
  56.     def __init__(self, entry, branches=()):
  57.         self.entry = entry
  58.         for branch in branches:
  59.             assert isinstance(branch, Tree)
  60.         self.branches = branches

  61.     def __repr__(self):
  62.         if self.branches:
  63.             branches_str = ', ' + repr(self.branches)
  64.         else:
  65.             branches_str = ''
  66.         return 'Tree({0}{1})'.format(self.entry, branches_str)

  67.     def is_leaf(self):
  68.         return not self.branches

  69. def square_tree(t):
  70.         """Mutates a Tree t by squaring all its elements.

  71.         >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
  72.         >>> square_tree(t)
  73.         >>> t
  74.         Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
  75.         """
  76.         "*** YOUR CODE HERE ***"
  77.         t.entry *= t.entry
  78.         for branch in t.branches:
  79.                 square_tree(branch)
  80.                
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 22:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表