Explain Shell Sort & WAP For It

The basic idea of this sorting algorithm, which was invented in 1959 by D. L. Shell, is that in early stages, far-apart elements are compared, rather than adjacent ones as in simpler interchange sorts. This tends to eliminate large amounts of disorder quickly, so later stages have less work to do. The interval between comparedelements is gradually decreased to one, at which point the sort effectively becomes an adjacentinterchange method.

/* shellsort: sort v[0]...v[n-1] into increasing order */


void shellsort(int v[], int n)
{
int gap, i, j, temp;

for (gap = n/2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap)
{
temp = v[j];
v[j] = v[j+gap];
v[j+gap] = temp;
}
}

int main()

{

int a[]={3,1,2,5,4};
shellsort(a,5);
int i=0;

for (i =0; i < 5; i++)
printf("%d ",a[i]);

return 0;
}






There are three nested loops. The outermost controls the gap between compared elements, shrinking it
from n/2 by a factor of two each pass until it becomes zero. The middle loop steps along the elements.
The innermost loop compares each pair of elements that is separated by gap and reverses any that are
out of order. Since gap is eventually reduced to one, all elements are eventually ordered correctly.

More Info http://en.wikipedia.org/wiki/Shell_sort

WAP to Do Clone of Tree e.g Mirror Tree

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)

{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Change a tree so that the roles of the left and
right pointers are swapped at every node.

So the tree...
4
/ \
2 5
/ \
1 3

is changed to...
4
/ \
5 2
/ \
3 1
*/
struct node* copy(struct node *root)
{
struct node *temp;

if(root==NULL)return(NULL);

temp = (struct node *) malloc(sizeof(struct node ));
temp->data= root->data;

temp->left = copy(root->left);
temp->right = copy(root->right);

return(temp);
}





/* Helper function to test mirror(). Given a binary
search tree, print out its data elements in
increasing sorted order.*/
void inOrder(struct node* node)
{
if (node == NULL)
return;

inOrder(node->left);
printf("%d ", node->data);

inOrder(node->right);
}

/* Driver program to test mirror() */
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

/* Print inorder traversal of the input tree */
printf("\n Inorder traversal of the constructed tree is \n");
inOrder(root);

/* Convert tree to its mirror */
root=copy(root);

/* Print inorder traversal of the mirror tree */
printf("\n Inorder traversal of the mirror tree is \n");
inOrder(root);

getchar();
return 0;
}

WAP to Find path in a tree represented with NXN array

I have an MST(anyway a tree..) represented with a NXN array.
I want to find the path between 2 nodes source, destination (or sensor, sink in WSN).


/*
given a MST graph[N][N]
we find the path from a node to the root
*/
#include
#define N 4

int main(){
int graph[N][N]={{0,1,1,0},
{1,0,0,1},
{1,0,0,0},
{0,1,0,0},
};
int leaves[N];
int i,j;
int count;
//initialize
for( i=0; i //find which nodes are leaves
for(i=0; i count=0;
for( j=0; j if (graph[i][j]==1) count++;
if (count>1) {leaves[i]=0;break;}
}
}
for( i=0;i printf("%d ",leaves[i]);
printf("\n");

int path[N];
for( i=0;i path[i]=-1;
int path_index=0;
int a=3,sink=0;//two nodes
int cur=a;
path[path_index]=a;
path_index++;
int parent=-1;
while(parent!=sink){//while destination not found
printf("parent=%d",parent);getchar();printf("\ncur: %d",cur);getchar();
for(j=0;j {
if (graph[cur][j]==1 && leaves[cur]==1){
parent=j;path[path_index]=parent;path_index++;
if (parent==sink) break;
printf("\ncur: %d",cur);getchar();
printf("parent: %d ",parent);
}
if (graph[cur][j]==1&& !(leaves[j])){
parent=j;path[path_index]=parent;path_index++;
if (parent==sink) break;
printf("\ncur: %d",cur);getchar();
printf("parent: %d ",parent);
}

}
cur=parent;

}
for(i=0;i if (path[i]!=sink) printf("%d--> ",path[i]);
else break;
}

getchar();
return 0;
}

WAP to WildCard Patern Matching

Write pattern matching algorithm i.e isMatch(String,Pattern)
Pattern can have ?(one character) and *(many characters). ex. abbdef and a?b*f are a match aaabab and a*ba are not a match


#include
using namespace std;
//check regexp against text recursively
bool match(char *regexp, char *text){
// the case regexp is empty, we don't need to check text == '\0'
if (*regexp == '\0') return (*text == '\0');
// the case ? and normal characters
if (*regexp == '?'||*regexp == *text) return match(regexp+1,text+1);
// the case *
if (*regexp=='*'){
do{
if (match(regexp+1,text)) return true;
}while (*text++!='\0');
}
return false;
}

int main(){
char p[4]={'a','*','d'};
char s[4] = {'a','c','b'};
bool k=match(p,s);
if(k) cout<<"yes";
else cout<<"no";
return 0;
}

WAP to Factorial of Very Big Number

Source - Algoseekar (Developer)
https://github.com/algoseeker/Interview/blob/b8b1aac7b133beb94637e17deea578ae29948271/factorial/Decimal.java



import java.lang.String;
import java.lang.StringBuilder;
import java.io.Console;

public class Decimal{
protected String number;

public Decimal(String s){
int i;
for(i=0;iif(s.charAt(i)!='0')
break;
}
this.number = s.substring(i,s.length());
}
public void add(Decimal anum){
this.number = Decimal.add(this,anum);
}
public void multiply(Decimal anum){
number = Decimal.multiply(this, anum).getNum();
}

public static Decimal multiply(Decimal num, Decimal num2){
Decimal greater;
Decimal smaller;
if(num.size()>=num2.size()){
greater = num;
smaller = num2;
} else{
greater = num2;
smaller = num;
}
StringBuilder ans = new StringBuilder();
String s1 = greater.getNum();
String s2 = smaller.getNum();
Decimal b = new Decimal("0");

for(int i=smaller.size()-1;i>=0;i--){
if(s2.charAt(i)!='0'){
String s = Decimal.multiply(s1,s2.charAt(i)-'0');
Decimal temp = new Decimal(Decimal.padZeroes(s,(smaller.size()-i-1)));
b.add(temp);
}
}
return b;
}

public static String multiply(String s, int single_digit){
int carry=0;
StringBuilder ans = new StringBuilder();
for(int i=s.length()-1;i>=0;i--){
int n = s.charAt(i) - '0';
int result = n * single_digit + carry;
carry = result/10;
ans.append(result%10);
}
if(carry!=0){
ans.append(carry);
}
return ans.reverse().toString();
}

public static String padZeroes(String s, int nzeroes){
StringBuilder ans = new StringBuilder(s);
for(int i=0;ians.append('0');
return ans.toString();
}

public static String add(Decimal num, Decimal num2){
Decimal greater;
Decimal smaller;
if(num.size()>=num2.size()){
greater = num;
smaller = num2;
} else{
greater = num2;
smaller = num;
}
int carry = 0;
int i= greater.size()-1;
String s1 = greater.getNum();
String s2 = smaller.getNum();
StringBuilder ans = new StringBuilder();
for(int j=smaller.size()-1;j>=0;j--,i--){
int digit1 = s1.charAt(i) - '0';
int digit2 = s2.charAt(j) - '0';
int result = digit1 + digit2 + carry;
carry = result/10;
ans.append(result%10);
}

// Adding the carry over left after adding smaller number
while(i>=0){
int n = s1.charAt(i) - '0';
int result = n + carry;
ans.append(result%10);
carry = result/10;
i--;
}
if(carry>0){
ans.append(carry);
}
if(ans.length()==0)
ans.append('0');
ans.reverse();
return ans.toString();
}

public int size(){
return number.length();
}

public String getNum(){
return number;
}
public static void main(String[] args){
Console c = System.console();
String num1 = c.readLine("Enter first decimal:");
String num2 = c.readLine("Enter second decimal:");
Decimal b1 = new Decimal(num1);
Decimal b2 = new Decimal(num2);
System.out.println("Num1: " + b1.getNum());
System.out.println("Num2: " + b2.getNum());

Decimal b3 = Decimal.multiply(b1,b2);
System.out.println("Result: " + b3.getNum());
System.out.println("Size:" +b3.getNum().length());

}
}

Given a matrix in which each row and each column is sorted, write a method to find an element in it..One of The Most Typical Question

Assumptions:
»»Rows are sorted left to right in ascending order. Columns are sorted top to bottom in ascending order.
»»Matrix is of size MxN.
This algorithm works by elimination. Every move to the left (--col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row

class matrix_search
{
static boolean FindElem(int[][] mat, int elem, int M, int N)
{
int row = 0;
int col = N-1;

while (row < M && col >= 0)
{

if (mat[row][col] == elem)//done
{
return true;
}
else if (mat[row][col] > elem) //obvious as all call are sorted because all value
{
col--;
}
else // its all same as all row are sorted so if element not found in a[i][] then got
//a[i+1][] row because all all value in row[i] < row[i+1] its given
{
row++;
}

}
return false;

}


public static void main(String a[])
{

System.out.println(FindElem(new int[][]{{1,2,3,4},{5,8,9,10},{6,11,13,14},{7,12,15,16}},9,4,4));

}


}

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.

Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

Use ordinary binary search, but when you hit an empty string, advance to the next non-empty string; if there is no next non-empty string, search the left half.


class string_search
{


public static int search(String[] strings, String str, int first, int last) {
while (first <= last) {
// Ensure there is something at the end
while (first <= last && strings[last] == "") {
--last;
}
if (last < first) {
return -1; // this block was empty, so fail
}
int mid = (last + first) >> 1;
while (strings[mid] == "") {
++mid; // will always find one
}
int r = strings[mid].compareTo(str);
if (r == 0) return mid;
if (r < 0) {
first = mid + 1;
} else {
last = mid - 1;
}
}
return -1;
}

public static int search(String[] strings, String str) {
if (strings == null || str == null) return -1;
if (str == "")
{
for (int i = 0; i < strings.length; i++) {
if (strings[i] == "") return i;
}
return -1;
}
return search(strings, str, 0, strings.length - 1);
}

public static void main(String a[])
{

String s[]=new String[]{"at", "","", "", "ball", "","", "car", "", "", "dad", "",""};

System.out.println((search(s,"ball")));

}
}


Retunr Answer 4 Position of String

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways

This is a recursive problem, so let’s figure out how to do makeChange(n) using prior solutions (i.e., sub-problems). Let’s say n = 100, so we want to compute the number of ways of making change of 100 cents. What’s the relationship to its sub-problems?
We know that makeChange(100):
= makeChange(100 using 0 quarters) + makeChange(100 using 1 quarter) + makeChange(100 using 2 quarter) + makeChange(100 using 3 quarter) + makeChange(100 using 4 quarter)
Can we reduce this further? Yes!
= makeChange(100 using 0 quarters) + makeChange(75 using 0 quarter) + makeChange(50 using 0 quarters) + makeChange(25 using 0 quarters) + 1
Now what? We’ve used up all our quarters, so now we can start applying our next biggest denomination: dimes.
This leads to a recursive algorithm that looks like this:



class denomination
{

public static int makeChange(int n, int denom) {
int next_denom = 0;
switch (denom) {
case 25:
next_denom = 10;
break;
case 10:
next_denom = 5;
break;
case 5:
next_denom = 1;
break;
case 1:
return 1;
}
int ways = 0;
for (int i = 0; i * denom <= n; i++) {
ways += makeChange(n - i * denom, next_denom);
}
return ways;
}

public static void main(String a[])
{

System.out.println(makeChange(100, 25));


}

}


Time Complexity O(n)

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algoritm to decide if T2 is a subtre of t1

Note that the problem here specifies that T1 has millions of nodes—this means that we should be careful of how much space we use. Let’s say, for example, T1 has 10 million nodes—this means that the data alone is about 40 mb. We could create a string representing the inorder and preorder traversals. If T2’s preorder traversal is a substring of T1’s preorder traversal, and T2’s inorder traversal is a substring of T1’s inorder traversal, then T2 is a substring
of T1. We can check this using a suffix tree. However, we may hit memory limitations because suffix trees are extremely memory intensive. If this become an issue, we can use an alternative approach.
Alternative Approach: The treeMatch procedure visits each node in the small tree at most once and is called no more than once per node of the large tree. Worst case runtime is at most O(n * m), where n and m are the sizes of trees T1 and T2, respectively. If k is the number of occurrences of T2’s root in T1, the worst case runtime can be characterized as O(n + k * m).


boolean containsTree(TreeNode t1, TreeNode t2) {
if (t2 == null) return true; // The empty tree is always a subtree
else return subTree(t1, t2);
}

boolean subTree(TreeNode r1, TreeNode r2) {
if (r1 == null)
return false; // big tree empty & subtree still not found.
if (r1.data == r2.data) {
if (matchTree(r1,r2)) return true;
}
return (subTree(r1.left, r2) || subTree(r1.right, r2));
}

boolean matchTree(TreeNode r1, TreeNode r2) {
if (r2 == null && r1 == null)
return true; // nothing left in the subtree
if (r1 == null || r2 == null)
return false; // big tree empty & subtree still not found
if (r1.data != r2.data)
return false; // data doesn’t match
return (matchTree(r1.left, r2.left) &&
matchTree(r1.right, r2.right));
}
}

Microsoft Excel Sheet Question-very Important

Given the sequence S1 = {a,b,c,d,…,x,y,z,aa,ab,ac…. } and given that this sequence corresponds (term for term) to the sequence S2 = {0,1,2,3,….}. Write code to convert an element of S2 to the corresponding element of S1.

Hint:

I’ve created the following table for your convenience.

a - 0 aa - 26 ..... za - 676 aaa - 702
b - 1 ab - 27 ..... zb - 677 aab - 703
c - 2 . . .
. . . .
. . . .
. . . .
z - 25 az - 51 ..... zz - 701 aaz - 727

From a-z, how many of them are there? How about aa-zz? And aaa-zzz?
Amazon’s HQ in Seattle

Solution:
You should be able to observe that from a-z (a total of 26), from aa-zz (a total of 262), from aaa-zzz (a total of 263), and so on… I will explain why this is important later.

Assume s1 = abc and we need to find its corresponding number, s2. Now imagine that aaa can be magically transformed to 000, aab –> 001, …, and abc to some number xyz. The question is, what should xyz be?

Now this is a trivial question. Why? Remember that our numeral system has 10 as its base. Here, we are merely converting the system from base 26 to base 10. Therefore, xyz = 2*260 + 1*261 + 0*262 = 28.

But wait, we are not finished yet. To find the real value of s2, we need to find how many of them appeared before aaa and add to xyz. Using the important observation earlier, we can easily determine that that there are a total of 26 + 262 = 702 that appeared before aaa. Therefore, s1 corresponds to the number s2 = 28 + 702 = 730.

Assume that we are converting from s2 = n to s1 = “abcde…”.
We can generalize to the following equation (Equation (1)):

Equation (1)

n = 26 + 262 + ... + 26k-1 + a0 + a1*26 + a2*262 + ... + ak-1*26k-1
= a0 + (a1 + 1) 26 + (a2 + 1) 262 + ... + (ak-1 + 1) 26k-1

where
ai ranges from 0-25 (each representing a letter in s1),
k is the number of letters in s1.

To solve the above equation, we have to find the values of a0, a1, …, ak-1. Once we solve this equation, we are able to determine the string of letters of s1 directly.

a0 can be solved by taking n % 26. Why? Because a0 ranges from 0-25, which is not divisible by 26, while the rest are factor of 26. After we obtained the value of a0, we divide n by 26. This will yield the number

n' = (a1 + 1) + (a2 + 1) 26 + ... + (ak-1 + 1) 26k-2

You might think that a1 + 1 = n’ % 26. This is wrong. What happens when a1 = 25? For sure, a1 +1 is divisible by 26, and thus the mentioned equation is invalid. We can easily resolve this by doing a1 = (n’ – 1) % 26.

The rest is easy, we continue further with n” = (n’ – 1) / 26 and a2 = (n” – 1) % 26, up until ak-1.

Clearly, we need to do both modulo 26 and divide by 26 operations a total of k-1 times. But do we really need to know the value of k (or the number of letters in s1)?

The beauty of this method is, since we start from the least significant digit and work our way up, we don’t need to evaluate k. We just need to divide n by 26 repeatedly until it becomes 0.

so then we can write

#include
#include
/* Convert the header to a number */
int main()
{
char header[] = "abc";
char temp;
int number = 0;
int len, i;
len = strlen(header);
printf("len : %d\n", len);
for(i = 0;i < len; i++)
{
number += (int)pow (26, (double)i) * (header[i] - 'a' + 1);

}
printf("number : %d\n", number);
/* Convert back the number to string header */
while(number != 0)
{
temp = number%26;
number = number/26;
printf("%d %c\t", temp ,temp + 'a'-1);
}
return 0;
}

Time Complexity O(N*26^N) for string to Number
Space Complexity O(K) Where K Number of digits in Number =O(1) Constant
Run here http://codepad.org/DNBbGm7j