# Ancient Astronaut Theory- Amazon Top Interview Questions

### Problem Statement :

```You are given a string dictionary, representing a partial lexicographic ordering of ancient astronauts' dictionary. Given a string s, return whether it's a lexicographically sorted string according to this ancient astronaut dictionary.

Example 1

Input

dictionary = "acb"

s = "aaaa h ccc i bbb"

Output

True

Explanation

The only constraint is that a comes before c which comes before b .

Example 2

Input

dictionary = "acb"

s = "aaaacccbc"

Output

False

Explanation

This is false because of the last c, which comes after b.```

### Solution :

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

bool isValid(char x, vector<int>& dict) {
return (x - 'a') >= 0 && (x - 'a') <= 25 && (dict[x - 'a'] != -1);
}

bool solve(string dictionary, string s) {
vector<int> dict(26, -1);
for (int i = 0; i < dictionary.size(); ++i) dict[dictionary[i] - 'a'] = i;
int n = s.size();
int last = -1;
for (int i = 0; i < n; ++i) {
if (isValid(s[i], dict)) {
if (dict[s[i] - 'a'] < last) return false;
last = dict[s[i] - 'a'];
}
}
return true;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public boolean solve(String dictionary, String s) {
Map<Character, Integer> map = new HashMap();
int dLen = dictionary.length();
for (int i = 0; i < dLen; i++) {
if (map.containsKey(dictionary.charAt(i))) {
continue;
}
map.put(dictionary.charAt(i), i);
}
int index = 0, sLen = s.length(), minVal = Integer.MIN_VALUE;
for (int i = 0; i < sLen; i++) {
if (!map.containsKey(s.charAt(i))) {
continue;
}
if (map.containsKey(s.charAt(i))) {
index = map.get(s.charAt(i));
}
if (index < minVal) {
return false;
}
minVal = Math.max(index, minVal);
}
return true;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, dictionary, s):
dic = {}
for i in range(len(dictionary)):
dic[dictionary[i]] = i
prev = 0
for i in s:
if i in dictionary:
ind = dic[i]
if ind < prev:
return False
prev = ind
return True```
```

## 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