Mushroom Picker (A problem on Prefix Sums)

Problem

You are given a non-empty, zero-indexed array A of n (1 <= n <= 100000) integers a0, a1,..., an−1 (0 <= ai <= 1000). This array represents number of mushrooms growing on the consecutive spots along a road. You are also given integers k and m (0 <= k, m < n).

A mushroom picker is at spot number k on the road and should perform m moves. In one move she moves to an adjacent spot. She collects all the mushrooms growing on spots

she visits. The goal is to calculate the maximum number of mushrooms that the mushroom

picker can collect in m moves.

For example, consider array A such that:

A[0]=2, A[1]=3, A[2]=7, A[3]=5, A[4]=1, A[5]=3, A[6]=9

The mushroom picker starts at spot k = 4 and should perform m = 6 moves. She might

move to spots 3, 2, 3, 4, 5, 6 and thereby collect 1 + 5 + 7 + 3 + 9 = 25 mushrooms. This is the

maximal number of mushrooms she can collect.

Code

# Counting prefix sums
  def prefix_sums(A):
      n = len(A)
      P = [0] * (n + 1)
      for k in xrange(1, n + 1):
          P[k] = P[k - 1] + A[k - 1]
      return P
  
  # Total of one slice
  def count_total(P, x, y):
      return P[y + 1] - P[x]
  # Mushroom picker — O(n + m)
  def mushrooms(A, k, m):
      n = len(A)
      result = 0
      pref = prefix_sums(A)
  
  # When we first take p steps on the left and return from their back in right direction.
      for p in xrange(min(m, k) + 1):
          left_pos = k - p
          right_pos = min(n - 1, max(k, k + m - 2*p))
          result = max(result, count_total(pref, left_pos, right_pos)) 
  
  # When we first take p steps on the right and return from their back in left direction.
      for p in xrange(min(m + 1, n - k)):
          right_pos = k + p
          left_pos = max(0, min(k, k - (m - 2*p)))
          result=max(result, count_total(pref, left_pos, right_pos)) 
      return result

Explanation (Part 1)

# When we first take p steps on the left and return from their back in right direction.
    for p in xrange(min(m, k) + 1):
        left_pos = k - p
        right_pos = min(n - 1, max(k, k + m - 2*p))
        result = max(result, count_total(pref, left_pos, right_pos)) 

Expression “for p in xrange(min(m, k) + 1)” has min(m, k) because we can only go m steps to the left or k steps to the left whichever number is minimum.

After going k steps, we cannot go past 0th position.

Or after taking m steps, we cannot take another step.

Expression “right_pos = min(n - 1, max(k, k + m – 2*p))” has ‘k+m-2*p’ because after taking p steps to the left, we are returning p steps back to position k, hence 2p.

And then number of steps left is: m – 2p

Then right position is identified by: m-2p steps after k ie, k+m-2p

Expression “right_pos = min(n - 1, max(k, k + m – 2*p))” has max(k, k + m – 2*p) because what if we take all the m steps to left and value of p becomes m.

Then there are no steps left to take to the right and right position is simply identified by k.

Similarly, for any value of p > m/2 (as in 0.6m or 0.75m), we would get same right position as k.

Explanation (Part 2)

# When we first take p steps on the right and return from their back in left direction.
    for p in xrange(min(m + 1, n - k)):
        right_pos = k + p
        left_pos = max(0, min(k, k - (m - 2*p)))
        result = max(result, count_total(pref, left_pos, right_pos))

Here in the expression “for p in xrange(min(m + 1, n – k))”, we have m+1 and not just m because xrange goes till m when passed the argument m+1. Similarly, we have n-k and not (n-1)-k because xrange goes till (n-1)-k when passed the argument n-k.

And we take minimum of m or (n-1)-k because that’s is the possible number of steps we can take on the right.

Here in the expression “left_pos = max(0, min(k, k - (m – 2*p)))”, we have k-(m-2p) because we take p steps on the right, then take those p steps back to k (on the left now).

Number of steps yet to take: m-2p

Left position would be identified by: k-(m-2p)

If p takes value m, which means we have taken m steps on the right, then we have no steps remaining to take to the left and left position is identified by k itself. (This logic is valid for any value of p > m/2)

Side Note

The way we calculating prefix sums and sums of subsections is without using the Python built-ins. But if we were to use Python built-ins, the code would look somewhat like this:

def get_mushrooms_sum(A, start, end):
  return sum(A[start : end + 1])

Coding Round in Interview for Data Scientist Role at a Bank (17 Nov 2023)

Task 1

Write a function:

    def solution(A)

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [1..100,000];
        each element of array A is an integer within the range [−1,000,000..1,000,000].

A brute-force solution to this problem that will fail the performance tests will look like this:


def solution(A):
    # a_sort = sorted(A)
    rtn = -1
    for i in range(1, 100001):
        if i in A: # This is the most time consuming instruction of this code that runs repeatedly for all of i(s)
            continue
        else:
            rtn = i
            break
    return rtn 


Task 2




Task 3

Fig 3.1



Fig 3.2



Fig 3.3

Building a Tree from a BODMAS Expression (An exercise in Recursion)

There is an expression with N variables as in A, B, C, X, Y, Z. Note that variables do not repeat. And N-1 variables which can be +,-,*, and /

For example:

Ex 1: X + Y * Z
Ex 2: X - Y * Z + A
Ex 3: X * Y - Z / A
Ex 4: X / Y / Z
Ex 5: X * Y / Z
Ex 6: Z - Y + X 

Now, can you give me a recursion based JavaScript code to create a tree with operators on non-leaf nodes and leaf nodes contains the variables based on the BODMAS evaluation of the expression.

Code Pre-read

Certainly! To represent an expression as a tree structure in JavaScript, you can use a recursive data structure. Here's a simple example of how you can create a tree with operators on non-leaf nodes and variables on leaf nodes based on BODMAS evaluation:

…

Code in on next slide

This code defines a TreeNode class to represent nodes in the expression tree. The buildExpressionTree function takes an expression as input and returns the root of the expression tree. The tree is built recursively based on the BODMAS rules, with operators on non-leaf nodes and variables on leaf nodes.

Note: This code assumes that the input expression is properly formatted and follows BODMAS rules.

Code to Build a Tree Node

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
} 

Code

function buildExpressionTree(expression) {
  // Tokenize Expression
  const tokens = expression.split(/\s/).filter(token => token.trim() !== ''); 

    
    // Helper function to build the expression tree recursively
    function buildTree(start, end) {
        if (start === end) {
            // Base case: single variable
            return new TreeNode(tokens[start]);
        }

        // Find the operator with the lowest precedence
        let minPrecedence = Infinity;
        let minIndex = -1;
        
        for (let i = start; i < end; i++) {
            if (tokens[i] === '+' || tokens[i] === '-') {
                const precedence = 1;
                if (precedence <= minPrecedence) {
                    minPrecedence = precedence;
                    minIndex = i;
                }
            } else if (tokens[i] === '*' || tokens[i] === '/') {
                const precedence = 2;
                if (precedence <= minPrecedence) {
                    minPrecedence = precedence;
                    minIndex = i;
                }
            }
        }
// Create the current node with the operator
        const currentNode = new TreeNode(tokens[minIndex]);

        // Recursively build left and right subtrees
        currentNode.left = buildTree(start, minIndex - 1);
        currentNode.right = buildTree(minIndex + 1, end);

        return currentNode;
    }

    // Build the tree starting from the root
    return buildTree(0, tokens.length - 1);
}

// Example usage:
const expression = "X + Y * Z";
const expressionTree = buildExpressionTree(expression);
console.log(expressionTree);

Explanation of the code

Certainly! Let's go through the code line by line:

TreeNode Class

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

This part defines a TreeNode class, which will be used to represent nodes in the expression tree. Each node has a value (either an operator or a variable), a left child, and a right child.

function buildExpressionTree(expression) {
    const tokens = expression.split(/\s/).filter(token => token.trim() !== ''); // Tokenize expression

    The buildExpressionTree function takes an input expression and splits it into tokens using a regular expression. The regular expression \b matches word boundaries, and filter is used to remove any empty or whitespace-only tokens.


    // Helper function to build the expression tree recursively
    function buildTree(start, end) {
        if (start === end) {
            // Base case: single variable
            return new TreeNode(tokens[start]);
        }

    The buildTree function is a helper function for building the expression tree recursively. The base case checks if start and end are the same, which means we have reached a leaf node containing a single variable. In this case, a new TreeNode is created with the variable as its value.

Operator Precedence
Next, we are going to look at operator precedence.
Viz:
In the order DM > AS 
And if it’s DD or MM or DM, then left to right.
        // Find the operator with the lowest precedence
        let minPrecedence = Infinity;
        let minIndex = -1;
        
        for (let i = start; i < end; i++) {
            if (tokens[i] === '+' || tokens[i] === '-') {
                const precedence = 1;
                if (precedence <= minPrecedence) {
                    minPrecedence = precedence;
                    minIndex = i;
                }
            } else if (tokens[i] === '*' || tokens[i] === '/') {
                const precedence = 2;
                if (precedence <= minPrecedence) {
                    minPrecedence = precedence;
                    minIndex = i;
                }
            }
        }

    This part of the code searches for the operator with the lowest precedence in the given range (start to end). It iterates through the tokens, updating minPrecedence and minIndex whenever it finds an operator with lower precedence.



        // Create the current node with the operator
        const currentNode = new TreeNode(tokens[minIndex]);

        // Recursively build left and right subtrees
        currentNode.left = buildTree(start, minIndex - 1);
        currentNode.right = buildTree(minIndex + 1, end);

        return currentNode;
    }

    Once the operator with the lowest precedence is found, a new TreeNode is created with that operator as its value. The left and right children of this node are then recursively built using the buildTree function.
    // Build the tree starting from the root
    return buildTree(0, tokens.length - 1);
}

    Finally, the buildExpressionTree function initiates the construction of the expression tree by calling buildTree with the entire range of tokens. The function returns the root of the expression tree.



// Example usage:
const expression = "X + Y * Z";
const expressionTree = buildExpressionTree(expression);
console.log(expressionTree);

    This part demonstrates the usage of the code by creating an example expression ("X + Y * Z") and building an expression tree from it. The resulting tree is then printed to the console. The example expression can be replaced with other expressions as needed.

Overall, this code recursively builds an expression tree based on the BODMAS rules, where operators are placed on non-leaf nodes and variables on leaf nodes.
  

Prompts we tried on ChatGPT

There is an expression with N variables as in A, B, C, X, Y, Z. And N-1 variables which can be +,-,*, and /

For example:

Ex 1: X + Y * Z
Ex 2: X - Y * Z + A
Ex 3: X * Y - Z / A
Ex 4: X / Y / Z
Ex 5: X * Y / Z
Ex 6: Z - Y + X 

A problem can have from 1 to 5 operators.

Now, can you give me a recursion based Python code to create a BODMAS based parenthesized expression for the given expression.

Bubble Sort (Using Recursion)

Can you give me python code for bubble sort?

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Here's a simple Python implementation of the bubble sort algorithm:


def bubble_sort(arr):
    n = len(arr)

    # Traverse through all array elements
    for i in range(n):
        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Example usage:
my_list = [64, 25, 12, 22, 11]
bubble_sort(my_list)

print("Sorted array:", my_list)


This code defines a function bubble_sort that takes a list as input and sorts it in ascending order using the bubble sort algorithm. The example usage shows how to sort an example list, and the sorted array is then printed.

Using recursion?

Although bubble sort is not typically implemented using recursion due to its inefficiency compared to iterative methods, it can be done for educational purposes. Here's an example of a recursive implementation of bubble sort in Python:


def recursive_bubble_sort(arr, n=None):
    # Base case: If the array is empty or contains only one element, it is already sorted
    if n is None:
        n = len(arr)
    
    if n <= 1:
        return
    
    # One pass of bubble sort: Traverse the array and swap adjacent elements if they are in the wrong order
    for i in range(n - 1):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]

    # Recursively call the function with a reduced size of the array
    recursive_bubble_sort(arr, n - 1)

# Example usage:
my_list = [64, 25, 12, 22, 11]
recursive_bubble_sort(my_list)

print("Sorted array:", my_list)

In this recursive implementation, the function recursive_bubble_sort takes an additional parameter n to represent the size of the array being considered in each recursive call. The base case checks if the array size is 1 or less, in which case the array is considered sorted. Otherwise, one pass of the bubble sort is performed, and the function is called recursively with a reduced size of the array.

What is the time complexity of the recursion based code?

The time complexity of the recursive version of bubble sort remains O(n^2) in the worst and average cases, just like the iterative version. This is because, even though recursion is used, the number of comparisons and swaps required to sort the array is still proportional to the square of the number of elements in the array.

Each recursive call performs one pass through the array, and there are a total of n recursive calls (each reducing the size of the array by 1). In each pass, the algorithm compares and potentially swaps adjacent elements, and this process is repeated for each pass until the array is sorted.

Therefore, the overall time complexity is still O(n^2), which makes bubble sort, whether implemented iteratively or recursively, inefficient for large datasets compared to more advanced sorting algorithms like quicksort or mergesort.

Tags: Algorithms,Python,Technology,

Missing Integer: Find the smallest positive integer that does not occur in a given sequence.

MissingInteger

Find the smallest positive integer that does not occur in a given sequence.

Problem

Write a function:

def solution(A)

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [−1,000,000..1,000,000].

Rohit’s Solution: Based on sorting of input array

def solution(A):
  B = [i for i in A if i > 0]
  if len(B) > 1:
      B = sorted(list(set(B)))
      if B[0] != 1:
          return 1
  elif len(B) == 1:
      if B[0] == 1:
          return 2
      else:
          return 1
  else:
      return 1
  for i in range(len(B) - 1):
      if B[i+1] - B[i] != 1:
          return B[i] + 1
      elif B[i+1] - B[i] == 1 and (i+1) == len(B)-1:
          return B[i+1] + 1

The idea is to:

(1) Sort the input array

(2) Capture differences between two consecutive numbers, if the difference is not equal to one return there with the appropriate value.

My Solution: Based on a counter variable

Detected time complexity: O(N) or O(N * log(N))

The idea is to maintain a counter with length equal to len(A) + 1

This counter is initialized to False and counter[0] initialized to True.

The n’th element of counter signifies () if the element was found in input array A or not.

We iterate of A to update our counter.

Then to return an output, we iterate over A again to detect the first False flag and return it’s index.

Code

def solution(A):
  if len(A) == 1:
      if A[0] == 1:
          return 2
      else:
          return 1
  else:
      B = [False for i in range(len(A) + 1)]
      B[0] = True 
      for i in A:
          if i < len(B) and i > 0:
              B[i] = True 
          
      for i in range(len(B)):
          if B[i] == False:
              return i
      return len(B)

Tags: Algorithms,Technology,Python,

Max Counters (a problem on counting elements)

MaxCounters

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

Problem

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,

max counter − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),

if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and array A such that:

A[0] = 3, A[1] = 4, A[2] = 4, A[3] = 6, A[4] = 1, A[5] = 4, A[6] = 4

the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)

(0, 0, 1, 1, 0)

(0, 0, 1, 2, 0)

(2, 2, 2, 2, 2)

(3, 2, 2, 2, 2)

(3, 2, 2, 3, 2)

(3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3, A[1] = 4, A[2] = 4, A[3] = 6, A[4] = 1, A[5] = 4, A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000];

each element of array A is an integer within the range [1..N + 1].

Example

For example, given integer N = 5 and array A such that:

A[0] = 3, A[1] = 4, A[2] = 4, A[3] = 6, A[4] = 1, A[5] = 4, A[6] = 4

the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)

(0, 0, 1, 1, 0)

(0, 0, 1, 2, 0)

(2, 2, 2, 2, 2)

(3, 2, 2, 2, 2)

(3, 2, 2, 3, 2)

(3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

If given:

A[0] = 3, A[1] = 4, A[2] = 4, A[3] = 6, A[4] = 1, A[5] = 4, A[6] = 4

the function should return [3, 2, 2, 4, 2] as explained.

Hint: Let’s analyze the Brute-Force Solution

In Brute-Force solution, we follow the instructions as given.

We increase the counters on encountering the increase operation.

And on encountering the maxCounter() operation, we loop over the counters and set them equal to max counter.

This would solve the problem but would result in a quadratic time complexity.

Hint: Worst Case Scenario For Brute Force Solution. Time Complexity of: N*M

Hint: Linear Time Complexity

The bottleneck for the code is the maxCounter() operation. So, in this solution we find a smart way of implementing the maxCounter() operation.

We would draw an analogy between our counters and racers on a race track.

We would maintain two variables:

1. startLine: that tracks the where the racers are starting.

Basically, on encountering the maxCounter() operation, we would update this field.

2. currentMax: That tracks the maximum value among the counters.

This variable will be used to update the other variable startLine on encountering a maxCounter() operation.

Hint: Linear Time Solution

Hint: What happens when we encounter a maxCounter() op? We update our startLine.

Code

def increase(X, counters, startLine, currentMax):
  if counters[X] < startLine:
      counters[X] = startLine 
  counters[X] += 1
  if counters[X] > currentMax:
      currentMax = counters[X]
  return counters, currentMax
def maxCounter(startLine, currentMax):
  startLine = currentMax
  return startLine 
def solution(N, A):
  startLine = 0
  currentMax = 0
  counters = [0 for i in range(N)]
  
  for i in A:
      if i < N+1:
          counters, currentMax = increase(i-1, counters, startLine, currentMax)
      else:
          startLine = maxCounter(startLine, currentMax)
          
  for i in range(len(counters)):
      if counters[i] < startLine:
          counters[i] = startLine 
  return counters

Detected time complexity: O(N + M)

Test Cases

Correctness tests

extreme_small: all max_counter operations

single: only one counter

small_random1: small random test, 6 max_counter operations

small_random2: small random test, 10 max_counter operations

Performance tests

medium_random1: medium random test, 50 max_counter operations

medium_random2: medium random test, 500 max_counter operations

large_random1: large random test, 2120 max_counter operations

large_random2: large random test, 10000 max_counter operations

extreme_large: all max_counter operations

'Continuous Bag of Words' Model For Getting Word Embeddings

CBOW stands for Continuous Bag of Words, and it is a type of word embedding model used in natural language processing (NLP). CBOW is a shallow neural network model that belongs to the family of neural network language models. The primary goal of CBOW is to predict a target word based on its context, which consists of the surrounding words in a given window.

Here's a brief overview of how CBOW works:

    Architecture:
        CBOW is a feedforward neural network with a single hidden layer.
        The input layer represents the context words (words within a specific window around the target word), and the output layer represents the target word.
        The hidden layer processes the input context to learn the relationships between words.

    Training:
        CBOW is trained using a large corpus of text data.
        The objective is to maximize the likelihood of predicting the target word given its context. The model is trained to minimize the cross-entropy loss between the predicted probability distribution over words and the actual distribution (one-hot encoded vector representing the target word).

    Word Embeddings:
        Once trained, the weights of the hidden layer in the CBOW model serve as word embeddings.
        These word embeddings capture semantic relationships between words based on their co-occurrence patterns in the training data.
        Each word in the vocabulary is represented as a dense vector in a continuous vector space.

    Context Window:
        CBOW uses a fixed-size context window around the target word. This window determines the input context for the model.
        For example, if the context window size is 2, and the target word is in the middle of a sentence, the model is trained to predict the target word based on the two words to its left and the two words to its right.

CBOW is known for its simplicity and efficiency in training compared to other more complex models. It is especially useful in scenarios where the focus is on word similarity and capturing semantic relationships in a given context. Word2Vec, a popular word embedding model, includes both CBOW and Skip-gram variants, with CBOW being one of the options for generating word embeddings.

Figure 1:



Figure 2: 
A simple application of CBOW model is an article spinner.



Figure 3:



Figure 4:

Tags: Natural Language Processing,Technology

Choice of activation function between Sigmoid and Hyperbolic tangent, and its relation to vanishing gradients problem

In terms of their use as activation functions, when is sigmoid used and when is hyperbolic tangent used?

Sigmoid and hyperbolic tangent (tanh) are both activation functions commonly used in neural networks, but they have different characteristics that make them suitable for different situations.

Sigmoid Function (Logistic Function):
        Range: It squashes input values to the range (0, 1).
        Output: The output is always positive, and it is particularly useful in binary classification problems where the goal is to output probabilities that sum to 1.
        Issues: Sigmoid tends to suffer from the "vanishing gradient" problem, which can make training deep networks challenging.

    Use Cases:
        Output layer of binary classification models.
        Situations where you need a binary decision, such as in logistic regression.

Hyperbolic Tangent Function (tanh):
        Range: It squashes input values to the range (-1, 1).
        Output: Like the sigmoid, it is suitable for models that require outputs in the form of probabilities. However, its output range includes negative values, making it zero-centered. This helps mitigate the vanishing gradient problem to some extent.
        Advantages: Zero-centered nature helps in the optimization process during training, compared to the sigmoid.

    Use Cases:
        Hidden layers of neural networks, especially in cases where zero-centered activation functions are preferred.
        Situations where the output needs to be in a range that spans both positive and negative values.

In practice, the choice between sigmoid and tanh depends on the specific requirements of your neural network and the nature of the problem you're trying to solve. In modern deep learning architectures, rectified linear units (ReLU) and its variants are also popular choices for hidden layers due to their training efficiency and ability to mitigate the vanishing gradient problem.

Why and how do sigmoid activation function results in vanishing gradient problem?

The vanishing gradient problem is a challenge that can occur during the training of deep neural networks, particularly when using activation functions with certain characteristics, such as the sigmoid function. The problem arises in the context of gradient-based optimization algorithms, like backpropagation, which are commonly used to update the weights of neural networks during training.

Here's why the sigmoid activation function can lead to the vanishing gradient problem:

    Output Range: The sigmoid function squashes input values to the range (0, 1). This means that for large positive or negative inputs, the sigmoid saturates, and the output becomes very close to 0 or 1. Once the output is near these extremes, the gradient of the sigmoid becomes extremely small.

    Derivative Characteristics: The derivative of the sigmoid function is maximum at its center (around 0.25) and approaches zero as you move away from the center. This means that the gradients for large positive or negative inputs are close to zero. In the context of backpropagation, the gradient is used to update the weights of the network, and if the gradients are very small, the updates to the weights become negligible.

    Multiplicative Nature of Gradients: In a deep neural network, during backpropagation, gradients are propagated backward through the layers. Since the gradients are multiplied at each layer, if the gradients are very small, they can quickly diminish as they are propagated backward through the network. This can result in the gradients becoming effectively zero for the weights in the early layers of the network, preventing effective learning in those layers.

In summary, the vanishing gradient problem occurs because the sigmoid function, when used in deep networks, can produce very small gradients for weights in the early layers, hindering the training process. This can lead to slower convergence and, in extreme cases, the early layers may not learn meaningful representations.

To mitigate the vanishing gradient problem, other activation functions like hyperbolic tangent (tanh) or rectified linear units (ReLU) are often used, as they exhibit better training characteristics in deep networks.

On a side note...

Derivative of Sigmoid function






Derivative of tanh(z)

An alternative to the logistic sigmoid is the hyperbolic tangent, or tanh function (Figure 1, green curves):




Like the logistic sigmoid, the tanh function is also sigmoidal (“s”-shaped), but instead outputs values that range (-1,1). Thus strongly negative inputs to the tanh will map to negative outputs. Additionally, only zero-valued inputs are mapped to near-zero outputs. These properties make the network less likely to get “stuck” during training. Calculating the gradient for the tanh function also uses the quotient rule:




Similar to the derivative for the logistic sigmoid, the derivative of gtanh(z) is a function of feed-forward activation evaluated at z, namely (1-gtanh(z)2). Thus the same caching trick can be used for layers that implement tanh activation functions.

Common Activation Functions and Plots of Their Derivatives

Side notes

(1) How are tanh and sigmoid related? Can you write tanh as a function of sigmoid?

The hyperbolic tangent function (tanh) and the sigmoid function (often the logistic sigmoid) are related through a simple mathematical transformation. The tanh function can be expressed in terms of the sigmoid function as follows:

$\tanh(x) = 2 \sigma(2x) - 1$

Here, $\sigma(x)$ represents the sigmoid function, defined as $\sigma(x) = \frac{1}{1 + e^{-x}}$.

So, to obtain the tanh function, you take twice the input ($2x$), apply the sigmoid function to it ($\sigma(2x)$), multiply the result by 2 ($2 \sigma(2x)$), and then subtract 1 ($2 \sigma(2x) - 1$). This transformation ensures that the output of the tanh function is in the range of $[-1, 1]$, similar to how the sigmoid function squashes values into the range $[0, 1]$.

(2) If both Sigmoid and Tanh based models face vanishing gradient problem, what's the alternative?: Ans: ReLU (Rectified Linear Unit)

Vedic Personality Test (From the Book 'Think Like a Monk') and Some other commonly used Personality Indicators

Vedic Personality Test is to assess your working style inclination.

THE VARNAS
    
The four varnas are the Guide, the Leader, the Creator, and the Maker. These labels aren't directly tied to specific jobs or activities. Sure, certain activities bring us pleasure because they fulfill our dharma, but there are many di erent ways tolive in our dharma. A Guide is compelled to learn and share knowledge—you could be a teacher or a writer. A Leader likes to influence and provide, but that doesn't mean you have to be a CEO or a lieutenant—you could be a school principal or shop manager. A Creator likes to make things happen—this could be at a start-up or in a neighborhood association. A Maker likes to see things tangibly being built—they could be a coder or a nurse.

Remember the gunas: tamas, rajas, and sattva—ignorance, impulsivity, and goodness. For each of the varnas I describe what their behavior looks like in each guna mode. We strive toward sattva through letting go of ignorance, working in our passion, and serving in goodness. The more time we spend in sattva, the more effective and fulfilled we become.

Creators

Originally: merchants, businesspeople
Today: marketers, salespeople, entertainers, producers, entrepreneurs, CEOs
Skills: brainstorming, networking, innovating
# Make things happen
# Can convince themselves and others of anything
# Great at sales, negotiation, persuasion
# Highly driven by money, pleasure, and success
# Very hardworking and determined
# Excel in trade, commerce, and banking
# Always on the move
# Work hard, play hard

Mode of Ignorance

# Become corrupt and sell things with no value / Lie, cheat, steal to sell something
# Beaten down by failure
# Burned out, depressed, moody, due to overwork

Mode of Impulse

# Status-driven
# Dynamic, charismatic, and captivating
# Hustler, goal-oriented, tireless

Mode of Goodness

# Use money for greater good
# Create products and ideas that make money but also serve others
# Provide jobs and opportunities for others

Makers

Originally: artists, musicians, creatives, writers
Today: social workers, therapists, doctors, nurses, COOs, heads of human
resources, artists, musicians, engineers, coders, carpenters, cooks
Skills: inventing, supporting, implementing

Mode of Ignorance

# Depressed by failure
# Feel stuck and unworthy
# AnxiousMode of Impulse
# Explore and experiment with new ideas
# Juggle too many things at the same time
# Lose focus on expertise and care; focus more on money and results

Mode of Goodness

# Driven by stability and security
# Generally content and satis ed with the status quo
# Choose meaningful goals to pursue
# Work hard but always maintain balance with family commitments
# Best right-hand man or woman
# Lead team gatherings
# Support those in need
# Highly skilled at manual professions

Connections

# Makers and Creators complement each other
# Makers make Creators focus on detail, quality, gratitude, and contentment
# Creators help Makers think bigger, become more goal-oriented

Guides

Originally and today: teachers, guides, gurus, coaches, mentors
Skills: learning, studying, sharing knowledge, and wisdom

# A coach and a mentor no matter what role they play want to bring out the best in the people in their life.
# Value knowledge and wisdom more than fame, power, money, security
# Like having space and time to re ect and learn
# Want to help people nd meaning, ful llment, and purpose
# Like to work alone
# Enjoy intellectual pursuits in their spare time—reading, debate, discussion

Mode of Ignorance

# Don't practice what they preach
# Don't lead by example
# Struggle with implementation

Mode of Impulse

# Love to debate and destroy others' arguments
# Use knowledge for strength and power
# Intellectually curious

Mode of Goodness

# Use knowledge to help people nd their purpose
# Aspire to better themselves in order to give more
# Realize knowledge is not theirs to use alone, but that they are here to serve

Leaders

Originally: kings, warriors
Today: military, justice, law enforcement, politics
Skills: governing, inspiring, engaging others

# Natural leaders of people, movements, groups, and families
# Directed by courage, strength, and determination
# Protect those who are less privileged
# Led by higher morals and values and seek to enforce them across the world
# Provide structures and frameworks for the growth of people
# Like to work in teams
# Great at organization, focus, and dedication to a mission

Mode of Ignorance

# Give up on change due to corruption and hypocrisy
# Develop a negative, pessimistic viewpoint
# Lose moral compass in drive for power

Mode of Impulse

# Build structures and frameworks for fame and money, not meaning
# Use their talents to serve themselves not humanity
# Focus on short term goals for themselves

Mode of Goodness

# Fight for higher morals, ethics, and values
# Inspire people to work together
# Build long-term goals to support society

Connections

# Guides and Leaders complement each other
# Guides give wisdom to Leaders
# Leaders give structure to Guides

The point of the varnas is to help you understand yourself so you can focus on your strongest skills and inclinations. Self-awareness gives you more focus. When I look at my Guide tendencies, it makes sense to me that I succeed when I focus on strategy. Creators and Makers are better at implementation, so I've surrounded myself with people who can help me with that. A musician might be a Maker, driven by security. In order to succeed, they might need to be surrounded by strategists. 

Invest in your strengths and surround yourself with people who can fill in the gaps.
When you know your varna—your passion and skills—and you serve with that, it becomes your dharma.

~~~

Answer these questions as who you believe you are at the core. Beyond what friends, family, or society have made you choose.

1. Which of the following sounds most like what you're about?
a. Values and wisdom
b. Integrity and perfection
c. Work hard play hard
d. Stability and balance

2. What role do you play in your friends circle / family?
a. I am comfortable dealing with conflict and helping people nd middle ground. My role is the mediator.
b. I make sure everything and everyone is taken care of. My role is the protector.
c. I help my family understand work ethic, hustle, and the value of having resources. My role is material support.
d. I focus on nurturing and wanting a healthy and content family. My role is emotional support.

3. What is most important to you in a partner?
a. Honest and smart
b. Strong presence and power
c. Fun and dynamic
d. Reliable and respectful

4. What do you watch most often on TV?
a. Documentaries, biographies, human observations
b. Entertainment, politics, current affairs
c. Comedy, sport, drama, motivational stories
d. Soap operas, reality TV, family, gossip, daytime shows

5. Which best describes how you behave when under stress?
a. Calm, composed, balanced
b. Irritated, frustrated, angry
c. Moody, loud, restless
d. Lazy, depressed, worried

6. What causes you the most pain?
a. Feeling like I don't live up to my own expectations
b. The state of the world
c. A sense of rejection
d. Feeling disconnected from friends and family

7. What is your favorite way of working?
a. Alone, but with mentors and guides
b. In a team as a leader
c. Independently, but with a strong network
d. In a team as a member

8. How would your ideal self spend spare time?
a. Reading, in deep discussion, and reflecting
b. Learning about issues and/or attending political events
c. There's no such thing as spare time! networking, connecting, working
d. Enjoying time with family and friends

9. How would you describe yourself in three words?
a. Idealistic, introverted, insightful
b. Driven, dedicated, determined
c. Passionate, motivated, friendly
d. Caring, loving, loyal

10. In what type of environment do you work best?
a. Remote, silent and still, natural
b. A meeting room or gathering space
c. Anywhere and everywhere (during my commute, in a coffee shop, in mybedroom)
d. A space specific to my type of work: home, office, laboratory

11. What's your work style?
a. Slow and reflective
b. Focused and organized
c. Fast and rushed
d. Specific and deliberate

12. How would you like to make a difference in the world?
a. Through spreading knowledge
b. Through politics and activism
c. Through business and/or leadership
d. Through local community

13. How do you prepare for a vacation?
a. By picking my reading material
b. By having a focused plan of key sites to visit
c. With a list of the best bars, clubs, and restaurants
d. With an easygoing attitude

14. How do you deal with tough conversations?
a. Look for a compromise
b. Fight for the most objective truth
c. Fight to prove I'm right
d. Avoid confrontation

15. If someone in your life is having a bad week, what do you do?
a. Give them advice and guidance
b. Become protective and encourage them to improve
c. Urge them to have a drink or take a walk with me
d. Go to them and keep them company

16. How do you see rejection?
a. It's part of life
b. It's a challenge I can rise to meet
c. It's frustrating but I'll move on
d. It's a real setback

17. At an event/party how do you spend your time?
a. I have a meaningful discussion with one or two people
b. I usually talk with a group of people
c. I somehow end up the center of attention
d. I help with whatever needs to be done

18. How do you feel if you make a mistake?
a. I feel guilty and ashamed
b. I have to tell everyone
c. I want to hide it
d. I reach out to someone supportive

19. What do you do when you have to make a big decision?
a. I reflect privately
b. I ask my mentors and guides
c. I weigh the pros and cons
d. I talk to family and friends

20. Which best describes your daily routine?
a. It changes moment to moment
b. It's very focused and organized
c. I follow the best opportunity that comes up
d. It's simple and scheduled

ANSWER KEY

Tally your answers now. The most selected letter likely re ects your varna.
A. Guide
B. Leader
C. Creator
D. Maker

A Look at Some Other Popular Personality Tests

Can you tell me about MBTI personality indicator?

Certainly! The Myers-Briggs Type Indicator (MBTI) is a widely used personality assessment that categorizes individuals into 16 personality types based on their preferences in four dichotomies. These dichotomies are:

    Extraversion (E) vs. Introversion (I):
        Extraversion: Focus on the outer world of people and activities.
        Introversion: Focus on the inner world of thoughts and reflections.

    Sensing (S) vs. Intuition (N):
        Sensing: Prefer concrete and practical information.
        Intuition: Prefer conceptual and innovative information.

    Thinking (T) vs. Feeling (F):
        Thinking: Make decisions based on logic and consistency.
        Feeling: Make decisions based on personal values and the impact on people.

    Judging (J) vs. Perceiving (P):
        Judging: Prefer a planned and organized approach to life.
        Perceiving: Prefer a flexible and spontaneous approach to life.

To determine your MBTI type, you can take a reliable MBTI assessment. There are many online resources that offer free or paid versions of the test. Keep in mind that while the MBTI is widely used, it has its critics, and some argue that it oversimplifies personality.

Once you have your four-letter MBTI type (e.g., ISTJ, ENFP), you can explore more about your personality type, including strengths, potential areas for growth, and how you might interact with others.

What are Big Five Personality Traits?

The Big Five Personality Traits, also known as the Five-Factor Model (FFM), is a widely accepted framework in psychology that describes human personality based on five core dimensions. These traits are considered to represent the most comprehensive and widely accepted model of personality. The Big Five Personality Traits are often remembered using the acronym OCEAN:

    Openness to Experience (O): This trait reflects the extent to which an individual is open-minded, imaginative, and willing to engage in new and unconventional experiences. People high in openness tend to be creative, curious, and open to new ideas, while those low in openness may prefer routine and familiarity.

    Conscientiousness (C): This trait measures how organized, responsible, and dependable a person is. Conscientious individuals are often diligent, reliable, and goal-oriented, while those low in conscientiousness may be more spontaneous and less focused on planning.

    Extraversion (E): Extraversion pertains to the extent to which a person is outgoing, social, and energetic. Extraverts enjoy the company of others, are assertive, and often seek social stimulation. Introverts, on the other hand, tend to be more reserved and prefer quieter, less stimulating environments.

    Agreeableness (A): This trait reflects how cooperative, compassionate, and empathetic an individual is. Agreeable people are typically warm, considerate, and eager to help others, while those low in agreeableness may be more competitive and less concerned with others' needs.

    Neuroticism (N): Neuroticism measures emotional stability and how prone an individual is to experiencing negative emotions such as anxiety, moodiness, and irritability. High neuroticism is associated with emotional instability, whereas low neuroticism suggests emotional resilience and calmness.

These five dimensions provide a comprehensive framework for understanding and describing personality. Each person possesses a unique combination of these traits, and they are considered relatively stable over time. The Big Five Personality Traits have been widely used in psychological research and are applied in various fields, including personality psychology, organizational psychology, and career counseling.

What are some other personality indicators?

In addition to the Myers-Briggs Type Indicator (MBTI) and the Big Five Personality Traits, there are several other personality indicators and assessments that have been developed for various purposes. Here are a few notable ones:

    DISC Assessment: The DISC model categorizes individuals into four primary personality types: Dominance, Influence, Steadiness, and Conscientiousness. It is often used in workplace settings to enhance communication and teamwork.

    Enneagram: The Enneagram is a personality system that identifies nine core personality types, each with its own set of characteristics, motivations, and fears. It also explores how individuals move along interconnected paths called wings and lines of integration and disintegration.

    StrengthsFinder (CliftonStrengths): This assessment identifies an individual's top strengths out of a list of 34 themes. It aims to help individuals focus on and develop their natural talents for personal and professional growth.

    16PF (Sixteen Personality Factor Questionnaire): Developed by Raymond Cattell, the 16PF assesses personality based on 16 primary factors, including warmth, reasoning, emotional stability, dominance, and more.

    Holland Code (RIASEC): The Holland Code assesses vocational interests based on six personality types: Realistic, Investigative, Artistic, Social, Enterprising, and Conventional. It is often used in career counseling to help individuals identify suitable career paths.

    Keirsey Temperament Sorter: Based on the MBTI, the Keirsey Temperament Sorter categorizes individuals into four temperaments: Artisan, Guardian, Idealist, and Rational. It provides insights into behavior, relationships, and communication styles.

    Personality Assessment Inventory (PAI): The PAI is a comprehensive personality assessment that covers a wide range of clinical and non-clinical factors, including mood, anxiety, and thought disorders.

    Minnesota Multiphasic Personality Inventory (MMPI): Originally designed for clinical assessment, the MMPI is widely used to assess psychopathology and personality disorders. It consists of several scales measuring different aspects of personality and mental health.

It's essential to note that the effectiveness and reliability of personality assessments can vary. When using these tools, it's crucial to consider the purpose, context, and the qualifications of the individuals interpreting the results. Additionally, self-awareness and personal reflection are valuable regardless of the specific personality model used.

Tags: Management,Personality Types,Psychology,Behavioral Science,

Perm Check (A problem of counting elements)

Check whether array A is a permutation.

Problem

A non-empty array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

A[0] = 4

A[1] = 1

A[2] = 3

A[3] = 2

is a permutation, but array A such that:

A[0] = 4

A[1] = 1

A[2] = 3

is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

def solution(A)

that, given an array A, returns 1 if array A is a permutation and 0 if it is not.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [1..1,000,000,000].

Example

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

A[0] = 4

A[1] = 1

A[2] = 3

A[3] = 2

is a permutation, but array A such that:

A[0] = 4

A[1] = 1

A[2] = 3

is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Hint

We will maintain two variables:

false_positions: this is a list of size len(A) + 1 containing all False values at the time of initialization but are set to True as we would iterate over A

Note: at the initialization step itself, we would set A[0] = True

count_false: maintains a decrementing count of 'False' values remaining in the false_positions variable

We would iterate over the input array A and keep updating the false_positions and count_false variables.

After the we are done iterating over array A, we would see if count_false is zero or not.

If count_false is zero: we would return 'permutation found', otherwise 'permutation not found'.

Code

def solution(A):
  false_positions = [False for i in range(len(A) + 1)]
  count_false = len(A)
  false_positions[0] = True

  for i in range(len(A)):
      if(A[i] <= len(A)):
          if(false_positions[A[i]] == False):
              false_positions[A[i]] = True
              count_false -= 1

  if count_false == 0:
      return 1
  else:
      return 0

Example Test Cases

Detected time complexity:

O(N) or O(N * log(N))

([4, 1, 3, 2])

([4, 1, 3])

([1, 1, 4, 4]) # Suggested by Rohit Sud

Performance Tests

Correctness tests

extreme_min_max

single element with minimal/maximal value

single

single element

double

two elements

antiSum1

total sum is correct, but it is not a permutation, N <= 10

small_permutation

permutation + one element occurs twice, N = ~100

permutations_of_ranges

permutations of sets like [2..100] for which the anwsers should be false

Performance tests

medium_permutation

permutation + few elements occur twice, N = ~10,000

antiSum2

total sum is correct, but it is not a permutation, N = ~100,000

large_not_permutation

permutation + one element occurs three times, N = ~100,000

large_range

sequence 1, 2, ..., N, N = ~100,000

extreme_values

all the same values, N = ~100,000

various_permutations

all sequences are permutations

Solution 2: Rohit’s Algo

Sort the input array A using the language’s built-in sorting method.

We would maintain two variables:

one_is_there: that makes sure we have a one in the array. This helps our code from breaking in case the numbers sequenced from let’s say 3 to 10, or 2 to 8 (for example) but one is missing.

diff_one: that checks that in the sorted array all the consecutive elements in the sorted array A are at a gap of one.

Then we iterate over the input array and maintain these two flags.

At the end, we check value of these flags and return whether input array is a permutation (1) or not a permutation (0).

Rohit’s Solution

def solution(A):
    A = sorted(A)

    one_is_there = False 
    diff_one = False

    if len(A) == 1 and A[0] == 1:
        return 1

    for i in range(len(A) - 1):
        if A[i] == 1 or A[i+1] == 1:
            one_is_there = True 
        if A[i+1] - A[i] != 1:
            diff_one = False
            return 0
        else:
            diff_one = True 

    if one_is_there and diff_one:
        return 1
    else:
        return 0

Frog River One (A problem of counting elements)

Find the earliest time when a frog can jump to the other side of a river.

Problem

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.

You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

Write a function:

def solution(X, A)

that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

Write an efficient algorithm for the following assumptions:

N and X are integers within the range [1..100,000];

each element of array A is an integer within the range [1..X].

Example

For example, you are given integer X = 5 and array A such that:

A[0] = 1

A[1] = 3

A[2] = 1

A[3] = 4

A[4] = 2

A[5] = 3

A[6] = 5

A[7] = 4

In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Hint

To solve this problem, we will maintain two variables.

true_positions and count_true

true_positions: identifies the positions that have been covered by a leaf

count_true: counts the number of true we have accumulated in the true_positions list.

We will write a program to traverse the input array and keep updating these two variables (true_positions and count_true).

We will exit the program once count_true is equal to X.

Code

def solution(X, A):
  
  true_positions = [False for i in range(X + 1)]
  count_true = 0
  
  for i in range(len(A)):
      if true_positions[A[i]] == False:
          true_positions[A[i]] = True
          count_true += 1

      if count_true == X:
          return i  

  return -1

Test

Example test: (5, [1, 3, 1, 4, 2, 3, 5, 4])

OK

Detected time complexity:

O(N)

Test Cases

Correctness tests

simple test

single element

extreme_frog

frog never across the river

small_random1

3 random permutation, X = 50

small_random2

5 random permutation, X = 60

extreme_leaves

all leaves in the same place

Performance tests

medium_random

6 and 2 random permutations, X = ~5,000

medium_range

arithmetic sequences, X = 5,000

large_random

10 and 100 random permutation, X = ~10,000

large_permutation

permutation tests

large_range

arithmetic sequences, X = 30,000