8 months ago

John 1.0k

Hyderabad

Job Roles: Backend Developer, Frontend Developer

Avg CTC: 22.4LPA

Apply here: Current Job Openings

Question 1

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.

21 months ago

Ujjwal Srivastava 320

Bengaluru

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 >> n;
string s;
cin >> s;
map<char, ll> mp;
for (ll i = 0; i < n; i++)
{
    mp[s[i]] = -1; // initialise with -1
}
ll ans = 0;
ll last_visisted_index = 0;
for (ll i = 0; i < 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 << ans << endl; // print the answer
return;

11 months ago

Akash 240

Ghaziabad

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<int, map<int, int>> count;
    for (int i = 0; i < n; i++) {
        if (count.find(arr[i]) != count.end()) {
            int q = x / __gcd(x, i + 1);
            ans += count[arr[i]][q];
        }
        else {
            map<int, int>mm;
            count[arr[i]] = mm;
        }
        addDivisors(i + 1, count[arr[i]]);         //sqrt(n) operation
    }
    cout << ans << endl;

2.7 years ago

Systumm • 200

Mumbai

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 :)

11 months ago

Akash 240

Ghaziabad

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

Complexity

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

Memory Complexity: O(1)