mindless monk
BAN USERCreate a HashMap<char, int, int> and Top: char for each position.
1. Say for position i, user enters 'a'.
Enter into map: <a, 0, 1> : 0 is the position of first occurrence of char in that position, 1 is count. Update Top to a.
2. So, for position i 'a' is suggested to user next time. But, say user enters 'b'. Add <b, 1, 1> to map. Now count of Top and current char are same, so look for position. Position of a is less than that of 'b'. So, top remains unchanged.
3. User is suggested 'a' again, but say user enters b again. Update map for 'b' to <b, 1, 2>. Now Top will be updated to 'b'.
Suffix tree is useful for finding sub-strings not sub-sequences. Won't work here.
- mindless monk November 18, 20131. Use a hashmap.
2. Scan linearly through given string.
3. For each character check if it is present in hashmap. If it is, then just remove the char from hashmap. Else, add it to hashmap and append it to new string.
4. Return new string.
@geekofthegeeks
I think abcplent would be the right answer, as suggested by @anonymous. If it is not then please give some examples and explain them.
"Small lexicographic order" is confusing me... do you mean "small" or "lexicographic order" or both?
Lets have an example.
apple, bc, plent => applentbc or applebcplent?
Need more info on this one.
1. Does that smallest string is one of the N strings? (I know that would be dumb, but not clear from question.)
2. If not, does the smallest string need to come from a dictionary? Or just and string with characters in sorted order would do?
Well then the question is re-defining what "sub-array" means. I do not think any interviewer would want to do that.
- mindless monk November 15, 2013Modified Kadane's algo will be O(N)
- mindless monk November 15, 2013Not sure if I am getting it right. But, I guess just returning current stack of program should be fine. You just need to keep track of line of code for each stack though.
- mindless monk November 14, 2013Use this recursion:
makeSum(n, n-1), returns sets such that sum of its elements is n and the elements in the set are less than or equal to n-1.
makeSum(n, n-1) = CreateSet(n-1, n-1...i times) U ForEach set in (makeSum(n-i(n-1), n-2)), where 0 <= i <= n/(n-1)
makeSum(n, 1) = CreateSet(1,1,...n times)
bool IsAMatch(string actual, string expected)
{
char faultyKey = '\0';
int i = 0, j = 0;
for(; i < expected.length() && j < actual.length(); ++i)
{
if(actual.at(j) != expected.at(i))
{
if('\0' != faultyKey)
{
if(faultyKey != expected.at(i))
return false;
}
else
{
faultyKey = expected.at(i);
}
}
else
{
++j;
}
}
return (i == expected.length() - 1 && j == actual.length() - 1)? true : false;
}
Assuming that buckets are contiguous in space and a rectangle represented by bucket is aligned with X and Y axis.
Question boils down to finding match in a row-wise and column-wise sorted matrix.
For database vs memcached, I think it will depend on the usage. Say we are using this for an gps application. In that case memcached must be used.
@Ajeet
Lets consider this example.
String: abcdaefgh
Method suggested by you:
after finding duplicate 'a' at position 4, you start comparisons from b
My suggestion:
You do not have to traverse b,c,d again
What you pointed about searching in map, is true. My solution does require you to traverse the map. But even your solution need to call clear on map. So, eventually you are also traversing the map and freeing the memory.
Similar to windowing solutions suggested in this thread, but a little better then them.
The idea is we do not need to move back the window to previous location of duplicate found in current window. Rather, we can continue from current location without ever moving back. Hence, can attain O(n) in true sense. This is on the lines of Knuth-Pratt-Morris algo.
int MaxLenUniqeCharsSubstr(string str)
{
map<char, int> win;
int max = 0, cur = 0;
for(int i = 0; i < str.length(); ++i)
{
char ch = str.at(i);
if(win.end() != win.find(ch))
{
if(max < cur)
max = cur;
RemoveFromMapPosLowerThan(win, ch);
cur = win.size();
}
cur++;
win[ch] = i;
}
return max;
}
void RemoveFromMapPosLowerThan(map<char, int> &win, char ch)
{
map<char,int>::iterator it = map.begin();
int pos = win[ch];
while(it != map.end())
{
if(it->second <= pos)
win.erase(it);
}
}
Sorry, my answer got posted twice.
- mindless monk April 07, 2013C# Code:
--------------------
using System;
using System.Linq;
using System.Collections.Generic;
namespace MaxProdForThreeAscendingNumbersInArray
{
class Program
{
private static IList<int> Arr;
private static IDictionary<ProdInput, ProdOutput> ProdCache;
private static int subseqLen = 3;
struct ProdInput
{
public int curIndex;
public int numbersLeft;
public int minValue;
public ProdInput(int p1, int p2, int p3)
{
curIndex = p1;
numbersLeft = p2;
minValue = p3;
}
}
struct ProdOutput
{
public int Value;
public Stack<int> Subseq;
public ProdOutput(int val, Stack<int> SubseqIn)
{
Value = val;
Subseq = new Stack<int>(SubseqIn);
}
}
static void Main(string[] args)
{
if (0 == args.Length)
{
Console.WriteLine("ERROR: Enter array.\n"
+"USAGE: exe 4 2 5 8 10 ");
return;
}
Arr = new List<int>();
ProdCache = new Dictionary<ProdInput, ProdOutput>();
PopulateInputArray(args);
DisplayInputArray();
ProdOutput Output = ComputeMaxProd();
Console.Write("Max product: ");
if(Output.Value == -1)
{
Console.Write("No subsequence found!");
}
else
{
Console.Write(Output.Value);
Console.WriteLine("");
foreach (var element in Output.Subseq.Reverse())
{
Console.Write(" {0}", element);
}
}
}
private static ProdOutput ComputeMaxProd()
{
return Prod(0, //curIndex
subseqLen, //numbersLeft
0 //minValue
);
}
private static ProdOutput Prod(int curIndex, int numbersLeft, int minValue)
{
if (0 == numbersLeft)
{
return new ProdOutput(1, new Stack<int>());
}
if (curIndex >= Arr.Count)
{
return new ProdOutput(-1, new Stack<int>());
}
ProdInput curInput = new ProdInput(curIndex, numbersLeft, minValue);
ProdOutput curOutput;
if (!ProdCache.ContainsKey(curInput))
{
if (Arr[curIndex] >= minValue)
{
ProdOutput withElem = Prod(curIndex + 1, numbersLeft - 1, Arr[curIndex]);
withElem.Value *= Arr[curIndex];
ProdOutput withoutElem = Prod(curIndex + 1, numbersLeft, minValue);
if (withElem.Value > withoutElem.Value)
{
withElem.Subseq.Push(Arr[curIndex]);
ProdCache[curInput] = withElem;
}
else
{
ProdCache[curInput] = withoutElem;
}
}
else
{
ProdCache[curInput] = Prod(curIndex + 1, numbersLeft, minValue);
}
}
curOutput = new ProdOutput(ProdCache[curInput].Value, ProdCache[curInput].Subseq);
return curOutput;
}
private static void DisplayInputArray()
{
Console.Write("Input Array:");
foreach (var element in Arr)
{
Console.Write(" {0}", element);
}
Console.WriteLine("");
}
private static void PopulateInputArray(string[] args)
{
foreach (var input in args)
{
Arr.Add(Int32.Parse(input));
}
}
}
}
Also using trie or prefix tree will be a solution here, but coming up with trie will again require DP.
- mindless monk August 01, 2011DP is basically a tree based approach. So till i=0 and j=3, we will have one branch which will have "the". Now DP will shoot out a branch for handling the case where we start making a word from scratch, while the original branch will go on appending the letters to "the" to handle the case where the should not have been chosen as word.
The same rule applies on each branch, and at the end we will have all possible combination of words from the letters.
Well, I would say DP will help here. To be sure that at any point when we find a match in dictionary and we put a space, remaining letters can also be grouped into some meaningful words, we have to depend on next letters.
word(i, j) = ( dict(i,j)? (word(i, j+1) && word(i+1, j+1)) : word(i, j+1))
word is a function which decides if the letters between position i and j (inclusive of i and j) can be a word, i.e., can have spaces at its ends.
dict(i,j) returns true if letters form i to j position finds a match in dictionary.
As we do not want number of valid combinations possible so we can exit the procedure when dict(i, N) is reached and is true.
Forgot to add in my previous post. Its complexity would be O(n^2).
- mindless monk December 05, 2013