1

I wrote the code for a circular buffer for an interviewstreet question. But as it happened, two testcases passed and the others are failing. The failure of the cause: index out f range. I tried several testcases after that to reproduce the failure. Unfortunately none of them reproduce the error. Here is the code.

Implement a circular buffer of size N. Allow the caller to append, remove and list the contents of the buffer. Implement the buffer to achieve maximum performance for each of the operations.

"A" n - Append the following n lines to the buffer. If the buffer is full they replace the older entries.
"R" n - Remove first n elements of the buffer. These n elements are the ones that were added earliest among the current elements.
"L" - List the elements of buffer in order of their inserting time.
"Q" - Quit. 

class circbuffer():

    #initialization
    def __init__(self,size):
            self.maximum=size
            self.data=[]
            self.current=0


    #appending when the buffer is not full
    def append(self,x):
            if len(self.data)==self.maximum:
                    self.current=0
                    self.data[self.current]=x
                    self.current=(self.current+1)%self.maximum
                    self.__class__=bufferfull
            else:
                    self.data.append(x)

    def remove(self,x):
            if self.data:
                    self.data.pop(0)

    def cget(self):
            return self.data

class bufferfull:

    def append(self,x):
            if len(self.data)<self.maximum:
                    self.data.insert(self.current, x)
            else:
                    self.data[self.current]=x
            self.current=(self.current+1)%self.maximum

    def remove(self,x):
            if self.data:
                    if self.current>len(self.data):
                            self.current=0
                    self.data.pop(self.current)

    def cget(self):
            return self.data[self.current:]+self.data[:self.current]
n=input()

buf=circbuffer(n)
outputbuf=[]

while True:
    com=raw_input().split(' ')
    if com[0]=='A':
            n=int(com[1])
            cominput=[]
            for i in xrange(n):
                    cominput.append(raw_input())
            for j in cominput:
                    buf.append(j)
    elif com[0]=="R":
            n=int(com[1])
            for i in range(n):
                    buf.remove(i)
    elif com[0]=="L":
            for i in buf.cget():
                    outputbuf.append(i)
    elif com[0]=="Q":
            break

for i in outputbuf:
    print i

The error is pointing to self.data.pop(self.current) in class bufferfull. I cannot get the test data from the interviewstreet people. I am trying to come up with testcase myself to reproduce the error.

Any insights?

Improve this question
8
  • 4
    I think you're making it unnecessarily difficult for yourself with that self.__class__ business. Commented Jul 2, 2013 at 19:18
  • @NPE, I will have to agree with you. I am new to Python and assigning a class to another got me pretty excited. Actually I am enamoured with Python..:) ! If there was a better way, I would really appreciate your help! Commented Jul 2, 2013 at 19:20
  • We have even less of a chance of coming up with an appropriate test case than you have being already familiar with your code... Commented Jul 2, 2013 at 19:20
  • 7
    Keep it simple. Don't be clever when you can be straightforward in the same number of lines. All you need is a head pointer, a tail pointer, and a list of a fixed size. You don't need any fancy metaprogramming stuff whatsoever. Commented Jul 2, 2013 at 19:20
  • Assigning to __class__ is silly. Design patterns (in here, you could do the same with a strategy) might seem like wanky overengineering but they communicate the purpose of the point of inflection and are less likely to of blow up in your face. Commented Jul 2, 2013 at 19:22

2 Answers 2

Reset to default
1

One bug is here:

def remove(self,x):
        if self.data:
                if self.current>len(self.data):
                        self.current=0
                self.data.pop(self.current)

If self.current == len(self.data), you'll try to pop a non-existent element.

As a general remark, your implementation is way too complicated and for that reason wouldn't score very highly in my book (others might view this differently). @9000's comment to your question sums it up nicely:

Keep it simple. Don't be clever when you can be straightforward in the same number of lines. All you need is a head pointer, a tail pointer, and a list of a fixed size. You don't need any fancy metaprogramming stuff whatsoever. – @9000

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I'm flattered :) These words are so generic / common sense, to my mind, that they don't need careful attribution. I'm definitely repeating countless engineers that told the same thing before me.
1

It looks like you are trying to stop the index out of range error with the code below, but the condition you are checking is wrong.

if self.current > len(self.data):
    self.current = 0
self.data.pop(self.current)

If you call self.data.pop(len(self.data)) you will definitely get that error since lists are 0-indexed. You probably meant:

if self.current >= len(self.data):
    self.current = 0
self.data.pop(self.current)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.