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 rtnTask 2
Task 3
Fig 3.1Fig 3.2
Fig 3.3
Thursday, December 28, 2023
Coding Round in Interview for Data Scientist Role at a Bank (17 Nov 2023)
Monday, December 25, 2023
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.