Job: Tekion, Online Assessments included with Recent Job Links, 2022 | Longest Substring Without Repeating Characters
0
Entering edit mode

Job Roles: Backend Developer, Frontend Developer

Avg CTC: 22.4LPA

Apply here: Current Job Openings

Question 1

Click here to Practice

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

Click here to Practice
 

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

Click here to Practice
 

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.

ADD COMMENTlink 18 months ago John 780
1
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.
  • The answer would max(answer, cur_index-last_visited_index+1).

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;
ADD COMMENTlink 18 months ago Ujjwal Srivastava 310
1
Entering edit mode

Question 3


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;
ADD COMMENTlink 18 months ago Akash 230
1
Entering edit mode

Q1.  very simple standard Sliding window question

approach:

   maintain two pointer start and end 

traverse through string and hash elements (expand window as we want largest substring) and whenever any charcater frequency is greater than 1 Shrink window

and update our answer in each step as max(ans,end-start+1)

thats it :)

ADD COMMENTlink 12 months ago Systumm • 200
Entering edit mode
0

Neat idea!

ADD REPLYlink 12 months ago
slime
• 320
Entering edit mode
0

Kudos on passing all the test cases ! :)

ADD REPLYlink 12 months ago
Abhilash Kalyanakrishnan
• 220
0
Entering edit mode

Question 2


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 6n.
  • 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 6ceil(n/2) / 6n or 1 / 6floor(n/2)

Complexity

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

Memory Complexity: O(1)

ADD COMMENTlink 12 months ago Akash 230

Login before adding your answer.

Similar Posts
Loading Similar Posts