0
$\begingroup$

Problem: Design a data-structure $BankAccount$ that supports the following operations in $ \underline{\text{constant time complexity}} $. Meaning $O(1) $.

  • $Init()$ - initializes bank account $L$ with $0$ dollars.
  • $Receive(L,d)$ - adds to the account balance $ d $ dollars.
  • $Send(L,d)$ - decreases from the account balance $d$ dollars.
  • $BestBalance(L)$ - returns the maximal account balance that had been so far on this bank account.
  • $Undo(L)$ - cancels the last operation that had been committed ( out of Send/Recieve ) as if like that operation had never occured.

Pay attention that multiple $Undo$ operations can be done continuously. In addition, the bank account's balance can be negative.

Attempt: ( With regards to the context of question above, I've learned about List ADT and it's implementations: linked lists, arrays.)

Init():
   L.sum = 0
   L.max = 0
   L.last= ('',0)

Recieve(L,d):
   L.sum += d
   if L.max < L.sum:
      L.max = L.sum
   L.last = ['Recieve',d]

Send(L,d):
   L.sum -= d
   L.last =['Send',d]

BestBalance(L):
   return L.max

Undo(L):
   if L.last[0] == 'Recieve':
      Send(L,L.last[1])
   else:
      Retrieve(L,L.last[1])

All of the above implementations run in $O(1)$, there is no list implementation in the above but only an object's and some object field definition. I'm not sure if the above is correct but I don't understand why, can you please tell me? Also, I thought of another interpretation to the answer and that is to store all the operations in a list, but I'm not sure.
In anycase, any help will be appreciated!

Edit:
Well, my friend has implemented the above data-structure using a linked-list and I've not encountered an example from my class which tells me to implement a data-structure in such a way as to not having to use a list, so these raised my suspicions, so I'm worried that my answer might be wrong. In any-case, from what I've understood, his idea was as follows:

$ \underline{\text{data-structure:}} $ Use circular linked-list. In every node of the list itself, in addition to the value, we'll save another field and in it the maximal value out of all the nodes in the list, we'll call this field $max$.

$ \underline{\text{operation implementation:}} $
Init(L,d) - create an empty linked-list.
Recieve(L,d) - insert $ d $ to the list ( and update its max field ).
Send(L,d) - remove that last element that was inserted into the list ( and update its max field ).
BestBalance(L) - return the value of the max field of the last inserted node.
Undo(L) - removes the last inserted node into the list ( and update the fields of the node preceding it ).

Obviously the above implementation and mine are way off and so, maybe I've misunderstood how I should've approached the problem?. The reason I haven't thought of using a list is because I don't see it as necessary to insert values into a list as we care of the latest values only.

$\endgroup$
12
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – Nathaniel
    Mar 11 at 21:24
  • $\begingroup$ My conceptual issue is part of the question which I must answer in order to learn. How else can one learn the specifics of a concept if he won't exercise such generalities? I can't learn if I'll leave the attempt as it is since I don't know if it is correct and if there is something else to take a bigger peak on at the problem. I can't seek a teacher since I've already been at his office hours and I've got help to other questions I had ( and he is not admitting any more hours any time soon ) and I've seeked friends but from what I've seen it doesn't seem they're answer is acceptable. $\endgroup$ Mar 11 at 22:23
  • $\begingroup$ My teacher didn't teach this subject in an organized way and the whole class struggles with it. Needless to say I've found little information in books regarding extended discussions on ADT's and their implementations, and the few questions that I had seen on stackexchange haven't been able to answer my question because the subject is problem dependent ( as in most dynamic programming problems ) and is scarcely discussed from what I've searched. $\endgroup$ Mar 11 at 22:30
  • $\begingroup$ So I don't think it is a "specific question", but rather it is a conceptual question which stems from an example from a pool of examples intended to teach the subject ( as it is such a subject that whoever learns it must learn it in that way, unlike some other subjects/topics where one can mind of to his bussiness for sometime after learning the basics and he'll have the answer later. ). I'm not being hostile, I'm trying to explain that my question's ambient is different from the cases you've unfolded before me. $\endgroup$ Mar 11 at 22:30
  • $\begingroup$ read up on stacks ,direct address tables and hash tables and try to approach the problem again. $\endgroup$
    – Rinkesh P
    Mar 12 at 4:47

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.