Given a integer matrix of size m*n. We need to find a sub matrix with the largest sum.

#include
using namespace std;

#define MAX(a, b) (a>b ? a : b)
#define MIN(a, b) (a>b ? b : a)
int const maxn = 102;
int map[maxn][maxn], sum[maxn][maxn];
int n;

int read()
{
int i, j;
if(cin >> n)
{
for(i=1;i<=n;++i)
{
sum[i][0] = 0;
for(j=1;j<=n;++j)
{
cin >> map[i][j];
sum[i][j] = map[i][j] + sum[i][j-1];
}
}
return 1;
}
return 0;
}

void solve()
{
int i, j, k, sub_row, max[maxn], min[maxn], best;
best = 0;
for(i=1;i<=n;++i)
{
for(j=i;j<=n;++j)
{
sub_row = 0;
max[0] = 0;
min[0] = 100000;
for(k=1;k<=n;++k)
{
sub_row = sum[k][j] - sum[k][i];
max[k] = MAX(max[k-1], sub_row);
min[k] = MIN(min[k-1], sub_row);
}
best = MAX(max[n] - min[n], best);
}
}

cout << best << endl;
/*for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
cout << map[i][j] << " " << endl;*/
}

int main()
{
while(read()) solve();
return 0;
}

WAP for Square Matrix Rotation by 90 Degree

Method 1 (Using auxiliary Space of matrix size)

void rotate (Matrix m)
{
Matrix temp;
for(int i=0;i for(int j=0;j temp[i][j]=m[SIZE-j-1][i];

for(int i=0;i for(int j=0;j m[i][j]= temp [i][j];

}

void print (Matrix a)
{
for(int i=0;i {
for(int j=0;j cout< cout< }
cout<

}
This is the before and after output
/*Original square matrix:
11 22 33
44 55 66
77 88 99

Matrix now rotated 90
77 44 11
88 55 22
99 66 33*/

Time Complexity O(m*n)
Space Complexity O(n)




2nd Method In Place Matrix Rotation (Will Work Only For Square Matrix)

void rotate_matrix_90degree(int **m, int n)
{
int i, j;

// first mirror the matrix along the diagonal line.
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
int tmp = m[i][j];
m[i][j] = m[j][i];
m[j][i] = tmp;
}
}

// mirror the matrix horizontally. for Left Rotation
// and mirror the matrix vertically for right rotation

for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n; j++)
{
int tmp = m[j][i];
m[j][i] = m[j][n - i - 1];
m[j][n - i - 1] = tmp;
}
}
}

Time Complexity O(m*n)
Space Complexity O(1)

Please write comment if you find any thing wrong in this code or anything
missing

Write a program to add two long positive numbers (each represented by linked lists).

mynode *long_add(mynode *h1, mynode *h2, mynode *h3)
{
mynode *c, *c1, *c2;
int sum, carry, digit;

carry = 0;
c1 = h1->next;
c2 = h2->next;

while(c1 != h1 && c2 != h2)
{
sum = c1->value + c2->value + carry;
digit = sum % 10;
carry = sum / 10;

h3 = insertNode(digit, h3);

c1 = c1->next;
c2 = c2->next;
}

if(c1 != h1)
{
c = c1;
h = h1;
}
else
{
c = c2;
h = h2;
}

while(c != h)
{
sum = c->value + carry;
digit = sum % 10;
carry = sum / 10;
h3 = insertNode(digit, h3);
c = c->next;
}

if(carry==1)
{
h3 = insertNode(carry, h3);
}

return(h3);
}

WAP for Converting integer in to string it means you have to implement your own itoa function

I used to function here after storing string in to char* we have to reverse it to get desired output

#include
#include


void reverse(char *str,int len) {
int i=0;
char ch;
for(i=0;i<=(len-1)/2;i++) {
ch=str[i];
str[i]=str[len-1-i];
str[len-1-i]=ch;
}
}


char* itoa(int number) {
char *str=malloc(sizeof(char)*20);
int negFlag=0,pos=0;
if(number<0) {
negFlag=1;
number=-number;
}
while(number>0) {
str[pos++]='0'+number%10;
number=number/10;
}
if(negFlag) {
str[pos++]='-';
}
str[pos]='\0';
reverse(str,pos);
return str;
}


int main() {
printf("reverse %d : %s ",-543,itoa(-543));
printf("reverse %d : %s ",54,itoa(54));
printf("reverse %d : %s ",5,itoa(5));
}

WAP for Converting String in to Integer it means you have to implement your own atoi function

so Here we Go its Simple Logic

#include

int main(int argc, char* argv[])
{
printf("\n%d\n", myatoi("1998"));
getch();
return(0);
}

int myatoi(const char *string)
{
int i;
i=0;
while(*string)
{
i=(i<<3) + (i<<1) + (*string - '0');
string++;

//i am using left shift which is equals to multiply by pow(2,n) & shifting is fast then multiplication
// Don't increment i!

}
return(i);
}

Run Herehttps://ideone.com/XUKdL

Given a list of numbers and a number x, find two numbers in the list such that product of those 2 numbers is equal to x

import java.util.*;

class twonummulti_equalto_x
{

public static void main(String[] args)
{

int x = 21;
int[] arr = {4, 7, 3, 2, 4, 7, 6, 5, 2};

Set set = new HashSet ();
for (int i=0; i{
set.add(arr[i]);
}

Iterator itr = set.iterator();

while (itr.hasNext())
{
int i = itr.next();
int div = x/i;
int mod = x%i;
if (mod==0 && set.contains(div))
{
System.out.println(i+"x"+div+"="+x);
}

}

}


}

Find common sequence that is out of order between two given strings in Java

/*
Given two strings, find the longest common sequence that is out of order. Initially it was royally confusing to me what the question meant, but I was able to come up with a solution. Please see the following program implemented in Java. The sample inputs and outputs have been provided at the end.
*/
Hashing is Most Efficient Solution

import java.util.LinkedHashMap;
import java.util.Map;

public class Sequence {
public static void main(String[] args) {
Sequence seq = new Sequence();
String str1 = "a111b3455yy";
String str2 = "byy115789";
System.out.println("Input1: "+str1);
System.out.println("Input2: "+str2);
String solution = seq.findCommonSequnce(str1, str2);
System.out.println("Output: "+solution);
}

public String findCommonSequnce(String str1, String str2){
if(str1==null || str2==null){
return "";
}
if(str1.length() == 0 || str2.length() == 0){
return "";
}
//parse first String store the frequency of characters
//in a hashmap
Map firstStringMap = frequencyMap(str1);

StringBuilder output = new StringBuilder();

for(int i=0;i int count = 0;
if(firstStringMap.containsKey(str2.charAt(i)) && (count=firstStringMap.get(str2.charAt(i)))>0){
output.append(str2.charAt(i));
firstStringMap.put(str2.charAt(i), --count);
}
}

return output.toString();
}

/**
* Returns a map with character as the key and its occurence as the value
* @param str
* @return
*/
private Map frequencyMap(String str) {
Map freqMap = new LinkedHashMap();
for(int i=0;i Integer count = freqMap.get(str.charAt(i));
if(count==null){//means the frequency is yet to stored
freqMap.put(str.charAt(i), 1);
}else{
freqMap.put(str.charAt(i), ++count);
}
}
return freqMap;
}
}

//SAMPLE OUTPUTS
//Input1: a111b3455yy
//Input2: byy115789
//Output: byy115

Given a square matrix, write a program to print the items in zig zag diagonal order.

if Give Matrix is

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

So the output expected for the above example is,

1 -> 2 -> 6 -> 3 -> 7 -> 11 -> 4 -> 8 -> 12 -> 16 -> 5 -> 9 -> 13 -> 17 -> 21 -> 10 -> 14 -> 18 -> 22 -> 15 -> 19 -> 23 -> 20 -> 24 -> 25

Solution:

This program is a bit tricky and is very hard to solve immediately when asked in an interview. People who try to attack problems involving matrices always think they need at least two loops to arrive at the solution. But the surprise here is the problem can be solved in just a single loop with a very simple logic.




#include
using namespace std;

#define MAX 5

int main(){
int a[MAX][MAX] =
{{ 1, 2, 3, 4, 5},
{ 6, 7, 8, 9,10},
{11,12,13,14,15},
{16,17,18,19,20},
{21,22,23,24,25}};
int i=0,j=0;
while(i cout << a[i][j] << " -> ";
if(i==MAX-1){
i = j+1; j = MAX-1;
}
else if(j==0){
j = i+1; i = 0;
}
else{
i++; j--;
}
}
cout << endl;

return 0;
}

WAP for Quick Sort Algorithm

Data Structure used:Array

Algorithm:Divide & Conquer
1. Phase:Partition O(N) Time
2. Phase: Divide the array in two part Recursively & call partition function until we are run out of array O(nlogn)

Recursive Function Looks Like T(n)=2*T(n/2)+O(n)

Working Code:
public class QuickSort
{

public static int SIZE = 1000000;

public int[] sort(int[] input) {
quickSort(input, 0, input.length-1);
return input;
}

public static void main(String args[]){
int[] a = new int[SIZE];
for(int i=0;i pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
}
//Time taken to sort a million elements : 156 milliseconds

Time Complexity O(nlogn)
Space Complexity O(logn)
Run Here http://ideone.com/clone/ClBCZ

Complexity Analysis ( More Focus on Space )

very Few of us Know & are abale to come up space compelxity of quick sort if asked during the interview isn't it ?

Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that

* in-place partitioning is used. This requires O(1).
* After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(logn) space. Then the other partition is sorted using tail-recursion or iteration.

The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(logn) nested recursive calls, it uses O(logn) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space.

However, if we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes O(logn) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires O(log2n) bits of space in the best and average case and O(nlogn) space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy O(nlogn) bits of space.

WAP to Implement Merge Sort Algorithm

public class MergeSortOptimized{

public static int SIZE = 1000000;

public static void main(String args[]){
int[] a = new int[SIZE];
for(int i=0;ia[i] = (int)(Math.random()*SIZE);
}
long start = System.currentTimeMillis();
MergeSortOptimized mNew = new MergeSortOptimized();
mNew.sort(a);
long end = System.currentTimeMillis();
System.out.println("Time taken to sort a million elements : "+(end-start)+" milliseconds");
}

public int[] sort(int[] input){
int[] temp = new int[input.length];
mergeSort(input, temp, 0, input.length-1);
return input;
}

public void mergeSort(int[] fromArray, int[] toArray, int left, int right){
if(leftint center = (left+right)/2;
mergeSort(fromArray, toArray, left, center);
mergeSort(fromArray, toArray, center+1, right);
merge(fromArray, toArray, left, center+1, right);
}
}

public void merge(int[] fromArray, int[] toArray, int leftPos, int rightPos, int rightEnd){
int leftEnd = rightPos - 1;
int tempPos = leftPos;

int numElements = rightEnd - leftPos + 1;

while(leftPos<=leftEnd && rightPos<=rightEnd){
if(fromArray[leftPos]toArray[tempPos++] = fromArray[leftPos++];
}else{
toArray[tempPos++] = fromArray[rightPos++];
}
}

while(leftPos<=leftEnd){
toArray[tempPos++] = fromArray[leftPos++];
}
while(rightPos<=rightEnd){
toArray[tempPos++] = fromArray[rightPos++];
}

for(int i=0;ifromArray[rightEnd] = toArray[rightEnd];
}

}

}
//Time taken to sort a million elements : 247 milliseconds

Some Quick Sort Implementation http://www.algolist.net/Algorithms/Sorting/Quicksort
http://scanftree.com/Data_Structure/Quick-Sort