Linked List Interview questions

Posted on May 29, 2008 by nolfonzo

I hadn’t done much programming for a while and thought I’d best brush up on some basic data structures and algorithm.

The following is from Programming Interviews Exposed. I implemented some of the Linked List stuff in the first section in Python. The code came out pretty close to the solutions in the book which were mainly in C++.

  1. class Stack:
  2. """
  3. Adapted from Programming Interviews Exposed problems
  4. LinkedList implementation that keeps track of head and tail
  6. Basic tests - push,pop,remove
  7. >>> s=Stack()
  8. >>> s.push(1)
  9. >>> s.push(2)
  10. >>> s.push(3)
  11. >>> s.push(4)
  12. >>> s.pop()
  13. 4
  14. >>> e=s.head.next
  15. >>> s.remove(e)
  16. True
  17. >>> s.head.data
  18. 3
  19. >>> s.tail.data
  20. 1
  21. >>> e=s.head.next
  22. >>> s.remove(e)
  23. True
  24. >>> s.head.data
  25. 3
  26. >>> s.tail.data
  27. 3
  28. >>> e=s.head
  29. >>> s.remove(e)
  30. True
  31. >>> s.head
  32. >>> s.tail
  33. """
  35. def __init__(self):
  36. self.head=None
  37. self.tail=None
  39. def push(self,data):
  40. if self.head==None:
  41. self.head=Element(data,None)
  42. self.tail=self.head
  43. else:
  44. self.head=Element(data,self.head)
  46. def pop(self):
  47. oldhead=self.head
  48. if oldhead==None:
  49. return None
  50. self.head=oldhead.next
  51. if self.head==None:
  52. self.tail=None
  53. return oldhead.data
  55. def remove(self,element):
  56. if self.head==None:
  57. return False
  58. if self.head==element:
  59. self.head=self.head.next
  60. if self.head==None:
  61. self.tail=None
  62. return True
  63. curr=self.head
  64. while curr!=None:
  65. if curr.next==element:
  66. curr.next=curr.next.next
  67. if curr.next==None:
  68. self.tail=curr
  69. return True
  70. else:
  71. curr=curr.next
  72. return False
  74. def insertAfter(self,element,data):
  75. """
  76. >>> s=Stack()
  77. >>> s.insertAfter(None,1)
  78. True
  79. >>> s.head.data
  80. 1
  81. >>> s.tail.data
  82. 1
  83. >>> s.insertAfter(None,2)
  84. True
  85. >>> s.head.data
  86. 2
  87. >>> s.tail.data
  88. 1
  89. >>> e=s.head
  90. >>> s.insertAfter(e,3)
  91. True
  92. >>> s.head.data
  93. 2
  94. >>> s.tail.data
  95. 1
  96. >>> s.head.next.data
  97. 3
  98. >>> e=s.tail
  99. >>> s.insertAfter(e,4)
  100. True
  101. >>> s.head.data
  102. 2
  103. >>> s.tail.data
  104. 4
  105. """
  106. if (element==None)|(self.head==None):
  107. self.head=Element(data,self.head)
  108. if self.head.next==None:
  109. self.tail=self.head
  110. return True
  111. curr=self.head
  112. while curr!=None:
  113. if curr==element:
  114. curr.next=Element(data,curr.next)
  115. if curr.next.next==None:
  116. self.tail=curr.next
  117. return True
  118. curr=curr.next
  119. return False
  121. def removeHead(self):
  122. """
  123. >>> s=Stack()
  124. >>> s.removeHead()
  125. >>> s.head
  126. >>> s.tail
  127. >>> s.push(1)
  128. >>> s.removeHead()
  129. >>> s.head
  130. >>> s.tail
  131. >>> s.push(1)
  132. >>> s.push(2)
  133. >>> s.removeHead()
  134. >>> s.head.data
  135. 1
  136. >>> s.tail.data
  137. 1
  138. """
  139. if self.head!=None:
  140. self.head=self.head.next
  141. if self.head==None:
  142. self.tail=None
  144. def findMToLastElement(self,m):
  145. """
  146. >>> s=Stack()
  147. >>> s.push(1)
  148. >>> s.push(2)
  149. >>> s.push(3)
  150. >>> s.findMToLastElement(0).data
  151. 1
  152. >>> s.findMToLastElement(1).data
  153. 2
  154. >>> s.findMToLastElement(2).data
  155. 3
  156. >>> s.findMToLastElement(3)
  157. """
  158. mToLast=None
  159. curr=self.head
  160. count=0
  161. while curr!=None:
  162. if count==m:
  163. mToLast=self.head
  164. if count>m:
  165. mToLast=mToLast.next
  166. if mToLast==None:
  167. return None
  168. curr=curr.next
  169. count+=1
  170. return mToLast
  172. class Element:
  173. def __init__(self,data,next=None):
  174. self.data=data
  175. self.next=next
  177. if __name__ == "__main__":
  178. import doctest
  179. doctest.testmod()
class Stack:
    """
    Adapted from Programming Interviews Exposed problems
    LinkedList implementation that keeps track of head and tail

    Basic tests - push,pop,remove
    >>> s=Stack()
    >>> s.push(1)
    >>> s.push(2)
    >>> s.push(3)
    >>> s.push(4)
    >>> s.pop()
    4
    >>> e=s.head.next
    >>> s.remove(e)
    True
    >>> s.head.data
    3
    >>> s.tail.data
    1
    >>> e=s.head.next
    >>> s.remove(e)
    True
    >>> s.head.data
    3
    >>> s.tail.data
    3
    >>> e=s.head
    >>> s.remove(e)
    True
    >>> s.head
    >>> s.tail
    """

    def __init__(self):
        self.head=None
        self.tail=None

    def push(self,data):
        if self.head==None:
            self.head=Element(data,None)
            self.tail=self.head
        else:
            self.head=Element(data,self.head)

    def pop(self):
        oldhead=self.head
        if oldhead==None:
            return None
        self.head=oldhead.next
        if self.head==None:
            self.tail=None
        return oldhead.data

    def remove(self,element):
        if self.head==None:
            return False
        if self.head==element:
            self.head=self.head.next
            if self.head==None:
                self.tail=None
            return True
        curr=self.head
        while curr!=None:
            if curr.next==element:
                curr.next=curr.next.next
                if curr.next==None:
                    self.tail=curr
                return True
            else:
                curr=curr.next
                return False

    def insertAfter(self,element,data):
        """
        >>> s=Stack()
        >>> s.insertAfter(None,1)
        True
        >>> s.head.data
        1
        >>> s.tail.data
        1
        >>> s.insertAfter(None,2)
        True
        >>> s.head.data
        2
        >>> s.tail.data
        1
        >>> e=s.head
        >>> s.insertAfter(e,3)
        True
        >>> s.head.data
        2
        >>> s.tail.data
        1
        >>> s.head.next.data
        3
        >>> e=s.tail
        >>> s.insertAfter(e,4)
        True
        >>> s.head.data
        2
        >>> s.tail.data
        4
        """
        if (element==None)|(self.head==None):
            self.head=Element(data,self.head)
            if self.head.next==None:
                self.tail=self.head
            return True
        curr=self.head
        while curr!=None:
            if curr==element:
                curr.next=Element(data,curr.next)
                if curr.next.next==None:
                    self.tail=curr.next
                return True
            curr=curr.next
        return False

    def removeHead(self):
        """
        >>> s=Stack()
        >>> s.removeHead()
        >>> s.head
        >>> s.tail
        >>> s.push(1)
        >>> s.removeHead()
        >>> s.head
        >>> s.tail
        >>> s.push(1)
        >>> s.push(2)
        >>> s.removeHead()
        >>> s.head.data
        1
        >>> s.tail.data
        1
        """
        if self.head!=None:
            self.head=self.head.next
        if self.head==None:
            self.tail=None

    def findMToLastElement(self,m):
        """
        >>> s=Stack()
        >>> s.push(1)
        >>> s.push(2)
        >>> s.push(3)
        >>> s.findMToLastElement(0).data
        1
        >>> s.findMToLastElement(1).data
        2
        >>> s.findMToLastElement(2).data
        3
        >>> s.findMToLastElement(3)
        """
        mToLast=None
        curr=self.head
        count=0
        while curr!=None:
            if count==m:
                mToLast=self.head
            if count>m:
                mToLast=mToLast.next
                if mToLast==None:
                    return None
            curr=curr.next
            count+=1
        return mToLast

class Element:
    def __init__(self,data,next=None):
        self.data=data
        self.next=next

if __name__ == "__main__":
    import doctest
    doctest.testmod()
This entry was posted in programming and tagged , , . Bookmark the permalink.

2 Responses to Linked List Interview questions

  1. Pol says:
    November 28, 2011 at 9:06 pm

    Just a minor comment:
    According to “Programming Interviews Exposed”,
    s.findMToLastElement(0).data should return the tail of the list and so s.findMToLastElement(1).data should return 2 in your test case.
    You can easily fix that in line 166 and 167.

  2. nolfonzo says:
    December 4, 2011 at 9:30 pm

    Thanks Pol.

    I think moving my count+=1 down to the end of the function fixes it (as corrected above)

Leave a Reply

Your email address will not be published. Required fields are marked *