Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.

For example, given s = “abcba” and k = 2, the longest substring with k distinct characters is “bcb”.

Solution

public static String getLongestSubstringDistinct(String str, Integer k){
    Integer n = str.length();
    
    Integer left = 0;
    Integer right = 0;
    
    Map<Integer, Integer> mapOfChars = new Map<Integer, Integer>();
    
    while (right < n){
        if (mapOfChars.size() < k+1){
            if (!mapOfChars.containsKey(str.charAt(right))){ 
               mapOfChars.put(str.charAt(right), right);           
            } else if (right-mapOfChars.get(str.charAt(right))<=1){
                mapOfChars.put(str.charAt(right), right);  
            }
              
            right++;
        }
        System.debug('mapOfChars > ' + mapOfChars);
        
        if (mapOfChars.size() == k+1){
            List<Integer> mapOfValues = mapOfChars.values();
            mapOfValues.sort();
            Integer leftMax = mapOfValues.get(0);
            
            mapOfChars.remove(str.charAt(leftMax));
            left = leftMax + 1;
        }
    }
    
    List<Integer> charStartEnd = mapOfChars.values();
    charStartEnd.sort();
    return str.subString(charStartEnd.get(0)-1, charStartEnd.get(1));
}

Testing

System.debug(getLongestSubstringDistinct('abcba', 2)); //bcb
System.debug(getLongestSubstringDistinct('zxybobc', 2)); //bob

This question was asked during an Amazon interview

Following schema is provided:

Account

Total_Salary__c (Number)

Max_Salary__c (Number)

Account_Salary__c

Account__c (lookup)

Name (String)

Salary__c (Number)

An Account can have multiple Account_Salary__c records that lookup to an Account by the Account__c.

Write a trigger that would update the Account Total_Salary__c, Max_Salary__c when a new Account salary record is:

1. Inserted
2. Update
3. Deleted
4. Undeleted

Declarative Programming solution

1. Master Detail relationship between Account and Account_Salary__c, use sum(Salary__c) and max(Salary__c) to do rollup to Account
2. Process Builder or Flow that calls out to @InvocableMethod to query all other Account_Salary__c records and makes the update

Imperative Programming solution 

Trigger

trigger AccountSalaryTrigger on Account_Salary__c (after insert, after update, after delete, after undelete) {
    if (Trigger.isUpdate){
        AccountSalaryHelper.updateAccount(Trigger.new, Trigger.oldMap);
    } else if (Trigger.isDelete){
       AccountSalaryHelper.updateAccount(Trigger.old, null);
    } else {
       AccountSalaryHelper.updateAccount(Trigger.new, null);
    }
}

Helper class

public with sharing class AccountSalaryHelper {

    public static void updateAccount(List<Account_Salary__c> newAccountSalaries, Map<Id, Account_Salary__c> oldMap){
        Set<Id> accountIds = new Set<Id>();
        for (Account_Salary__c newAccountSalary : newAccountSalaries){
            if (oldMap!=null){
                Account_Salary__c oldAccountSalary = oldMap.get(newAccountSalary.Id);
                if (oldAccountSalary.Salary__c != newAccountSalary.Salary__c){
                    accountIds.add(newAccountSalary.Account__c);
                }
            } else {
                accountIds.add(newAccountSalary.Account__c);
            }
        }
        
        if (!accountIds.isEmpty()){
            List<AggregateResult> aggResults = [Select Account__c accId, sum(Salary__c) sumSalary, max(Salary__c) maxSalary from Account_Salary__c where Account__c IN :accountIds Group By Account__c];
            
            List<Account> accountsToUpdate = new List<Account>();
            for (AggregateResult aggResult : aggResults){
                Id accountId = (Id)aggResult.get('accId');
                if (accountId!=null){
                    Account updateAccount = new Account();
                    updateAccount.Id =accountId;
                    updateAccount.Total_Salary__c=(Decimal)aggResult.get('sumSalary');
                    updateAccount.Max_Salary__c = (Decimal)aggResult.get('maxSalary');
                    accountsToUpdate.add(updateAccount);
                }
            }
            
            if (!accountsToUpdate.isEmpty()){
                SavePoint sp = Database.setSavePoint();
                try{
                    update accountsToUpdate;
                } catch(DMLException ex){
                    Database.rollback(sp);
                }
            }
        }
    }
}

Helper Test class

@isTest
private class AccountSalaryHelperTest {

    @TestSetup static void setup(){
        Account acc = new Account();
        acc.Name = 'Test';
        insert acc;
    
        Account_Salary__c as1 = new Account_Salary__c();
        as1.Name='as1';
        as1.Account__c = acc.Id;
        as1.Salary__c = 500;
        insert as1;
        
        Account_Salary__c as2 = new Account_Salary__c();
        as2.Name = 'as2';
        as2.Account__c = acc.Id;
        as2.Salary__c = 700;
        insert as2;
    }

    @isTest static void testInsertAccountSalary(){
        Account acc = [Select Id, Max_Salary__c, Total_Salary__c from Account][0];
        
        Test.startTest();
            Account_Salary__c as3 = new Account_Salary__c();
            as3.Name = 'as3';
            as3.Account__c = acc.Id;
            as3.Salary__c = 300;
            insert as3;
        Test.stopTest();
        
        Account accAfter = [Select Id, Max_Salary__c, Total_Salary__c from Account][0];
        System.assertEquals(accAfter.Max_Salary__c, 700);
        System.assertEquals(accAfter.Total_Salary__c, 1500);
    }
    
    @isTest static void testUpdateAccountSalary(){
        Account_Salary__c accSalary = [Select Id, Salary__c from Account_Salary__c where Name='as2'][0];
         Test.startTest();
            accSalary.Salary__c = 800;
            update accSalary;
        Test.stopTest();
        
        Account acc = [Select Id, Max_Salary__c, Total_Salary__c from Account][0];
        System.assertEquals(acc.Max_Salary__c, 800);
        System.assertEquals(acc.Total_Salary__c, 1300);
    }
    
    @isTest static void testDeleteAccountSalary(){
        Test.startTest();
            delete [Select Id from Account_Salary__c where Name='as2'][0];
        Test.stopTest();
        
        Account acc = [Select Id, Max_Salary__c, Total_Salary__c from Account][0];
        System.assertEquals(acc.Max_Salary__c, 500);
        System.assertEquals(acc.Total_Salary__c, 500);
    }
}

Follow up question
1. How can we make the trigger more dynamic so when a new field is added it would do the max and sum on account

Answer:
Create a custom metadata mapper table that would contain the SOQL query values and then related Account mapped fields. Create a dynamic SOQL query reading the fields that needs to be queried from custom metadata. Use the SObject set method to set the field values. Account.put(‘Total_Salary_Count__c’, (Decimal)aggResult.get(‘countSalary’));