DEV Community: Ritik Sharma

Computer System

Ritik Sharma — Fri, 10 Nov 2023 06:18:35 +0000

Content is uploading...

Encoding Schemes and Number System

Ritik Sharma — Fri, 10 Nov 2023 06:11:35 +0000

Introduction

Computer keyboards have keys in human-readable forms, but - computers interpret them differently.
Computers understand only binary language (0s and 1s), so keyboard inputs need to be converted.
When a key is pressed, it's mapped to a unique code, which is further converted to binary.

Example

When the key 'A' is pressed, it's mapped to a decimal value 65 (code value), which is then converted to binary.
Similarly, when 'अ' is pressed on a Hindi keyboard, it's mapped to a hexadecimal value 0905, with a binary equivalent of 0000100100000101.

Encoding

Encoding is the process of converting data into an equivalent cipher using a specific code.
It's important to understand why code value 65 is used for 'A' and if it's the same for all keyboards, regardless of their make.

Standard Encoding Schemes
Standard encoding schemes ensure consistency across keyboards.
Each letter, numeral, and symbol is encoded or assigned a unique code.
Various well-known encoding schemes will be described in the following sections.

American Standard Code for Information Interchange (ASCII)
Indian Script Code for Information Interchange (ISCII)
UNICODE

American Standard Code for Information Interchange (ASCII)

Developed in the early 1960s to address the issue of computers not being able to communicate due to different keyboard representations.
ASCII was created to standardize character representation, and it remains the most commonly used encoding scheme.
Initially, ASCII uses 7 bits to represent characters. Recall that there are only 2 binary digits (0 or 1).
With 7 bits, ASCII can encode 2^7 = 128 different characters and range from 0 to 127.
However, ASCII can only encode the character set of the English language, limiting its applicability to other languages and character sets.

Here are some important ASCII codes for commonly used characters:

Numbers 0-9: ASCII codes 48-57
Uppercase Letters A-Z: ASCII codes 65-90
Lowercase Letters a-z: ASCII codes 97-122

Stack: deep dive

Ritik Sharma — Thu, 13 Jul 2023 15:16:19 +0000

Stack

A stack is an ordered list in which insertion and deletion are done at one end, called top.
The last element inserted is the first one to be deleted.
Hence, it is called the Last in First out(LIFO) or First in Last out (FILO) list.

Stack ADT

Main stack operations

Push (int data): Inserts data onto stack.
int Pop(): Removes and returns the last inserted element from the stack.

Auxiliary stack operations

int Top(): Returns the last inserted element without removing it.
int Size(): Returns the number of elements stored in the stack.
int IsEmptyStack(): Indicates whether any elements are stored in the stack or not.
int IsFullStack(): Indicates whether the stack is full or not.

Implementing Stack using Array

#include<bits/stdc++.h>
using namespace std;

class Stack {
    int size = 5;
    int *items = new int[size];
    int top = 0;

    public:
    void push(int item) {
        if(top == size) cout << "StackOverFlowError" << endl;
        else items[top++] = item;
    }

    int pop() {
        if(top == 0) {
            cout << "StackUnderFlowError" << endl;
            return 0;
            cout <<"HI" << endl;
        }
            cout <<"2HI" << endl;
        return items[--top];
    }

    int length() {
        return top;
    }

    void print() {
        for(int i = 0; i < top; i++)
            cout << *(items + i) << " ";
    }

    int top() {
        return items[top-1];
    }

    bool isEmpty() {
        return top == 0;
    }

    bool isFull() {
        return top == size;
    }

};


int main(int argc, char const *argv[]) {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Size : " << s.length() << endl;
    return 0;
}

Performance

Let n be the number of elements in the stack. The complexities of stack operations with this representation can be given as:

Space Complexity (for n push operations): O(n)
Time Complexity of Push() : O(1)
Time Complexity of Pop() : O(1)
Time Complexity of Size() : O(1)
Time Complexity of IsEmpty(): O(1)
Time Complexity of IsFull : O(1)

Limitations

The maximum size of the stack must first be defined and it cannot be changed. Trying to push a new element into a full stack causes an implementation-specific exception.

Stacks: Problems

Discuss how stacks can be used for checking balancing of symbols.
Discuss infix to postfix conversion algorithm using stack.
Discuss postfix evaluation using stacks?
Can we evaluate the infix expression with stacks in one pass?
How to design a stack such that GetMinimum() should be O(1)?
For Problem-5 is it possible to improve the space complexity?

Hackerrank Angry Professor Solutions

Ritik Sharma — Mon, 06 Mar 2023 12:14:27 +0000

A Discrete Mathematics professor has a class of students. Frustrated with their lack of discipline, the professor
decides to cancel class if fewer than some number of students are present when class starts. Arrival times go
from on time (arrivalTime 0) to arrived late (arrivalTime > 0).
Given the arrival time of each student and a threshhold number of attendees, determine if the class is
cancelled.

Python

def angryProfessor(k, a):
    students = 0
    for i in a:
        if i <= 0: students += 1
    if students < k: print("YES")
    else: print("NO")

angryProfessor(3,[-1,-3,4,2])

JavaScript

function angryProfessor(k, a) {
  let students = 0;
  for (let i = 0; i < a.length; i++) {
    if (a[i] <= 0) {
      students++;
    }
  }
  if (students < k) {
    console.log("YES");
  } else {
    console.log("NO");
  }
}

C++

#include <iostream>
using namespace std;

void angryProfessor(int k, int a[], int n) {
  int students = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] <= 0) {
      students++;
    }
  }
  if (students < k) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

🔥Building Array Data Structure in python

Ritik Sharma — Tue, 14 Feb 2023 07:52:03 +0000

What is list?

A list in Python is a built-in(comes with python itself) data structure that stores a collection of values of any data type.
Lists are ordered, mutable (i.e., can be changed), and can contain elements of different data types.

for example:-

grocery = ["Sugar:1kg", "Tooth paste : 1", "masala:1kg"]
person = ["Ritik", "patna", 8, 56.32]

Here are some common operations and examples of how to use lists in Python:

How to use?

Creating a list:

numbers = [10, 20, 30]
# index =  0   1    2

Accessing list elements using an index:

print(numbers[0]) # Output: 10
print(numbers[1]) # Output: 20

Accessing list elements using an -ve index:

print(numbers[-1]) # Output: 30
print(numbers[-2]) # Output: 10

Building Linked List Data Structures in Python

Ritik Sharma — Thu, 09 Feb 2023 15:50:13 +0000

What is Linked List?

A linked list is a linear data structure where each element, called a node, contains a reference to an object and a reference to the next node in the list. This structure allows for efficient insertion and removal of elements, as the references only need to be updated, rather than all elements being shifted in memory. Linked lists can be singly-linked, where each node only points to the next node, or doubly-linked, where each node points to both the next and previous nodes.

Linked lists are often used as an alternative to arrays when the size of the data is unknown or changing frequently, as elements can be easily added or removed without the need to allocate new memory or move existing elements. Linked lists can also be used to implement various abstract data structures such as stacks, queues, and associative arrays.

Creating a Linked List

Each node in a linked list consists of two parts: the data and a reference to the next node in the list. To create a linked list, we first define a class for the nodes, called "Node", that has two properties: "data" and "next". The "data" property holds the element's value, while the "next" property holds the reference to the next node. Here's an example in Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Next, we create the linked list itself, which consists of a head node that references the first node in the list, and a tail node that references the last node.

Red-Black Tree

Ritik Sharma — Sun, 29 Jan 2023 17:05:22 +0000

Red-Black Tree

Red-Black tree is a self-balancing binary search tree in which each node contains an extra bit for denoting the color of the node, either red or black. It was created in 1972 by Rudolf Bayer who termed them "symmetric binary B-trees."

Properties of Red-Black Tree:

Root element of Red-Black Tree is always black.
Every NULL node or Leaf Nodes is black.
If a red node has children then, the children or its parent are always black.
Number of black Node on Any path from root to leaf is always same.
Two consecutive red node should not be in Red-Black Tree.
If you are inserting a new node is always a red node.

Maximum height of Red-Black Tree :

log n <= h <= 2log n

DEV Community: Ritik Sharma

Computer System

Encoding Schemes and Number System

Stack: deep dive

Stack

Stack ADT

Implementing Stack using Array

Performance

Limitations

Stacks: Problems

Hackerrank Angry Professor Solutions

Python

JavaScript

C++

🔥Building Array Data Structure in python

What is list?

How to use?

Creating a list:

Accessing list elements using an index:

Accessing list elements using an -ve index:

Building Linked List Data Structures in Python

What is Linked List?

Creating a Linked List

Red-Black Tree

Red-Black Tree

Properties of Red-Black Tree:

Maximum height of Red-Black Tree :

Examples of Red-Black Tree:-