Job: Tekion, Online Assessments included with Recent Job Links, 2022
0
Entering edit mode

Job Roles: Backend Developer, Frontend Developer

Avg CTC: 22.4LPA

Apply here: Current Job Openings

## Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

Examples:

Input 1: s = "abcabcbb"

Output 1: 3

Explanation: The answer is "abc", with the length of 3.

Input 2: s = "bbbbb"

Output 2: 1

Explanation: The answer is "b", with the length of 1.

Input 3: s = "pwwkew"

Output 3: 3

Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

## Question 2

Return Probability of Palindromes for 'n' dice throws where each throw can give result 1 to 6.

For Ex. if n=3 then (111),(121),(131),(141),(151),(161),(212),...(666) = 36; total permutations is 216 hence probability is 36/216

## Question 3

Find number of sub array combinations A[i],A[j] in array A and an int X with the following conditions,

• A[i]=A[j]
• i < j and i != j
• i*j is divisible by X

we use 1-index here;

Example:

A={2,2,2}, X=2

Combinations if i,j are {1,2},{1,3} and {2,3}

Divisible by X are {1,2} and {2,3}

Hence number of combinations = 2.

0
Entering edit mode

## Overview

• Find the probability of palindromes for `n` dice throws where each throw can give results 1 to 6.

## Approach

• The total number of `n` digit numbers is `6`<sup>`n`</sup>.
• A number is a palindrome when the first `n/2` digits match with the last `n/2` digits in reverse order.
• For an even number of digits, we can pick the first `n/2` digits and then duplicate them to form the rest of `n/2` digits so we can choose `n/2` digits.
• For an odd number of digits, we can pick first `(n-1)/2` digits and then duplicate them to form the rest of `(n-1)/2` digits so we can choose `(n+1)/2` digits.
• So the probability that an `n` digit number is a palindrome is `6`<sup>ceil(n/2)</sup> `/` `6`<sup>n</sup> or 1 / `6`<sup>floor(n/2)</sup>

## Complexity

Time Complexity: `O(N), N` is the number of dice throws.

Memory Complexity: `O(1)`

0
Entering edit mode

## Question 1

Overview

• Given a string s consisting of English letters, digits, and symbols, find the length of the longest substring without repeating characters.

Solution

• The idea is to scan the string from left to right, and keep track of the maximum length Non-Repeating Character Substring seen so far in res.
• When we traverse the string, to know the length of the current window we need two indexes.
• First is the current_index. The second is the last_visited_index which is initialized as 0.
• Every time we visit a new character in the string we update last_visited_index as max(last_visited_index, last_seen_index[s[cur_char]]).
• last_seen_index is a map that will be initialized as -1 for all characters in the string and would store the most recent index for each character as we scan along the string.

Code

``````ll n;
cin &gt;&gt; n;
string s;
cin &gt;&gt; s;
map&lt;char, ll&gt; mp;
for (ll i = 0; i &lt; n; i++)
{
mp[s[i]] = -1; // initialise with -1
}
ll ans = 0;
ll last_visisted_index = 0;
for (ll i = 0; i &lt; n; i++)
{
last_visisted_index = max(last_visisted_index, mp[s[i]] + 1); // update the last visited vertex
ans = max(ans, i - last_visisted_index + 1);                  // update the answer
mp[s[i]] = i;                                                 // update the most recent index for a charater
}
cout &lt;&lt; ans &lt;&lt; endl; // print the answer
return;
``````
0
Entering edit mode

## Overview

• Determine the number of pairs satisfying the given conditions.

## Approach

• Let’s maintain a hashtable,`count[v][f]`, which would store the count of how many indexes having a certain value `v` is divisible by `f`.

• Now, let's iterate, and then from each index `i`, the other index should be divisible by - `X/gcd(X, i)`, therefore, we will increment the count by `count[A[i]][X/gcd(X, i)]`. After counting from each index, we will just update the table and that requires each of us to iterate on all factors of the current index and just increment by `1` `count[A[i]][factor]`.

• Updating requires `sqrt(n)` time and the table could be represented by an ordered or unordered map, and the final time complexity should be `O(n*sqrt(n))` or with an extra log with the ordered map.

## Pseudocode

``````    int ans = 0;
map&lt;int, map&lt;int, int&gt;&gt; count;
for (int i = 0; i &lt; n; i++) {
if (count.find(arr[i]) != count.end()) {
int q = x / __gcd(x, i + 1);
ans += count[arr[i]][q];
}
else {
map&lt;int, int&gt;mm;
count[arr[i]] = mm;
}
addDivisors(i + 1, count[arr[i]]);         //sqrt(n) operation
}
cout &lt;&lt; ans &lt;&lt; endl;
``````