Anil
BAN USER- 0of 0 votes
AnswersYou have a set of interdependent tasks (no loops), What data structures would you use and how would you find the correct sequence of execution of the tasks. For example: Suppose we have six tasks A,B,C,D,E. A depends on B and D. C depends on D. E depends on A, then one possible sequence is: B, D, A, C, E.
- Anil| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersYou have two lists, each containing position of a word in some document. Write a program that returns minimum distance between the words in the document.
- Anil
For example: Suppose X occurs at places {2, 3, 5, 10, 12, 16, 19, 20} and Y occurs at {8, 14, 27, 29}, then the minimum distance between X and Y is 1 (X=12,Y=14 OR X=16,Y=14).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a MxN matrix, find the total number of possible paths from top-left to bottom-right element, you can go rightwards and downwards only.
- Anil
Now, assume some of the entries in the matrix are blocked, find the number of such paths. For example: For a 3X3 matrix, total number of paths in first case is 6!/3!3! = 20.
For second case, if we block entry (2,2), we have only 2 paths available.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersYou are given n petrol stations s(0), s(1), s(2), ..., s(n-1) which have petrol available p(0), p(1), p(2), ..., p(n-1). Going in a circle, with distance to next station being d(0), d(1), d(2), ..., d(n-1), how will you find where to start, such that you can complete the loop. You can assume mileage to be 1.
- Anil| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersPrint a 2D array spirally.
- Anil| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Arrays
#include<stdio.h>
void printList(char **l, int length) {
for(int i=0; i<length; i++)
printf("%s ", l[i]);
printf("\n");
}
void swapList(char *s[], int i, int j) {
char *temp = s[i];
s[i] = s[j];
s[j] = temp;
}
void permuteList(char **l, int start, int len) {
if(start==len)
printList(l, len);
for(int i=start; i<len; i++) {
swapList(l, start, i);
permuteList(l, start+1, len);
swapList(l, start, i);
}
}
int main() {
char *list[3] = {"the", "quick", "brown"};
permuteList(list, 0, 3);
return 0;
}
The match will not be unique, say I'm looking for 'cat', this approach will match with 'act' as the first match. You need to consider permutations of string once you know it's constituents. Also, first steps complexity is O(k) as words like 'aaaaaaa' will require multiple passes for same alphabet.
Let me know if I've missed something.
I may be spoiling the fun here.
For part 1, the total number of ways in which one can travel from top-left to bottom-right in (M+1)x(N+1) matrix is equivalent to arrangement of M DOWN arrows and N RIGHT arrows. The formula for which is (M+N)!/M!N!.
For blocked case: suppose we start at (1,1), end at (M,N) and (i,j) is blocked. If we have p TOTAL paths from (1,1) to (i,j) and q UNBLOCKED paths from (i,j) to (m,n) then the unique paths passing through (i,j) is p*q. These we should ignore. Similarly, we ignore for other blocked elements. That there is no overlapping among these ignored paths is ensured by q.
Let me know if this is still not clear, for its somewhat difficult to explain. Also, let me know if you see any error in the approach.
Below is the implementation. Code is non-optimal (didn't use Dynamic Programming). Also space complexity can be improved.
#include<stdio.h>
#define FREE 0
#define BLOCKED 1
/* static allocation */
int M[100][100];
/* Matrix entry */
typedef struct {
int r, c;
} entry;
int factorial(int n) {
int nfact;
for(nfact=1; n>0; n--)
nfact*=n;
return nfact;
}
/* ignoring blockages, total number of paths */
int free_path(entry s, entry d) {
int total;
int m, n;
m = d.r - s.r;
n = d.c - s.c;
return factorial(m+n) / (factorial(m) * factorial(n));
}
/* considering blockages, total number of paths */
int available_path(entry s, entry d) {
entry temp;
int total = free_path(s, d);
int r, c;
for(r=s.r; r<=d.r; r++) {
for(c=s.c; c<=d.c; c++) {
/* ignore if first entry is blocked (bad workaround)
check if current entry is blocked, if so ignore all paths
passing through this entry */
if(!(r==s.r && c==s.c) && M[r][c] == BLOCKED) {
temp.r = r;
temp.c = c;
total -= (free_path(s, temp) * available_path(temp, d));
}
}
}
return total;
}
/* initialize the matrix with given number of rows and columns */
void initialize(int m, int n) {
int r, c;
for(r=0; r<m; r++) {
for(c=0; c<n; c++) {
M[r][c] = FREE;
}
}
}
/* block a specific entry */
void block(int r, int c) {
M[r][c] = BLOCKED;
}
int main() {
entry start, end;
int m, n;
m = 5;
n = 4;
// create an MxN matrix
initialize(m, n);
start.r = 0;
start.c = 0;
end.r = m-1;
end.c = n-1;
// block a set of entries
block(1, 1);
block(2, 1);
printf("Count=%d\n", available_path(start, end));
return 0;
}
Taking mileage as 1 KM/Liter, suppose p(0) is 2 Liters and d(0) is 3 KM, then we can't make it from s(0) to s(1).
An O(n) approach is to start from s(0), go on till available petrol Sum(p(i)-d(i)), becomes negative, then move backwards s(n-1), s(n-2), ... till it becomes +ve again, go on doing like this, till you arrive at same node from both sides... let me know if this is still not clear. Sorry, the question is easy to explain in picture - the way it was put in front of me, think of it in terms of circular list, will be easier to comprehend.
I'm not sure if this will retain the structure. Basically its like doing an inorder traversal, which in itself doesn't preserve complete information. I think you need to push those NULL entries as well, and check while popping.
Here's my code (mirrorLR function, ignore the rest if you don't want to run it):
#include <stdio.h>
struct snode {
void *data;
struct snode *next;
};
struct snode *newSNode(void *data, struct snode *next) {
struct snode *node = (struct snode *) malloc(sizeof(struct snode));
node->data = data;
node->next = next;
return node;
}
typedef struct {
struct snode *top;
} Stack;
Stack *newStack() {
Stack *s = (Stack *) malloc(sizeof(Stack));
s->top = NULL;
return s;
}
void *pop(Stack *s) {
struct snode *node = s->top;
void *data;
if(node == NULL)
return NULL;
s->top = node->next;
data = node->data;
free(node);
return data;
}
void push(Stack *s, void *data) {
struct snode *node = newSNode(data, s->top);
s->top = node;
}
int isEmpty(Stack *s) {
return (s->top == NULL);
}
struct tnode {
int data;
struct tnode *left, *right;
};
struct tnode *newTNode(int data, struct tnode *left, struct tnode *right) {
struct tnode *node = (struct tnode *) malloc(sizeof(struct tnode));
node->data = data;
node->left = left;
node->right = right;
return node;
}
typedef struct {
struct tnode *root;
} Tree;
Tree *newTree() {
Tree *t = (Tree *) malloc(sizeof(Tree));
t->root = NULL;
return t;
}
void inorder(struct tnode *node) {
if(node == NULL)
return;
printf("%d\n", node->data);
inorder(node->left);
inorder(node->right);
}
void preorder(struct tnode *node) {
if(node == NULL)
return;
preorder(node->left);
printf("%d\n", node->data);
preorder(node->right);
}
Tree *buildTree() {
Tree *t = newTree();
t->root = newTNode(1, NULL, NULL);
t->root->left = newTNode(2, NULL, NULL);
t->root->right = newTNode(8, NULL, NULL);
t->root->left->left = newTNode(3, NULL, NULL);
t->root->left->right = newTNode(6, NULL, NULL);
t->root->left->left->left = newTNode(4, NULL, NULL);
t->root->left->left->right = newTNode(5, NULL, NULL);
t->root->left->right->right = newTNode(7, NULL, NULL);
t->root->right->right = newTNode(9, NULL, NULL);
t->root->right->right->left = newTNode(10, NULL, NULL);
t->root->right->right->right = newTNode(11, NULL, NULL);
return t;
}
// Mirror the tree using stack
void mirrorLR(Tree *t) {
struct tnode *node, *temp;
Stack *s = newStack();
push(s, t->root);
while(!isEmpty(s)) {
node = pop(s);
if(node == NULL)
continue;
temp = node->left;
node->left = node->right;
node->right = temp;
push(s, node->left);
push(s, node->right);
}
}
int main() {
Tree *t1 = buildTree();
Tree *t2 = newTree();
mirrorLR(t1);
printf("Inorder Traversal\n");
inorder(t1->root);
printf("Preorder Traversal\n");
preorder(t1->root);
return 0;
}
Output:
Inorder Traversal
1
8
9
11
10
2
6
7
3
5
4
Preorder Traversal
11
9
10
8
1
7
6
2
5
3
4
I think the question has been already answered in much better way. But I couldn't think of that approach by myself. Here's another approach:
Consider an array of 8 elements, to be rotated by 3, the indices are given below:
After: {5, 6, 7, 0, 1, 2, 3, 4}
Before: {0, 1, 2, 3, 4, 5, 6, 7}
We have one cycle, which covers all elements:
0 -> 3
3 -> 6
6 -> 1
1 -> 4
4 -> 7
7 -> 2
2 -> 5
5 -> 0
Now, consider another array, this time of 10 elements, to be rotated by 6, indices are given below:
After: {4, 5, 6, 7, 8, 9, 0, 1, 2, 3}
Before: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
We have two cycles:
Cycle1:
0 -> 6
6 -> 2
2 -> 8
8 -> 4
4 -> 0
Cycle2:
1 -> 7
7 -> 3
3 -> 9
9 -> 5
5 -> 1
Its not difficult to see that the number of cycles is gcd(n, k), where n is the array size and k is the rotation.
Proof: let g = gcd(n, k)
We have: i -> i+k -> i+2k -> ... i+(r-1)k -> i, therefore, i = i+rk, and (r*k)%n=0
we can write k as k=g*p, since r is the least number such that (r*g*p)%n=0, and p is coprime with n, we have n = g*r
r is the size of cycle and g is the number of cycles.
Withing each cycle, we only need to maintain one additional variable to achieve rotation.
Below is the algorithm:
g = gcd(n,k)
r = n/g
for(i=0; i<g; i++) {
temp = A[(i+(r-1)k)%n]
for(j=i+k; j<i+rk; j+=k)
A[j%n] = A[(j-k)%n];
A[i] = temp;
}
Here's the program:
#include <stdio.h>
int gcd(int p, int q) {
if(p%q==0)
return q;
return gcd(q, p%q);
}
// rotate an array by k
void rotateArr(int A[], int n, int k) {
int g, r, i, j, temp;
g = gcd(n, k);
r = n / g;
for(i=0; i<g; i++) {
temp = A[(i+(r-1)*k)%n];
for(j=i+(r-1)*k; j>=i; j-=k)
A[j%n] = A[(j-k)%n];
A[i] = temp;
}
}
void printArr(int A[], int n) {
int i;
for(i=0; i<n; i++)
printf("%2d ", A[i]);
printf("\n");
}
int main() {
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
rotateArr(A, 10, 6);
printArr(A, 10);
return 0;
}
Output: 5 6 7 8 9 10 1 2 3 4
- Anil January 28, 2011Algo is pretty simple.
Maintain a stack s, two pointers p1, p2. Let the list be l and first node be l->start.
p1 points to the next node to be processed
p2 points to end of new list with nodes in desired order (K-reversed)
As we traverse the list, we push the nodes onto stack, after every K-steps, we pop the stack (till it gets empty) and add to the end of p2.
Here's code for same (function reverseK):
#include <stdio.h>
// List node with int as payload
struct lnode {
int data;
struct lnode *next;
};
struct lnode *newLNode(int data, struct lnode *next) {
struct lnode *node = (struct lnode *) malloc(sizeof(struct lnode));
node->data = data;
node->next = next;
return node;
}
// List node
typedef struct {
struct lnode *start;
} List;
List *newList() {
List *l = (List *) malloc(sizeof(List));
l->start = NULL;
return l;
}
// Stack node
struct snode {
void *data;
struct snode *next;
};
struct snode *newSNode(void *data, struct snode *next) {
struct snode *node = (struct snode *) malloc(sizeof(struct snode));
node->data = data;
node->next = next;
return node;
}
// Stack
typedef struct {
struct snode *top;
} Stack;
Stack *newStack() {
Stack *s = (Stack *) malloc(sizeof(Stack));
s->top = NULL;
return s;
}
void push(Stack *s, void *data) {
struct snode *node = newSNode(data, s->top);
s->top = node;
}
void *pop(Stack *s) {
void *data;
struct snode *node = s->top;
if(node == NULL)
return;
s->top = node->next;
data = node->data;
free(node);
return data;
}
int isEmpty(Stack *s) {
return (s->top == NULL);
}
void printList(List *l) {
struct lnode *node = l->start;
while(node!=NULL) {
printf("%2d ", node->data);
node = node->next;
}
printf("\n");
}
// Reverse in steps of K elements
void reverseK(List *l, int k) {
Stack *s = newStack();
int i;
struct lnode *p1, *p2;
// To maintain l->start, do it separately for first K-elements
for(i=0, p1=l->start; i<k && p1!=NULL; i++, p1=p1->next)
push(s, p1);
p2 = l->start = (struct lnode *) pop(s);
// empty list
if(l->start == NULL)
return;
while(!isEmpty(s)) {
p2->next = (struct lnode *) pop(s);
p2 = p2->next;
}
// Now do it for remaining elements 0..k-1, k...2k-1,...
for(i=0; p1!=NULL; i++, p1=p1->next) {
if(i%k==0) {
while(!isEmpty(s)) {
p2->next = (struct lnode *) pop(s);
p2 = p2->next;
}
}
push(s, p1);
}
// lastly for elements left in stack
while(!isEmpty(s)) {
p2->next = (struct lnode *) pop(s);
p2 = p2->next;
}
// avoid loops
p2->next = NULL;
}
List *buildList() {
List *l = newList();
l->start = newLNode(1, NULL);
l->start->next = newLNode(2, NULL);
l->start->next->next = newLNode(3, NULL);
l->start->next->next->next = newLNode(4, NULL);
l->start->next->next->next->next = newLNode(5, NULL);
l->start->next->next->next->next->next = newLNode(6, NULL);
l->start->next->next->next->next->next->next = newLNode(7, NULL);
l->start->next->next->next->next->next->next->next = newLNode(8, NULL);
l->start->next->next->next->next->next->next->next->next = newLNode(9, NULL);
l->start->next->next->next->next->next->next->next->next->next = newLNode(10, NULL);
l->start->next->next->next->next->next->next->next->next->next->next = newLNode(11, NULL);
l->start->next->next->next->next->next->next->next->next->next->next->next = newLNode(12, NULL);
return l;
}
int main() {
List *l = buildList();
printList(l);
reverseK(l, 3);
printList(l);
return 0;
}
Maintaining heap completely ignores the fact that lists are sorted.
We can maintain k pointers and select least and next-to-least elements (O(k) + O(logK) - 2), once we increment the pointer in list with least element, we can immediately compare it with the next-to-least element - this will potentially reduce the time to half. I don't think asymptotic bound can go below O(nk).
P = n*(n^2-1) = (n-1)*n*(n+1)
let, n = 2m+1 (n being odd)
We have, P = (2m)*(2m+1)*(2m+2) = 4*m*(m+1)*(2m+1)
Now, the formula for sum of squares of integers as:
S = 1^2 + 2^2 + ... + m^2 = [m*(m+1)*(2m+1)]/6
Therefore, m*(m+1)*(2m+1) = 6S
Hence we have, P = 4*6S = 24S
Rotation here doesn't meant rotation in N-dimensional space. It means rotating the matrix, I don't think there's a simple matrix which can achieve this.
Career Cup book describes this problem. Here's my implementation for a sample 5x5 matrix:
#include <stdio.h>
#define N 5
int main() {
int m[N][N] = {
{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, j, temp;
// Initial Matrix
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
printf("%2d ", m[i][j]);
}
printf("\n");
}
printf("-----------------------\n");
// Rotate Matrix
for(i=1; i<=N/2; i++) {
for(j=i; j<N+1-i; j++) {
temp = m[i-1][j-1];
m[i-1][j-1] = m[N-j][i-1];
m[N-j][i-1] = m[N-i][N-j];
m[N-i][N-j] = m[j-1][N-i];
m[j-1][N-i] = temp;
}
}
// Rotated Matrix
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
printf("%2d ", m[i][j]);
}
printf("\n");
}
getchar();
return 0;
}
This is the code I used:
#include <stdio.h>
// a: array
// n: last index of a
// sum: desired sum
// curr: current sum
int subsetSum(int a[], int n, int sum, int curr) {
if(curr==sum)
return 1;
if(curr>sum || n<0)
return 0;
return subsetSum(a, n-1, sum, curr+a[n]) + subsetSum(a, n-1, sum, curr);
}
int main() {
int a[] = {5, 5, 10, 2, 3};
printf("%d\n", subsetSum(a, 4, 15, 0));
system("pause");
return 0;
}
RepMildredLane, abc at 8x8
As a Personnel Services Specialist, I thrive at the intersection of human resources and organizational excellence. With a passion for ...
- Anil October 24, 2015