Skip to content

Instantly share code, notes, and snippets.

@zyxar

zyxar/equation.cc

Created October 27, 2012 11:26
Show Gist options
  • Save zyxar/3964343 to your computer and use it in GitHub Desktop.
Save zyxar/3964343 to your computer and use it in GitHub Desktop.
Download ZIP
#amazon hiring 2012-2013 final unknown
Raw
equation.cc
/*Question:
Given an array with positive integers and another integer for example{7 2 4} 9, you are required to generate an equation, by inserting operator add ("+") and minus ("-") among the array . The left side of equation are consist of the array and the right side of equation is the integer. here the result is 7-2+4=9
Rules:
Don't include any space in the generated equation.
In case there is no way to create the equation, please output "Invalid". For example {1 1} 10, output is "Invalid"
The length of the integer array is from 1 to 15( include 1 and 15). If the length is 1, for example the input {7} 7, the output is 7=7
There is no operator "+" or "-" in front of the first number:
Don't change the order of the numbers. For example: {7 2 4} 9. 7-2+4=9 is correct answer, 4-2+7=9 is wrong answer.
There could be multiple input, meaning your function could be called multiple times. Do remember print a new line after the call.
Sample Input and Output:
Input:
1 2 3 4 10
1 2 3 4 5
Output:
1+2+3+4=10
Invalid
---------------------------*/
#include <iostream>
#include <cstring>
using namespace std;
/************************************************************************/
/**
Args:
array[]: the inputted array
final: the target value
length: the element length
*/
void createEquationAndPrint(int array[], int length, int final){
//Your Code is here
if (length == 1) {
if (array[0] == final) cout<<array[0]<<'='<<final;
else cout<<"Invalid";
return;
}
int sum = array[0];
char punc[length];
for (int i = 0; i < (1<<(length-1)); ++i) {
for (int j = 0; j < length-1; ++j) {
if ((i & (1<<(length-2-j))) != 0) {
punc[j] = '+';
sum += array[j+1];
} else {
punc[j] = '-';
sum -= array[j+1];
}
}
if (sum == final) {
cout<<array[0];
for (int j = 0; j < length-1; ++j) {
cout<<punc[j];
cout<<array[j+1];
}
cout<<'='<<final;
return;
}
sum = array[0];
}
cout<<"Invalid";
}
int splitAndConvert(char* strings,int array[]){
char*tokenPtr = strtok(strings," ");
int i=0;
while(tokenPtr!=NULL){
array[i] = atoi(tokenPtr);
i++;
tokenPtr=strtok(NULL," ");
}
return i;
}
int main(){
char line[1000] = {0} ;
while(gets(line)){
int array[30] = {0};
int length = splitAndConvert(line,array);
if(length==0){
break;
}
createEquationAndPrint(array, length-1, array[length-1]);
cout<<endl;
}
return 0;
}
Raw
matrix.c
/*Question:
There is a 5*5 matrix; the elements in this matrix are different integer from 0 to 24. The elements in this matrix are disordered. 0 is a special element. The upper element, under element, left element and right element of 0 can be exchanged with 0. Such exchange operations are named as ‘U’, ‘D’, ‘L’ and ‘R’.
Operation "U" means 0 exchanged with its upper element.
Operation "D" means 0 exchanged with its under element.
Operation "L" means 0 exchanged with its left element.
Operation "R" means 0 exchanged with its right element.
For example, the original matrix is
[20, 18, 7, 19, 10
24, 4, 15, 11, 9
13, 0, 22, 12, 14
23, 16, 1, 2, 5
21, 17, 8, 3, 6]
With the operation sequence “URRDDL”, the new matrix will be
[20, 18, 7, 19, 10
24, 15, 11, 12, 9
13, 4, 22, 2, 14
23, 16, 0, 1, 5
21, 17, 8, 3, 6]
Now, we know the original matrix, the matrix after the operations and all the operations made on the original matrix. Please provide the correct sequence for the operations.
The input will be the original matrix, the target matrix and an operation sequence with wrong order.
If there is a correct sequence for this input, then print the correct sequence. Otherwise, print “None”.
Rules and example:
The elements in the original matrix are different.
The elements in the original matrix are random ordered.
The max lenght of operatoins is 15.
If "0" is already on the boundary, it is not possible to do further movement. for example, if 0 is in the top row, then there is no more "U".
The input will be the original matrix, the target matrix and an operation sequence with wrong order.
The output will be a correct operation sequence.
In case there is no way to get the target matrix with the input operations, please output “None”
Don’t include any space in the generated operation sequence.
For examples, the original matrix is
Example 1:
[20, 18, 7, 19, 10
24, 4, 15, 11, 9
13, 0, 22, 12, 14
23, 16, 1, 2, 5
21, 17, 8, 3, 6]
The target matrix is
[20, 18, 7, 19, 10
24, 4, 0, 11, 9
13, 22, 15, 12, 14
23, 16, 1, 2, 5
21, 17, 8, 3, 6]
The input operation sequence is “UR”
The output operation sequence should be “RU”
Example 2:
[20, 18, 7, 19, 10
24, 4, 15, 11, 9
13, 0, 22, 12, 14
23, 16, 1, 2, 5
21, 17, 8, 3, 6]
The target matrix is
[20, 18, 7, 19, 10
24, 15, 11, 12, 9
13, 4, 22, 2, 14
23, 16, 0, 1, 5
21, 17, 8, 3, 6]
The input operation sequence is “RRLUDD”
The output operation sequence should be “URRDDL”*/
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#include <string.h>
void calculateTheRightSequence(int originalMatrix[][5], int newMatrix[][5],
char inputSequence[], char outputSequence[]);
int Getnput( char operation[], int originalMatrix[][5], int newMatrix[][5]);
int main()
{
int original[5][5];
int newMatrix[5][5];
char inputOperation[100]={0};
char outputOperation[100]= {0};
while( Getnput(inputOperation, original, newMatrix) )
{
calculateTheRightSequence(original, newMatrix, inputOperation, outputOperation);
printf("%s\n", outputOperation);
}
return 0;
}
//your code is here
void calculateTheRightSequence(int originalMatrix[][5], int newMatrix[][5],
char inputSequence[], char outputSequence[])
{
int i, j, k, h;
int exch = 0;
for (i = 0; i < 5; ++i)
{
for (j = 0; j < 5; ++j)
{
if (originalMatrix[i][j] == 0) goto next;
}
}
next:
h = 0;
memset(outputSequence, 0, 100);
for (k = 0; k < strlen(inputSequence); ++k)
{
exch = newMatrix[i][j];
if (j > 0 && originalMatrix[i][j-1] == exch) {
outputSequence[h++] = 'L';
j--;
} else if (i > 0 && originalMatrix[i-1][j] == exch) {
outputSequence[h++] = 'U';
i--;
} else if (j < 4 && originalMatrix[i][j+1] == exch) {
outputSequence[h++] = 'R';
j++;
} else if (i < 4 && originalMatrix[i+1][j] == exch) {
outputSequence[h++] = 'D';
i++;
} else {
memcpy(outputSequence, "None", 4);
outputSequence[4] = 0x00;
return;
}
}
if (newMatrix[i][j] != 0) {
memcpy(outputSequence, "None", 4);
outputSequence[4] = 0x00;
return;
}
// compare output and input
for (i = 0; i < k; ++i)
{
j = 0;
while (j < k && inputSequence[j] != outputSequence[i]) j++;
if (j == k) {
memcpy(outputSequence, "None", 4);
outputSequence[4] = 0x00;
return;
} else {
inputSequence[j] = '0';
}
}
}
int Getnput( char operation[], int originalMatrix[][5], int newMatrix[][5])
{
int i = 0, j = 0;
for( i = 0; i < 5; ++i )
for(j = 0; j < 5; ++j)
{
if( scanf(" %d ", &originalMatrix[i][j]) != 1 )
break;
}
if( j < 5 ) return 0;
for( i = 0; i < 5; ++i )
for(j = 0; j < 5; ++j)
{
scanf(" %d ", &newMatrix[i][j]);
}
scanf( "%s", operation );
return 1;
}
Raw
neightbourpeakvalley.c
/*Question 1 / 2.
Given an array A, find the maximum neighboring-peak-valley difference of A, MaxD(A).
For example, A={2, 3, 6, 5, 7, 9}, the elements 2, 5 could be regarded as the valley while 6 and 9 are the peaks. The difference of each neighboring peak-valley pair could be enumerated as below:
D[2, 6]=4, D[6,5]=1, D=[5,9]=4.
Thus, MaxD(A)=4.
Please write a program to find the maximum neighboring-peak-valley difference of an array. The input contains several lines(10 lines at most), and each line contains of several numbers separated by space. We treat every line an array.And each line has 2 numbers at least and 20 numbers at most.
The output should be the maximum neighboring-peak-valley difference of the arrays and separated by comma. For example:
Input:
2 3 6 5 7 9
2 3 6 5 7
2 3 6 5 7 9 10
Output:
4,4,5
*/
#include <stdio.h>
#include <string.h>
#define ISSPACE(x) ((x)==' '||(x)=='\r'||(x)=='\n'||(x)=='\f'||(x)=='\b'||(x)=='\t')
char * rightTrim(char *str){
int len = strlen(str);
while(--len>=0){
if(ISSPACE(str[len])){
str[len] = '\0';
}else{
break;
}
}
return str;
}
char * getInputLine(char *buffer, int length){
if(fgets(buffer,length, stdin)==NULL){
return NULL;
}
rightTrim(buffer);
if(strlen(buffer)<=0){
return NULL;
}
return buffer;
}
/*
For example, A={2, 3, 6, 5, 7, 9}, the elements 2, 5 could be regarded as the valley while 6 and 9 are the peaks.
The difference of each neighboring peak-valley pair could be enumerated as below:
D[2, 6]=4, D[6,5]=1, D=[5,9]=4.
Thus, MaxD(A)=4.
*/
void maxNeighboringPeak(char ** data, int count){
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
char* curr = NULL;
int i, j, h, k;
int max;
int maxim[512];
int value[512];
for (i = 0; i < count; ++i)
{
memset(value, 0, 512);
memset(maxim, 0, 512);
curr = data[i];
j = 0;
h = 0;
while (j < strlen(curr)) {
if (curr[j] != ' ') {
value[h] = curr[j]-0x30;
j++;
while (j < strlen(curr) && curr[j] != ' ') {
value[h] *= 10;
value[h] += curr[j]-0x30;
j++;
}
h++;
}
j++;
}
j = 1;
k = 1;
maxim[0] = value[0];
while (j < h-1) {
if ((value[j] > value[j-1] && value[j] > value[j+1]) ||
(value[j] < value[j-1] && value[j] < value[j+1])) {
maxim[k++] = value[j];
}
j++;
}
maxim[k++] = value[j];
max = 0;
for (h = 0; h < k-1; ++h)
{
j = maxim[h]-maxim[h+1];
if (j < 0) j = -j;
if (max < j) max = j;
}
printf("%d", max);
if (i != count-1) printf(",");
}
printf("\n");
}
int main(int argc, char ** argv){
char buffers[512][512];
char *input[512];
int inputCount = 0;
while(getInputLine(buffers[inputCount], 512) != NULL){
input[inputCount++] = buffers[inputCount];
}
maxNeighboringPeak(input, inputCount);
return 0;
}
Raw
parser.c
/*
Question 2 / 2.
We have a file which contains lines of some classify rules, we can place integers ( 0 < n < max(Integer)) to different categories by the rules, for example:
n1 : a = 4
n2 : a = 1 or a = 2 or a = 23
n3 : a > 100
n4 : a > 24 and a < 54
n5 : a > 54 and a < 58 or a = 22
The first line means if a number equals to 4, then it should be place to category n1;
The second line means if a number equals to 1 or 2 or 23, then it should be place to category n2;
The third line means any number greater than 100 should be placed into category n3;
The fourth line means any number greater than 24 and smaller than 24 should be placed into category n4;
The fifth line means any number greater than 54 and smaller than 58 or equals to 22 should be placed into category n5.
The file has the following rule
1. Category and rules are sperated by semicolon;
2. "a" is a key words in the file, it represent the integer;
3. Key words(":", "=", "or", ">", "<", "and", "a") are sperated by space;
4. "and" should have a higher precedence then "or", this meas rule "a > 10 or a > 5 and a < 8" will get true if a = 11
Write a program to parse a rule file and output the given number's category. If it's not belongs to any of the category, output "none". Please notice that expression evaluation API(eval() function or other equivalent functions) should not be used.
In all the testcases, we have a input like the following(The fist line contains several numbers we want to classify, and the category name can be any string):
45,22
n1 : a = 4
category 2 : a = 1 or a = 2 or a = 23
n3 : a > 100
n4 : a > 24 and a < 54
n5 : a > 54 and a < 58 or a = 22
And the output should be:
n4,n5
Information may be help:
1. The rules in the same testcase we provide are not conflict with anyone else;
2. None of the rule we provided is a self-conflict rule, for example, we provide no rule like this "n1 : a = 5 and a = 3".
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ISSPACE(x) ((x)==' '||(x)=='\r'||(x)=='\n'||(x)=='\f'||(x)=='\b'||(x)=='\t')
char * rightTrim(char *str)
{
int len = strlen(str);
while(--len>=0) {
if(ISSPACE(str[len])) {
str[len] = '\0';
} else {
break;
}
}
return str;
}
char * getInputLine(char *buffer, int length)
{
if(fgets(buffer,length, stdin)==NULL) {
return NULL;
}
rightTrim(buffer);
if(strlen(buffer)<=0) {
return NULL;
}
return buffer;
}
int extractNumbersToArray(char *str, int *numbers)
{
const char *split = ",";
char *p = strtok (str,split);
int index = 0;
while(p!=NULL) {
numbers[index++] = atoi(p);
p = strtok(NULL,split);
}
return index;
}
void determineRuleAndOutput(int *numbers, int numberCount, char ** rules, int ruleCount)
{
//your code here
char* name = NULL;
char* curr = NULL;
char* rule = NULL;
char eval[1024];
int i, j, k, final, h;
for (i = 0; i < numberCount; ++i) {
for (j = 0; j < ruleCount; ++j) {
h = 0;
k = 0;
memset(eval, 0, 1024);
name = rules[j];
while (name[k] != ':') k++;
name[k-1] = 0x00;
curr = &name[k]+1;
while ((rule = strstr(curr, "a ")) != NULL) {
curr = rule+7;
if (strncmp("and", rule-4, 3) == 0) {
eval[h++] = '&';
} else if(strncmp("or", rule-3, 2) == 0) {
eval[h++] = '|';
}
k = 4;
final = strtol(&rule[4], NULL, 10);
switch (rule[2]) {
case '>':
if (numbers[i] > final) eval[h++] = '1';
else eval[h++] = '0';
break;
case '<':
if (numbers[i] < final) eval[h++] = '1';
else eval[h++] = '0';
break;
case '=':
if (numbers[i] == final) eval[h++] = '1';
else eval[h++] = '0';
break;
default:
printf("error!\n");
}
}
// printf("%s\n", eval);
k = 1;
while (eval[k] != 0x00) {
if (eval[k] == '&') {
if (eval[k-1] == '1' && eval[k+1] == '1') {
eval[k] = '1';
} else {
eval[k-1] = '0';
eval[k] = '0';
eval[k+1] = '0';
}
}
k += 2;
}
k = 1;
while (eval[k] != 0x00) {
if (eval[k] == '|') {
if (eval[k-1] == '1' || eval[k+1] == '1') {
printf("%s", name);
goto ending;
}
}
k += 2;
}
k = 0;
while (eval[k] != 0x00) {
if (eval[k] == '0') break;
k++;
}
if (k == h) {
printf("%s", name);
goto ending;
}
}
printf("none");
ending:
if (i != numberCount-1) printf(",");
}
printf("\n");
}
int main(int argc, char ** argv)
{
int numbers[1024];
char numberBuffer[1024];
getInputLine(numberBuffer, 1024);
int numberCount = extractNumbersToArray(numberBuffer, numbers);
char buffers[1024][1024];
char *rules[1024];
int ruleCount = 0;
while(getInputLine(buffers[ruleCount], 1024) != NULL) {
rules[ruleCount++] = buffers[ruleCount];
}
determineRuleAndOutput(numbers, numberCount, rules, ruleCount);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment