当前在线人数10326
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
骑驴找马结束,分享面试题回馈贵版
[版面:待字闺中][首篇作者:kepler84] , 2015年08月26日14:25:59 ,3477次阅读,16次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
kepler84
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: kepler84 (kepler84), 信区: JobHunting
标  题: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Wed Aug 26 14:25:59 2015, 美东)

为了防止违反NDA,就不列出公司名了,就是一些常见公司。

1. Write a iterator to iterate a nested array.
   For example, for given array: [1, 2, [3, [4, 5], [6, 7], 8], 9, 10]
   call iterator.next() 10 times should return 1,2,3,4,5,6,7,8,9,10.
   用了stack存(array, index)的tuple。

2. LeetCode 原题,120 - Triange。有一点变种,给的是一维数组。

3. Implement HashTable 主要看dynamic expanding

4. Implement MaxHeap.

5. Topology sort,就是版上常见的给一些排过序的未知语言的词,求该语言的字母序
。要求实现核心算法。可以给出一些helper function定义不需实现。

6. LeetCode 付费题 157 & 158 - Read N Characters Given Read4()。提供int
read4(char* buf),实现int read(char* buf, int len)。read4函数读至多4个字符,
除非EOF,并返回实际读到的字符个数。题没有难度要注意一些细节问题。

7. Given an array with length n + 1. The array contains numbers from 1 to n,
with one of the number duplicated. Now find the duplicated number.
   讨论各种解法以及时间空间复杂度,最后实现O(N)时间O(1)空间的解法。数组可以
mutate.

8. Given a bag of characters and a dictionary, find longest string that can
be constructed.

9. Given a grid of characters and a dictionary, find all possible words from
grid.
   以上两题都用的标准Trie树解法。讨论复杂度,和优化方案。

10. Given a grid with 'o' and 'x'. Find minimum steps from top-left to
bottom-right without touching 'x'.
   a) You can only move right or move down. (BFS or DP)
   b) You can move in all 4 directions. (BFS)

11. CS basics. Thread & Process, address space, how memory mapped file works
, etc.

同时感谢版上大牛们的内推:mitbbsfanfan, xjm,虽然都没有去成...

最后祝大家找工作顺利!


--
※ 修改:·kepler84 於 Aug 26 14:27:38 2015 修改本文·[FROM: 131.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 131.]

 
helloca
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: helloca (helloca), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Wed Aug 26 14:38:11 2015, 美东)

恭喜!
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 71.]

 
jobhunter123
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: jobhunter123 (jobhunting), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Wed Aug 26 16:34:59 2015, 美东)

恭喜,请问是几年工作经验?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 157.]

 
liunicv
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: liunicv (liunicv), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Wed Aug 26 18:18:05 2015, 美东)

Write a iterator to iterate a nested array.
能不能稍微详细讲下怎么运用stack的啊?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 132.]

 
adp10
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: adp10 (w41q), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Wed Aug 26 18:33:09 2015, 美东)

mark
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 68.]

 
saric
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: saric (saric), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Wed Aug 26 18:38:34 2015, 美东)

第一题如果是用cpp,输入咋个弄法

【 在 kepler84 (kepler84) 的大作中提到: 】
: 为了防止违反NDA,就不列出公司名了,就是一些常见公司。
: 1. Write a iterator to iterate a nested array.
:    For example, for given array: [1, 2, [3, [4, 5], [6, 7], 8], 9, 10]
:    call iterator.next() 10 times should return 1,2,3,4,5,6,7,8,9,10.
:    用了stack存(array, index)的tuple。
: 2. LeetCode 原题,120 - Triange。有一点变种,给的是一维数组。
: 3. Implement HashTable 主要看dynamic expanding
: 4. Implement MaxHeap.
: 5. Topology sort,就是版上常见的给一些排过序的未知语言的词,求该语言的字母序
: 。要求实现核心算法。可以给出一些helper function定义不需实现。
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 192.]

 
adp10
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: adp10 (w41q), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Wed Aug 26 19:09:19 2015, 美东)


【 在 kepler84 (kepler84) 的大作中提到: 】
: 为了防止违反NDA,就不列出公司名了,就是一些常见公司。
: 1. Write a iterator to iterate a nested array.
:    For example, for given array: [1, 2, [3, [4, 5], [6, 7], 8], 9, 10]
:    call iterator.next() 10 times should return 1,2,3,4,5,6,7,8,9,10.
:    用了stack存(array, index)的tuple。
: 2. LeetCode 原题,120 - Triange。有一点变种,给的是一维数组。
: 3. Implement HashTable 主要看dynamic expanding
: 4. Implement MaxHeap.
: 5. Topology sort,就是版上常见的给一些排过序的未知语言的词,求该语言的字母序
: 。要求实现核心算法。可以给出一些helper function定义不需实现。
: ...................


请问hashmap用closed hashing可以么?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 68.]

 
dalianmaomao
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: dalianmaomao (大脸猫), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Wed Aug 26 20:51:47 2015, 美东)

没想出怎么用stack, 大牛讲解一下?
"""
Write a iterator to iterate a nested array.
   For example, for given array: [1, 2, [3, [4, 5], [6, 7], 8], 9, 10]
   call iterator.next() 10 times should return 1,2,3,4,5,6,7,8,9,10.
"""
def traverse(l):
  if not l:
    return
  for i in l:
    if isinstance(i, list):
      traverse(i)
    else:
      print i

class NestIterator(object):

  def __init__(self, l):
    self.l = l
    self.cur = -1
    self.iterator = None
       
  def next(self):
    if self.iterator and self.iterator._has_next_element():
      return self.iterator.next()
    else:
      self.iterator = None
      if self.cur >= len(self.l)-1:
        return None
      self.cur += 1
      if isinstance(self.l[self.cur], list):
        self.iterator = NestIterator(self.l[self.cur])
        if self.iterator._has_next_element():
          return self.iterator.next()
        else:
          self.iterator = None
          if self._has_next_element():
            return self.next()
          else:
            return None
      else:
        return self.l[self.cur]

  def _has_next_element(self):
    """It is impossible to know if there is next value."""
    if (self.cur + 1 <= len(self.l) - 1 or
        bool(self.iterator and self.iterator._has_next_element())):
      return True
    return False


def print_with_iter(l):
  iter = NestIterator(l)
  for i in range(100):
    ele = iter.next()
    if ele:
      print 'output:', ele
  print '================'



if __name__=='__main__':
  traverse([1, 2, [3, [4, 5], [6, 7], 8], 9, 10])
  print_with_iter([1, 2, [3, [4, 5], [6, 7], 8], 9, 10])
  print_with_iter([1, 2, [], [3, [4, 5], [6, 7], 8], 9, [11, 12, 15],10, []])
       


数据验证:
output: 1
output: 2
output: 3
output: 4
output: 5
output: 6
output: 7
output: 8
output: 9
output: 10
================
output: 1
output: 2
output: 3
output: 4
output: 5
output: 6
output: 7
output: 8
output: 9
output: 11
output: 12
output: 15
output: 10
================



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 104.]

 
qillura
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: qillura (qillura), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Thu Aug 27 14:24:23 2015, 美东)

恭喜!

--
☆ 发自 iPhone 买买提 1.22.06
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 199.]

 
kepler84
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: kepler84 (kepler84), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Thu Aug 27 15:21:03 2015, 美东)

哈哈,我当时面的时候也随口说了一句,这题cpp不好搞啊,结果他说well, let's do
it in cpp then. 当时心里一万个草泥马奔腾啊!

其实cpp需要一个好的表示方式,代码写起来倒也还简单,就是构造数组比较费行数。

mitbbs代码太难看了,放到gist上:
https://gist.github.com/anonymous/9bcbe32ed4405fa7978f

【 在 saric (saric) 的大作中提到: 】
: 第一题如果是用cpp,输入咋个弄法





--
※ 修改:·kepler84 於 Aug 27 15:24:14 2015 修改本文·[FROM: 131.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 131.]

 
kepler84
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: kepler84 (kepler84), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Thu Aug 27 15:31:02 2015, 美东)

这个和tree的iterator是一样的,stack里放(数组,当前下标)。一开始把整个数据放
进去,下标是0。next()的时候看当前元素是数字还是数组。如果是数字就输出,是数
组的话把数组push到stack里去。当前数组做完了就pop出来。记得正确更新下标就行了。

代码见:

https://gist.github.com/anonymous/9bcbe32ed4405fa7978f

【 在 liunicv (liunicv) 的大作中提到: 】
: Write a iterator to iterate a nested array.
: 能不能稍微详细讲下怎么运用stack的啊?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 131.]

 
fengyu225
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: fengyu225 (yfeng), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Thu Aug 27 19:11:45 2015, 美东)

如果用python的话stack里不用放当前下标。当栈顶是数组的话就弹出数组, 然后逆序
入栈。以下是python代码,假定只有list 和 basic type 两种类型

class ListIter(object):
    def __init__(self, lst):
        self.stack = [lst]

    def next(self):
        if len(self.stack) == 0:
            raise StopIteration
        while isinstance(self.stack[-1],list):
            l = self.stack.pop()
            self.stack.extend([i for i in reversed(l) if not isinstance(i,
list) or len(i)>0])
            if len(self.stack) == 0:
                raise StopIteration
        return self.stack.pop()

    def __iter__(self):
        return self


--
※ 修改:·fengyu225 於 Aug 27 22:05:20 2015 修改本文·[FROM: 66.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 66.]

 
vincentxia
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: vincentxia (smallshrimp), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Thu Aug 27 19:54:40 2015, 美东)

不需要用stack,两个指针足够。

class Iterator:
   
    def __init__(self, arr):
        self.arr = arr
        self.major = 0
        self.minor = -1
   
    def next(self):
        if type(self.arr[self.major]) != list:
            val = self.arr[self.major]
            self.major += 1
            self.minor = -1
            return val
        else:
            self.minor += 1
            if self.minor >= len(self.arr[self.major]):
                self.major += 1
                self.minor = -1
                return self.next()
            else:
                val = self.arr[self.major][self.minor]
                return val
   
    def hasNext(self):
        #print self.major, self.minor, '////////////'
        if self.major >= len(self.arr):
            return False
        elif self.major == len(self.arr) - 1:
            if type(self.arr[-1]) == list and self.minor >= len(self.arr[-1]
) - 1:
                return False
        return True
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 63.]

 
dalianmaomao
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: dalianmaomao (大脸猫), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Fri Aug 28 19:45:53 2015, 美东)

原来大家都喜欢python啊, 哈哈

不过明显stack 的清晰很多。 我还是和大牛有很大差距。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 216.]

 
chinajordan
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: chinajordan (chinajordan), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Sat Aug 29 15:08:07 2015, 美东)

楼主能不能说下8的解法?还有时间复杂度?这种要递归的怎么分析复杂度我一直不太
会。还有9的复杂度?


--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 166.]

 
repast
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: repast (xebec), 信区: JobHunting
标  题: Re: 骑驴找马结束,分享面试题回馈贵版
发信站: BBS 未名空间站 (Sat Aug 29 17:35:33 2015, 美东)

第一题最简,最快写法应该是这样,直接了当。
太多人把 python 当 java 写了,除非限制了不让递归。

def iflatten(iterable):
    for item in iterable:
        try:
            for j in iflatten(item):
                yield j
        except TypeError:
            yield item



--
※ 修改:·repast 於 Aug 29 20:52:22 2015 修改本文·[FROM: 76.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

[分页:1 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996