Question: Accenture | 26th September | Online Assessments | String Letter Search

Entering edit mode

I had my Online Assessments with Accenture on 26th September, awaiting results for now. These are the two questions presented to me during my online assessment. Hope I'll clear my rounds, in the meantime you guys solve the problem and let me know!

Question 1

Click here to Practice

Submit Problem to OJ

String Letter Search

You are given a string X and a string containing single character Y. Your task is to find 92 the largest distance between any two occurrences of the character Yin string X The distance is defined by the number of distinct characters between any two occurrences of character in string X (excluding whitespaces and the character being searched for). If there is no occurrence or only one occurrence of the given character the function should return -1.

Input Specification:

input1: A string value X 
input2: A string value containing a single character Y for which the largest distance has to be calculated

Output Specification:

Return the largest distance between any to occurrences of the character Y i.e., the number of 
distinct characters that exist between any to occurrences of character in string X

Example 1:

input1: my name is granar
input2:a

Output: 7

Explanation:

The largest substring between the two occurrences of a is. 'ame is grana' and the distinct 
characters between the two occurrences of 'a' are-m, e, i, s, g, r and n. 
Since there are 7 distinct characters, therefore 7 will be the output.

Example 2:

input1: the capital of minnesota is saint paul 
input2: y

Output: 0

Explanation:

Since y does not occur in the given string, we cannot form a sub string with y, therefore the output will be 0.

Question 2

Add alternate nodes in Linked List

Problem Statement There is a singly linked list represented by the following structure:

struct Node
{
int data; 
struct Node* next;
};

Implement the following function:

struct Node* AddAlternateNodes (struct Node head);

The function accepts a pointer to the start of the linked list, 'head' as its argument. Implement the function to modify the given list in node is added to the value of next to the next node and return the modified list.

Note:

Return null if list is null. In case of python if list is None return None.
Do not create new linked list, just modify the input linked list
1st and 2nd node values remain unchanged

Example:

Input: head: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

Output: 1 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12

Explanation: Adding original value of the node to its next to next node,

Replace value of '3' with 1 + 3 = 4
Replace value of '4' with 2 + 4 = 6
Replace value of 's' with 3 + 5 = 8
Replace value of '6' with 4 + 6 = 10
Replace value of '7' with 5 + 7 = 12

Thus obtained inked list is 1 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12

The custom input format for the above case: 7 1 2 3 4 5 6 7 (The first line represents the number of nodes, the second line represents the linked list)

Sample input head: 2 -> 1 -> 9 -> 2

Sample Output 2 -> 1 -> 11 -> 3

The custom input format for the above case: 4 2 1 9 2 (The first line represents the number of nodes, the second line represents the linked list)

ADD COMMENT • link

Entering edit mode

Solution to Question 2

For a linked list of length <= 2, we can simply return the list as it is since it does not require any modifications.

For lists of length greater than 2, we can achieve the modification in a single go as follows:

Maintain two variables secondLast and last and initialize them with the first and second values of the list respectively.
Start iterating from the third node in the linked list and update the value of the current node through the variables.
Update the values of the variables as you move to the next node in the linked list.

Pseudo Code:

AddAlternateNodes(head):

    //if the list is of length 2 or smaller, return the list as it is
    if(head==null or head-&gt;next==null or head-&gt;next-&gt;next==null) return head; 

    //we maintain the last and second last values as we iterate the list
    secondLast = head-&gt;data              
    last = head-&gt;next-&gt;data

    //head now points to the third node of the list
    head = head-&gt;next-&gt;next

    while(head!=null):

        temp = head-&gt;data                   //store the value of current node in a temporary variable

        head-&gt;data += secondLast      //update the value of current node by adding the value of second last node

        secondLast = last                     //update the values of the last and second last variables accordingly
        last = temp

        head = head-&gt;next                  //move the head pointer forward

ADD COMMENT • link 2.2 years ago Ayush Gangwani 1.2k

Entering edit mode

Solution 1

Since reading the string will take O(N) time complexity, a simple brute-force implementation does the job. To implement it, I have created two modes that exists as we process string X:-

Mode 1 We haven't encountered character Y so far
Mode 2 We have encountered character Y previously, and now we are actively maintaining frequency of characters and every time we find another occurrence of Y, we update the answer based on currently known frequency of characters.

We maintain frequency of characters using Hashmap, which in C++ can be implemented using "unordered_set" from STL.

int solve(string X, string Y) {
    int mode = 1, ans = 0;
    unordered_set&lt;int&gt; freq;

    for (auto ch: X) {
        if (mode == 1) {
            if (ch == Y) mode = 2;
        } else {
            if (ch == Y) ans = freq.size();
            else freq.insert(ch);
        }
    }
    return ans;
}

INSIGHT - Above idea of keeping different modes is extremely useful in simplifying a lot of implementation / simulation kind of problems. Especially helpful in string processing and parsing problems. I picked this trick up from one of Amazon interview post here on TJO, let me know if you need that link to practice this mode based implementation trick. It was much harder problem on parsing unlike this problem.

Followup - This problem would have been interesting, if we had multiple queries of character Y and had a larger key-size of characters than just 26 lower latin alphabets. In that case we can pre-compute and solve queries in constant time using prefix sums.

ADD COMMENT • link 2.2 years ago Aman • 20

Entering edit mode

Solution 1:

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder str = new StringBuilder();
StringBuilder ch = new StringBuilder();
Set<Character> s = new HashSet<>();

str.append(sc.nextLine()); // Use append instead of assignment
ch.append(sc.next()); // Use append instead of assignment
char c = ch.charAt(0); // Use charAt to get the first character
int st = str.indexOf(ch.toString());
int end = str.lastIndexOf(ch.toString());
if(st==-1 || st==end)
System.out.println("-1");
else{
for (int i = st; i < end; ++i) {
if (str.charAt(i) != c && str.charAt(i)!=' ') {
s.add(str.charAt(i));
}
}

System.out.println(s.size()); // Print the result
}
}
}

ADD COMMENT • link 10 months ago Mayank Chouhan • 0

Entering edit mode

Question 1

#include <bits/stdc++.h>
using namespace std;

int main() {
int first = INT_MAX, last = -1;
string str;
getline(cin,str);
char ch;
cin>>ch;
for(int i=0;i<str.size();i++){
if(str[i]==ch){
first = min(first,i);
last = max(last,i);
}
}

if(first==INT_MAX || last==-1){
cout<<-1;
return 0;
}

int dist = last-first-1;
map<char,int> mp;
for(int i=first;i<last;i++){
if(str[i]==' '){
dist--;
continue;
}
char c = str[i];
mp[c]++;
if(mp[c]>1) dist--;
}

cout<<dist;
}

ADD COMMENT • link 4 months ago Kaushan Dey • 30