KnowledgeSeeker
BAN USERIf there are no duplicate.
Associate int value characters, may be using hashtable
i.e. first word is GUM so
G = 0
U = 1
M = 2
Then do simple bubble sort on MUG with knowlege of associated int values.
Can you explain little more about 2nd algorithm.
- KnowledgeSeeker October 30, 2013I think its Recursive DP problem.
- KnowledgeSeeker October 13, 2013Can it be modeled as 0/1 knapsack problem, where knapsack size is the end time and length of task as value?
- KnowledgeSeeker August 28, 2013It can be solved without recursion with a loop. Anyways suggest if you have other solution or anything constructive with this one rather than thinking about my ingenuity.
- KnowledgeSeeker August 07, 2013thats why I asked for
"Please suggest on optimization, with data structure in case of DP", I guess you missed reading it.
Its simple recursive solution.
Initially set start index =0 and calculate the max sub array satisfying the condition, and keep incrementing the start end index till length of array. and Compare the resulting subarray length and return the indexes with max subarray length.
Here is the C# solution.
Please suggest on optimization, with data structure in case of DP.
void Main()
{
// Given 2 binary arrays A and B i.e. containing only 0s and 1s each of size N.
// Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i (i.e. the length of the set i,j) is the maximum possible value.
Tuple<int,int> result = FindMaxSubArray(0);
Console.WriteLine("start index " + result.Item1.ToString() + "end index" + result.Item2.ToString());
}
// Define other methods and classes here
BitArray A = new BitArray(new bool[]{false,true,false,false,true,true,false,false,false,true});
BitArray B = new BitArray(new bool[]{true,true,false,false,false,true,false,false,true,true});
Tuple<int,int> FindMaxSubArray(int startIndex)
{
int endIndex = 0;
int additionOfA = 0, additionOfB = 0;
if(startIndex >= A.Length - 1)
{
return new Tuple<int,int>(startIndex,-1000);
}
for(int i=startIndex; i<A.Length; i++)
{
additionOfA = additionOfA + Convert.ToInt32(A[i]);
additionOfB = additionOfB + Convert.ToInt32(B[i]);
if(additionOfA == additionOfB)
{
endIndex = i;
}
}
Tuple<int,int> subProblemSolution = FindMaxSubArray(startIndex + 1);
if((subProblemSolution.Item2 - subProblemSolution.Item1) > (endIndex - startIndex))
{
return subProblemSolution;
}
else
{
return new Tuple<int,int>(startIndex,endIndex);
}
}
void Main()
{
int[] input = new []{2, 8, 3, 6, 9, 3, 0, 0, 1, 3};
Console.WriteLine(FindMinimumJumps(input,0,0));
}
int FindMinimumJumps(int[] input, int currentPosition, int numberOfJumps)
{
int lastPosition = input.Length - 1;
if(currentPosition > lastPosition)
return int.MaxValue;
else if(currentPosition == lastPosition)
return numberOfJumps;
int maxJump = input[currentPosition];
if(maxJump == 0)
return int.MaxValue;
int minHops = int.MaxValue;
for(int i = 1;i<=maxJump;i++)
{
minHops = Math.Min(minHops, FindMinimumJumps(input, currentPosition + i,numberOfJumps+1));
}
return minHops;
}
Answer will depend on the data.
Solution is to find a hash to data item to map to array index.
If its allowed to use extra space, create a int array of 256.
iterate through set 1, and increment value of array element at position (int)char. Then iterate through set 2.
Iterate through int array for all values = 2.
Question - About the 2 visits in 3 days
- KnowledgeSeeker December 26, 2013suppose user visits on 1st, 2nd and 3rd, so he is not to be tracked.
But on 4th he doesn't visit the site, so as per 2 visits in 3 days he should be tracked
i.e. visited on 2nd, 3rd and not on 4th
Is this assumption correct? also can you clarify around 3 days, are those need to be consecutive?