1. Given four digits, find the maximum valid time that can be displayed on a dig
ID: 3852572 • Letter: 1
Question
1. Given four digits, find the maximum valid time that can be displayed on a digital clock (in 24-hour format) using those digits. For example, given digits 1,8,3,2 the maximum valid time is "23:18". Note that "28:31" is not a valid time. Write a function: string MaxTime(int A, int B, int C, int D); that, given four integers A,B,C,D, returns the maximum valid time in string format "HH:MM" or "NOT POSSIBLE" if it is not possible to display a valid time. Examples: given 1,8,3,2, the function MaxTime shoud return "23:18". Given 2,4,0,0 the funtion should return "20:40". Given 3,0,7,0 the function should return "07:30" Given 9,1,9,7 the function should return "NOT POSSIBLE". Since there is no possible valid time. Assume that: A,B,C,D are integers with in the range [0..9] In your solution, focus on correctness as well as the performance of your solution. Try to achieve O(n) if possible rather than O(n^2) solution.
2. File I/Os: Given two text files, each of which contains a sorted list of integers (one integer per line) in non-decreasing order, write a C++ program to merge these two input files into a third file in which all the numbers remain their sorted order. Your program will include the main() function and another function that merges the two files. Specifically, the main() function will ask a user to type in the names of the two input files. It will then call the merging function to merge the two files. Finally, it informs the user the name of the merged file. Note that you are not allowed to first load all the numbers in the two files into an array or vector then apply a sorting algorithm to this array.
3. Random accesses to a file.The file posted here on iLearn contains a formatted list of 9999 integers that are randomly generated in the range of [1,9999]. Each integer occupies one single line and takes 4 characters' space per line. Alternatively, you can think that each number takes 5 characters' space, four for the number and one for the newline character. Write a C++ program using the seekg() and seekp() functions to insert the numbers 7777 through 7781 between the 6000-th and 6001-st numbers of the input file. Below are a few useful tips: The tellg() and tellp() functions return the position of the current character in an input stream or output stream, respectively. You are strongly recommended to use the tellg() function to first learn about the starting position of each integer. This will help you locate the exact starting position to insert the new numbers. You can use the width() function to specify the number of characters you'd like an integer to occupy. In addition to the "output" operator (<<), you can also use the write() function to write to a file.
Before you insert the numbers, you will need to first store all the numbers from the 6001-st number in an internal data structure, e.g., array. Otherwise, some of them will be overwritten. Finally, always call the clear() function before calling the seekg() or seekp() function. Otherwise, you might encounter inexplicable behaviors. Requirements: You are not allowed to create or use any other files except the single input file. You must use seekg() or seekp() to directly identify the insertion point to insert the new numbers. It's acceptable to hardcode the input file name and implement everything in the main() function. However, it's preferred to create a separate function that handles the insertion of new numbers.
Explanation / Answer
File Sort and Merge
----------------------------------------------------------
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <iomanip>
#include <random>
using namespace std;
void fillFile(fstream &file)
{
srand(time(NULL));
int randomInt = rand() % 100 + 1;
cout << randomInt;
cout << "Filling file with random numbers (1-99)......." << endl;
while (file.is_open())
{
for (int i = 0; i < 10; i++)
{
file << randomInt << endl;
}
file.close();
}
}
void merge(fstream &file1, fstream &file2, fstream &merge)
{
string line;
int counter = 1;
int num1 = 0;
int num2 = 0;
bool first = true;
if (file1.is_open())
{
getline(file1, line);
num1 = atoi(line.c_str()); //convert alpha to int
}
else if (file2.is_open())
{
getline(file2, line);
num2 = atoi(line.c_str()); //convert alpha to int
}
while ((file1.is_open()) || (file2.is_open()))
{
if (file1.is_open() && file2.is_open())
{
if (num1 >= num2)
{
merge << counter++ << ": " << num1 << endl;
getline(file1, line);
num1 = atoi(line.c_str());
}
else
{
merge << counter++ << ": " << num2 << endl;
getline(file2, line);
num2 = atoi(line.c_str());
}
}
else
{
if (first)
{
if (!file1.is_open())
{
merge << counter++ << ": " << num2 << endl;
}
else if (!file2.is_open())
{
merge << counter++ << ": " << num1 << endl;
}
}
else
{
merge << counter++ << ": " << line << endl;
}
if (file1.is_open())
{
getline(file1, line);
}
else if (file2.is_open())
{
getline(file2, line);
}
first = false; // break condition for while-loop
}
}
}
int main()
{
string line; // used to read in each line from the file
fstream file1("file1.txt", ios::out | ios::app); // creates a file to read/write from/to a file
fstream file2("file2.txt", ios::out | ios::app);
fstream mergeFile("mergedFile.txt");
fillFile(file1);
cout << "File 1 now filled with 100 random numbers. ";
fillFile(file2);
cout << "File 2 now filled with 100 random numbers. ";
merge(file1, file2, mergeFile);
/*This is wrong somehow.....
if (mergeFile.is_open())
{
while (mergeFile.good())
{
getline(mergeFile, line);
cout << line << endl;
}
mergeFile.close();
}
else
{
cout << "Could not open file.";
}*/
file1.close();
file2.close();
mergeFile.close();
return 0;
}
----------------------------------------------------------------------------------------------------
RandomAccessFile
--------------------------------------------------
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;
int main()
{
//vector<int> numVector;
int myArray[10000];
const int SKIP_NUM = 6000;//number in file to skip to
int numBytes = 5;//bytes to be read in(4byte num + newline)
int product = (numBytes * SKIP_NUM);//to be used with seekg()
fstream file("file1.txt");
if (!file)
{
cout << "Cannot open file. ";
exit(1); //exit program if file isnt open
}
//cout << "check";
/*file.seekg(product);//skipping to the pointer to start adding new nums
while (file.is_open())//read in the numbers of the file
{
int nextNum;
file >> nextNum;
if (file.fail())
{
break;
}
numVector.push_back(nextNum);//subscript out of range
}
file.clear();//clear the file handles
file.seekp(product);
for (int i = 7777; i <= 7781; i++) //inserting 5 new numbers starting at pos. 6001
{
file << i << endl;
}
for (int i = 6006; i <= 9999; i++) //continuing to add the rest of the numbers from the file
{
file << numVector[i] << endl;
}*/
//===================================different logic testing========================================
int count = 0;
while (!file.fail())
{
int num;
file >> num;
if (num == SKIP_NUM)
{
break;
}
}
int numLoc = file.tellg();
//cout << "CHECK";
file >> myArray[count];//subscript out of range
//cout << "CHECK1";
while(!file.fail())
{
count++;
file >> myArray[count];
}
//cout << "CHECK2";
file.clear();
file.seekp(product);
for (int i = 7777; i <= 7781; i++)
{
file << i << endl;
}
//cout << "CHECK3";
for (int i = 0; i < count; i++)
{
file << myArray[i] << endl;
}
//cout << "CHECK 4";
cout << "Numbers being placed.............";
cout << " Complete. ";
file.close();
return 0;
}
-----------------------------------------------------
MaxPossibleTime
--------------------------
MaxPossibleTime.java
---------------------------
import java.util.*;
/**
* Given four digits, find the maximum valid time that can be displayed on
* a digital clock (in 24 -hour format) using those digits. for example,
* given digits 2,3,5,9 the maximum valid time is "23:59". note that "24:39"
* is not a valid time.
*/
public class MaxPossibleTime {
List<Integer> calc(List<Integer> input) {
List<Integer> output = new ArrayList<Integer>();
Collections.sort(input, Collections.reverseOrder());
if (findSolutions(0, output, input)) {
return output;
} else {
return null;
}
}
boolean findSolutions(int n, List<Integer> output, List<Integer> input) {
if (output.size() == 4) {
System.out.println(output);
return true;
}
for (int i=0; i<input.size(); i++) {
Integer val = input.get(i);
if (isValid(val, n, output)) {
applyValue(val, n, output);
List<Integer> newInput = new ArrayList<Integer>();
for (int j=0; j<input.size(); j++) {
if ( i != j) {
newInput.add(input.get(j));
}
}
if (findSolutions(n+1, output, newInput))
return true;
removeValue(val, n, output);
}
}
return false;
}
boolean isValid(Integer value, int n, List<Integer> output){
return isGoodCandidate(output, value);
}
void applyValue(Integer value, int n, List<Integer> output){
if (output.size() > n)
output.set(n, value);
else
output.add(n, value);
}
void removeValue(Integer value, int n, List<Integer> output){
output.remove(n);
}
boolean isGoodCandidate(List<Integer> result, Integer candidate){
if (result.isEmpty()) {
return checkH1(result, candidate);
} else if (result.size()==1) {
return checkH2(result, candidate);
} else if (result.size()==2) {
return checkM1(result, candidate);
} else if (result.size()==3) {
return checkM2(result, candidate);
}
return false;
}
boolean checkH1(List<Integer> result, Integer candidate){
return candidate>=0 && candidate<=2;
}
boolean checkH2(List<Integer> result, Integer candidate){
Integer d1 = result.get(0);
Integer d2 = candidate;
if (d1 == 2 && d2 > 3) {
return false;
} else if (d2 < 0 || d2 > 9) {
return false;
}
return true;
}
boolean checkM1(List<Integer> result, Integer candidate){
Integer d3 = candidate;
if (d3 < 0 || d3 > 5) {
return false;
}
return true;
}
boolean checkM2(List<Integer> result, Integer candidate){
Integer d4 = candidate;
if (d4 < 0 || d4 > 9) {
return false;
}
return true;
}
}
-----------------------------------------------------------
MaxPossibleTimeTest.java
-------------------------------------
import org.junit.Test;
import java.util.*;
import static org.fest.assertions.Assertions.assertThat;
public class MaxPossibleTimeTest {
@Test
public void test_time_10(){
MaxPossibleTime maxPossibleTime = new MaxPossibleTime();
List<Integer> input = Arrays.asList(3,9,2,5);
List<Integer> output = maxPossibleTime.calc(input);
assertThat(output).containsSequence(2,3,5,9);
}
@Test
public void test_time_20(){
MaxPossibleTime maxPossibleTime = new MaxPossibleTime();
List<Integer> input = Arrays.asList(1,9,2,5);
List<Integer> output = maxPossibleTime.calc(input);
assertThat(output).containsSequence(2,1,5,9);
}
@Test
public void test_time_30(){
MaxPossibleTime maxPossibleTime = new MaxPossibleTime();
List<Integer> input = Arrays.asList(1,2,7,7);
List<Integer> output = maxPossibleTime.calc(input);
assertThat(output).containsSequence(1,7,2,7);
}
@Test
public void test_time_40(){
MaxPossibleTime maxPossibleTime = new MaxPossibleTime();
List<Integer> input = Arrays.asList(3,2,7,7);
List<Integer> output = maxPossibleTime.calc(input);
assertThat(output).isNull();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.