Pre-processing

Let us try to understand this problem statement first. It is actually very verbose. We will try to simplify it as much as possible. Christy wants to give chocolates to her colleagues, and at the same time tries to ensure that everyone has equal chocolates at the end. To achieve this she either gives 1,2, or 5 chocolates to everyone except any one individual. Every-time she does this, it is counted as 1 operation. We need to make sure that Christy can achieve this task in the minimum number of…

Question: Given a two strings, find the minimum number of characters that must be deleted to make them anagrams. Input: str1 = “a b c”, str2 = “a m n o p”Output: 6 Let us try to understand this problem statement and its test case first. We have two strings of english alphabet which may or may not have the same length. Anagrams are two words with same characters and frequencies. It is not necessary that the order of the characters is same. We have to determine, how many total…

Given an array of strings, group all the anagrams together. This post explores 2 methods to solve this problem. You can create groups by sorting, or by categorizing using the frequency of characters.

Question: Given a string, Sherlock considers it valid if all the characters in the string occur the same number of time. However, a string is also valid if the frequencies are same after removing any one character. Example 1:Input: str = “aabbcd”Output: NO Example 2:Input: str = “abcc”Output: YES Problem Statement: Let us try to simplify the problem statement first. Sherlock needs to verify if a given string is valid. A string is valid under 2 conditions: All characters of the string appear the same number of times. If you…

Question: Given two strings, determine if they share a common sub-string. Input: “a” and “art” Output: YES Problem Statement Let me try to simplify this problem statement first. You are given two strings, and you need to find out if they share a common sub-string or not. If you can find a common sub-string, output “YES”, else output “NO”. Note that you don’t have to find out what is the common sub-string. Another important aspect of this problem is that the sub-string can be as small as 1 character. A…

There can be several aspects when you think about analysis of algorithms. You may be writing a large scale application where you have to decide between two choices. You may be trying to submit a solution to some online competition and you want a higher score, or probably you may just want to write fewer lines of code. Analysis during an Interview Let’s say you are appearing for an interview. The person who is interviewing you gives you a problem to solve. He or she is not just interested in…

Given two strings str1 and str2. Write a function to determine if str1 is an anagram of str2. Example 1:str1 = “listen”, str2 = “silent”Output = True Example 2:str1 = “mississippi”, str2 = “mips”Output = False Terminology: Anagram: Two words or phrases are said to be anagrams of each other if they can be formed by re-shuffling of characters in one of them. Problem Statement: In the given problem we have 2 strings as input. They may be single words or phrases. Return true if they anagrams of each other,…

You are given a string with some repeating characters and some unique characters. Find the first unique character and return its index. Example 1:Input: studyAlgorithmsOutput: 2 Example 2:Input: iLoveToCodeOutput: 0 Problem Statement: I want to simplify the problem statement first before we begin to solve it. An input string consists of some uppercase and lowercase characters which may or may not be repeated. Out of all the unique characters, you need to return the characters that occurs first in the string. In the first example studyAlgorithms, s, and t are…

Question: Given an array A, find the sum of maximum sum of two non-overlapping subarrays, with lengths L and M.In other words, return the largest V for which V = (A[i] + A[i+1] …. A[i+L-1]) + (A[j] + A[j+1] …. A[j+M-1])Input: A = {3, 8, 1, 3, 2, 1, 8, 9, 0}; L = 3, M = 2Output: 29 The problem statement is quite clear. We need to find 2 contiguous sub-arrays from an array Add the elements of both these arrays The sum should be the maximum possible sum…

Question: Given an integer N, find the prime numbers in that range from 1 to N. Input: N = 25Output: 2, 3, 5, 7, 11, 13, 17, 19, 23 We have several ways of finding prime numbers. Some of the methods are discussed in the these posts. Method 1 Method 2 Method 3 In this post we will find the first N prime numbers using the Sieve of Eratosthenes. This technique is helpful in scenarios when we have to give immediate results and we need to query the prime numbers…