# Lexicographic Combination Iterator - Amazon Top Interview Questions

### Problem Statement :

```Implement an iterator where, given a sorted lowercase alphabet string s of unique characters and an integer k:

next() polls the next lexicographically smallest subsequence of length k
hasnext() which returns whether the next subsequence exists

Constraints

n ≤ 100,000 where n is the number of calls to next and hasnext

Example 1

Input

methods = ["constructor", "next", "next", "next", "hasnext"]
arguments = [["abc", 2], [], [], [], []]`

Output

[None, "ab", "ac", "bc", False]```

### Solution :

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

class LexicographicCombinationIterator {
public:
LexicographicCombinationIterator(string s, int k) : _k(k), ss(s) {
}

string next() {
if (states.empty()) {
states.resize(_k);
iota(states.begin(), states.end(), 0);
} else {
int i = get_index();
states[i++]++;
for (; i < _k; i++) states[i] = states[i - 1] + 1;
}
string ans;
for (int i : states) ans.push_back(ss[i]);
return ans;
}

bool hasnext() {
return states.empty() || get_index() >= 0;
}

private:
int get_index() {
int N = ss.size(), cur = N - 1, i = _k - 1;
for (; i >= 0 && states[i] == cur; i--, cur--)
;
return i;
}
int _k;
string ss;
vector<int> states;
};```
```

```                        ```Solution in Python :

class LexicographicCombinationIterator:
def __init__(self, s, k):
self.pointers = [i for i in range(k)]
self.s = s
self.k = k
self.possible = True

def next(self):
res = "".join([self.s[i] for i in self.pointers])
self.possible = False
for i in range(len(self.pointers) - 1, -1, -1):
remaining = len(self.pointers) - 1 - i
if (
self.pointers[i] + 1 < len(self.s)
and len(self.s) - 1 - (self.pointers[i] + 1) >= remaining
):
self.pointers[i] += 1
for j in range(i + 1, len(self.pointers)):
self.pointers[j] = self.pointers[j - 1] + 1
self.possible = True
break
return res

def hasnext(self):
return self.possible```
```

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