Sunday, November 17, 2013

Very nice iOS Development Resources

Blog which shows how to draw graphs in Objective-C:

http://www.sitepoint.com/creating-a-graph-with-quartz-2d/

Blog which shows database operations using SQLite library in iOS:

http://www.tutorialspoint.com/ios/ios_sqlite_database.htm

Steps to port an iPhone application to work on iPad:

http://www.raywenderlich.com/1111

Blog which shows the implementation of UICollectionViewController

http://nscookbook.com/2013/02/ios-programming-recipe-14-implementing-a-uicollectionviewcontroller/

Sunday, November 3, 2013

Important links for beginning development of iOS Applications

A blog giving full details of running an app on a device:

http://www.raywenderlich.com/8003/how-to-submit-your-app-to-apple-from-no-account-to-app-store-part-1
http://www.raywenderlich.com/8045/how-to-submit-your-app-to-apple-from-no-account-to-app-store-part-2
http://www.raywenderlich.com/8045/

It is possible to get an app running on a device before actually submitting it for approval.

Another blog showing how to get an app running on a real device:
http://docs.appcelerator.com/titanium/2.0/#!/guide/Deploying_to_iOS_devices

Another blog for the steps to follow:
http://mobile.tutsplus.com/tutorials/iphone/how-to-test-your-apps-on-physical-ios-devices/

Blog which gives the steps to test iOS apps on jail-broken devices:
http://techtalktone.wordpress.com/2011/12/05/testing-your-ios-apps-on-a-jailbroken-device-2/

Wednesday, September 25, 2013

Pattern matching in a two dimensional matrix

Problem:
You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.
Java Program:
public class Matrix {
private static boolean[][] visited;
private char[][] grid = {{'a','i','b'},
{'m','b','c'},
{'g','r','i'},
{'o','o','t'},
{'s','f','m'}};
private String searchString = "microsoft";
public static void main(String[] args) {
Matrix gridObject = new Matrix();
gridObject.initialize(gridObject.grid.length, gridObject.grid[0].length);
boolean result = false;
for (int i = 0; i < gridObject.grid.length; i++) {
for(int j = 0; j < gridObject.grid[i].length; j++) {
result = gridObject.traverseAndFind(gridObject.grid, i, j, gridObject.searchString, 0);
if(result) {
break;
}
}
if(result) {
break;
}
}
if(result) {
System.out.println("The string is present in the grid");
}
else {
System.out.println("The string is not present in the grid");
}
}
//Function to do all the primary initialization.
public void initialize(int x, int y) {
visited = new boolean[x][y];
}

public boolean traverseAndFind(char[][] inputGrid, int r, int c, String inputString, int index) {
if(index == inputString.length()) {
return true;
}
else if(r >= 0 && r < inputGrid.length && c >= 0 && c < inputGrid[r].length
&& !visited[r][c] && inputGrid[r][c] == inputString.charAt(index)) {
visited[r][c] = true;
return (traverseAndFind(inputGrid, r, c + 1, inputString, index + 1)) ||
traverseAndFind(inputGrid, r + 1, c + 1, inputString, index + 1) ||
traverseAndFind(inputGrid, r + 1, c, inputString, index + 1) ||
traverseAndFind(inputGrid, r + 1, c - 1, inputString, index + 1) ||
traverseAndFind(inputGrid, r, c - 1, inputString, index + 1) ||
traverseAndFind(inputGrid, r - 1, c - 1, inputString, index + 1) ||
traverseAndFind(inputGrid, r - 1, c, inputString, index + 1) ||
traverseAndFind(inputGrid, r - 1, c + 1, inputString, index + 1);
}
else if(r >= 0 && r < inputGrid.length && c >= 0 && c < inputGrid[r].length) {
visited[r][c] = false;
}
return false;
}
}

Tuesday, September 24, 2013

[Fox and Rabbit Problem]: How many rabbits can the fox eat

Problem:
Given a grid, the coordinates of a fox and the coordinates of the rabbits, find out the number of rabbits that the fox can eat.
Condition:
The fox can only eat rabbits which are in its own row, own column or in any of the diagonals.
Example configuration:

Grid

Java Code

import java.util.ArrayList;
import java.util.List;

class Coordinate {
Integer x;
Integer y;
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
public String toString() {
return "(" + this.x.toString() + "," + this.y.toString() + ").";
}
}

public class Fox {
private static final String prefixEatString = "Fox can eat the rabbit at: ";
private static final String prefixCannotEatString = "Fox cannot eat the rabbit at: ";
private static final String prefixTotalEatableString = "In all the fox can eat ";
private static final String suffixTotalEatableString = " rabbits.";
public static void main(String[] args) {
Coordinate foxCoordinates = new Coordinate(0,0);
List rabbitCoordinates = new ArrayList();
//Initialize the coordinates of the rabbits.
for (int i =-2; i <= 2; i++) {
for (int j =-2; j <= 2; j++) {
if(foxCoordinates.getX() == i && foxCoordinates.getY() == j) {
continue;
}
rabbitCoordinates.add(new Coordinate(i, j));
}
}
int foodCount = 0;
for (int i=0; i<rabbitCoordinates.size(); i++) {
int diffX = foxCoordinates.getX() - rabbitCoordinates.get(i).getX();
int diffY = foxCoordinates.getY() - rabbitCoordinates.get(i).getY();
if (diffX == 0) {
foodCount++;
System.out.println(prefixEatString + rabbitCoordinates.get(i).toString());
}
else if (diffY == 0) {
foodCount++;
System.out.println(prefixEatString + rabbitCoordinates.get(i).toString());
}
else if (diffY/diffX == 1 || diffY/diffX == -1) {
foodCount++;
System.out.println(prefixEatString + rabbitCoordinates.get(i).toString());
}
else {
System.out.println(prefixCannotEatString + rabbitCoordinates.get(i).toString());
}
}
System.out.println(prefixTotalEatableString + foodCount + suffixTotalEatableString);
}
}
Output:
Fox can eat the rabbit at: (-2,-2).
Fox cannot eat the rabbit at: (-2,-1).
Fox can eat the rabbit at: (-2,0).
Fox cannot eat the rabbit at: (-2,1).
Fox can eat the rabbit at: (-2,2).
Fox cannot eat the rabbit at: (-1,-2).
Fox can eat the rabbit at: (-1,-1).
Fox can eat the rabbit at: (-1,0).
Fox can eat the rabbit at: (-1,1).
Fox cannot eat the rabbit at: (-1,2).
Fox can eat the rabbit at: (0,-2).
Fox can eat the rabbit at: (0,-1).
Fox can eat the rabbit at: (0,1).
Fox can eat the rabbit at: (0,2).
Fox cannot eat the rabbit at: (1,-2).
Fox can eat the rabbit at: (1,-1).
Fox can eat the rabbit at: (1,0).
Fox can eat the rabbit at: (1,1).
Fox cannot eat the rabbit at: (1,2).
Fox can eat the rabbit at: (2,-2).
Fox cannot eat the rabbit at: (2,-1).
Fox can eat the rabbit at: (2,0).
Fox cannot eat the rabbit at: (2,1).
Fox can eat the rabbit at: (2,2).
In all the fox can eat 16 rabbits.

Monday, September 16, 2013

Recursive program to find the number of ways a particular amount can be obtained using a given set of Currency values.


public class Coins {
private static int count = 0;
public static void main(String[] args) {
int[][] currencyList = {{5,10,20},{0,0,0}};
//The first row contains the list of the currency values available.
//The second row contains the frequency of each currency value.
//The number of columns in both the rows should be the same.
//Else an index-out-of-bounds exception will happen.
int sum=0;
int amount = 20;
int index=0;
computeCombinations(currencyList, sum, amount, index);
System.out.println("Total possible combinations: "+ Coins.count);
}

public static void computeCombinations(int[][] currencyList, int sum, int amount, int index) {
if(index >= currencyList[0].length) {
return;
}
else {
for(int i=0; i<=(amount/currencyList[0][index]);i++) {
currencyList[1][index]=i;
sum+=currencyList[0][index]*currencyList[1][index];
if(sum == amount) {
count++;
for(int j=0;j <=index; j++) {
if(currencyList[1][j] != 0) {
System.out.print(currencyList[0][j] + "-->" + currencyList[1][j] + " ");
}
}
System.out.println();
}
else {
computeCombinations(currencyList, sum, amount, index + 1);
sum-=currencyList[0][index]*currencyList[1][index];
}
}
}
}
}
Output:
20-->1
10-->2
5-->2 10-->1
5-->4
Total possible combinations: 4

Sunday, May 5, 2013

Rotate a 2-D matrix by 90° counter-clockwise


#include<iostream>
using namespace std;
int main()
{
int n,A[100][100];
cout<<"Enter the dimension of the square matrix:"<<endl;
cin>>n;
cout<<"Enter the elements:"<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>A[i][j];
}
}
for(int i=0;i<n/2;i++)
{
for(int j=i;j<n-1-i;j++)
{
int t=A[i][j];
A[i][j]=A[j][n-1-i];
A[j][n-1-i]=A[n-1-i][n-1-j];
A[n-1-i][n-1-j]=A[n-1-j][i];
A[n-1-j][i]=t;
}
}
cout<<"The counter-clockwise rotated matrix is:"<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<A[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
Output:
Enter the dimension of the square matrix: 4
Enter the elements:
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
The counter-clockwise rotated matrix is:
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

Sunday, April 28, 2013

Given a binary tree output should have the node values as sum of all the children data and its node data

Input tree:                  Output tree:
Untitled
C++ Program:

#include<iostream>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
return new_node;
}

void postorder(struct node* root)
{
if(root)
{
postorder(root->left);
postorder(root->right);
if(root->left)
{
root->data=root->data+root->left->data;
}
if(root->right)
{
root->data=root->data+root->right->data;
}
}
}

int height(struct node* root)
{
if(root==NULL)
{
return 0;
}
else
{
int lheight=1+height(root->left);
int rheight=1+height(root->right);
return lheight>rheight?lheight:rheight;
}
}

void levelorderprint(struct node* root,int level)
{
if(root && level==0)
{
cout<<root->data<<" ";
}
else if(root)
{
levelorderprint(root->left,level-1);
levelorderprint(root->right,level-1);
}
}

void levelorder(struct node* root)
{
int h=height(root);
for(int i=0;i<h;i++)
{
levelorderprint(root,i);
cout<<endl;
}
}

int main()
{
struct node* root1=createnode(1);
root1->left=createnode(2);
root1->right=createnode(3);
root1->left->right=createnode(5);
root1->left->left=createnode(4);
root1->right->right=createnode(7);
root1->right->left=createnode(6);
//root1->right->right->left=createnode(8);
cout<<"The input tree is:\n";
levelorder(root1);
postorder(root1);
cout<<"The sum tree is\n";
levelorder(root1);
}
Output:
The input tree is:
1
2 3
4 5 6 7
The sum tree is
28
11 16
4 5 6 7

Process returned 0 (0x0) execution time : 0.016 s
Press any key to continue.

Right Neighbour of nodes in a Binary Tree

Given a binary tree with nodes that have left, right pointers pointing to the left and right children respoectively. Each node also has a right-neighbor pointer that currently points to null.
Write a function to make it point to its neighbor.

Example:
Input tree
1
2 3
4 5 6 7
Expected configuration of the tree
1 right-neighbour should point to null
2 right-neighbour should point to 3
3 right-neighbour should point to null
4 right-neighbour should point to 5
5 right-neighbour should point to 6
6 right-neighbour should point to 7
7 right-neighbour should point to null

Approach
1. Do a level-order traversal of the binary tree.
2. During this traversal keep track of the current root you visit in a level.
3. The next time you visit a root in the same level, make the right-neighbour pointer of the current root to point to this root.
4. Update the current pointer to this root.

#include<iostream>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
struct node* right_neighbour;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
new_node->right_neighbour=NULL;
return new_node;
}

int height(struct node* root)
{
if(root==NULL)
{
return 0;
}
else
{
int lheight=1+height(root->left);
int rheight=1+height(root->right);
return lheight>rheight?lheight:rheight;
}
}

void levelorderprint(struct node* root,int level,struct node** current)
{
if(root && level==0)
{
cout<<root->data<<" ";
if(*current == NULL)
{
*current = root;
}
else
{
(*current)->right_neighbour=root;
*current=root;
}
}
else if(root)
{
levelorderprint(root->left,level-1,current);
levelorderprint(root->right,level-1,current);
}
}
void levelorder(struct node* root)
{
int h=height(root);
struct node* addr=NULL;
struct node** current=&addr;
for(int i=0;i<h;i++)
{
addr=NULL;//Very important step because addr gets changed in the function levelorderprint as its address is passed.
current=&addr;
levelorderprint(root,i,current);
cout<<endl;
}
}

void inorder(struct node* root)
{
if(root)
{
inorder(root->left);
cout<<root->data;
if(!root->right_neighbour)
{
cout<<endl;
}
else
{
cout<<"->"<<root->right_neighbour->data<<endl;
}
inorder(root->right);
}
}

int main()
{
struct node* root1=createnode(1);
root1->left=createnode(2);
root1->right=createnode(3);
root1->left->right=createnode(5);
root1->left->left=createnode(4);
root1->right->right=createnode(7);
root1->right->left=createnode(6);
root1->right->right->left=createnode(8);
cout<<"The input tree is\n";
levelorder(root1);
cout<<"The right neighbours are:\n";
inorder(root1);
}
Output:
1
2 3
4 5 6 7
8
The right neighbours are:
4->5
2->3
5->6
1
6->7
3
8
7

Process returned 0 (0x0)   execution time : 0.056 s
Press any key to continue.

Sunday, March 17, 2013

Gambling game

In a game, you bet using the following strategy. Whenever you lose a bet, you double the value of the bet for the next round. Whenever you win, the bet for the next round will be one dollar. You start the round by betting one dollar.

For example, if you start with 20 dollars, and you win the bet in the first round, lose the bet in the next two rounds and then win the bet in the fourth round, you will end up with 20+1-1-2+4 = 22 dollars.

You are expected to complete the function, getFinalAmount, which takes two arguments. The first argument is an integer initialAmount which is the initial money we amount we have when we start the betting. The second argument is a string betResultsThe ith character of outcome will be either 'W' (win) or 'L' (lose), denoting the result of the ith round.
Your function should return the amount of money you will have after all the rounds are played. If at some point you don't have enough money in your account to cover the value of the bet, you must stop and return the sum you have at that point.

Sample Test Cases:

Input #00:
12
WWWWWWWW

Output #00:
20

Explanation:
The initial amount is 12, for every win, you gain 1 dollar.
There are totally 8 consecutive wins and no losses, hence total money gained = 12 + 8 = 20

Input #01:
15
LLLWLLLL

Output #01:
1

Explanation:
The initial amount is 15. As stated in the problem, the amount of bet doubles for every loss.
1st round - Loss: 15-1 = 14
2nd round - Loss: 14-2 = 12 (Bet doubles)
3rd round - Loss: 12-4 = 8
4th round - Win: 8 + 8 = 16
5th round - Loss:16-1 = 15 (Since the previous bet was a win, this bet has a value of 1 dollar)
6th round - Loss: 15-2 = 13
7th round - Loss: 13-4 = 9
8th round - Loss: 9-8 = 1

#include<iostream>
#include<string.h>
using namespace std;
int getFinalAmount(int init,char result[100])
{
int amt=1;
for(int i=0;i<strlen(result);i++)
{
if(result[i]=='W' || result[i]=='w')
{
if(init < amt)
{
return init;
}
init+=amt;
amt=1;
}
else if(result[i]=='L' || result[i]=='l')
{
if(init < amt)
{
return init;
}
init-=amt;
amt*=2;
}
}
return init;
}
int main()
{
int T;
int win,lose,init;
char result[100];
cin>>T;
while(T--)
{
cin>>init;
cin>>result;
cout<<getFinalAmount(init,result)<<endl;
}
}
Input:
2
12
WWWWWWWW
15
LLLWLLLL

Output:
20
1

Thursday, February 14, 2013

Number-to-Alphabet Decoding System


Problem
There is a coding system where all the letters in an Alphabet is coded into a number such as a-->1, b-->2,..., z-->26. Given an array of the integers, the program should output the number of possible letter arrangements in the decoded string.
C++ Program
#include<iostream>
using namespace std;
#define SIZE 4
int getCount(int A[SIZE],int s)
{
if(s>=SIZE - 1)
{
return 1;
}
else
{
if(A[s]*10 + A[s+1] <= 26)
{
return getCount(A,s+1) + getCount(A,s+2);
}
else if(A[s] <= 26)
{
return getCount(A,s+1);
}
else
{
return 0;
}
}
}
int main()
{
//int A[SIZE]={1,2,6,1,2,4};
int A[SIZE]={1,1,2,3};
int s=0;
cout<<"Recursive: "<<getCount(A,s)<<endl;
int a=1;
int b=1;
int ans=a;
int n=SIZE;
if(10*A[n-2]+A[n-1] <= 26)
{
a=2;
}
for(int i=n-3; i>=0; i--)
{
if(10*A[i]+A[i+1] <= 26)
{
ans=a+b;
b=a;
a=ans;
}
else
{
ans=a;
b=a;
}
}
cout<<"Dynamic Programming: "<<ans<<endl;
}
Output
Recursive: 5
Dynamic Programming: 5

Process returned 0 (0x0) execution time : 0.018 s
Press any key to continue.

Thursday, January 17, 2013

C++ program for jumps problem

Given an array of positive numbers, find the number of ways to reach the end of the array in minimum number of steps where the value at each index represents the maximum number of steps one can move.
Sample Input:
The first line contains a number n, the number of elements in the array. The second line contains n space separated numbers.
11
1 3 5 8 9 2 6 7 6 8 9
Sample Output
Output should contain n space separated numbers, each represents the number of ways at that index.
2 2 4 1 1 2 1 1 1 1 0
#include<iostream>
using namespace std;
int main()
{
int n,A[100];
cin>>n;
int max=-9999999;
for(int i=0;i<n;i++)
{
cin>>A[i];
if(A[i]>max)
{
max=A[i];
}
}
//cout<<max<<endl;
cout<<"The given array is:\n";
for(int i=0;i<n;i++)
{
cout<<A[i]<<" ";
}
cout<<endl;
int B[100]={0};
for(int i=0;i<n-1;i++)
{
B[i]=A[i];
}
for(int i=n-2;i>=0;i--)
{
if(i+A[i] >= n-1)
{
B[i]=1;
}
else
{
int min=max;
bool inside = false;
for(int j=i+A[i];j>i;j--)
{
if(B[j]!=0 && B[j]<=min)
{
min=B[j];
inside = true;
}
}
if(inside)
{
B[i]=min+1;
}
}
}
cout<<"The distance array is:\n";
for(int i=0;i<n;i++)
{
cout<<B[i]<<" ";
}
cout<<endl;
int num[100]={0};
for(int i=n-2;i>=0;i--)
{
if(B[i]==1)
{
num[i]=B[i];
}
else
{
for(int j=1;i+j<n && j<=A[i];j++)
{
if(B[i+j]==B[i]-1)
{
//cout<<i<<" "<<B[i]<<" "<<j<<endl;
num[i]+=num[i+j];
}
}
}
}
cout<<"Number of ways:\n";
for(int i=0;i<n;i++)
{
cout<<num[i]<<" ";
}
cout<<endl;
}
11
1 3 5 8 9 2 6 7 6 8 9
The given array is:
1 3 5 8 9 2 6 7 6 8 9
The distance array is:
3 2 2 1 1 2 1 1 1 1 0
Number of ways:
2 2 4 1 1 2 1 1 1 1 0

Saturday, January 12, 2013

C++ program to find all the possible interleavings of two input strings


#include<iostream>
#include<string.h>
#include<map>
using namespace std;
map<string,bool> myMap;
void generateInterleaved(char A[100],char B[100],char out[200],int start1,int start2)
{
if(strlen(out)==strlen(A)+strlen(B))
{
if(myMap.find(out) == myMap.end())
{
myMap[out]=true;
}
return;
}
else
{
if(start1<strlen(A))
{
out[strlen(out)]=A[start1];
generateInterleaved(A,B,out,start1+1,start2);
out[strlen(out)-1]=0;
}
if(start2<strlen(B))
{
out[strlen(out)]=B[start2];
generateInterleaved(A,B,out,start1,start2+1);
out[strlen(out)-1]=0;
}
}
}
int main()
{
char A[100],B[100],C[100];
bool isInterleaved(char[],char[],char[]);
cin>>A>>B>>C;
bool result=isInterleaved(A,B,C);
if(result==true)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
char out[200]={0};
cout<<"The possible interleavings are:\n";
generateInterleaved(A,B,out,0,0);
for(map<string,bool>::iterator it = myMap.begin();it != myMap.end(); ++it)
{
cout<<it->first<<endl;
}
}
bool isInterleaved(char A[100],char B[100],char C[100])
{
int j=0,k=0;
for(int i=0;i<strlen(C);i++)
{
if(j<strlen(A) && C[i]==A[j])
{
j++;
}
else if(k<strlen(B) && C[i]==B[k])
{
k++;
}
}
if(j==strlen(A) && k==strlen(B))
{
return true;
}
else
{
return false;
}
}
Input:
ab
cd
Output:
ab
cd
abcd
YES
The possible interleavings are:
abcd
acbd
acdb
cabd
cadb
cdab