Blue Optima visited for 5 different Profiles.

1. Back End Developer (Java)
2. SDE in Testing
3. UI Developer (Javascript)
4. DevOps
5. Data Engineer (Machine Learning and Data Mining Expert)

The Online Round had three sections.
1. Aptitude
2. Technical ( OS / CN / DBMS / OOPS / DSA)
3. Coding

1st Coding Question

A pure number is defined as follows.

1. It has only even no of digits
2. Digits are only 4 or 5
3. The number is a palindrome

For eg 44,55,4444,4554,5445,5555 etc are pure numbers.
Your task is to output the N^th pure number.

2nd Coding Question

Given an array of positive integers. You have to answer two types of queries

1. Sum of all numbers in range [L,R]
2. Update all numbers in range [L,R] by applying xor operation with K.

Constraints
Array length <=10⁵
Queries <= 10⁵

FIrst Problem

Linear O(N) Solution

This is a neat BFS Problem and a simple one.

You start with a queue with an empty string

q = {""}

At each step, you pop out all strings from the queue one by one. Let some string be S.

Push 4S4 in the queue. Do this for all popped strings S.
Now, push 5S5 in the queue for all popped strings S.
Stop when you are pushing the Nth string.

Constructive O(|S|) Solution

First, make N 0-indexed by decreasing it by 1.

Realize that there are exactly pow(2, L/2) palindromic strings of L here.

Thus we can find out the length of the Nth string of length L as well as it's first and last characters. Either both are 4 or both are 5.
Fix them both and then recursive solve for length L-2 and appropriate remaining N = N-pow(2, L/2)+1 (please verify this).

Obviously, the recursion ends at the base case with an empty string.