varun
BAN USERvoid swap(Node* parentQ, Node* Q, Node* parentR, Node* R) {
if(!parentQ) {
start = R;
} else {
parentQ->next = R;
}
if(!parentR) {
start = Q;
}else {
parentR->next = Q;
}
Node* temp = Q->next;
Q->next = R->next;
R->next = temp;
}
void alternateReverse() {
if(isEmpty()) {
cout<<"\nEMPTY LIST...";
return;
}
if(!start->next) {
cout<<"\nONLY ONE ELEMENT IN LIST...";
return;
}
Node *P = NULL, *Q = start, *R = start->next;
start = R;
while(R) {
swap(P,Q,Q,R);
P = Q;
Q = Q->next;
if(!Q)
return;
R = Q->next;
}
}
for (int i = 0; i < target.length ; i++)
Here target contains N*N elements and ignoring the inner for loop, this iteration itself is O(N^2).
Isn't this a O(N^3) solution?
I tried doing same yesterday, keeping i (index in target 1-D array) fixed and finding the candidates for index i. There are over N candidates for a position.
For position (0) there are 0 candidates, (0,0) is the smallest.
For position (1) there are N candidates, N-1 candidates in column1 and 1 candidate at (o,1).
For position (2) there are 2N-2 candidates, elements in column0 and column1 excluding those that have been picked for 0th and 1st index.
I tried various approaches but I couldn't do better than O(N^2logN) and I think that's the best we can do. Atleast I am not able to think of any method that gives next element in target 1-D array in O(1) time and every element needs to be scanned atleast once O(N^2).
Please let me know, if I am missing something.
Why O(nlogn) solution when you are using O(N) extra space?
If you are given O(N) extra space then you can do it in O(N) time.
1. Scan the input array and count no. of positive elements (countP) and negative elements (countN).
2. Populate output array (extra space) .
scan input array from left to right
for i = 0 to i = size-1.
3. if arr[i] > 0 then output[countN] = arr[i]; countN++
4. if arr[i] < 0 then output[countP] = arr[i]; countP++
Please take care of boundary cases when there are no -ve or +ve elements in the array.
Easy enough, you don't even need the matrix for given example
consider a = 0, b=1,....z=25.
we have a 5x5 matrix, coordinate of a = 0,0 , b =0,1 and so on.
coordinate of an alphabet is (n/5, n%5) n=> integer value of alphabet, (a=0...z=25).
scan the input string left to right, "CON"
coordinates of C in given matrix, is ( 2/5 , 2%5) = (0,2).
coordinates of O in given matrix, is (14/5 , 14%5) = (2,4).
coordinates of N in given matrix, is (13/5, 13%5) = (2,3).
so problem reduces to giving direction for reaching 2,3 from 0,0 and from given path.
(0,0) -> (0,2) -> (2,4) -> (2,3).
first reduce distance vertical distance
0,0 to 0,2 difference on x =0-0 hence print nothing for x.
Now reduce distance on horizontal distance
0,0 to 0,2 difference on y=+2 hence print right 2 times, if value is -ve print left difference no. of times.
now we are at (0,2) have to go to (2,4).
again reduce distance on vertical axis first.
(2,2) from (0,2) distance = +2 hence print down 2 times, if difference is -ve print up difference no. of times.
reduce distance on horizontal axis,
(2,4) from (2,2) distance = +2 hence print right 2 times.
(2,3) from (2,4) print distance on horizontal axis = -1 print left one time.
how about scalability of this solution?
can we extend it for any configuration of matrix as well?
Yes we can, in that case create a hash map, that will store coordiantes of each alphabet.
This can be done by scanning the given matrix as part of pre-processing step.
Now, once you get input string, you immediately have coordinates of each alphabet and problem again reduces to printing path from source to destination. This part of above solution remains unchanged.
People down vote without even understanding the post, bad.
can anyone write a code for inplace 90deg rotation of MXN matrix?
If some can, I am more than happy to accept the downvote.
Rotating a MxN array is trivial if you have extra O(NM) memory.
simply copy contents of current cell to new cell.
RotatedA[col][M-1-row] = A[row][col]
Traverse input array and just copy content of current cell to new cell, O(NM) solution I don't understand the difficulty part here.
Are you sure this BST approach always work?
how you are constructing your BST to be sure search time is O(logn) (balanced BST).
I suppose you need to sort the given set and then build the BST to get O(logn) search time.
If we are ignoring this fact, then yes BST approach will give the correct and optimized solution.
oh yes, absolutely.
stacks/queues/LL were eliminated in step-2 only, I was just trying to demonstrate how to approach a problem like this.
looking at requirement 1,2 and 3 Hashtable was an obvious choice .
And arrays offer random access so best choice for 4th requirement.
how to merge hash + array that was the basic question.
Get leaf node at max depth and get leaf node at minimum depth, if difference is greater than 1 then tree is not balanced.
Inorder/preorder/postorder any of the 3 traversal can be modified to get maxdepth and mindepth.
below is the code for maxdepth similary min depth can be found.
ms-amazon.blogspot.co.uk/2012/08/calculate-depth-of-binary-tree.html
complexity : O(n)
I am not sure if below solution is correct as problem doesn't state what is valid pair clearly.
My validity criteria is there should always be opening bracket before closing bracket.
void printAll(int cleft, int cright, int sleft, int sright, int pleft,int pright, string str) {
if(cleft>0) {
printAll(cleft-1,cright,sleft,sright,pleft,pright,str + "{");
}
if(cright>cleft && cright>0) {
printAll(cleft,cright-1,sleft,sright,pleft,pright,str + "}");
}
if(sleft>0) {
printAll(cleft,cright,sleft-1,sright,pleft,pright,str + "[");
}
if(sright>sleft && sright>0) {
printAll(cleft,cright,sleft,sright-1,pleft,pright,str + "]");
}
if(pleft >0) {
printAll(cleft,cright,sleft,sright,pleft-1,pright,str + "(");
}
if(pright>0 && pright > pleft) {
printAll(cleft,cright,sleft,sright,pleft,pright-1,str + ")");
}
if(pleft ==0 && pright ==0 && cleft ==0 && cright ==0 && sleft ==0 && sright==0)
cout<<"\n"<<str;
}
output:
when there is only 1 pair of each type of bracket.
{}[]() {}[(]) {}[()] {}([]) {}([)] {}()[] {[}]() {[}(]) {[}()]
{[]}() {[](}) {[]()} {[(}]) {[(})] {[(]}) {[(])} {[()}] {[()]}
{(}[]) {(}[)] {(})[] {([}]) {([})] {([]}) {([])} {([)}] {([)]}
{()}[] {()[}] {()[]} [{}]() [{}(]) [{}()] [{]}() [{](}) [{]()}
[{(}]) [{(})] [{(]}) [{(])} [{()}] [{()]} []{}() []{(}) []{()}
[]({}) []({)} [](){} [({}]) [({})] [({]}) [({])} [({)}] [({)]}
[(]{}) [(]{)} [(]){} [(){}] [(){]} [()]{} ({}[]) ({}[)] ({})[]
({[}]) ({[})] ({[]}) ({[])} ({[)}] ({[)]} ({)}[] ({)[}] ({)[]}
([{}]) ([{})] ([{]}) ([{])} ([{)}] ([{)]} ([]{}) ([]{)} ([]){}
([){}] ([){]} ([)]{} (){}[] (){[}] (){[]} ()[{}] ()[{]} ()[]{}
Lets see what we have in hand and what we have to do.
we have to perform Insert/Delete/Search/Get Random all operations in O(1).
It is clear there is no data structure that satisfies all the requirements, some support one of the operations, some 2 but neither supports all 4 operations.
By now, it is evident we have to use Hybrid of 2 or more data structures.
Now question we have in front of us is which ones?
Lets move operation by operation and we will keep the ones that are present in maximum operations.
1. O(1) Insert
==========
Stacks/Queues/Linked lists and hash tables support this operation, at this step BST, heap,Skip list, TRIE etc are eliminated.
2. O(1) delete
===========
question doesn't clearly specify delete what? first element, last element or any element?
If we have to delete first element than we go for queues, if we have to delete last element we select stack, if we have to delete any element then we opt for hash.
so contenders in the list till now are - stack/Queues and Hash table.
3. O(1) search
===========
At this step both stacks and queues are ruled out and only hash table remains in the list.
so at this step we are clear that one of the data structure should be hash table.
4. O(1) Get Random
================
we have selected hash as our choice of data structure for this problem, but hash fails to fulfill this requirement, hash requires key to fetch any element and we have no way of generating random keys...now what to do?
Let's follow the approach we were following in our earlier steps:
which data structure satisfies O(1) random access?
There is only one Arrays.
Just give index + starting address and boom array gives you the result in O(1).
But our problem is still not solved, how to use this property with hash and also how can we generate a random hash key??
re generating random key, it is clear it is something we can't do because key might or might not be present in hash table but there is one thing we can do we can generate random integers.
How to use these random integers?
this is the final part of our solution simple keep all hash keys in an array, use a random number generator to generate a random number between 0 and totalNumberofkeys-1.
Fetch the key stored at this index O(1) and get value corresponding to this key O(1) again and return the result.
keeping array for storing keys involve inserting keys in array (insert op) and also deleting keys in array (delete op), I'll leave that to you guys for implementation.
use Randomize selection algo or median of median Algorithm.
Median of median promises a tighter upperbound of O(n) as compare to randomize select O(n2)
But in practise randomize select is faster as compare to median of median as constants in median of median are large.
Edit:
In my opinion Median of Medians is slower as compare to QuickSelect with randomly chosen pivot in practice (never tested on large data).
Although worst case is O(N2) for Quickselect where as it is O(N) for median of Medians but it is near to impossible to produce worst case scenario for randomly chosen pivot.
I just posted an article on quick select on my blog, too lazy to explain it here as well, interested user can find the code + explanation + linear time complexity analysis (brief) at below link:
ms-amazon.blogspot.in/2013/10/quick-select-select-kth-smallest.html
In case I get some time, I'll post Median of Medians as well.
Hope it helps.
cheers :)
You cannot rotate a MxN matrix in-place.
MxN matrix means M - rows and N - columns and on rotating it by 90deg, rows change to columns and columns to rows i.e. M-columns and N-rows which calls for allocating new matrix of size NxM in memory.
1 2 3 4 5
6 7 8 9 10
when rotated 90deg clockwise forms.
6 1
7 2
8 3
9 4
10 5
Please let me know if have not understood the question properly.
The function of load balancer is to distribute the load on all available backends equally.
Assuming load balancer has details of load of all backends, now if new request comes it should be directed to the backend with minimum load and this can be done in O(1) using min Heap data structure.
1. Request arrives at load balancer.
2. Load balancer picks the minimum load backed and route the request to it.
3. Load balancer increases the load on this backend server and performs heapify operation. O(logn).
Below is the efficient code of doing it,
Time : O(n2)
Space: O(1) Inplace.
complete implementation and logic can be found at : ms-amazon.blogspot.in/2013/05/rotate-matrix-90-degrees-clockwise.html
void setNewIndex(int &row, int &col, int N)
{
int temp = col;
col = N - 1 - row;
row = temp;
}
void moveCyclic(int row , int col , int N)
{
int temp1 = matrix[row][col];
int temp2;
for(int k=1; k<=4; k++)
{
setNewIndex(row,col, N);
temp2 = matrix[row][col];
matrix[row][col] = temp1;
temp1 = temp2;
}
}
so what?
I gave it as second best option.
Hashmap takes O(n) and if BST is second best it meant it takes more than Hashmap O(nlong).
BST have the property of identifying the duplicates in O(logn) by which I meant searching and finding duplicates, and I have not mentioned building BST will take O(logn).
The question is more interested in knowing the data structures that have the property of identifying duplicate elements.
which I have correctly pointed out to :
1. Hashmap
2. BST
3. SkipList.
Consider you have 1000 elements and you want to eliminated duplicates, you don't have inbuilt Hash implementation/BST implementation which data structure will you implement?
If you say Hash
Hash will require implementation of a good hash function that evenly distributes which is a complex task.
It will also require collision resolution by chaining or whatever implementation.
In the above case I will rather opt for BST.
Now lets assume the data I have is partially sorted in this case I will get a degenerated tree which increases the complexity in this case I will opt for skip list it will take O(nlogn) space but for 10000 elements it is managable given O(logn) search time guaranteed each time.
So on basis of the size of data/search time/ space available we have different options to opt for.
I am not sure whether your approach will work for all the cases, not read the complete code just had a glance seems like you are using array representation of binary tree which will lead to correct answer only in cases binary tree is complete.
And also finding lowest common ancestor can be done without extra space (ignoring recursion stack space) I have pasted the code in my comments.
Simple:
1. First check whether both the nodes exist in the tree? (skipping for simplicity)
2. Find the lowest common ancestors of both the nodes.
3. Trace path to node1 from LCA node.
4. Trace path from node2 to LCA node.
Let node1.val = val1
and node2.val = val2
node* LowestCommonAncestor(node *ptr, int val1, int val2)
{
if (!ptr)
return NULL;
if (ptr->getData() == val1 || ptr->getData()== val2)
return ptr;
node *left = LowestCommonAncestor(ptr->getLeftChild(), val1, val2);
node *right = LowestCommonAncestor(ptr->getRightChild(), val1, val2);
if (left && right)
return ptr;
if(left)
return left;
else
return right;
}
For tracing path to the node:
LCA = LowestCommonAncestor(root,item1,item2)
trace(LCA,item1);
trace(LCA,item2);
int equal=0;
void trace(node *r,int item)
{
if(equal==1)
return;
if(r->data==item)
equal=1;
if(r!=NULL)
{
trace(r->left,item);
trace(r->right,item);
if(equal==1)
cout<<" "<<r->data;
}
}
Easy, considering dictionary is implemented using TRIE.
keep a string word Initialized with "" (empty string)
Keep a string sentence initialized with "" (empty string)
String input, is the input sentence without any spaces.
scan input from left to right.
for i=0 to i = input.length
{
//Add alphabets to word.
word += input[i]
//check if word forms any word in dictionary?
// If yes add word to sentence followed by a space.
if(dictionary.isWord(word))
sentence += word + " ";
// If word forms prefix of any word in dictionary then continue;
else if(dictionary.isPrefix(word))
continue;
else
return invalid sentence.
}
cout<<sentence;
@chih.chiu this is a separate question, I have coded it for the case where all elements are unique in array.
Complexity:
Time : O(n)
Space: O(1)
void sort(int arr[],int size)
{
int pos = 0;
while(pos <size)
{
int desiredPos = arr[pos]-1;
if(pos == desiredPos)
{
pos++;
continue;
}
else
{
swap(arr,pos,desiredPos);
}
}
}
But giving a second thought to it, why do we even need to sort it when range is given?
All element are unique, we should simply overwrite the values and continue moving forward in array.
Sorry forgot to mention it will take O(1) space.
The simplest sorting algo with O(1) space and O(n) time complexity must have 2 conditions all elements must be in some range and all elements must be unique.
I believe this approach can be extended to arrays not satisfying the second condition, that will require some thinking.
In above I have not sorted instead manage to store the frequency without sorting, You can follow the other approach as well.
@sibendu If you are using counting sort then yes it will.
Given range of array you can sort it in O(n) time.
And by range I mean no. of elements in range must be equal to the number of elements in array.
for eg. if we have 10 int array and range is (1,100) (any 10) then it is not possible but if range is (20,30) yes in this case it is possible.
@vishnu yes you are right, I missed it thanks for pointing out.
@algos It words for your example, just try introducing continue as vishnu suggested.
Output for your example:
Element = 1 Frequency = 0
Element = 2 Frequency = 0
Element = 3 Frequency = 0
Element = 4 Frequency = 0
Element = 5 Frequency = 0
Element = 6 Frequency = 0
Element = 7 Frequency = 1
Element = 8 Frequency = 1
Element = 9 Frequency = 9
Element = 10 Frequency = 0
Element = 11 Frequency = 0
It says that given an array of n integers.
Below is the output generated for array arr[] = {6,4,1,4,3,2,5,2,1};
Element = 1 Frequency = 2
Element = 2 Frequency = 2
Element = 3 Frequency = 1
Element = 4 Frequency = 2
Element = 5 Frequency = 1
Element = 6 Frequency = 1
Element = 7 Frequency = 0
Element = 8 Frequency = 0
Element = 9 Frequency = 0
It was not as simple as I thought in first go, but with a little thinking I was able to code it.
void getDuplicate(int arr[],int size)
{
int pos = 0;
int desiredPos = 0;
while(pos < size)
{
if(arr[pos] <= 0)
{
pos++;
}
desiredPos = arr[pos] -1;
if(arr[desiredPos] > 0)
{
arr[pos] = arr[desiredPos];
arr[desiredPos] = -1;
}
else
{
arr[desiredPos]--;
arr[pos] = 0;
pos++;
}
}
}
you can check the complete executing code with explanation at : ms-amazon.blogspot.in/2013/07/you-are-given-array-of-n-integers-which.html
- varun July 15, 2013First Let's see what all approaches we can take and then we check if it fits our requirement.
1. Brute Force: Select an element from 1 to N and check it frequency of occurrence. But this will be O(n2) and not O(n) .
2. XOR : but this technique won't work as question mentions an element can be repeated multiple times. so if element repeats 2 times or 4 times each time result of xor will be 0 so we cannot get the frequency of occurrences.
3. HashMap : We can create a HashMap in O(n) key will be elements and value will be their frequency of occurrence. But since we have to do it in O(1) space we cannot take this approach.
So we cannot opt for any of the above 3 approach. We have to check for some 4th approach.
Since we have range of numbers given to us we have to think in those lines.
Array Index is from 0 to N-1 and range is from 1 to N.
Can't we use the array as hash itself?
where array "Index-1" represents the key (element) and value stored at index will represent the "frequency of occurrence".
But how will we take care that an element present at any index is not overwritten as this can cause problem?
We can sort the array in that case value present at index i is I+1 itself.
What is the complexity of sorting the array?
O(nlogn) if we opt for heap/merge/quick sort.
But since the range of element is given to us we can sort it in O(n).
Below is the recursive code for finding all words in a matrix.
I have considered all posssible 8 directions from any given cell which can be modified according to what is asked.
A cell can constitute to only one word and hence if it is a part of any word I have marked it with a '*'.
bool solveMatrix(int row,int col, string word)
{
if(word.compare("*") ==0)
return false;
if(dictionary.search(word))
{
cout<<"\n"<<word;
matrix[row][col] = '*';
return true;
}
for(int i=0; i<MAXNEIGHBOURS ; i++)
{
int newRow = row + displacement[i][0];
int newCol = col + displacement[i][1];
char originalCharacter = matrix[row][col];
matrix[row][col] = '*';
if(isValid(newRow,newCol))
{
if(solveMatrix(newRow,newCol,word+matrix[newRow][newCol]))
return true;
}
matrix[row][col] = originalCharacter;
}
return false;
}
complete executing code can be found at ms-amazon.blogspot.in/2013/07/print-all-words-in-matrix-cbk-dal-gti.html
- varun July 14, 2013Simple backtracking algorithm.
I have used a TRIE for storing the dictionary.
const int DIM = 3;
const int MAXNEIGHBOURS = 8;
int displacement[8][2] = {{-1,-1},{0,-1},{1,-1},{1,0},{-1,1},{0,1},{-1,1},{-1,0}};
char matrix[DIM][DIM] = {{'c','a','t'},{'a','j','i'},{'t','n','o'}};
bool solveMatrix(int row,int col, string word)
{
if(word.compare("*") ==0)
return false;
if(dictionary.search(word))
{
cout<<"\n"<<word;
matrix[row][col] = '*';
return true;
}
for(int i=0; i<MAXNEIGHBOURS ; i++)
{
int newRow = row + displacement[i][0];
int newCol = col + displacement[i][1];
char originalCharacter = matrix[row][col];
matrix[row][col] = '*';
if(isValid(newRow,newCol))
{
if(solveMatrix(newRow,newCol,word+matrix[newRow][newCol]))
return true;
}
matrix[row][col] = originalCharacter;
}
return false;
}
This code can be further optimized with little tweaks to search function of trie such that it can return 3 possible values.
0 - no sequence with current word as prefix.
1 - Sequence like current word is present in trie but it is not the complete word only the prefix.
2- It is complete word.
We can continue search only in case of 1, when 2 is returned word is found and when 0 is returned no use of searching further.
/*
1. Scan pre-order from left to right and search the encountered node in given in-order array.
2. Store position of element in pos.
3. Construct node having value inorder[pos].
4. Divide inorder in left (start, pos-1) and right (pos+1,end).
*/
private int[] preOrder = {50,30,20,40,35,45,70,60,80};
private int[] inOrder = {20,30,35,40,45,50,60,70,80};
private int prePos = 0;
public int searchInOrder(int s , int e , int n)
{
for(int i =s ; i <= e; i++)
{
if(inOrder[i] == n)
return i;
}
return -1;
}
public BSTNode createTree(int start, int end)
{
if(prePos >= preOrder.length)
return null;
BSTNode newNode = new BSTNode();
newNode.setData(preOrder[prePos++]);
if(start == end)
{
return newNode;
}
int pos = searchInOrder(start,end,newNode.getData());
newNode.setLeftChild(createTree(start, pos-1));
newNode.setRightChild(createTree(pos+1, end));
return newNode;
}
public void buildTree()
{
prePos = 0;
root = createTree(0,preOrder.length-1);
}
BST tree = new BST();
tree.buildTree();
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
Kth order statistic will work when all elements can be stored in main Memory.
- varun October 26, 2013I am not sure if we can use secondary storage for implementing kth order statistic.