Category "Web"

Implementing Stack using List in Python – Python Programming Essentials

- - Web


Stack is a collection of objects inserted and removed in a last-in first-out fashion (LIFO). Objects can be inserted onto stack at any time but only the object inserted last can be accessed or removed which coins the object to be top of the stack.

Realization of Stack Operations using List


Methods Realization using List Running Time
S.push(e) L.append(e) O(1)*
S.pop() L.pop() O(1)* L[-1] O(1)
S.isempty() len(L) == 0 O(1)
len(S) len(L) O(1)

What is O(1)* ?

The running time for push and pop operations are given O(1)* in the above table. This is known as amortization. It is a principle used in complexity analysis of data structures and algorithms. It should be used carefully and for special cases only.

Why did we use amortized analysis for push/pop?

The list(our stack’s underlying data structure) is a series of objects which eventually are realized by arrays. The objects are stored in a continuous block of memory which offers indexing property for lists. As such, a list cannot occupy the entire memory but restricts to some specific size. When there is no more space for the objects to be added to the end of the list, a new memory series is allocated with the increased size, all the objects are copied to the new allocation and new object is added next to the last object of the current series. The previously held memory is then released free. Here, on every append, resizing of list is not required but true once in a while. Hence the running time of append in list (push on stack) for most elements is O(1) but as a whole in an amortized sense, it is O(1)* which accounts for the timely resizing and copying of elements.

Similarly for pop operations, shrinking of the underlying list is done once in a while therefore accounting for an amortized complexity of O(1)*

Implementation of Stack using List


class ListStack:
    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)

    def isempty(self):
        return len(self._data) == 0

    def top(self):
        return self._data[-1]

    def push(self, e):

    def pop(self):
        return self._data.pop()


Stack is an important data structure for realizing solutions to various programming problems. As such, it is even more essential to understand the running time evaluations and working mechanism of these data structures.

Follow me on github Github

Hire me for a project Fiverr

How To Swap Values Without Temporary Variable

- - Web
My dear readers, this article will be invested in explaining about swapping two integers without the use of temporary variable. The reason I am writing this article is because it has been asked several times in an interview for a CS internship/job. In fact, a friend of mine who applied for an internship at a local company was asked the same question. The problem tends to test your analytical skills as well as understanding of programming fundamentals. However, in practice one should never use the following approaches which I will explain why towards the end of the article.


Starting with no further delay, there are two approaches to the problem.

1. Using XOR operator

2. Using addition and subtraction operators

Throughout the article we use ‘^’ symbol for representing XOR.

Below is a table showing the results of XOR operation

0 0 0
0 1 1
1 0 1
1 1 0

This concludes that for different value of A and B, the XOR operation gives 1 while it gives 0 for the same value of A and B.

XOR also termed as exclusive-or has following properties

1. Self – inversed

A ^ A = 0

Any value XOR’d with itself gives 0.

2. Identity

A ^ 0 = A

Any value XOR’d with 0 remains unchanged.

3. Associative

A ^ (B ^ C) = (A ^ B) ^ C

The order does not matter.

4. Commutative

A ^ B = B ^ A

How to swap two integers using XOR

It is simple and underlies on the above mentioned properties/principles.

Say for an instance a = 2 and b = 3

The XOR operation is performed between two corresponding bits of the numbers.

In binary 2 = 0010 and 3 = 0011

For instance, while performing a ^ b, the most significant bit of a is XOR’d with the most significant bit of b and so on.

The following three statements swaps values of a and b.

a = a ^ b

b = a ^ b

a = a ^ b

Congratulations, you’ve swapped values in a and b without the use of a temporary variable. How?

What going on in the first statement, lets see it in a table.

a b Final value of a = a ^ b
0 0 0 (from self-inversed)
0 0 0 (from self-inversed)
1 1 0 (from self-inversed)
0 1 1 (from Identity)

At the end of the first statement, the value of a = 0001 = 1

Now the value of a = a ^ b,

What’s going on in the second statement, lets see it in a table.

a = a ^ b b Final value of b = (a ^ b) ^ b
0 0 0 (from self-inversed)
0 0 0 (from self-inversed)
0 1 1 (from Identity)
1 1 0 (from self-inversed)

Voila, we’ve got the initial value of a I.e 2 to be held by b now. It worked but how? It’s nothing but the combination of self-inversed property followed by identity over the integers. For the second statement

b = a ^ b // After the first statement the value of a is equal to a ^ b, so

b = (a ^ b) ^ b

This can be rearranged by associative property and written as

b = a ^ (b ^ b)

We know from self-inversed rule, anything XOR’d with itself gives 0 . So we may now write

b = a ^ (0)

From Identity rule, we know something XOR’d to 0 will leave the number unchanged. Therefore we get

b = a

That’s how we got the initial value of a to be stored to b at the end of second statement.

Moving on to the third statement which is

a = a ^ b // By now the value of a is a ^ b and value of b is the initial value of a

so we may also write

a = a ^ b ^ a

Now this can be written as

a = a ^ a ^ b

Using self-inversed rule

a = 0 ^ b

Using identity rule

a = b

Through Table

A = a ^ b B = a A = a ^ b ^ a
0 0 0
0 0 0
0 1 1
1 0 1

At the end of the computation, we have b = 0010 = 2 and

a = 0011 = 3

Why you shouldn’t use XOR for swapping values?

For an instance, say

int a = 2

int *aptr = &a

int *bptr = &a

In the above set of statements, aptr and bptr are pointers to a. Using what we just learned

*aptr = *aptr ^ *bptr

*bptr = *aptr ^ *bptr

*aptr = *aptr ^ *bptr

Now since both the pointers are pointing to the number in the same location so all the above statements are making change at the same location whose result is data loss.

Swapping using addition and subtraction operators

a = a + b

b = a – b

a = a – b

This is pretty straight forward. Say for an instance

a = 5 and b = 10

Then the result of the first statement will be

a = a + b yields

a = 5 + 10

a = 15 and b is unchanged I.e b = 10

Now when the second statement is run, we have

b = a -b yields

b = 15 – 10

b = 5 (which is the initial value of a. Note that the value of a has already been changed to 15)

Running the third statement

a = a – b

a = 15 – 5

a = 10 (which is the initial value of b. Note that the value of b has already changed to 5)

So what do we have at the end

a = 10 and b = 5 (values swapped)

Why addition and subtraction shouldn’t be used to swap values

Say for an instance the values of a and b are large integers. We are performing addition on the first statement which can lead to overflow since we have large integers.

Should you have any questions, do comment below.

Beware, scammers in your inbox

- - Web

An unknown email lands into your inbox with some fascinating deals. Fascinating because these kinds of electronic mails involves surprisingly high amount of money deals. These emails seduce you to bounce your fingertips onto the typing machine to let the reply fly back with no waste of time. Ever encountered this situation? Feeling lucky to receive the mail? Let me spoil the whole thing. The mail that earned your attention had dozens of BCCs. Blind Carbon Copy would be an appropriate option for the mailer to drive your attention-filled mail to his account. The contents of the email mostly start with a sad and convincing story explaining they were seeking your help. If you respond to the mail showing sharp attention, you would be asked for your location, bank account number plus some additional information. They would want to transfer a huge amount of money to your personal account and guide you to transfer 90% of the sum to some other account or through IMEs and reward you with the remaining 10%. A convincing deal, isn’t it? Easy money. Continue Reading