Dung Nguyen
BAN USERAs all the files hold stream of integers, I would design a program that read each file and count the number of each integer in the files. When the program starts, it will create 8 temporary count files to hold the count of all integers each of which will keep counts of 2^29 numbers in sorted order. As each count will be a 64 bit number, each file will be 4GB. 8 files will cover count of all possible numbers.
A program will be designed to read each integer from each file and store integer counts temporarily in a sorted key-pair values such as sorted dictionary Dictionary<int, long>. When the number of element in the dictionary reach a point where it would run out of memory (about 340k element), the program will update the count files by adding the new value to existing one and saved to the same location. The program then clears the dictionary and continues the loop until all input files are read and processed.
When all the input files are processed, the program reads the 8 temporary count files, the output the number of integer to the final output file.
This solution limit is that there are at most 2^64-1 appearance of each number in all the input files
Not sure why the function take i, j, and k as parameters instead of length, width and floor to be more intuitive.
(int i, int j, int k) nextPreferredSlot = (-1, -1, -1);
const int Length = 0;
const int Width = 1;
const int Floor = 2;
// parking Lot: true if occupied, false otherwise
bool parkingLot[,,] = Initialise();// not implemented
void Unpark(int i, int j, int k)
{
if (i >= parkingLot.GetLength(Length) || j >= parkingLot.GetLength(Width) || k >= parkingLot.GetLength(Floor))
return; //
parkingLot[i, j, k] = false;
if (k < nextPreferredSlot.k)
{
nextPreferredSlot = (i, j, k);
}
else if (k == nextPreferredSlot.k)
{
if (i < nextPreferredSlot.i)
nextPreferredSlot = (i, j, k);
else if (i == nextPreferredSlot.i)
{
if (j < nextPreferredSlot.j)
nextPreferredSlot = (i, j, k);
}
}
}
static void Park()
{
if (nextPreferredSlot.i == -1)
{
nextPreferredSlot = FindNextAvailableSlot((0,0,0));
if (nextPreferredSlot.i == -1)
return; // No available slot;
}
parkingLot[nextPreferredSlot.i, nextPreferredSlot.j, nextPreferredSlot.k] = true;
nextPreferredSlot = FindNextAvailableSlot(nextPreferredSlot);
}
static (int i, int j, int k) FindNextAvailableSlot((int i, int j, int k) currentSlot)
{
(int i, int j, int k) = currentSlot;
for (; k < parkingLot.GetLength(Floor); k++)
{
for (; i < parkingLot.GetLength(Length); i++)
{
for (; j < parkingLot.GetLength(Width); j++)
{
if (!parkingLot[i, j, k])
return (i, j, k);
}
j = 0;
}
i = 0;
}
return (-1, -1, -1); // Parking lot are full
}
C# - simple string manipulation
void main()
{
//string input = "(a + (b*c)) * (d * ( f * j) )";
// use more complicated input
string input = "(a * (b+c)) * (d * ( f * j) ) + ((e-d*r)*s) + (e-d*r*(r-e))";
Dictionary<int, int> brackets = new Dictionary<int, int>();
int level = 0;
StringBuilder sb = new StringBuilder(input);
for (int i = 0; i < sb.Length; i++)
{
if (sb[i] == '(')
{
brackets[level++] = i;
}
else if (sb[i] == ')')
{
int openIndex = brackets[brackets.Count - 1];
string temp = sb.ToString();
string middleString = temp.Substring(openIndex, i - openIndex + 1);
if (KeepBracket(middleString))
{
sb.Replace('+', '=', openIndex, i - openIndex + 1);
sb.Replace('-', '_', openIndex, i - openIndex + 1);
}
else
{
sb[openIndex] = ' ';
sb[i] = ' ';
}
brackets.Remove(brackets.Count - 1);
level--;
}
}
string result = sb.ToString();
result = result.Replace('_', '-').Replace('=', '+');
Console.WriteLine("Org string :" + input);
Console.WriteLine("Modified string:" + result);
}
public bool KeepBracket(string str)
{
if (str.Contains('+') || str.Contains('-'))
return true;
return false;
}
void main()
{
//string input = "(a + (b*c)) * (d * ( f * j) )";
// use more complicated input
string input = "(a * (b+c)) * (d * ( f * j) ) + ((e-d*r)*s) + (e-d*r*(r-e))";
Dictionary<int, int> brackets = new Dictionary<int, int>();
int level = 0;
StringBuilder sb = new StringBuilder(input);
for (int i = 0; i < sb.Length; i++)
{
if (sb[i] == '(')
{
brackets[level++] = i;
}
else if (sb[i] == ')')
{
int openIndex = brackets[brackets.Count - 1];
string temp = sb.ToString();
string middleString = temp.Substring(openIndex, i - openIndex + 1);
if (KeepBracket(middleString))
{
sb.Replace('+', '=', openIndex, i - openIndex + 1);
sb.Replace('-', '_', openIndex, i - openIndex + 1);
}
else
{
sb[openIndex] = ' ';
sb[i] = ' ';
}
brackets.Remove(brackets.Count - 1);
level--;
}
}
string result = sb.ToString();
result = result.Replace('_', '-').Replace('=', '+');
Console.WriteLine("Org string :" + input);
Console.WriteLine("Modified string:" + result);
}
public bool KeepBracket(string str)
{
if (str.Contains('+') || str.Contains('-'))
return true;
return false;
}
I would hashset the array to remove duplicate items. Then find the min and max value. If (max-min) + 1 == hashset size then the array is contiguous, otherwise it is not.
- Dung Nguyen April 17, 2019