# Noisy Palindrome - Facebook Top Interview Questions

### Problem Statement :

```You are given a string s containing lowercase and uppercase alphabet characters as well as digits from "0" to "9".

Return whether s is a palindrome if we only consider the lowercase alphabet characters.

Constraints

0 ≤ n ≤ 100,000 where n is the length of s

Example 1

Input

s = "a92bcbXa"

Output

True

Explanation

If we only consider the lowercase characters, then s is "abcba" which is a palindrome.

Example 2

Input

s = "abZ"

Output

False```

### Solution :

```                        ```Solution in C++ :

bool solve(string s) {
int n = s.length();
int i = 0, j = n - 1;
while (i < j) {
if (!isalpha(s[i]) || isupper(s[i])) {
i++;
}
if (!isalpha(s[j]) || isupper(s[j])) {
j--;
}
if (isalpha(s[i]) && islower(s[i]) && isalpha(s[j]) && islower(s[j])) {
if (s[i] == s[j]) {
i++, j--;
} else {
return false;
}
}
}
return true;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public boolean solve(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
char l = s.charAt(left), r = s.charAt(right);
if (l >= '0' && l <= '9' || l >= 'A' && l <= 'Z')
left++;
else if (r >= '0' && r <= '9' || r >= 'A' && r <= 'Z')
right--;
else if (l != r)
return false;
else {
left++;
right--;
}
}
return true;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, s):
s0 = (c for c in s if c in string.ascii_lowercase)
s1 = (c for c in reversed(s) if c in string.ascii_lowercase)
return all(c0 == c1 for c0, c1 in zip(s0, s1))```
```

## Jenny's Subtrees

Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n - 1 edges, and each edge is ` unit in length. She wants to cut a subtree (i.e., a connected part of the original tree) of radius r from this tree by performing the following two steps: 1. Choose a node, x , from the tree. 2. Cut a subtree consisting of all nodes which are not further than r units from node x .

## Tree Coordinates

We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty