saifullah.baig
BAN USER- Imagine that the 2^32 bytes has 2^20 pages each of size 4k and aligned at 4k boundaries
- When an allocation request comes, it can either by aligned at 4k boundary in which case it takes the whole page. Otherwise it overlaps two adjacent pages.
- Maintain an array of 2 byte words of total 2^20 words. This array needs to be in a separate area of memory. Each word maintains the state of the imaginary 4k aligned page. The total size of the array will be 2MB
- Each 2 byte word in the array (16 bits) is divided into two portions
-- A 12 bit portion containing the start of used offset e.g. 0, 59, 23 etc.
-- A 4 bit portion containing the info whether the page is used or not. Only one bit is really needed to keep this boolean information.
With the above data structure, checking can be done in O(1) steps. Say we want to check address A
- Partition A into A20 and A12 meaning uppper 20 and lower 12 bits
- Check word A20 in the array. If it is used and the offset stored in it is <= A12, return ((A20 << 20) | offset at A20)
- Check previous word (A20-1). If it is used and A12 <= (offset at A20-1)-1, return ((A20-1)<<20 | (offset stored at A20-1))
- If we reach here, then return 0
If we can have a constraint that memory requests in the range 0 - 4095 always fail, then the above scheme of returning start address should work perfectly.
I think it can be done with a recursive pattern. You get three arrays with corresponding start and end (both inclusive) indices. They are the inorder, preorder and postorder representations of the tree. The algorithm is like:-
- Match the start element of preorder with last element of postorder. If match is successful, search this element in the inorder representation using linear search and keeping duplicates in mind. If found, use it as potential root element.
- Use the location of potential root in inorder representation to determine the number of nodes in left and right subtrees
- Recurse on inorder, preorder and postorder representations of left and right subtrees. If recursion on subtrees fails then find another potential root in the inorder representation and repeat
This is easy to follow in the following C# implementation
// helper method for linear search
public static int SearchFirst(int[] a, int start, int end, int key)
{
for (int i = start; i <= end; i ++)
{
if (a[i] == key)
return i;
}
return -1;
}
public static bool Verify(int[] inOrder, int inStart, int inEnd,
int[] preOrder, int preStart, int preEnd,
int[] postOrder, int postStart, int postEnd)
{
// empty traversals imply empty trees
if (inOrder == null || preOrder == null || postOrder == null)
{
if (inOrder == null && preOrder == null && postOrder == null)
return true;
else
return false;
}
if (inStart > inEnd || preStart > preEnd || postStart > postEnd)
{
if (inStart > inEnd && preStart > preEnd && postStart > postEnd)
return true;
else
return false;
}
// if we reach here then we have non empty traversals
// verify root in preOrder and postOrder
if (preOrder[preStart] != postOrder[postEnd])
return false;
int i = inStart;
while ((i = SearchFirst(inOrder, i, inEnd, preOrder[preStart])) != -1)
{
int leftLength = i - inStart;
int rightLength = inEnd - i;
// verify left and right subtrees
if (Verify(inOrder, inStart, i - 1,
preOrder, preStart + 1, preStart + leftLength,
postOrder, postStart, postStart + leftLength - 1) &&
Verify(inOrder, i + 1, inEnd,
preOrder, preStart + leftLength + 1, preEnd,
postOrder, postStart + leftLength, postEnd - 1))
return true;
i++;
}
return false;
}
It seems so to me
- saifullah.baig March 16, 2011Here is a solution in C#. The implementation is simple due to the use of SortedSet type provided by .NET
static ulong GetHammingNumber(int n)
{
int i = -1; // sequence number
ulong x = 0; // Hamming number at i
// duplicates not allowed in SortedSet
// min can be retrieved in O(1)
SortedSet<ulong> candidateSequence = new SortedSet<ulong>();
candidateSequence.Add(1); // first candidate is 1
do
{
x = candidateSequence.Min();
// add three more candidates 2x 3x 5x
// duplicates are discarded by the data type
candidateSequence.Add(2 * x);
candidateSequence.Add(3 * x);
candidateSequence.Add(5 * x);
candidateSequence.Remove(x);
i++;
}
while (i < n);
return x;
}
Here is a C# solution based on DP. The problem is trivially solved for frame size 1 (output == input). Using solution for frame size k-1 and input array, we can build solution for frame size k using the formula
maxK[i] = max(maxK_1[i-1], input[i])
static void PrintMaxSubK(int[] a, int k)
{
if (a == null || a.Length < 1 || k < 0)
{
// error cases
return;
}
// adjust target frame size if needed
if (k > a.Length) k = a.Length;
int[] maxCurrent = new int[a.Length];
a.CopyTo(maxCurrent, 0);
int[] maxNext;
int l;
// gradually increase frame size
for (l = 1; l < k; l++)
{
maxNext = new int[a.Length];
for (int i = l; i < a.Length; i++)
{
maxNext[i] = (a[i] >= maxCurrent[i-1]) ? a[i] : maxCurrent[i-1];
}
maxCurrent = maxNext;
}
// output values
for (int i = k - 1; i < maxCurrent.Length; i++)
{
Console.WriteLine(maxCurrent[i]);
}
}
This can be done using a BFS pattern. The tree levels can be printed from bottom to top (root). Direction of printing needs to be adjusted (forward/backward). Here is a C# implementation
class Node<T>
{
public T data;
public Node<T> left, right;
}
static void PrintReverseSpiral<T>(Node<T> root)
{
List<Node<T>> current = new List<Node<T>>();
List<Node<T>> next = new List<Node<T>>();
List<List<Node<T>>> levels = new List<List<Node<T>>>();
if (root != default(Node<T>))
current.Add(root);
// build a list of all the levels
while (current.Count > 0)
{
foreach (Node<T> n in current)
{
if (n.left != null) next.Add(n.left);
if (n.right != null) next.Add(n.right);
}
levels.Add(new List<Node<T>>(current));
current = next;
next = new List<Node<T>>();
}
// print in spiral order
for (int i = levels.Count - 1; i >= 0; i--)
{
if (i % 2 == 0)
{
// even levels printed forward
for (int j = 0; j < levels[i].Count; j++)
Console.Write("{0}, ", levels[i][j].data);
}
else
{
// odd levels printed backward
for (int j = levels[i].Count - 1; j >= 0 ; j--)
Console.Write("{0}, ", levels[i][j].data);
}
}
Console.WriteLine();
}
Here is a possible solution in C#. It lacks error checking of arguments. The processing step is O(n^2) both in time and space. After that, any average can be computed in O(1) time.
// build a running sum of input
// output[x,y] = sum of all elements in the rectactange with top left as [0,0] and bottom right as [x,y]
int[,] Process(int[,] input)
{
int[,] output = new int[input.GetLength(0), input.GetLength(1)];
int row, col;
output[0, 0] = input[0, 0];
// populate top most row of output
for (col = 1; col < input.GetLength(1); col++)
{
output[0, col] = output[0, col - 1] + input[0, col];
}
// populate left most column of output
for (row = 1; row < input.GetLength(0); row++)
{
output[row, 0] = output[row - 1, 0] + input[row, 0];
}
// populate remaining elements of output
for (row = 1; row < input.GetLength(0); row++)
{
for (col = 1; col < input.GetLength(1); col++)
{
output[row, col] = output[row, col - 1] - output[row - 1, col - 1] + output[row - 1, col] + input[row, col];
}
}
return output;
}
// compute sum of all elements in a sub-rectangle defined by start and end coordinates
int Sum(int[,] output, int startRow, int startCol, int endRow, int endCol)
{
int A, B, C, D;
A = (startRow == 0 || startCol == 0) ? 0 : output[startRow - 1, startCol - 1];
B = (startRow == 0) ? 0 : output[startRow - 1, endCol];
C = (startCol == 0) ? 0 : output[endRow, startCol - 1];
D = output[endRow, endCol];
return D - C - B + A;
}
// compute the number of elements in a sub-rectangle
int CountElements(int startRow, int startCol, int endRow, int endCol)
{
int totalRows = endRow - startRow + 1;
int totalCols = endCol - startCol + 1;
return totalRows * totalCols;
}
// compute the average of all the elements in a sub-rectange
double Average(int[,] output, int startRow, int startCol, int endRow, int endCol)
{
return (double) Sum(output, startRow, startCol, endRow, endCol) /
CountElements(startRow, startCol, endRow, endCol);
}
Here is a recursive approach
- create circular list of left child
- create circular list of right child
- merge both lists
class Node<T>
{
public T data;
public Node<T> left;
public Node<T> right;
}
void BTToCL(Node<T> root)
{
if (root == null)
return;
Node<T> saved1, saved2;
if (root.left != null)
{
BTToCL(root.left);
saved1 = root.left.right;
root.left.right = root;
}
else
{
root.left = root;
saved1 = root;
}
if (root.right != null)
{
BTToCL(root.right);
saved2 = root.right.left;
root.right.left = root;
}
else
{
root.right = root;
saved2 = root;
}
saved1.left = saved2;
saved2.right = saved1;
}
It seems like a set intersection problem to me. One of the arrays has limited values. We can track its values using a hash set or a bit vector. Then iterate over the other array and find out any matches
- saifullah.baig April 03, 2011