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

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

Swap The Elements (A problem on counting elements)

Swap The Elements

Problem

Problem: You are given an integer m (1 <= m <= 1 000 000) and two non-empty, zero-indexed arrays A and B of n integers, a0, a1, … , a(n-1) and b0, b1, ... , b(n-1) respectively (0 <= ai , bi <= m).

The goal is to check whether there is a swap operation which can be performed on these arrays in such a way that the sum of elements in array A equals the sum of elements in array B after the swap. By swap operation we mean picking one element from array A and one element from array B and exchanging them.

Example

x = [3, 4, 2, 1, 0]

y = [3, 1, 4, 2, 2]

print(sum(x))

print(sum(y))

Out:

10

12

# Swapping '2 from y' with '1 from x'.

x = [3, 4, 2, 2, 0]

y = [3, 1, 4, 2, 1]

print(sum(x))

print(sum(y))

Out:

11

11

# Also, on swapping '3 from y' and '2 from x'.

x = [3, 4, 3, 1, 0]

y = [2, 1, 4, 2, 2]

print(sum(x))

print(sum(y))

Out:

11

11

# Also, on swapping '4 from y' and '3 from x'.

x = [4, 4, 2, 1, 0]

y = [3, 1, 3, 2, 2]

print(sum(x))

print(sum(y))

Out:

11

11

Hint

After the swap operation, the two sums (sum_a and sum_b) should become equal.

And if initially, sum_b - sum_a = d

This is total change we want.

Now, since sum_b + sum_a = Constant (before and after the swap), we can then say:

Half of this change (viz. d/2) will come from side 'b' and half (viz. d/2) will come from side 'a'.

(This is equivalent to saying side 'a' and side 'b' will meet the halfway.)

Since side 'b' is higher, we would have to swap a value B[i] with B[i] - d/2

Now for this, we will loop through side 'b' to find that B[i] for which 'B[i] - d/2' is in side 'a'.

Brute Force Solution

Solution O(n^2): The simplest method is to swap every pair of elements and calculate the totals. Using that approach gives us O(n^3) time complexity. A better approach is to calculate the sums of elements at the beginning, and check only how the totals change during the swap operation.

Linear Time Complexity Solution

Solution O(n + m): The best approach is to count the elements of array A and calculate the difference d between the sums of the elements of array A and B.

For every element of array B, we assume that we will swap it with some element from array A. The difference d tells us the value from array A that we are interested in swapping, because only one value will cause the two totals to be equal. The occurrence of this value can be found in constant time from the array used for counting.

Code

def fast_solution(A, B, m):
  n = len(A)
  sum_a = sum(A) 
  sum_b = sum(B) 
  d = sum_b - sum_a
  if d % 2 == 1: 
      return False
  d //= 2
  count = counting(A, m)
  for i in xrange(n):
      if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
          return True
  return False

Note: counting() is:
def counting(A, m):
  n = len(A)
  count = [0] * (m + 1)
  for k in xrange(n):
    count[A[k]] += 1
  return count

'counting()' can be replaced with 'Counter':
>>> l = ['A', 'B', 'C']

>>> from collections import Counter
>>> Counter(l)
Counter({'A': 1, 'B': 1, 'C': 1})
>>> 

Tape Equilibrium (A problem in time complexity)

Tape Equilibrium: Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|

Problem

A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts:

A[0], A[1], … , A[P − 1] and A[P], A[P + 1], … , A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

Write a function:

def solution(A)

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

Write an efficient algorithm for the following assumptions:

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

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

Example

For example, consider array A such that:

A[0] = 3

A[1] = 1

A[2] = 2

A[3] = 4

A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7

P = 2, difference = |4 − 9| = 5

P = 3, difference = |6 − 7| = 1

P = 4, difference = |10 − 3| = 7

In this example, the function should return 1

Hint

A naive way to think how to solve this problem is to go through each element from second index to second last index, split the array into two parts: left and right and then compute the sum of both left side and right side to get the absolute difference for this split.

But the way we optimize this code is to do away with the need to compute the sum of left side and right side again and again.

In the a better approach, we change what we store in our left and right variable (viz integers, instead of lists).

This is achieved by maintaining two integer variables as left and right that contain the current value of sum of left and right side.

In each step, we update the values left and right by the amount of element which is changing the side from right to left.

Code

def solution(A):
  left = A[0]
  right = sum(A) - A[0]

  g_diff = abs(left - right)

  for i in range(1, len(A) - 1):
      left = left + A[i]
      right = right - A[i]
      l_diff = abs(left - right)
      if (l_diff < g_diff):
          g_diff = l_diff 
  
  return g_diff  

Complexity

O(n)

Perm Missing Element (A problem of time complexity)

Perm Missing Element Find the missing element in a given permutation.

Problem

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

def solution(A)

that, given an array A, returns the value of the missing element.

Write an efficient algorithm for the following assumptions:

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

the elements of A are all distinct;

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

Example

For example, given array A such that:

A[0] = 2

A[1] = 3

A[2] = 1

A[3] = 5

the function should return 4, as it is the missing element.

Hint

Concept 1: Arithmetic Progression

General case of Arithmetic Progression.

An arithmetic progression (AP) is a sequence of numbers in which the difference of any two successive members is a constant. This constant difference is often denoted by "d." The general form of an arithmetic progression is:

a, a+d, a+2d, a+3d, …

Here:

a is the first term (initial term) of the sequence.

d is the common difference between consecutive terms.

For example, consider the arithmetic progression with a first term (a) of 3 and a common difference (d) of 2:

3, 5, 7, 9, 11,…

Sum of an A.P. is: ​[2a+(n−1)d] * n / 2

Concept 2: Triangular Numbers

Which is a specific case of Arithmetic Progression.

Triangular numbers are a sequence of numbers that represent the number of objects that can be arranged in the shape of an equilateral triangle. The n-th triangular number is the sum of the first n natural numbers. The formula for the n-th triangular number, often denoted as Tn​, is given by:

Tn=1+2+3+…+n = n⋅(n+1) / 2

The sequence of triangular numbers begins with:

1, 3, 6, 10, 15, 21,…

Code

We will use the idea of N’th Triangular number to find our missing number using the following steps:

1. We find the ideal sum if the missing number were also there.

This is given by the formula for the sum of an A.P. or formula for N’th Triangular number.

2. We find the sum of input we have.

3. Missing number = result_from_step_1 - result_from_step_2

def solution(A):
    # Implement your solution here
    sum_of_series = (len(A) + 1) * (len(A) + 2) / 2
    sum_of_input = sum(A)
    missing_element = int(sum_of_series - sum_of_input)
    return missing_element 

Detected Time Complexity

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

Test Cases

Correctness tests

empty_and_single

empty list and single element

missing_first_or_last

the first or the last element is missing

single

single element

double

two elements

simple

simple test

Performance tests

medium1

medium test, length = ~10,000

medium2

medium test, length = ~10,000

large_range

range sequence, length = ~100,000

large1

large test, length = ~100,000

large2

large test, length = ~100,000

Frog Jump (A problem of time complexity. Level: Easy)

Frog Jump: Count minimal number of jumps from position X to Y.

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.

Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

def solution(X, Y, D)

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

Write an efficient algorithm for the following assumptions:

X, Y and D are integers within the range [1..1,000,000,000];

X ≤ Y.

Example

For example, given:

X = 10

Y = 85

D = 30

the function should return 3, because the frog will be positioned as follows:

after the first jump, at position 10 + 30 = 40

after the second jump, at position 10 + 30 + 30 = 70

after the third jump, at position 10 + 30 + 30 + 30 = 100

Code

import math

def solution(X, Y, D):
    # Implement your solution here
    return math.ceil((Y-X)/D)  

Test Cases

Correctness tests

simple1

simple test

simple2

extreme_position

no jump needed

small_extreme_jump

one big jump

Performance tests

many_jump1

many jumps, D = 2

many_jump2

many jumps, D = 99

many_jump3

many jumps, D = 1283

big_extreme_jump

maximal number of jumps

small_jumps

many small jumps

Combinations of a set of alphabets using JavaScript (A problem of recursion)

Problem

Write a function that takes two parameters:
A: a list of distinct alphabets
n: a number that denotes the size of the selection we are going to make of the alphabets from the list A

The output of the function should be a list of lists containing all the possible combinations of size n from the list of alphabets A.

For example:
solution(['A', 'B', 'C', 'D'], 2)
Produces:

[
    [ 'A', 'B' ],
    [ 'A', 'C' ],
    [ 'A', 'D' ],
    [ 'B', 'C' ],
    [ 'B', 'D' ],
    [ 'C', 'D' ]
]

/*
Example 1:

Combinations ([A,B,C,D], 3) is equal to:
A + Combinations([B,C,D], 2) and
B + Combinations([C,D], 2)

~~~

Example 2:

Combinations(ABCDE, 3) is equal to:
A + Combinations(BCDE, 2) and
B + Combinations(CDE, 2) and
C + Combinations(DE, 2)

~~~

Example 3:

Combinations(ABCDE, 2) is equal to:
A + Combinations(BCDE, 1) and
B + Combinations(CDE, 1) and
C + Combinations(DE, 1) and
D + Combinations(E, 1)

*/

function solution(A, n) {
    if (A.length == 1 || A.length == n) { 
        return [A]; 
    } else if (n == 1) {        
        return A.map(function (i){ return [i] });
    }
    
    const resultArr = []
    for (let i = 0; i < A.length - n + 1; i++) {
        let currentElement = A[i]

        otherElements = A.slice(i+1)
        subCombinations = solution(otherElements, n-1)
        
        for (let j = 0; j < subCombinations.length; j++) {
            
            resultArr.push([currentElement].concat(subCombinations[j]))
        }
    }

    return resultArr
}

console.log(solution(['A', 'B', 'C', 'D'], 2))
console.log("~~~")

console.log(solution(['A', 'B', 'C', 'D'], 3))
console.log("~~~")

console.log(solution(['A', 'B', 'C', 'D', 'E'], 2))
console.log("~~~")


console.log(solution(['A', 'B', 'C', 'D'], 4))
console.log("~~~")

console.log(solution(['A', 'B', 'C', 'D'], 1))
console.log("~~~")

/*
[
    [ 'A', 'B' ],
    [ 'A', 'C' ],
    [ 'A', 'D' ],
    [ 'B', 'C' ],
    [ 'B', 'D' ],
    [ 'C', 'D' ]
]
~~~
[
    [ 'A', 'B', 'C' ],
    [ 'A', 'B', 'D' ],
    [ 'A', 'C', 'D' ],
    [ 'B', 'C', 'D' ]
]
~~~
[
    [ 'A', 'B' ], [ 'A', 'C' ],
    [ 'A', 'D' ], [ 'A', 'E' ],
    [ 'B', 'C' ], [ 'B', 'D' ],
    [ 'B', 'E' ], [ 'C', 'D' ],
    [ 'C', 'E' ], [ 'D', 'E' ]
]
~~~
[ [ 'A', 'B', 'C', 'D' ] ]
~~~
[ [ 'A' ], [ 'B' ], [ 'C' ], [ 'D' ] ]
~~~

*/

Permutations of a set of alphabets using JavaScript (A problem of recursion)

Problem
In the given problem statement we are asked to generate every possible permutation of the array given as input by the in JavaScript going from brute force method to optimized solution.

What is Permutation of Array in JavaScript?

Permutation of Array refers to the shuffling and ordering of elements present in an array. It generates all possible ways or arrangements of elements using the array as input source of it.

If we have an array of n elements in javascript, it generates n! possible ways to order and output elements.

The permutation of elements is the core of solving problem statement where the input and output can be visualized as follows :


const arr = [ 1 , 2 , 3 ] ;

// generate all permutations

[ 1 , 2 , 3 ] 
[ 1 , 3 , 2 ]
[ 2 , 1 , 3 ]
[ 2 , 3 , 1 ]
[ 3 , 1 , 2 ]
[ 3 , 2 , 1 ]    


Solution


function solution(A) {
    let resultArr = []

    if (A.length > 1) {
        for (let i = 0; i < A.length; i++) {
            const currentElement = A[i];

            otherElements = A.slice(0,i).concat(A.slice(i+1));

            subPermutations = solution(otherElements);
            for (let j = 0; j < subPermutations.length; j++) {
                resultArr.push([currentElement].concat(subPermutations[j]));
            }
        }
    }

    else if(A.length == 1) {
        return [A]
    }

    return resultArr
}

console.log(solution(['A', 'B']))

[ Ref ]

Substring in another string (Lesson in Algorithms)

Substring in another string

Problem

Detect if a shorter string is part of a longer string.

Shorter string is the substring.

Longer string is the superstring.

Example

Shorter string is ‘eng’.

Longer string is ‘opengenus’.

‘eng’ is a substring in ‘opengenus’.

‘123’ is not a substring in ‘opengenus’.

Code in Python

# s1 is the superstring
# s2 is the substring

def solution(s1, s2):
    for i in range(len(s1)-len(s2)+1):
        if s1[i:i+len(s2)] == s2:
            return 'Match Found'  

Testing

s1 = 'opengenus'

# Test case: no match found

s2 = '123'

print(s2, solution(s1, s2))

# Test case: single character

s2 = 'p'

print(s2, solution(s1, s2))

# Test case: match substring at the beginning (at index 0)

s2 = 'ope'

print(s2, solution(s1, s2))

# Test case: match substring somewhere in the middle

s2 = 'eng'

print(s2, solution(s1, s2))

# Test case: match substring at the end

s2 = 'nus'

print(s2, solution(s1, s2))

# Test case: match both the strings completely

s2 = 'opengenus'

print(s2, solution(s1, s2))

Output

123 None
p Match Found
ope Match Found
eng Match Found
nus Match Found
opengenus Match Found

2.2 - Odd occurrences in an array

Odd Occurrences in an Array

Problem

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

Write a function:

def solution(A)

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

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

the function should return 7, as explained in the next slide.

Write an efficient algorithm for the following assumptions:

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

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

all but one of the values in A occur an even number of times.

Example

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9

A[3] = 3 A[4] = 9 A[5] = 7

A[6] = 9

the elements at indexes 0 and 2 have value 9,

the elements at indexes 1 and 3 have value 3,

the elements at indexes 4 and 6 have value 9,

the element at index 5 has value 7 and is unpaired.

Trick: Use of Key-Value Pair and a Set

The Key-Value pair in the heading could be a dictionary (dict) in Python (or HashMap in Java).

We would need to traverse the input array once and maintain two data structures (a dict and a set).

Dict named counts: would contain the elements as keys

Set named odds: would contain the elements whose number of occurrences are found to be odd.

Note during the program’s lifetime, size of set ‘odds’ would change but by the end of iteration, there would be only one element in it.

Java Based Code of a Variant of The Solution From My Friend Rohit

import java.util.*; 
class Solution { 
 public int solution(int[] A) { 
  Map<Integer, Integer> integerMap = new HashMap<Integer, Integer>(); 
  for (int i = 0; i < A.length; A++)) {
   if (!integerMap.containsKey(A[i])) { 
    integerMap.put(A[i], 1); 
   } 
   else { 
    int count = integerMap.get(A[i]);      	 
    integerMap.put(A[i], count + 1); 
  }
  int missingNumber = 0; 
  for (Map.Entry<Integer, Integer> map : integerMap.entrySet()) 
  { 
   if (map.getValue() % 2 == 1) { 
    missingNumber = map.getKey(); 
  } 
  return missingNumber; 
 }
}  

In Python Code

def solution(A):
    counts = dict()
    odds = set()

    for i in A:
        if i in counts:
            counts[i] += 1
        else:
            counts[i] = 1

        if counts[i] % 2 == 1:
            odds.add(i)
        else:
            odds.remove(i)

    return odds.pop()  

Time Complexity

Detected time complexity:

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

Test Cases

-simple1

simple test n=5

-extreme_single_item

[42]

-small1

small random test n=201

- medium1

medium random test n=2,001

big1

big random test n=999,999, multiple repetitions

-big2

big random test n=999,999

Tags: Technology,Algorithms,