Question: There is an ant which can walk around on a planar grid. The ant can move one space at a time left, right, up or down. That is, from (x, y) the ant can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the x coordinate plus the sum of the digits of the y coordinate are greater than 25 are inaccessible to the ant. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25. How many points can the ant access if it starts at (1000, 1000), including (1000, 1000) itself?
Answer:
If we look at the question carefully ant can move only in the increasing fashion of x and y. Because if it tries to reduce initial x or y (1000,1000) in both cases the sum of digits will become more than 25. e.g 1000-1=999(9+9+9=27).
So ant can only increase x and y and it can not decrease x and y (1000,1000). the will be only in the positive area of x and y coordinates. In this manner if we increase X coordinate with Y fixed at 1000. we will see that ant can move up to (1698,1000). Now we can follow a staircase pattern from here by decreasing X by 1 and increasing Y by 1. But then we will get a loop hole at (1689, 1009). So we need to set y as 1000 again at X = 1689. Following the staircase pattern, same problem will happen again at (1599, 1090), so we need to set Y as 1000 again at X = 1599. The final graph will be as given below.
Total number of points will be:
600*601/2 + 2*90*91/2 + 2*9*10/2 = 188580
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Ant's travel in a grid
Convert IP address from string to Int
Question: Network ip address is given in string form; read that, parse that from left to right; push into integer. 4 parts of ip, each part can be stored in one byte.
Example:
i/p: 172.12.13.14
o/p: 0xCA0C0D0E (0xCA = 172, 0x0C = 12, 0x0D = 13, 0x0E = 14)
Code:
#include<iostream>
using namespace std;
main()
{
char in[20];
int out,i, tmp;
cout <<"enter ip string: " << endl;
cin >> in;
int len = strlen(in);
int place = 3;
out = tmp = 0;
for (i=0; i<len ; i++)
{
if(in[i] == '.')
{
out += tmp << (8*place--);
tmp = 0;
continue;
}
tmp = tmp*10 + in[i] - '0';
}
out = out + tmp;
cout << "IP address is: " << hex << out << endl;
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Convert an Roman integer in decimal
Question: Convert an roman integer in its decimal equivalent.
Code:
//Assumption: only valid string containing following Roman numerlas are entered.
// MDCLXVI
#include<iostream>
#include<string.h>
using namespace std;
main()
{
char in[10], outn[100];
long int out=0;
cout << "Enter Roman String (Characters allowed are M,D,C,L,X,V,I) : "<<endl;
cin >> in;
int len = strlen(in);
int i = 0;
int lastval = 1000;
while(in[i] != '\0')
{
switch (in[i])
{
case 'M':
case 'm':
out = out + 1000;
if (lastval < 1000)
out = out - 2*lastval;
lastval = 1000;
break;
case 'D':
case 'd':
out = out + 500;
if (lastval < 500)
out = out - 2*lastval;
lastval = 500;
break;
case 'C':
case 'c':
out = out + 100;
if (lastval < 100)
out = out - 2*lastval;
lastval = 100;
break;
case 'L':
case 'l':
out = out + 50;
if (lastval < 50)
out = out - 2*lastval;
lastval = 50;
break;
case 'X':
case 'x':
out = out + 10;
if (lastval < 10)
out = out - 2*lastval;
lastval = 10;
break;
case 'V':
case 'v':
out = out + 5;
if (lastval < 5)
out = out - 2*lastval;
lastval = 5;
break;
case 'I':
case 'i':
out = out + 1;
if (lastval < 1)
out = out - 2*lastval;
lastval = 1;
break;
default:
cout << "Invalid Input" <<endl;
break;
}
i++;
}
cout << "Decimal Equivalent = " << out <<endl;
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Reverse an integer array
Problem: Reverse an integer array bitwise algorithm
Example:
i/p : A[]{1,2,3,4,5}
o/p: A[]{5,4,3,2,1}
Process:
//1. Declare Assumptions
//2. Explain algo
//3. take an Example
//4. give testcases
//5. 1st write the solution
//6. then add exception handels and try/catch/finally blocks
//7. Order
ALGO:
//check for even or odd
//using a swap method swap using XOR swap
TEST CASES:
//Functional:
//1. empty array
//2. odd/even array
//3. negative numbers
//4. large numbers[32767]
//5. characters
Non-Functional:
Performance
//1. same array used multiple time test for time complexity
//Memory
//2. same array tested for multiple time test for memory leakage
//Security
//3. test with array having escape characters
//4. test with array have special char or ASCII values
//Stress
//6. run multiple instance of the method and test for stress
Load
//7. test with very large array
//Globalisation/localisation
//8. test with unicode char
//9. test with kanji char
//10. test with mix of both characters
CodeCoverage
Exception Handelling
//11. test whether exceptions are handelled.
TEST HARNESS:
using System;CODE:
namespace problem
{
public class answer
{
static void Main()
{
int[] A=new int[5]{1,2,3,4,5};
bitreverse(A);
Console.ReadLine();
}
public static void bitreverse(int[] A)
{
try
{
int j=A.Length-1;
for (int i=0; j>i; i++, j--)
{
A[i]=A[i]^A[j];
A[j]=A[i]^A[j];
A[i]=A[j]^A[i];
}
}
catch(Exception ex)
{
Console.WriteLine(ex);
}
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Link List Reversal
Question: WAP to reverse a linklist non-recursively.
Answer:
void reverse (struct list **list1)
{
struct list *next, *cur, *tmp;
cur = *list1;
tmp=0;
if (!list1)
return;
while(cur)
{
next = cur->next;
cur->next=tmp;
tmp = cur;
cur = next;
}
*list1 = tmp;
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Find us on Facebook
I write about
- Algorithm (31)
- Amazon EC2 (3)
- Amazon Interview (9)
- Amazon S3 (5)
- Amazon SimpleDB (5)
- Amazon SQS (1)
- Architecture (3)
- Arrays/Strings (32)
- backtracking (1)
- Brain Teasers (8)
- C++ (3)
- Cloud Computing (14)
- Design Pattern (2)
- Dynamic programming (11)
- Facebook Interview (3)
- General (14)
- Git (2)
- Google Interview (6)
- Humour (1)
- Interviews (7)
- Link List (8)
- Mac (2)
- Mathematics (3)
- MIcrosoft Interview (4)
- Miscellany (1)
- python (3)
- queue (1)
- Ruby (9)
- tree (19)
- web development (1)