Theory

Question 1

Describe self in python except for the answer that it works like “this”. Give some example!

Answer 1

When we call a method of an object(of MyClass) as myobject.method(arg1, arg2), this is automatically converted by Python into MyClass.method(myobject, arg1, arg2) – this is all the special self is about.

Question 2

Rules of solving a problem?

Answer 2

1) What are the inputs? -
What are the assumptions?
How are inputs represented?
2)What is the desired output? How is it represented?
3)Understand the relationship between input and output i.e. workout some cases.
4)Start solving the problem in a systematic way, draw out an algo if required.
5)Find a SIMPLE mechanical solution, think in terms of the machine and not in terms of human mind. DEVELOP INCREMENTALLY AND TEST AS YOU GO. DON’T LEAVE ALL TESTS FOR THE END.
(If things are getting hard and you are losing motivation, do the easier things(functions) first, leave the hard part for now. Ticking things off a checklist gives you a motivation boost)

Question 3

What do assert mean? Give an example.

Answer 3

Assert is a debugging tool which means “Make Sure That”. Eg - print(a/b) . Here b shouldn’t be ==0 or else it wont divide. Hence we put assert b!=0 “Divide error”. Which means “Make Sure That” b!=0.

We can use assert in our test function when we don’t have someone checking our output as happens in hackerrank.

Question 4

What is the best complexity for union-find problem? Can it be O(n)?

Answer 4

It was proved that it cannot be N, it is N+Mlog*N which is pretty close to being linear in real world but it is not LITERALLY linear. It is lowest with weighted quick find having a path compression.

Question 5

Difference between extend and append?
Difference in complexity of append and concatenate?
Where to use append and where to use concatenate?
Can one form of concatenation be faster than another?

Answer 5

append: Appends object at the end.
x = [1, 2, 3]
x.append([4, 5])
gives you: [1, 2, 3, [4, 5]]
extend: Extends list by appending elements from the iterable.
x = [1, 2, 3]
x.extend([4, 5])
gives you: [1, 2, 3, 4, 5]

Append has O(1) and conc has O(k)
Append is used when you need to do things one by one like adding 1 number in each loop run to a list.

You are creating a new list object each time by concatenating. This requires copying all elements from the old list into a new one, plus one extra. So yes, using l = l + [i] is an O(N) algorithm, not O(1).

At the very least, don’t use + concatenation; use += augmented concatenation, which is the same thing as list.extend() with a re-assignment to the same reference

Question 6

What do list.reverse() return?

Answer 6

It returns None. So if we do list = list.reverse(), then since the method returns None, our list will become None. Same for list.sort()
To reverse a list, we simply do list.reverse and then print list. We don’t save it into a variable as it returns None since it does inplace reversing.

Question 7

How to resize a stack made of an array or literally - how to resize an array. Which implementation of stack is better in what ways - linked list vs array.

Answer 7

Push()-Increase the array size by one
Pop() - Decrease the array size by one
This way is easy to implement but highly expensive. This crappy idea goes to QUADRATIC time.

A better way is repeated Doubling. We double the size of array every time it becomes full. It goes at linear time.

In linked list stack, every operation takes constant time but it consumes extra space to store all those chains.
In array, operations take constant amortized time but much higher compared to linked list. On the other side, arrays don’t consume as much space as linked lists.