DEV Community: Abhishek Sharma Gaur

Leetcode 935: Knight Dialer

Abhishek Sharma Gaur — Mon, 27 Nov 2023 09:51:21 +0000

Intuition

LeetCode Problem: Knight Dialer
Problem Description:
The problem is to find the number of different sequences a knight can make on a dial pad after making n moves. The knight can move to any of the valid digits based on its current position on the dial pad.

Approach:

The given solution uses dynamic programming to iteratively calculate the number of sequences for each digit after making a move. The sequences are updated in each iteration based on the knight's valid moves.

Initialization:

arr = Array.new(10, 1): This initializes an array arr with 10 elements, each initialized to 1. The array represents the count of sequences for each digit.
Iterative Calculation:

(n - 1).times do: This loop iterates n - 1 times, as the initial state already represents the sequences after the first move.
Inside the loop:
A temporary array tmp is created to store the updated counts for each digit based on the knight's moves.
The arr array is then updated with the values from tmp.
Return Result:

The final result is the sum of all sequences in the arr array, and it is returned modulo (10**9 + 7) to avoid integer overflow.

Complexity

Time Complexity: The time complexity of this solution is O(n), where n is the number of moves. The loop runs n - 1 times, and the operations inside the loop take constant time.

The space complexity is O(1), as the solution uses a constant amount of space regardless of the input size. The size of the arr array remains constant, and the tmp array is created within the loop.

# @param {Integer} n
# @return {Integer}
def knight_dialer(n)
    arr = Array.new(10, 1)

    (n - 1).times do
      tmp = [
        arr[4] + arr[6],
        arr[6] + arr[8],
        arr[7] + arr[9],
        arr[4] + arr[8],
        arr[3] + arr[9] + arr[0],
        0,
        arr[1] + arr[7] + arr[0],
        arr[2] + arr[6],
        arr[1] + arr[3],
        arr[2] + arr[4]
      ]

      arr = tmp
    end

    return arr.sum % (10**9 + 7)
end

Beat 100% of solutions from Leet code problem 1980: Find Unique Binary String

Abhishek Sharma Gaur — Thu, 16 Nov 2023 05:39:26 +0000

Problem: Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.
https://leetcode.com/problems/find-unique-binary-string/

Intuition

his method generates binary strings by flipping individual bits and checks if each generated string is in the input list nums. It returns the first binary string found that is not in the list.

Approach

The solution systematically generates binary strings by flipping individual bits and checks whether each generated string is in the input list nums. If a binary string is found in the list, it continues the process by flipping the next bit. The loop continues until it finds a binary string that is not present in the list nums or until the position exceeds the length of the binary string.

The solution leverages the fact that the binary string can be represented as a list of characters, allowing for easy manipulation of individual bits. The algorithm efficiently explores possible binary strings until it finds one that satisfies the given conditions.

Initialize a binary string (result) with all zeros, represented by a list of characters (chars) containing '0' repeated as many times as there are elements in the input list nums.

Use a while loop to iterate until a binary string is found that is not present in the input list nums or until the position (k) exceeds the length of the binary string.

Inside the loop:

Convert the current binary string (result) into a list of characters (chars).
Flip the bit at the current position (k) in the binary string.
Update the binary string (result) with the modified list of characters.
Increment the position (k) to move to the next bit.
Return the binary string that is not present in the input list nums.

Complexity

Time complexity: O(n * m):

The while loop runs until a binary string is found that is not in the list nums or until the position k exceeds the length of the binary string. In the worst case, this loop iterates through all possible binary strings of length m.

Within the loop, operations such as converting the binary string to a list of characters, flipping a bit, and joining the characters back into a string all take O(m) time.
Space complexity: O(m)

chars: A list of characters representing the current binary string. The length of this list is equal to the length of each binary string in nums (m). Therefore, the space complexity for chars is O(m).

result: The binary string constructed from the chars list. The space complexity for result is also O(m).

k: An integer variable used to keep track of the position in the binary string. This variable requires constant space, O(1).

The input list nums and the class itself do not contribute to the space complexity as they are not dependent on the size of the input.

Code Python

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        chars = ['0'] * len(nums)
        result = ''.join(chars)
        k = 0
        while(result in nums and k < len(result)):
            chars = list(result)
            chars[k] = '1' if chars[k] == '0' else '0'
            result = ''.join(chars)
            k += 1
        return result

Code JS

function findDifferentBinaryString(nums: string[]): string {
    let result = '0'.repeat(nums.length);
    let k = 0;

    while (nums.includes(result) && k < result.length) {
        result = result.slice(0, k) + (result[k] === '0' ? '1' : '0') + result.slice(k + 1);
        k += 1;
    }

    return result;  
}

Code in Ruby

def find_different_binary_string(nums)
    chars = ['0'] * nums.length
    result = chars.join('')
    k = 0

    while nums.include?(result) && k < result.length
      chars = result.chars
      chars[k] = (chars[k] == '0' ? '1' : '0')
      result = chars.join('')
      k += 1
    end

    result
end

Leet code problem 1441: Build an Array With Stack Operations

Abhishek Sharma Gaur — Fri, 03 Nov 2023 06:48:53 +0000

Problem: https://leetcode.com/problems/build-an-array-with-stack-operations/

Intuition

The code defines a method named buildArray that takes two parameters: target (an array of integers) and n (an integer). The goal of this code is to build an array that represents a sequence of "Push" and "Pop" operations required to transform an empty array into the target array, considering the value of n.

Approach

Here's a step-by-step explanation of the code:

result = []: This initializes an empty array named result, which will store the sequence of "Push" and "Pop" operations.

target_set = Set.new(target): This line creates a set named target_set containing the elements from the target array. A set is a data structure in Ruby that stores unique elements. This set is used to efficiently check if a specific number i is present in the target array later in the code.

(1..target[-1]).each do |i|: This line sets up a loop that iterates from 1 to the last element of the target array, which is accessed with target[-1].

result << "Push": In each iteration, "Push" is added to the result array, as this operation is performed unconditionally.

result << "Pop" unless target_set.include?(i): This line adds "Pop" to the result array unless the current value i is present in the target_set. It uses the include? method to check for the presence of i in the target_set.

result: Finally, the result array is returned, which contains the sequence of "Push" and "Pop" operations required to transform an empty array into the target array.

This Ruby code is similar in functionality to the Python code you provided earlier, but it uses Ruby-specific constructs, such as the Set data structure and the << operator for array appending.

Complexity

Time complexity:
O(n)
Space complexity:
O(1)

Code

# @param {Integer[]} target
# @param {Integer} n
# @return {String[]}
def build_array(target, n)
    result = []
    target_set = Set.new(target)
    (1..target[-1]).each do |i|
        result << "Push"
        result << "Pop" unless target_set.include?(i)
    end
    result
end

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        return [
            x
            for i in range(1, target[-1] + 1)
            for x in ["Push"] + ["Pop"] * (i not in set(target))
        ]

/**
 * @param {number[]} target
 * @param {number} n
 * @return {string[]}
 */
var buildArray = function(target, n) {
    const result = [];

    for (let i = 1; i <= target[target.length - 1]; i++) {
        result.push("Push");
        if (!target.includes(i)) {
            result.push("Pop");
        }
    }

    return result;

};

Leet code problem 22 Generate Paranthesis

Abhishek Sharma Gaur — Thu, 02 Nov 2023 13:26:34 +0000

This code defines a class Solution with a method generateParenthesis to generate valid combinations of parentheses for a given number n. It uses a backtracking algorithm to create these combinations. Here's a breakdown of the code:

stack and element are defined as empty lists. stack will store the valid parenthesis combinations, and element will keep track of the current combination being constructed.

Inside the Solution class, there's a nested function backtrack which is used for the recursive backtracking. It takes two parameters, openN and closeN, representing the count of open and close parentheses, respectively.

The backtrack function starts by checking if the number of open parentheses (openN) is equal to n, and the number of close parentheses (closeN) is also equal to n. If this condition is met, it means a valid combination of parentheses has been formed, so it joins the elements in the element list and appends it to the stack.

If the above condition is not met, the code proceeds with two recursive calls:

If the count of open parentheses (openN) is less than n, it appends an opening parenthesis "(" to the element, increments openN, and makes a recursive call to backtrack`.
If the count of close parentheses (closeN) is less than the count of open parentheses (openN), it appends a closing parenthesis ")" to the element, increments closeN, and makes another recursive call to backtrack.
The code prints some debugging information at various points within the backtrack function.

Finally, the backtrack function is called initially with both openN and closeN set to 0 to start the process of generating valid combinations. The stack containing all the valid combinations is returned.

The code includes some commented-out example usage at the end. To use the generateParenthesis function, you should create an instance of the Solution class and call the method on that instance with the desired value of n.

Code in python
`
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
stack = []
element = []

    def backtrack(openN, closeN):
        print("openN: " + str(openN) + " closeN: " + str(closeN) + " n: " + str(n))
        if openN == n and closeN == n:
            print("First condition: ", element)
            stack.append("".join(element))
            return
        if openN < n:
            element.append("(")
            backtrack(openN + 1, closeN)
            print("Second condition: ", element)
            element.pop()
        if closeN < openN:
            element.append(")")
            backtrack(openN, closeN + 1)
            print("Third condition: ", element)
            element.pop()

    backtrack(0, 0)
    return stack

Code in Javascript

`
/**

@param {number} n
@return {string[]}
*/
var generateParenthesis = function(n) {
let stack = []
let element = []

var backtrack = function(openN, closeN) {
console.log("openN: " + openN + " closeN: " + closeN + " n: " + n);
if(openN == n && closeN == n){
console.log("First condition: ", element);
stack.push(element.join(""))
return
}
if(openN < n) {
element.push("(")
backtrack(openN+1, closeN)
console.log("Second condition: ", element);
element.pop()
}
if(closeN < openN) {
element.push(")")
backtrack(openN, closeN+1)
console.log("Third condition: ", element);
element.pop()
}
return
}
backtrack(0, 0)
return stack
};
`

Leet code problem 2265: Count Nodes Equal to Average of Subtree

Abhishek Sharma Gaur — Sun, 15 Oct 2023 19:22:55 +0000

This code defines a class called Solution with a method named averageOfSubtree. The method takes a binary tree's root node as input and calculates the count of nodes where the average value of the subtree rooted at that node is equal to the value of the node itself.

Here's a breakdown of the code:

ans is initialized as an empty list. This list will store the values of nodes where the average of their subtree is equal to their own value.

The dfs function is defined as a nested function within the averageOfSubtree method. It is a depth-first search function used to traverse the binary tree recursively. It takes a root node as input and returns a tuple of two values: the sum of all node values in the subtree rooted at root, and the count of nodes in that subtree.

Inside the dfs function, it checks if the root is None, indicating an empty subtree. If so, it returns (0, 0) to represent the sum and count of an empty subtree.

If the root is not None, it recursively calls dfs on the left and right subtrees (root.left and root.right). It then calculates leftSum and leftCount for the left subtree and rightSum and rightCount for the right subtree.

The total sum is calculated as the sum of the current node's value, the leftSum, and the rightSum.

The total count is calculated as 1 (for the current node) plus the leftCount and rightCount.

It checks whether the average of the subtree (sum // count) is equal to the value of the current node. If it is, it appends the current node's value to the ans list.

The dfs function returns a tuple containing the calculated sum and count for the current subtree.

The dfs function is called initially with the root of the binary tree to start the recursive traversal.

Finally, the averageOfSubtree method returns the length of the ans list, which represents the count of nodes whose subtree averages are equal to the node values.

In essence, this code calculates the number of nodes in a binary tree where the average of the values in their subtrees matches their own value and stores these values in the ans list. The length of this list is returned as the final result.

Code in python

class Solution:
    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
        ans = []

        def dfs(root: Optional[TreeNode]) -> Tuple[int, int]:
            nonlocal ans
            if not root:
                return (0, 0)
            leftSum, leftCount = dfs(root.left)
            rightSum, rightCount = dfs(root.right)
            sum = root.val + leftSum + rightSum
            count = 1 + leftCount + rightCount
            if sum // count == root.val:
                ans.append(root.val)
            return (sum, count)

        dfs(root)
        return len(ans)

Code in Ruby

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer}
def average_of_subtree(root)
    @ans = []

    def dfs(root)
      return [0, 0] if root.nil?

      left_sum, left_count = dfs(root.left)
      right_sum, right_count = dfs(root.right)
      summ = root.val + left_sum + right_sum
      count = 1 + left_count + right_count
      @ans << root.val if summ / count == root.val
      return [summ, count]
    end

    dfs(root)
    @ans.length

end

Code in Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
function averageOfSubtree(root) {
    let ans = [];
    function dfs(root) {
        if (!root) {
            return [0, 0];
        }
        let [leftSum, leftCount] = dfs(root.left);
        let [rightSum, rightCount] = dfs(root.right);
        let sum = root.val + leftSum + rightSum;
        let count = 1 + leftCount + rightCount;
        if (Math.floor(sum / count) === root.val) {
            ans.push(root.val);
        }
        return [sum, count];
    }
    dfs(root);
    return ans.length;
}

Leet code problem 620. Not Boring Movies

Abhishek Sharma Gaur — Sun, 15 Oct 2023 14:29:27 +0000

Problem: Table: Cinema

Write a solution to report the movies with an odd-numbered ID and a description that is not "boring".

Return the result table ordered by rating in descending order.

The result format is in the following example.

Example 1:

Input:
Cinema table:
+----+------------+-------------+--------+
| id | movie | description | rating |
+----+------------+-------------+--------+
| 1 | War | great 3D | 8.9 |
| 2 | Science | fiction | 8.5 |
| 3 | irish | boring | 6.2 |
| 4 | Ice song | Fantacy | 8.6 |
| 5 | House card | Interesting | 9.1 |
+----+------------+-------------+--------+
Output:
+----+------------+-------------+--------+
| id | movie | description | rating |
+----+------------+-------------+--------+
| 5 | House card | Interesting | 9.1 |
| 1 | War | great 3D | 8.9 |
+----+------------+-------------+--------+
Explanation:
We have three movies with odd-numbered IDs: 1, 3, and 5. The movie with ID = 3 is boring so we do not include it in the answer.

Code in SQL

# MySQL query statement below
SELECT * FROM Cinema WHERE id %2 != 0 AND description != "boring" ORDER BY rating DESC;

This SQL query is written to retrieve data from a table called "Cinema." Let me explain it step by step in plain English:

SELECT *: This part of the query instructs the database to retrieve all columns (indicated by the asterisk) from the "Cinema" table.

FROM Cinema: It specifies that the data we want to retrieve is located in the "Cinema" table.

WHERE id % 2 != 0: Here, we're applying a filter to the rows. It's looking for rows where the "id" column is not divisible evenly by 2, which essentially means it's looking for rows with odd values in the "id" column.

AND description != "boring": In addition to the previous filter, this condition further refines the selection. It only includes rows where the "description" column does not contain the word "boring."

ORDER BY rating DESC: Finally, it specifies how the selected rows should be sorted. It arranges them in descending order (indicated by "DESC") based on the values in the "rating" column. So, the rows with the highest ratings will appear at the top of the result set.

In summary, this SQL query retrieves all columns for rows in the "Cinema" table where the "id" is odd and the "description" is not "boring," and it sorts these rows by their "rating" values in descending order.

Leet code problem 563: Binary Tree Tilt

Abhishek Sharma Gaur — Sun, 15 Oct 2023 14:09:19 +0000

Problem: Given the root of a binary tree, return the sum of every tree node's tilt.

The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if the node does not have a right child.

Example 1:

The goal of this problem is to find the "tilt" of a binary tree, which is defined as the absolute difference in the sums of values in the left and right subtrees for each node in the tree. To do this, the algorithm implements a post-order traversal technique, which analyses the nodes of the tree in the following order: first, the left subtree, then the right, and finally, the current node. The process starts with the findTilt function, which takes the binary tree's root node as input.

There is a tilt_counter variable inside the findTilt function that is set to 0 and maintains track of the cumulative tilt for the entire tree. The code includes a recursive function named post_order_traversal, which traverses the binary tree using the post-order algorithm.If a node is null (indicating there is no node), this function returns 0.

post_order_traversal computes the sums of values in the left and right subtrees by performing recursive calls to itself for the current node's left and right children. These totals are kept in the variables left_sum and right_sum. The method calculates the absolute difference between left_sum and right_sum and accumulates this tilt in the tilt_counter variable to determine the tilt of the current node. Finally, the method returns the total of values for the current node and its subtrees, calculated as left_sum + right_sum + node.val.

The findTilt function executes the post_order_traversal function using the root node of the tree to do the post-order traversal, as defined in the function declaration. The binary tree's overall tilt accumulates in the tilt_counter variable, which is returned by the findTilt method.

In essence, this code calculates the total tilt of a binary tree carefully using a post-order recursive traversal, determining the tilt for each node and storing the results in the tilt_counter. The final result indicates the total tilt of the binary tree.

Code in Javascript

var findTilt = (root) => {
    let tilt_counter = 0;
    const post_order_traversal = (node) => {

        // If the node does not exist.
        // It has no value and therefore it's a 0.
        if (!node) {
            return 0;
        }

        // Post Order, get me their SUMS!!!
        let left_sum  = post_order_traversal(node.left);
        let right_sum = post_order_traversal(node.right);

        // Figure out the difference between the left and right subtrees
        // We use the absolute value of the difference to keep track of the tilt
        tilt_counter += Math.abs(left_sum - right_sum);

        // Return the value of the node and it's subtrees.
        return left_sum + right_sum + node.val;
    };

    post_order_traversal(root);
    return tilt_counter;
};

Code in Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        tilt_counter = 0

        def post_order_traversal(node):
            """
            Perform post-order traversal to calculate the tilt of each node.

            Args:
                node: The current node being traversed.

            Returns:
                The sum of the node and its subtrees.
            """
            if not node:
                # If the node does not exist, return 0.
                # It has no value and therefore it's a 0.
                return 0

            # Post Order, get me their SUMS!!!
            left_sum = post_order_traversal(node.left)
            right_sum = post_order_traversal(node.right)

            # Figure out the difference between the left and right subtrees
            # We use the absolute value of the difference to keep track of the tilt
            nonlocal tilt_counter
            tilt_counter += abs(left_sum - right_sum)

            # Return the value of the node and its subtrees.
            return left_sum + right_sum + node.val

        post_order_traversal(root)
        return tilt_counter

Loops in Javascript vs Python vs Ruby

Abhishek Sharma Gaur — Thu, 08 Jun 2023 17:55:32 +0000

Loops are programming constructs that allow you to repeat a block of code multiple times. They are used to automate repetitive tasks, iterate over collections of data, or execute a certain code sequence until a particular condition is met. Loops help in writing more efficient and concise code by reducing redundancy.

In general, loops consist of three main components:

Initialisation: It involves initializing the loop control variable(s) with an initial value. This step is typically performed before the loop starts.

Condition: The loop executes the code block repeatedly until a specific condition is evaluated as false. The condition is checked before each iteration. If the condition is true, the loop continues; otherwise, it terminates.

Update: After each iteration, the loop control variable(s) are updated to a new value. The update step ensures progress towards the termination condition, allowing the loop to eventually exit.

The three most common types of loops are:

For Loop: The for loop is used when the number of iterations is known or can be determined in advance. It consists of an initialisation, condition, and update statement within its syntax.

While Loop: The while loop is used when the number of iterations is uncertain, and the loop continues until a specific condition becomes false. It evaluates the condition before each iteration.

Do...While Loop: The do...while loop is similar to the while loop, but it executes the code block at least once before evaluating the condition. It ensures that the code inside the loop runs before the condition is checked.

Below we have a Javascript implementation

// Example: Iterate over an array
const fruits = ["apple", "banana", "cherry"];
for (let i = 0; i < fruits.length; i++) {
  console.log(fruits[i]);
}

// Example: Iterate over a range of numbers
for (let i = 1; i <= 5; i++) {
  console.log(i);
}

// Example: Print numbers from 1 to 5
let count = 1;
while (count <= 5) {
  console.log(count);
  count++;
}

// Example: Ask for user input until a valid number is entered
let userInput;
do {
  userInput = prompt("Enter a number:");
} while (isNaN(userInput));

// Example: Iterate over object properties
const person = {
  name: "John",
  age: 30,
  city: "New York",
};

for (let key in person) {
  console.log(key + ": " + person[key]);
}

// Example: Iterate over an array
const fruits = ["apple", "banana", "cherry"];
for (let fruit of fruits) {
  console.log(fruit);
}

Below we have a Python implementation

# Example: Iterate over a list
fruits = ["apple", "banana", "cherry"]
for fruit in fruits:
    print(fruit)

# Example: Iterate over a string
message = "Hello"
for char in message:
    print(char)

# Example: Iterate using range
for i in range(1, 6):  # Iterates from 1 to 5 (inclusive)
    print(i)

# Example: Print numbers from 1 to 5
count = 1
while count <= 5:
    print(count)
    count += 1

# Example: Ask for user input until a specific condition is met
user_input = ""
while user_input != "quit":
    user_input = input("Enter a value ('quit' to exit): ")
    print("You entered:", user_input)

# Example: Break and continue statements
for i in range(1, 10):
    if i == 5:
        break  # Terminate the loop when i equals 5
    if i % 2 == 0:
        continue  # Skip even numbers
    print(i)

Below we have a Ruby implementation

# Example: Iterate over an array
fruits = ["apple", "banana", "cherry"]
for fruit in fruits do
    puts fruit
end

# Example: Iterate using range
for i in 1..5 do
    puts i
end

# Example: Print numbers from 1 to 5
count = 1
while count <= 5 do
    puts count
    count += 1
end

# Example: Print numbers from 1 to 5 using until loop
count = 1
until count > 5 do
    puts count
    count += 1
end

# Example: Iterate over an array using each
fruits = ["apple", "banana", "cherry"]
fruits.each do |fruit|
    puts fruit
end

# Example: Execute code a certain number of times using times
5.times do |i|
    puts i + 1
end

Manipulation of string in Javascript, Python and Ruby

Abhishek Sharma Gaur — Wed, 17 May 2023 18:16:50 +0000

A string is known as a sequence of characters, and string manipulation is something we programmers do all the time. Here are some of the basic string manipulation operations and how we implement them in Python, Javascript and Ruby.

To Uppercase: Converting all the characters in a string into uppercase.

To Lowercase: Converting all the characters in a string into lowercase.

Length of string: A very midget but crucial function used in most of the code. Is to find the length of a string.

Finding a character: Another crucial function to detect a substring inside a string.

Reverse a string: Mostly used in the form of a stack, a native function with O(n) time complexity to help out resolving code convolutions.

Below we have a Javascript implementation

let my_name = "Abhishek Sharma"
console.log('my_name in toLowerCase', my_name.toLowerCase());
console.log('my_name in toUpperCase', my_name.toUpperCase());
console.log('my_name string length', my_name.length);
console.log('find character in string', my_name.includes("b"), my_name[2]);
console.log('my_name in reverse', my_name.split('').reverse().join(''));

Below we have a Python implementation

my_name = "Abhishek Sharma"
print('my_name in toLowerCase', my_name.casefold());
print('my_name in toUpperCase', my_name.capitalize());
print('my_name string length', len(my_name));
print('find character in string', my_name.rfind("b"), my_name[2]);
print('my_name in reverse', my_name[::-1]);

Below we have a Ruby implementation

my_name = "Abhishek Sharma"

puts "my_name in toLowerCase #{my_name.downcase}"
puts "my_name in toUpperCase #{my_name.upcase}"
puts "my_name string length #{my_name.size} #{my_name.length}"
puts "find character in string #{my_name.include? 'b'} #{my_name[1]}"
puts "my_name in reverse #{my_name.reverse}"

Arrays Data Structure in Javascript, Python and Ruby

Abhishek Sharma Gaur — Tue, 16 May 2023 17:24:44 +0000

An array is a collection of items stored in contiguous memory. The idea is to keep many items of the same type together. This makes it easy to calculate the position of each element by adding an offset to the base value, which is the memory location of the first element of the array (usually indicated by the name of the array).

Algorithm for PUSH operation

Check if the array is full or not.
If the array is full, exit the program.
If the array is not full, then increment the size and add the element to the end of the array.

Algorithm for POP operation

Check if the array is empty or not.
If the array is empty, print the underflow error and exit the program.
If the array is not empty, pop the last element.

Time complexity

Push: O(1)
Pop: O(1)
Size: O(1)
SearchByIndex: O(1)
SearchByValue: O(n)

The functions associated with stack are:

size() – Returns the length of the array

push(a) – Inserts the element at the end of an array.

pop() – Deletes the last element of the array.

searchByIndex - Identifies element on a known index.

searchByValue - Retrieve the value's index in the array.

print - To print the array

Below we have a Javascript program implementing an array data structure

class CustomArray {
    constructor(limit) {
      this.customArray = [];
      this.limit = 10
    }

    push = (item) => {
      if(this.customArray.length > this.limit) this.limit++
      this.customArray.push(item)
    };

    pop = () => this.customArray.pop();

    print = () => console.log("array:", JSON.stringify(this.customArray));

    searchByIndex = (index) => {
        console.log('searchByIndex for index', this.customArray[index]);
        return this.customArray[index]
    }

    searchByValue = (value) => {
        for(let x in this.customArray){
            if(this.customArray[x] === value) {
                console.log(`searchByValue for value ${x}`);
                return x
            }
        }
        return -1
    }
  }

  let customArray = new CustomArray();
  customArray.push(1);
  customArray.push(2);
  customArray.push(3);
  customArray.print();

  customArray.pop();
  customArray.print();
  customArray.searchByIndex(1);
  customArray.searchByValue(1);

Below we have a Python program implementing an array data structure

class CustomArray:
    def __init__(self, limit):
        self.customArray = []
        self.limit = limit

    def push(self, item):
        if len(self.customArray) > self.limit:
            self.limit = self.limit + 1
        return self.customArray.insert(0, item)


    def pop(self):
        return self.customArray.pop(0)

    def size(self):
        return self.limit

    def print(self):
        return print("Stack is:", self.customArray)

    def searchByValue(self, value):
        print(self.customArray.index(value))
        return self.customArray.index(value)

    def searchByIndex(self, index):
        print(self.customArray[index])
        return self.customArray[index]

customArray = CustomArray(10)
customArray.push(1)
customArray.push(2)
customArray.push(3)
customArray.print()

customArray.pop()
customArray.print()
customArray.searchByIndex(1)
customArray.searchByValue(1)

Below we have a Ruby program implementing an array data structure

class CustomArray
    def initialize(limit)
        @@customArray = []
        @@limit = limit
    end

    def pop
        if @@customArray.length > 0
            @@customArray.pop
        end
    end

    def push(item)
        @@customArray.push(item)
    end

    def print
        puts "#{@@customArray}"
    end

    def searchByIndex(index)
        puts @@customArray.at(index)
    end

    def searchByValue(item)
        puts @@customArray.find_index(item)
    end

    def size
        puts "#{@@limit}"
    end    
end

arr = CustomArray.new(10)
arr.push(1);
arr.push(2);
arr.push(3);
arr.print();

arr.pop();
arr.print();
arr.searchByIndex(1);
arr.searchByValue(1);
arr.size

Queue Data Structure in Javascript, Python and Ruby

Abhishek Sharma Gaur — Sat, 13 May 2023 19:13:32 +0000

Like stacks, queues are abstract data structures. In a queue, the first element is inserted from one end, called REAR (also called the tail), and the removal of existing elements from the other end, is called FRONT (also called the head).

This makes the queue a FIFO (First In First Out) data structure, where the first element inserted is the first element removed.

Queue applications
Queues, as the name suggests, are used whenever we need to manage any group of objects on a first-come-first-served basis. Here are a few examples of the same:

Serving requests on a single shared resource, such as a printer, CPU task scheduling, etc.
In a real-life scenario, call centre phone systems use queues to queue people who call them, unless the service representative is free.

Algorithm for ENQUEUE operation

Check if the queue is full or not.
If the queue is full, then pop the first element / give an overflow error and exit the program.
If you popped the first element, then increment the tail and add the element.
If the queue is not full, then increment the tail and add the element.

Algorithm for DEQUEUE operation

Check if the queue is empty or not.
If the queue is empty, then print the underflow error and exit the program.
If the queue is not empty, then print the element at the head and increment the head.

Time Complexity:

Enqueue: O(1)
Dequeue: O(1)
Size: O(1)

The functions associated with queue are:

empty() – Returns whether the stack is empty – Time Complexity: O(1)

size() – Returns the size of the stack – Time Complexity: O(1)

top() / peek() – Returns a reference to the topmost element of the stack – Time Complexity: O(1)

push(a) – Inserts the element ‘a’ at the top of the stack – Time Complexity: O(1)

pop() – Deletes the topmost element of the stack – Time Complexity: O(1)

print - To print the stack

Stack Data Structure in Javascript, Python and Ruby

Abhishek Sharma Gaur — Sat, 13 May 2023 17:36:58 +0000

A stack is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack and the only element that can be removed is the element that is at the top of a stack, just like a pile of books.

Stack is an ordered list of similar data types following the LIFO(Last in First out) principle. Here the push() function is used to insert new elements into the Stack and the pop() function is used to remove the topmost element from the stack.

Algorithm for PUSH operation

Check if the stack is full or not.
If the stack is full, exit the program.
If the stack is not full, then increment the top and add the element.

Algorithm for POP operation

Check if the stack is empty or not.
If the stack is empty, print the underflow error and exit the program.
If the stack is empty, print the element at the top and decrement the top.

Time complexity

Push: O(1)
Pop: O(1)
Size: O(1)

The functions associated with stack are:

empty() – Returns whether the stack is empty – Time Complexity: O(1)

size() – Returns the size of the stack – Time Complexity: O(1)

top() / peek() – Returns a reference to the topmost element of the stack – Time Complexity: O(1)

push(a) – Inserts the element ‘a’ at the top of the stack – Time Complexity: O(1)

pop() – Deletes the topmost element of the stack – Time Complexity: O(1)

print - To print the stack

Below we have a Javascript program implementing a stack data structure

class Stack {
  constructor(){
        this.stack = [];
    }

  push = (item) => {
    return item ? this.stack.push(item) : "do nothing";
  };
  pop = () => this.stack.pop();
  isEmpty = () => (this.stack.length === 0 ? true : false);
  size = () => this.stack.length
  peek = () => this.stack[-1]
  print = () => 
   console.log("stack:",JSON.stringify(this.stack));
}

Below we have a Python program implementing a stack data structure

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        return self.items.insert(0, item)


    def pop(self):
        return self.items.pop(0)

    def peek(self):
        return self.items[0]

    def size(self):
        return len(self.items)

    def print(self):
        return print("Stack is:", self.items)

Below we have a Ruby program implementing a stack data structure

class Stack
    attr_reader :item
    @@contents = []
    def initialize(item)
        @item = item
        @@contents << item 
    end

    def pop
        @@contents.pop
    end

    def push(item)
        @@contents.push(item)
    end

    def print
        puts "#{@@contents}"
    end

    def peek
        puts "#{@@contents.last}"
    end

    def size
        puts "#{@@contents.length}"
    end    
end