P.M
BAN USER- 0of 0 votes
AnswersWrite a function that returns true if the bit stream has an alternating pattern. For example 000000101010 would return true and 0000001010000 would return false. Also I had to write test cases for the function.
- P.M in United States| Report Duplicate | Flag | PURGE
Bit Manipulation
Can we assume that the binary search tree is stored in an array? If that is so, then we can simply apply Knade's algorithm to do this O(n) time, which works like this:
1. Put a pointer at first node and another pointer at last node.
2. If the sum of the nodes on the two pointers is equal to k, then those are your two nodes.
3. If sum is less, then, increment lower pointer.
4. If sum is more, then decrement higher pointer.
Hmm.. this is a very interesting question, so I am going to take a stab at this.
1. Go through the array once and map everything to a hash table. Also keep track of the largest positive vale you find - O(n)
2. Start a second loop from 0 or 1 (depending on your definition of smallest positive integer). - O(n)
3. In every iteration, check if value exists in hash table. If it does not, that is your value
Total time: O(n) runtime, O(n) space.
I will be very interested in a solution that can pull this off in less than O(n) space.
- P.M February 19, 2012You don't want to make elementsPickedSoFar, subsetSum and sumSoFar static variables. The reason for this is because you want each recursive call to have its own copy.
On a side note, the sumSoFar was introduced for code clarity. You can choose to remove that parameter and change the code logic slightly so that it terminates when targetSum == 0 and in each recursive call you do sumSoFar - arr[i] (in case you want to pick that element).
- P.M February 17, 2012Here is the code (this is a recursive solution, and quite obviously it is exponential). DP-fying it should be pretty easy given the recursive code:
The code is in C# and is 100% working. You can simply copy paste it in a Console Application and hit Run :)
public void SubsetSum()
{
int[] arr = { 7, 6, 5, 1, 11, 2, 9, 17, 3, 4, 0 };
SubsetSum(arr, 3, 0, 9, 0, 0, "");
Console.ReadLine();
}
private void SubsetSum(int[] arr, int k, int elementsPickedSoFar, int targetSum, int sumSoFar, int i, string subsetSum)
{
if (k >= arr.Length) return;
if (i >= arr.Length)
{
if (elementsPickedSoFar == k && targetSum == sumSoFar)
Console.WriteLine(subsetSum);
return;
}
if (elementsPickedSoFar == k)
{
if (targetSum == sumSoFar)
Console.WriteLine(subsetSum);
return;
}
SubsetSum(arr, k, elementsPickedSoFar, targetSum, sumSoFar, i + 1, subsetSum);
SubsetSum(arr, k, elementsPickedSoFar + 1, targetSum, sumSoFar + arr[i], i + 1, subsetSum + " " + arr[i].ToString());
}
Let me explain the recurrence in English:
1. In each step of the recursion, you don't pick the current element from the array (denoted by i) and DO NOT add anything to the sum (denoted by sumSoFar)
2. OR, you pick the current element from the array (denoted by i) and it to the sum (denoted by sumSoFar)
3. That's it! All that is left are the bases cases, which are pretty self-explanatory, but to give a quick rundown:
3i. You terminate when i >= arr.Length (quite obviously)
3ii. OR the total elements that you have picked so far (refer to Step 1) is equal to 'k' (max elements you can pick).
Nvm... I didn't see that this was for Program Managers. I thought this was for SDE/SDET
- P.M February 20, 2012