Welcome to Interview Documentation!

Interview Documentation

Array

Static Array

Important

A static array is a fixed length container containing n elements indexable from the range [0 , n-1]

Complexity

Static Array

Dynamic Array

Access

O(1)

O(1)

Search

O(n)

O(n)

Insertion

NA

O(n)

Appending

NA

O(1)

Deletion

NA

O(n)

Array Operations

class array_operation[source]

Bases: object

All the operations associated with list

delete_at_end()[source]
delete_at_index(index)[source]
delete_ele(ele)[source]
display()[source]
get(index)[source]
insert_at_end(ele)[source]
insert_at_index(ele, index)[source]
search(key)[source]
class array_operation:
"""All the operations associated with Array"""

    def __init__(self):
        self.array = []

    def get(self, index):
        if index < len(self.array):
            return self.array[index]
        return -1

    def insert_at_end(self, ele):
        self.array.append(ele)
        return

    def insert_at_index(self, ele, index):
        self.array.insert(index, ele)
        return

    def delete_at_end(self):
        if len(self.array) > 0:
            return self.array.pop()
        return -1

    def delete_ele(self, ele):
        res = self.search(ele)
        if res == -1:
            return res
        self.array.remove(ele)
        return res

    def delete_at_index(self, index):
        if index < len(self.array):
            return self.array.pop(index)
        return -1

    def search(self, key):
        for i in range(len(self.array)):
            if self.array[i] == key:
                return i
        return -1

    def display(self):
        for i in range(len(self.array)):
            print("{0} ".format(self.array[i]), end=" ")
        print()

Important Problems

Stack

Important

Stack is a data structure where we store data with the rule Last In First Out (LIFO).

  • Used in recursion.

  • Valid Parenthesis.

Warning

In python stack is implemented using list, the stack class here is just to tell about the implementation.

Complexity

Time

Insertion

O(1)

Deletion

O(1)

Stack Operations

class Stack(size)[source]

Bases: object

In python, stack doesn’t make any sense as list has all inbuilt methods for the same But algorithm works as demonstrated below

display()[source]
get_top()[source]
overflow()[source]
pop() → int[source]
push(ele) → None[source]
underflow() → bool[source]
class Stack:
    def __init__(self, size):
        self.stack = []
        self.size = size  # fixed sized stack
        self.top = -1  # index of stack

    def push(self, ele) -> None:
        if not self.overflow():
            self.top += 1
            self.stack.append(ele)
        else:
            print("Stack Overflow")

    def pop(self) -> int:
        if not self.underflow():
            self.top -= 1
            return self.stack.pop()
        print("Stack Underflow")
        return -1

    def underflow(self) -> bool:
        if self.top == -1:
            return True
        return False

    def overflow(self):
        if self.top == self.size - 1:
            return True
        return False

Important Problems

Linked List

Important

A linked-list is a sequential list of nodes that hold data which point to other nodes also containing data

Where are they used

  • Used in many list, queue & stack implementation

  • For creating Circular List

  • Used in separate chaining, which is present certain hashtable implementations to deal with hashing collisions

  • Often used in the implementation of the adjacency lists for graph

Pros and Cons

Pros

Cons

Singly Linked List

  • Uses Less Memory

  • Simpler Implementation

Can’t easily access previous elements

Doubly Linked List

Can be Traversed backwards

Takes 2x memory

Complexity

Singly Linked List

Doubly Linked List

Search

O(n)

O(n)

Insert at Head

O(1)

O(1)

Insert at Tail

O(1)

O(1)

Remove at Head

O(1)

O(1)

Remove at Tail

O(n)

O(1)

Remove in middle

O(n)

O(n)
class LinkedList[source]

Bases: object

Operations associated with the Linked List

add_at_index(index: int, val: int) → None[source]

Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.

delete_at_index(index: int)[source]

Delete the index-th node in the linked list, if the index is valid.

get(index: int)[source]

Get the value of the index-th node in the linked list. If the index is invalid, return -1.

insert_at_head(data)[source]

Insert at head

insert_at_tail(data)[source]

Insert at the tail

search(data)[source]

To search the given data in the Linked list and find it’s first occurrence, if it is not present return -1

Node

Defining the node for a Linked List

Node(data: int)[source]
def Node(data):
    data = data
    next = None

head = None

Insert

Insert at head

insert_at_head(data: int)
def insert_at_head(data):
    """Insert at head """
    new_node = Node(data)
    new_node.next = head
    head = new_node

Insert at Tail

insert_at_tail(data: int)
def insert_at_tail(data):
    """Insert at the tail"""
    new_node = Node(data)
    # If there is no element in the linked list then add it to the head
    if head is None:
        head = new_node
    else:
        curr = head
        while curr.next:
            curr = curr.next
        curr.next = new_node

Insert at an Index

insert_at_index(data: int)
def insert_at_index(data):
    """
    Add a node of value val before the index-th node in the linked list. If index equals to the length of linked
    list, the node will be appended to the end of linked list. If index is greater than the length, the node will
    not be inserted.
    """
    index -= 1
    new_node = Node(val)
    if not head:
        head = new_node
        return
    curr = head
    if index < 1:
        new_node.next = head
        head = new_node
        return
    else:
        count = 0
        prev = head
        while curr:
            count += 1
            if count == index:
                new_node.next = curr.next
                curr.next = new_node
                return
            prev = curr
            curr = curr.next
        if count == index:
            curr.next = new_node
            return
        else:
            prev.next = new_node
            return

Delete

Delete at head

delete_head()
def delete_head():
    if not head:
        return -1
    else:
        value = head.data
        temp = head.next
        head = None
        head = temp
        return value

Delete at Tail

delete_tail()
def delete_tail():
    if not head:
        return -1
    else:
        curr = head
        if not curr.next:
            value = curr.data
            head = None
            return value
        while curr.next.next:
            curr = curr.next
        value = curr.next.data
        curr.next = None
        return value

Delete at Index

delete_at_index(index: int)
def delete_at_index(index: int):
    """
    Delete the index-th node in the linked list, if the index is valid.
    """
    index -= 1
    if head is None:
        return -1
    curr = head
    if index == 0:
        value = curr.data
        head = curr.next
        return value
    elif index < 0:
        return -1
    else:
        for i in range(index - 1):
            curr = curr.next
            if curr is None:
                break
        if curr is None:
            return -1
        if curr.next is None:
            return -1
    value = curr.data
    next = curr.next.next
    curr.next = None
    curr.next = next
    return value

Important Problems

Leetcode Problems

Linked List Cycle

Sl No

Level

Questions

Solutions

Tags

141

Easy

Linked List Cycle

Python

Two Pointers

142

Medium

Linked List Cycle II

Python

Hash Table

2

Medium

Add Two Numbers

Python

Traversal

19

Medium

Remove Nth Node From End of List

Python

Two Pointers

Array

Boyer–Moore majority vote algorithm

boyer_moore_voting_algorithm(arr: list) → int[source]
Parameters

arr – list

Returns

int

Description

To find the majority element from the sequence, majority means the element should be present more than n/2 times the total length, n, of the sequence.

If no such element occurs, then algorithm can return any arbitrary element, and is not guaranteed that this element will be the mode or occurred maximum number of times.

Important

  • Linear TIme

  • Constant Space

See also

Reference : wiki

Python

def boyer_moore_voting_algorithm(arr: list) -> int:
    """
    :param arr: list
    :return: int
    """
    res = arr[0]  # Initialization
    counter = 0  # Counter

    for i in range(len(arr)):
        if counter == 0:
            res = arr[i]
            counter = 1
        elif res == arr[i]:
            counter += 1
        else:
            counter -= 1

    return res

Implementation

LeetCode

Sl No

Level

Questions

Solutions

Tags

169

Easy

Majority Element

Python

Linked List

Floyd’s Tortoise and Hare

class FloydTortoiseAndHare[source]

Implementation of Floyd’s Tortoise and Hare Algorithm

check_cycle(head)[source]

Return True if cycle is present else False :param head: :return:

cycle_node(head)[source]

Finding the node where cycle exists :param head: :return:

class FormLinkedList(array, ind)[source]

Class to form linked-list with cycle

createll()[source]

Function to create linked-list with cycle :return:

class Node(data=0, next=None)[source]

Node for the linked-list

Description

Floyd’s cycle-finding algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the tortoise and the hare algorithm

Checking the existence of the cycle in the linked-list. We can also find the node with which linked-list is linked

Important

  • Linear TIme

  • Constant Space

See also

Reference : wiki

Python

Check For Cycle
def check_cycle(self, head):
    """
    Return True is cycle is present else False
    :param head:
    :return:
    """
    # Two pointers
    tortoise, hare = head, head

    # Base Case
    while hare and hare.next:
        tortoise = tortoise.next
        hare = hare.next.next

        # Condition for cycle
        if tortoise == hare:
            return True

    # Condition when there is no cycle
    return False
Get the Node where cycle exists
def cycle_node(self, head):
    """
    Finding the node where cycle exists
    :param head:
    :return:
    """
    # Two pointers
    tortoise, hare = head, head

    while True:
        # Condition when pointer reaches to end
        if not hare or not hare.next:
            return None

        tortoise = tortoise.next
        hare = hare.next.next

        if tortoise == hare:
            break

    # Iterating over the ll to find
    tortoise = head
    while tortoise != hare:
        tortoise = tortoise.next
        hare = hare.next

    # Returning node where cycle was found
    return tortoise

Implementation

LeetCode

Sl No

Level

Questions

Solutions

Tags

141

Easy

Linked List Cycle

Python

Two Pointers

142

Medium

Linked List Cycle II

Python

Hash-Table, Two Pointers

Searching

Search Algorithms

Sl No.

Algorithm

Worst Time

Average Time

Best Time

Memory

1

Linear Search
\[1\]
\[n\]
\[1\]
\[1\]

2

Binary Search
\[log(n)\]
\[log(n)\]
\[1\]
\[1\]

Sorting

Sorting Algorithms

Sl No.

Algorithm

Worst Time

Average Time

Best Time

Memory

Stability

1

Bubble Sort
\[n^2\]
\[n^2\]
\[n\]
\[1\]

Stable

2

Selection Sort
\[n^2\]
\[n^2\]
\[n^2\]
\[1\]

Unstable

3

Insertion Sort
\[n^2\]
\[n^2\]
\[n^2\]
\[1\]

Stable

4

Merge Sort
\[n * log(n)\]
\[n * log(n)\]
\[n * log(n)\]
\[n\]

Stable

5

Quick Sort
\[n * log(n)\]
\[n * log(n)\]
\[n^2\]
\[n * log(n)\]

Unstable

Note

  • Stable : Relative position of equal elements after sorting remains same.

  • In-place Sorting : Sorting Input elements without having backup, thus unsorted form is lost.

Bubble Sort

class bubbleSort[source]

Bases: object

bubble_sort(data)[source]

Description

Important

TIme Complexity

  • Worst Case: \(n^2\)

  • Average Case: \(n^2\)

  • Best Case: \(n\)

Space Complexity: \(O(1)\)
In Place Sorting
Stable Sorting

Python

def bubble_sort(data):
    for i in range(len(data) - 1):
        for j in range(0, len(data) - i - 1):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
    return data

Implementation

Selection Sort

class selectionSort[source]

Bases: object

selection_sort(data)[source]

Description

Important

TIme Complexity

  • Worst Case: \(n^2\)

  • Average Case: \(n^2\)

  • Best Case: \(n^2\)

Space Complexity: \(O(1)\)
In Place Sorting
Unstable Sorting

Python

def selection_sort(data):
    for i in range(len(data)):
        min_index = i
        for j in range(i + 1, len(data)):
            if data[min_index] > data[j]:
                min_index = j
        data[i], data[min_index] = data[min_index], data[i]
    return data

Implementation

Insertion Sort

class insertionSort[source]

Bases: object

insertion_sort(data)[source]

Description

Tip

  • Insertion sort is used when number of elements is small.

  • It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

Important

TIme Complexity

  • Worst Case: \(n^2\)

  • Average Case: \(n^2\)

  • Best Case: \(n^2\)

Space Complexity: \(O(1)\)
In Place Sorting
Stable Sorting

Python

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and key < data[j]:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key
    return data

Implementation

Merge Sort

class MergeSort[source]

Bases: object

merge_sort(data)[source]

Description

Important

TIme Complexity

  • Worst Case: \(n * log(n)\)

  • Average Case: \(n * log(n)\)

  • Best Case: \(n * log(n)\)

Space Complexity: \(O(n)\)
In Place Sorting
Stable Sorting

Python

def merge_sort(data):
    if len(data) > 1:
        mid = len(data) // 2
        left = data[:mid]
        right = data[mid:]

        merge_sort(left)
        merge_sort(right)

        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                data[k] = left[i]
                i += 1
            else:
                data[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            data[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            data[k] = right[j]
            j += 1
            k += 1

Implementation

Quick Sort

class QuickSort[source]

Bases: object

partition(data, low, high)[source]
quick_sort(data, low, high)[source]

Description

Important

TIme Complexity

  • Worst Case: \(n * log(n)\)

  • Average Case: \(n * log(n)\)

  • Best Case: \(n^2\)

Space Complexity: \(O(n * log(n))\)
In Place Sorting
Unstable Sorting

Python

Algorithm for partition
def partition(data, low, high):
    pivot = data[high]
    i = low  # To keep the index of element smaller than pivot
    j = low  # To keep the index of element greater than pivot

    while j < high:
        if data[j] < pivot:
            data[j], data[i] = data[i], data[j]
            i += 1
        j += 1

    data[i], data[high] = data[high], data[i]

    return i
Recursive Algorithm for quicksort
def quick_sort(data, low, high):
    if low < high:
        pivot = partition(data, low, high)
        quick_sort(data, low, pivot - 1)
        quick_sort(data, pivot + 1, high)

Implementation

Two Pointers

Description

Variations

  • Same Direction

  • Opposite Direction

Implementation

LeetCode

Sl No

Level

Questions

Solutions

Tags

26

Easy

Remove Duplicates from Sorted Array

Python

Two Pointers

189

Easy

Rotate Array

Python

Two Pointers

167

Easy

Two Sum II - Input array is sorted

Python

Two Pointers

11

Medium

Container With Most Water

Python

Two Pointers

238

Medium

Product of Array Except Self

Python

Two Pointerss

IP Address

  • IP Address is assigned to an Interface port

Important

8 bits = 1 Byte = 1 Octet

IPv4

  • 32 bits (4 byte) address format.

Interview Preparation

Interview Best Practices

  • Be Authentic

    • Don’t lie but this does not mean you have to tell everything.

    • Be Strategic and concise.

  • Sell Yourself

    • Focus on preparing authentic answers that highlight your greatest strengths.

    • Tell good, authentic, relevant stories about your experience.

  • Be Concise

    • Don’t bore interviewers with the long answers.

    • Don’t go beyond 2 minutes for a single answer.

    • If you bore them, you lose them.

    • Emphasise your most impressive points.

  • Show Enthusiasm

    • Demonstrate convincing enthusiasm for the company and the position.

    • Ask Questions

    • Be Motivated

Common Mistakes

  • Lack of Professionalism

    • Never be late for an interview

    • How you Dress matters.

    • How you present yourself.

    • Job Etiquette like saying Thank You.

  • Lack of Preparation

    • Analyzing Job Interviews

    • Thinking to key questions before Job Interview

    • Good Behavioural Stories

  • Lack of Content

    • Lame descriptions

    • Lcck of Preparation

    • Don’t give generic answers.

  • Negativity

Types of Inerviews

Phone Interview

  • The one to one in Person Interview

  • The Video Interview

  • The Panel Interview

  • The Group Interview

Types of Interviewers

  • External Recruiter: Doesn’t work for the company but can assign people to the company and get paid.

  • Internal Recruiter or HR Rep: Part of the Company and generally check for the authenticity and personality.

  • The Hiring Manager: Can dig deeper into the technical Questions and even for the personality.

  • Senior Level Management: More likely to see the work or hands-on experience and will check for the potential people.

  • Direct Report: You might be interviewed with someone who will work for you.

You need to do

  • Building Report

  • Showing Respect for the current Team

  • Show respect for the way they do things now.

  • Hope for the best.

Analyzing the Job Description

Note

A written description of the qualifications, duties and responsibilities of a position.

  • Work your network to find out more about the position.

  • Try searching the job description for the similar roles at similar companies.

  • Customizing your approach is the key to standing out from the pack.

To create your Job Description

  • Identify Competencies: Highlight the description of the position multiple times in form of your work experience.

  • Identify Themes: Most important of your work should be at the top which will also include the demand of the company.

  • Identify your Selling Points: Emphasize your strengths and be prepared for the weaknesses.

  • Identify Gaps or Issues: be Honest, Identify your weakness, what could be perceived as weaknesses by others.

  • Anticipate Question

Answering Inappropriate Questions

Tip

  • Decline or deflect the questions that include the following topics

  • Gender, Age, Marital Status, Where you are from, originally.

Where you are from originally?

I think I am <Your current location>, since I residing here for a long time.

I don’t think that’s too relevant, but I would love to tell you more about my programming experience.

General Standards

  • Dress a little bit more formally, than the company’s dress code.

  • Hair and nails should be clean and groomed

  • Your dress should be clean and wrinkles free.

  • Wear knee lengths skirts.

  • If you are not asked to wear suit, avoid it.

  • At last make it your choice.

Why dressing is important

  • To reduce distractions

  • Not to let people judge you based upon your dress.

  • They could listen more about your skills.

Overcoming Nerves

  • Do your homework

    • Practice more and keep a not of your points

    • Don’t repeat the same words time and again

  • Accentuate the Positive

    • Fake Smile can create positive impact but only if you can smile internally.

    • Don’t think more or out of context during the interview process.

  • Psyche yourself up

Networking

Important

Networking is interacting with others to exchange information and develop professional or social contacts.

  • Seeking support from people who already know and respect you

  • Define your network

    1. Name

    2. How you are connected

    3. Potential

    4. Reasons

    5. Contacts

  • Expand your thinking

  • Reach Out
    • Strong Connections: Consider these details

      • Clarify what you are looking for

      • Build Credibility

      • Ask open ended questions

      • Ask for Introductions

      • Be appreciative

      • Note next steps

    • Medium Connections

    • Low Connections

    • Targeting Specific Employers: Reach out to the employees of your target companies.

    • How to Contact: Don’t spam out for messages just for networking favour.

    • Following Up: Thank them for even their smallest help. Thank them when you get a job.

  • LinkedIn

    • Setting up profile: put clear, professional photo.

    • About Section: Write a nice summary without using generic words like experienced, learning etc. Update it regularly.

    • How to be found:

      • Change the public url to your name or username.

      • Adapt Public Visibility

      • Use Keywords

      • Complete your Contact Details

      • List only relevant Skills

    • LinkedIn Contacts:

      • Your Contacts

      • Don’t Spam

      • Informational Interviews

    • Finding Jobs

    • Jumping Gatekeepers

  • Keep a clean Web Presence

    • Don’t use bad spelling or grammars.

    • Personal Website

    • GitHub

      • Fill out your profile

      • Be mindful about pinned repository

      • Cleaned up your starred repository

      • Include an informative readme

Python Interview Questions

Memory Management in Python

Python is a high-level programming language that’s implemented in the C programming language. The Python memory manager manages Python’s memory allocations. There’s a private heap that contains all Python objects and data structures. The Python memory manager manages the Python heap on demand. The Python memory manager has object-specific allocators to allocate memory distinctly for specific objects such as int, string, etc… Below that, the raw memory allocator interacts with the memory manager of the operating system to ensure that there’s space on the private heap. The Python memory manager manages chunks of memory called “Blocks”. A collection of blocks of the same size makes up the “Pool”. Pools are created on Arenas, chunks of 256kB memory allocated on heap=64 pools. If the objects get destroyed, the memory manager fills this space with a new object of the same size. Methods and variables are created in Stack memory. A stack frame is created whenever methods and variables are created. These frames are destroyed automatically whenever methods are returned. Objects and instance variables are created in Heap memory. As soon as the variables and functions are returned, dead objects will be garbage collected. It is important to note that the Python memory manager doesn’t necessarily release the memory back to the Operating System, instead memory is returned back to the python interpreter. Python has a small objects allocator that keeps memory allocated for further use. In long-running processes, you may have an incremental reserve of unused memory.

Resources

Books

Competitive Coding

Online Study Materials

Credits

We recognise and thank everyone who contributed or whose code or related documentation or hyperlink has been used in the documentation.

There might be cases when your name might not be in the list please feel free to raise a PR to the repository along with the details of your work.

We thank You

Sl. No.

Name

Contact

1

Pamela Skillings

2

William Fiset

Collaborators

We really thank each member of our team, who have made this documentation really helpful for the people.

For their unique contribution we are mentioning them on this page.

We thank You

Sl. No.

Name

Contact

1

Aditya Raman

LinkedIn, GitHub

Indices and tables