pavi.8081
BAN USER- 0of 2 votes
AnswersIn a Binary tree, every element(node's value) must contain the sum of its left and right sub-trees.
- pavi.8081 in India
Follow up question: how would you solve this if you can ONLY increment the value of a node
Eg. If a node’s value is 20 and its sub-tree sum is 10, the node’s value can’t be set to 10 because you can only increment.
How would you solve this if you can ONLY increment the value of a node
Further clarifications.
1. You can make assumption that leaf nodes retain their original value and does not change.
2. "Sum of its left and right subtrees" means sum of all nodes' values in its left subtree + sum of all nodes' values in its right subtree.
PS: I am asking this question coz I am not sure of its solution myself. Hence seeking experts' advice.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 1 vote
AnswersDesign a DVD renting library system
- pavi.8081 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Object Oriented Design - 0of 2 votes
Answersgiven two arrays of same size, arrange the arrays such that a1*b1 + a2*b2 + .... + an*bn should ne minimum.
- pavi.8081 in India for Fraud prevention| Report Duplicate | Flag | PURGE
Amazon SDE-2 Arrays - 0of 0 votes
AnswerDesign the juglee.com.
- pavi.8081 in United States for Online Fraud Prevention
Write objects involved and their properties, behaviour and interactions.
Make valid and practical assumptions and design.
Please let me know your approach to this design questions.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Object Oriented Design - 0of 0 votes
AnswersDesign a Dropbox invite system (refer other guys to join and get more space)
- pavi.8081 in United States for Online Fraud Prevention
Assume whats required and design.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Object Oriented Design - 0of 0 votes
AnswersDesign a task scheduler
- pavi.8081 in United States for STB and MVO| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Object Oriented Design - 0of 0 votes
AnswersDesign a vending machine.
- pavi.8081 in United States for STB and MVO| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Object Oriented Design - 0of 0 votes
Answersarray of numbers are given. WAP to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.
- pavi.8081 in India for STB and MVO
Follow up: After writing program to return the largest sum modify it to return the start and end index of such a subarray.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven an array with source code and braces (braces means '{' or '}' ) intermixed. WAP to return true of braces are balanced (implies that for each opening brace there must be a closing brace and for each closing brace there must be opening brace) and false otherwise.
- pavi.8081 in India for STB and MVO| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven a pattern P and a text T, WAP to return all indices from T where P matches.
- pavi.8081 in India for STB and MVO| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 1of 3 votes
AnswersPosition of Knight is given on a chessboard.
- pavi.8081 in United States for STB and MVO
Return me something (adjacency matrix or list or anything) which shows all
the positions the knight can reach upto from a given position.
I must be able to tell, from what is returned, if the position is reachable or not
and if reachable I must be able to trace the path from given position to target position
<<FOLLOW-UP>>
For example if 4 cells are reachable from a cell A, then these 4 cells become children of A.
Then from a cell, say B, out of these 4 cells, you can reach 2 more cells: C and D. Then C and D become children of B.
Likewise program need to return me a DS. I have given a valuable hint with this follow-up. I hope this will help| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersN boys are sitting in a circle. Each of them have some apples in their hand.
- pavi.8081 in United States
You find that the total number of the apples can be divided by N.
So you want to divide the apples equally among all the boys.
But they are so lazy that each one of them only wants to give one apple to one of the neighbors at one step.
Calculate the minimal number of steps to make each boy have the same number of apples.
Input Given:
1. A number N => number of children.
2. Sequence of N numbers, each representing number of apples a child has.
<<P.S.>>
Passing an apple means a child giving away one apple to one of its neighbour.
Even if 2 separate children can pass apples simultaneously or one child can pass 1-1 apple to each of its neighbours then that will still be counted as 2 steps and not 1 step.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm
Hi Ehsan,
Thanks for the elaborate explanation. But as I understand it, I think you have misunderstood the question.
Question is not about counting total number of nodes in left and right sub-trees and setting that as value of the root node.
Here, Question is to set node's value as sum of node values in left and rt subtrees.
For example:
let tree be:
20
5 6
null 3 null null
the resultant tree becomes:
9
3 6
null 3 null null
Please refer to "Further clarifications." section in the Question.
I hope I understood it right. Please let me know if I am wrong
Here's my solution. I gave in interview adjacency Iist based solution.
Here I am giving both, adjacency-list and adjacency-matrix based solution for your reference:
//+--------------------------------------+
//| == ADJACENCY MATRIX BASED SOLUTION ==|
//+--------------------------------------+
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
using namespace std;
#define MAX_MOVES 8
struct coord
{
int row;
int col;
};
coord possibleMoves[] =
{
{-2, +1},
{-1, +2},
{+1, +2},
{+2, +1},
{+2, -1},
{+1, -2},
{-1, -2},
{-2, -1}
};
int isValid(int r, int c)
{
if((r >= 0 && r <= 7)&&
(c >= 0 && c <= 7))
return 1;
return 0;
}
void getValidMoves(int r, int c, coord *lst, int *size)
{
assert(lst);
assert(size);
*size = 0;
for(size_t i = 0; i<sizeof(possibleMoves)/sizeof(possibleMoves[0]); i++)
{
if(isValid(r + possibleMoves[i].row, c + possibleMoves[i].col))
{
lst[*size].row = r + possibleMoves[i].row;
lst[*size].col = c + possibleMoves[i].col;
(*size)++;
}
}
return ;
}
int ChessBoard[MAX_MOVES*MAX_MOVES][MAX_MOVES*MAX_MOVES];
void backTrack(int row, int col)
{
int size = 0;
coord moves[MAX_MOVES] = {{0, 0}};
getValidMoves(row, col, moves, &size);
for(int i = 0; i < size; i++)
{
if(ChessBoard[row*8+col][moves[i].row*8 + moves[i].col] != 1)
{
ChessBoard[row*8+col][moves[i].row*8 + moves[i].col] = 1;
backTrack(moves[i].row, moves[i].col);
}
}
}
void getAllPositions()
{
int r = 0, c = 0;
cout << "Cell's row index = ";
cin >> r;
cout << "Cell's column index = ";
cin >> c;
//r = 3, c = 3;
backTrack(r, c);
cout << " " ;
for(int i = 0; i < MAX_MOVES*MAX_MOVES; i++)
printf("%2d ", i);
cout << endl;
for(int i = 0; i < MAX_MOVES*MAX_MOVES; i++)
{
printf("%2d ", i);
for(int j = 0; j < MAX_MOVES*MAX_MOVES; j++)
printf("%2d ", ChessBoard[i][j]); // << endl;
cout << endl;
}
return;
}
/////////////////////////////////////////////////////////////////////////
//+------------------------------------+
//| == ADJACENCY LIST BASED SOLUTION ==|
//+------------------------------------+
#define MAX_CHILDREN 8
#define POSITIONS 8
class graphNode
{
static bool bChessBoard[POSITIONS][POSITIONS];
public:
coord pos;
graphNode* children[MAX_CHILDREN];
int count;
static bool isOccupied(int r, int c)
{
if(isValid(r, c))
return bChessBoard[r][c];
return false;
}
static void setOccupied(int r, int c)
{
if(isValid(r, c))
bChessBoard[r][c] = 1;
}
graphNode():count(0)
{
pos.row = -1;
pos.col = -1;
}
graphNode(int r, int c):count(0)
{
pos.row = r;
pos.col = c;
}
static graphNode *getGraphNode(int r, int c)
{
graphNode *aNode = new graphNode(r, c);
memset(aNode->children, 0, MAX_CHILDREN*sizeof(graphNode*));
return aNode;
}
};
bool graphNode::bChessBoard[POSITIONS][POSITIONS];
void backTrackAdjList(graphNode *root, int row, int col)
{
assert(root);
int size = 0;
coord moves[MAX_MOVES] = {{0, 0}};
getValidMoves(row, col, moves, &size);
for(int i = 0; i < size; i++)
{
if(!graphNode::isOccupied(moves[i].row, moves[i].col) )
{
graphNode *g = graphNode::getGraphNode(moves[i].row, moves[i].col);
root->children[root->count++] = g;
graphNode::setOccupied(moves[i].row, moves[i].col);
backTrackAdjList(g, moves[i].row, moves[i].col);
}
}
}
void dfsVisit(graphNode* root)
{
if(!root)
return;
cout << "row = " << root->pos.row << " col = " << root->pos.col << endl;
for(int i = 0; i < root->count; i++)
dfsVisit(root->children[i]);
return;
}
void freeGraph(graphNode* root)
{
if(!root)
return;
for(int i = 0; i < root->count; i++)
freeGraph(root->children[i]);
free(root);
root = NULL;
return;
}
void getAllPositionsAdjList()
{
int r = 0, c = 0;
cout << "Cell's row index = ";
cin >> r;
cout << "Cell's column index = ";
cin >> c;
//r = 3, c = 3;
if(!isValid(r, c))
return;
graphNode *root = graphNode::getGraphNode(r, c);
graphNode::setOccupied(r, c);
backTrackAdjList(root, r, c);
dfsVisit(root);
freeGraph(root);
return;
}
- pavi.8081 March 09, 2014@BigKdotAtTdot: Thanks for clearly mentioning. Now I accept there was little confusion in 1st version of question. But confusion was only one. It was about the leaf node (like should it maintain its value or pick 0 from its null children)
Apart from that I think few people also got confused about the sum, which I proactively clarified in question.
Misleading people was not the intention. Apologies! for that if I did that to you.
Now coming to your questions:
1. Which Amazon location asked you this?: India
2. Did you ask them clarifying questions?: Yes I did about leaf nodes but interviewer asked me to make valid assumptions. Hence I made assumptions after taking interviewer's approval.
3. Why aren't these in your post?: They were not because I thought I asked dumb question :(
Hi Ehsan,
Assuming parent pointer as part of node structure may not be right. Moreover its not mentioned in question to assume it.
Secondly if I assume parent pointer and follow your solution then , as I traced it, It gave wrong answer :(
two suggestions:
1. If you can give a solution without parent pointer then better.
2. If you need parent pointer, then I request you to review and trace your solution once and let me know. Thanks
HI Guy: As per my understanding when you are writing this statement:
n.value = Math.max(leftValue, rightValue);
I can think of an example say if node's value is 20 and its left and right child node's values are 3 and 4 respectively. So, when you execute above statement, its actually reducing the value of the node and not increasing it.
If its so then its against the rule mentioned in question. your take?
@vgeek: I tried your solution. But its making a node's value equal to sum of its left and right child nodes.
Whereas In the question, its required to make the node's value as sum of its left and right subtree.
Where the sum of its left and right subtree means that sum of all nodes in left subtree + sum of all nodes in right subtree
@BigKdotAtTdot : Hey stop making absurd comments and spamming this thread. What made you write this: "you don't even know what the question". can you please explain?
Moreover I have not held your ears to force you waste your time. you are free to abandon and not respond to this question.
And there is no need to be rude! instead of making vague comments you could have precisely mentioned what's confusing you.
I don't think you are doing the right thing.
In case of diff < 0, you are increasing the value of node to sum of its subtrees, but in this process you are also increasing the value of nodes' of left and right subtree. Am I right?
If I am then this is not what is expected out of the solution.
I think you are right.
For your question : "space; O(1) - I don't think making a list into two halves is an extra space. So, it takes constant space... I'm not 100 % sure about this. Can any one confirm."
my answer is that when you are traversing to middle of the list you are just forwarding the pointer towards middle node, which is O(1) space operation.
Hence it is surely O(1) space solution.
I agree with @eugene and also with @given-test . This solution will give trouble when a string and its substring both are present in the dictionary as valid words. Hence I propose following solution:
when a valid split position is found check if substring from char after previous valid pos till this split pos exists in dictionary. If it does then this split position is a valid split pos else not. This way keep an array of all valid split pos and finally display the words.
hmm.. looks good. Can you please also enlist the functions/methods and collaborations among these classes.
by
Customer::paymentlist;
did you mean the transaction history?
Few suggestions:
1)
DVDLibrary
should also have customer list.
2)
class Customer
can have privileges. By it I mean privileges like: restricted access, power_user etc. where
privilege
can be either property or class in its own right depending upon the complexity of
privilege
3)There's also need for:
class Transactions
{
Customer& cust;
list<Dvd*> borrowed;
Date& transaction date;
public:
//methods
};
4)
class Payment
can have field: discount offered.
More enhancements can be followed.. your take?
This was question from my friend's interview. He could not make through because as per him Manager round didn't go well. So probably its the soft skills which let him down rather than technical.
Moreover, there were a couple of design questions asked in earlier rounds, so probably some things might have went wrong there as well, we're not sure.
Please have a look at those questions at:
question?id=21718663
question?id=21219666
Please people, suggest your solutions to these....
my c++ based program. Using only stl: stack as helper.
No other stl or library is used (not even C++ string).
Hope it helps from-scratch implementation. Thanks @eugene.yarovoi for providing the idea. Though, I came up with the same logic but since u posted here earlier than me so I think acknowledgement is due :)
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
struct ll
{
char *str;
int len;
// ll *next;
ll(char* a=0, int l=0): str(a), len(l){}
};
void static clearStack(stack<ll*> &st)
{
while(!st.empty())
{
ll* temp = st.top();
st.pop();
delete(temp);
}
return;
}
void printStr(char* ptr, int len)
{
if(!ptr || len == 0)
return;
for(int i=0; i<len; i++)
cout << ptr[i];
}
void printPath(stack<ll*> &st)
{
while(!st.empty())
{
ll* node = st.top();
st.pop();
printPath(st);
printStr(node->str, node->len);
delete(node);
cout << "/";
}
}
void relToAbs(char *rpath, int len)
{
// STATE MACHINE TO PROCESS THE RELATIVE PATH STRING
stack<ll*> st;
char *aName = NULL;
for(int i=0; rpath[i] != '\0' && i<len; /* i++ */)
{
if(rpath[i] == '/')
{
i++;
}
else if(rpath[i] == '.')
{
if(rpath[++i] == '.')
{
if(!st.empty())
{
ll *aNode = st.top();
st.pop();
delete(aNode);
}
++i;
}
}
else if(tolower(rpath[i]) >= 'a' && tolower(rpath[i]) <= 'z')// character is seen
{
aName = &rpath[i];
int size = i;
while(tolower(rpath[i]) >= 'a' && tolower(rpath[i]) <= 'z')
i++;
st.push(new ll(aName, i-size));
}
else
{
cout << "ill-formed path" << endl;
clearStack(st);
return ;
}
}
//------------------------------------------------------
return printPath(st);
}
void relToAbsDriver()
{
char* str = "/windows/abs/../temp/new/../$";
relToAbs(str, strlen(str));
cout << endl << "--------------------------------" << endl;
}
Here's my code for rank of string with all distinct characters..
Description:
freq(char *str, int len, int* count/*assumed to be of len=26*/): counts the frequency of each char present in the string. As per my assumption each char count must be 1.
factorial(int n): finds factorial of given n.
int countLessThan(char c, int *freq) : counts number of characters which are less than char c
ull findRank(char *str, int len, int pos, int* count): actually finds the rank of given word.
ull wordRank(char *str, int len): wrapper around findRank(). Just to supply the count[] array
void wordRankDriver(): main driver function.
IDEA: The idea is to calculate the rank of given word, find the number of permutations which are rank wise smaller than current word. To do so, permutation is calculated recursively.
1. Take all the chars which are smaller than char at position: pos=0. Now each of smaller char can be placed at pos 0 and rest (total # of chars -1) can be arranged among themselves in factorial((total # of chars -1) ways.
2. Once this is calculated for current position: pos, increment pos by 1 and calculate recursively # of permutations for next pos, that is pos.
Hope this description makes it somewhat clear. Appologies if not able to describe the procedure clearly.
BIG ASSUMPTION: All characters in the word are unique with no repeated chars.
#include<iostream>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
void freq(char *str, int len, int* count/*assumed to be of len=26*/)
{
memset(count, 0x00, 26*sizeof(int));
if(!str || len == 0)
return ;
for(int i=0; (str[i]!= '\0') && (i < len); i++)
count[tolower(str[i])-'a']++;
return ;
}
ull factorial(int n)
{
ull fact = 1;
for(int i=2; i <= n; i++)
fact *= i;
return fact;
}
int countLessThan(char c, int *freq)
{
int count=0;
for(int i =0; i<c-'a'; i++)
count += freq[i];
return count;
}
//ASSUMPTION: All characters in the word are unique with no repeated chars.
ull findRank(char *str, int len, int pos, int* count)
{
if(!str || len == 0)
return 0;
if(pos == len-1)
return 1;
int rank = countLessThan(str[pos], count);
rank = rank*factorial(len-pos-1);
count[tolower(str[pos])-'a']--;
return rank + findRank(str, len, pos+1, count);
}
ull wordRank(char *str, int len)
{
int count[26] = {0,};
freq(str, len, count);
return findRank(str, strlen(str), 0, count);
}
void wordRankDriver()
{
ull rank = wordRank("question", strlen("question"));
cout << "Rank of word question = " << rank << endl;
rank = wordRank("einoqstu", strlen("question"));
cout << "Rank of word einoqstu = " << rank << endl;
rank = wordRank("education", strlen("education"));
cout << "Rank of word education = " << rank << endl;
}
Here is my C/C++ based solution.
Idea here is that calculate the cumulative frequency array.
Now suppose a number 10 appears at index 3 so cumu[3] will contain number 10 + cumu[3-1].
Therefore a index will have numbers, out of total sum in its bucket, equal to the weight assigned to it.
Now take a random function which returns a number "output" uniformly between 0 and (sum-1) that is rand()%sum. check this output falls in which bucket and return the index of that bucket.
Hence this function will give you the index with probability equal to the weight of the number it holds in the original array.
#include<cstdlib>
using namespace std;
int getRandom(int *Array, int len)
{
int sum = 0;
int *cumu = new int[len];
for(int i =0; i < len; i++)
{
sum += Array[i];
cumu[i] = ((i == 0) ? Array[i] : (Array[i] + cumu[i-1]));
}
int output = rand()%sum;
if(output<= cumu[0])
return 0;
for(int i = 1; i < len; i++)
if(output > cumu[i-1] && output <= cumu[i])
return i;
}
Please let me know your comments :)
- pavi.8081 April 12, 2013@aka: I dont want printing of paths...u can give me a tree or graph anything u like. Using the Data structure u return I can print the cells. For example if u give me graph adjacency list or adjacency matrix I can use DFS or BFS to traverse it to print the cells reachable
- pavi.8081 April 12, 2013I am not concerned about minimum path.
I just want to know the cells I am reachable from source cell.
For ex. from (3, 3) I am reachable to 8 cells (I hope u know which ones)
Then from each of those 8 cells I am reachable to 8 more (or probably less because some cells may be out of range of chessboard cells) and so on and on.
So this will give me reachable cells. Now you can give me back a tree or graph or anything which depicts this. I hope I am clear now.
@aka: I need all the cells reachable from a given cell either directly or indirectly.
For example: if given cell is (7, 7) then I can reach to (5, 6) and (6, 5)
then from (5, 6) I can reach to (3, 5), (4, 4), (3, 7) and so on.
and similarly for (6, 5).
Obviously I want to stop this traversal and stop at those cells which are invalid in a chessboard.
I need all the places knight can reach from a given position along with all the positions reachable from new found positions.
suppose knight is at position (x,y) and it can reach (i, j) from it and can reach (w,q) from (i, j). So I need (i, j) and (w,q) both.
Therefore I need all positions reachable directly from (x, y) and all positions reachable from positions reachable from position (x, y) and so on and on.
I understand that eventually all the cells would be traversed by knight. But it will not give me the intermediate positions
which knight travelled before landing at a cell.
Therefore give me anything which also tells me the path. You decide what u need to return me to do so.
See the comment by prakash1529 above. I solved in the same way.
Only thing is I didnt have to consider any special case because my logic covered special cases.
For example while processing the braces I maintained that the partial sum of braces (that is adding +1 for '{' and -1 for '}' ) be
always greater than equal to zero.
It can never go negative at any point of processing and must exactly equate to zero at the end.
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is:
Theta(1)
This is because since the array is sorted then the number which is repeated more than n/2 times will appear as the middle element in array, that is, it will appear at index n/2 for (both even and odd n).
/*Following is the BACKTRAKING Algorithm for printing all the permutation of
Given string in decreasing order.
Time Complexity: O(N^2)
Input is taken as pointer to character arrays. Which is then sorted via :
QuickSortdecreasingOrder(): which sorts the strings in reverse order. That is "9" will come before "89"
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define TRUE 1
#define FALSE 0
static int isASolution(k, n)
{
return (k == n-1);
}
static void printPermutation(int a[], int n)
{
int i=0;
for(i=0; i<n; i++)
printf("%s", numbers[a[i]]);
printf("\n");
return;
}
static void candidatesForNextPlace(int a[], int k, int n, int c[], int *ncandidates)
{
int i, is_in_perm[MAX];
for(i=0; i<n; i++)
is_in_perm[i] = FALSE;
for(i=0; i<k; i++)
is_in_perm[a[i]] = TRUE;
*ncandidates = 0;
for(i=0; i<n; i++)
{
if(is_in_perm[i] == FALSE)
{
c[*ncandidates] = i;
(*ncandidates)++;
}
}
return;
}
//Elegant Backtrack method
//Time Complexity: O(N^2)
static void allDecreasingPermutations(int a[], int k, int n)
{
int i, ncandidates, c[MAX];
if(isASolution(k, n))
printPermutation(a, n);
else
{
k++;
candidatesForNextPlace(a, k, n, c, &ncandidates);
for(i=0; i<ncandidates; i++)
{
a[k] = c[i];
allDecreasingPermutations(a, k, n);
}
}
return;
}
//main driver method
void generateDecreasingPermutationsDriver(char *numbers[], int n)
{
int a[MAX]; /* solution vector */
// trivial to sort in decreasing order, hence omitted the below function.
//Complexity: O(N*lg(N))
QuickSortdecreasingOrder(numbers, n);
allDecreasingPermutations(a,-1,n); // Complexity: O(N^2)
return;
}
Here is a basic C program without using any supplementary DS (except array obviously).
Time complexity: Horrible
Space complexity: No extra space . Just constant which is a few vars. here and there.
Assumption:
1. All the numbers in array are unique.
2. Numbers in array are given in Non-increasing order with respect to their Most Significant Digit.
If not then we can sort the array in O(NlogN) time. This will not affect my algo as Time complexity is Horrible anyway.
Advantages:
Only two:
1. Not using any extra DS.
2. Only using O(1) extra space.
///////////
//RECURSIVE APPROACH:
//Helper function
static void shiftLeftOrRight(int arr[], int start, int end, int len, int left)
{
int startElem, from;
if(left)
{
startElem = arr[start];
from = start+1;
if((start < 0) || (end>=len))
return;
for(; from <=end; from++)
arr[from-1] = arr[from];
arr[end] = startElem;
}
else
{
startElem = arr[end];
from = end;
if((start < 0) || (end>=len))
return;
for(; from > start; from--)
arr[from] = arr[from-1];
arr[start] = startElem;
}
return;
}
//Main function.
static void PermuteInNonIncOrder(int arr[], int len, int start, int end)
{
int i=0;
if(start>=end)
{
Print(arr, len);
return;
}
for(i=start; i<=end; i++)
{
shiftLeftOrRight(arr, start, i, len, 0);
PermuteInNonIncOrder(arr, len, start+1, end);
shiftLeftOrRight(arr, start, i, len, 1);
}
return;
}
//////////////////
Explanation:
=============
Instead of swapping the 2 elements before and after the permutation, I have done
Right and left rotation before and after respectively. This is because of foll. reason as described by following example:
For ex.
Array in sorted order is :
9 8 66 4 12
when for example 66 is swaped with 12 for the next permutation, the resulting array: 9 8 12 4 66 is not in non-inc order
To make it in that order 66 is shifted to rightmost as 4 and 12 are brought before it in order. so that the resulting array
becomes: 9 8 4 12 66 . This will give the next permutation and swapping 12 and 66 with give the next to next permutation.
Hope its clear.
///////////////////////////////////////////////////////////////////////////////////////////////
Iterative Program logic explaination of function: alternateLettersAndNums()
initial: 1 2 3 4 5 6 7 8 | a b c d e f g h
step 1a: 1 [2] 3 [4] 5 [6] 7 [8] | [a] b [c] d [e] f [g] h
leaving 1 element from start, elements selected from step 1a in [] are swapped respectively with elements after the bar: '|', resulting in:
Step 1b: 1 [a] 3 [c] 5 [e] 7 [g] | [2] b [4] d [6] f [8] h
Step 2a: 1 [a] {3 [c]} 5 [e] {7 [g]} | {[2] b} [4] d {[6] f} [8] h
leaving 2 element from start, elements in group of 2 with in {} are swapped with elements with in {} after bar, resulting in:
step 2b: 1 [a] [2] b 5 [e] [6] f | 3 [c] [4] d 7 [g] [8] h
Step 3a: 1 [a] [2] b {5 [e] [6] f} | {3 [c] [4]} d 7 [g] [8] h
leaving 4 element from start, elements in group of 4 with in {} are swapped with elements with in {} after bar, resulting in:
Step 3b: 1 [a] [2] b {3 [c] [4] d} | {5 [e] [6] f} 7 [g] [8] h
Final o/p: 1 a 2 b 3 c 4 d 5 e 6 f 7 g 8 h
/////////////////////////////////////////
Program:
/*
Constraints met:
Space complexity: In-Place, O(1)
Time Complexity: O(N):
*/
#include<stdio.h>
#include<math.h>
static void swap(char a[], int s, int e, int len)
{
int i=s, j=e, temp=0;
for(i=s; (i-s+1<=len)&&(i); i++, j++)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
void alternateLettersAndNums(char arr[], int len)
{
int jumps, i, k, no, ch, temp;
int c = (len + 1)/2;
for(jumps=0; (i = (int)pow((double)2, jumps))<(int)len/2; jumps++)
{
i = (int)pow((double)2, jumps);
for(k=0; k < c; k+=i*2)
{
no = i+k;
ch = c+k;
swap(arr, no, ch, i);
}
}
return;
}
void alternateLettersAndNumsDriver()
{
int i;
char A[] = {'1', '2', '3', '4', '5', '6', '7', '8', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
printf("\nGiven array:\n");
for(i=0; i<sizeof(A)/sizeof(char); i++)
printf("%c ", A[i]);
alternateLettersAndNums(A, sizeof(A)/sizeof(char));
printf("\nAfter alternating:\n");
for(i=0; i<sizeof(A)/sizeof(char); i++)
printf("%c ", A[i]);
return;
}
/////////////////////////////////////////////
Repallisonepollard, Applications Developer at Accenture
I am Allison from Germantown. I work as a Staff manager at The LawnGuru company. But my interest in blogging ...
Hi Ganesh,
- pavi.8081 March 11, 2014Solution is gud for single digit numbers in the array. But it will not handle numbers with double/triple digits in the series like this:
a10b11c12d13.....