chennavarri
BAN USERFeel free to contact me for my resume.
chennavarri@gmail.com
 0of 0 votes
AnswersXbox for Zombies:
 chennavarri
There are 10 zombies wating for the new Xbox in a line at a store. The store has 4 lanes, i.e. 3 waiting lanes and 1 purchase lane. The zombies are standing in the first waiting lane (ordered 1st to 10th)
All zombies have to end up in purchase lane in the same order, you can use the other waiting lanes and can move only one zombie at a time. You can talk to and move only the front zombie in any lane if you talk to any other zombie behind the first one then it will eat you. Ex: if zombies 3,6,7 are in lane 2 then you have to move zombie 3 to other lane if you want to move zombie 6.
Also, if the i'th zombie sees any zombie greater than i in the same lane then it will kill all zombies. Ex: if zombie 4 sees zombie 5 or greater in front of it in the same lane then all zombies will be killed.
And you can only move zombie's from the front of the lane, the back of the lanes are closed. So if you move zombie3 to purchase lane then only zombies 1&2 can be moved to that lane because any other zombie greater than 3 cannot stand in front of zombie3.
Think of the lanes as a stack.
In how many moves can you move all zombies into purchase lane without killing yourself and any zombies? Report Duplicate  Flag  PURGE
Software Engineer / Developer Algorithm  0of 0 votes
AnswersThere are n princesses, there is one lamp inside a tower. A princess is picked randomly with repetitions and she can turn on or off the lamp. The princesses are picked infinitely. The princesses have to come up with a strategy to count the number of princesses by using the lamp information. (here lamp is a single bit, it can be on or off).
 chennavarri Report Duplicate  Flag  PURGE
Software Engineer / Developer Algorithm  0of 0 votes
AnswerProblem:
 chennavarri
Given a board containing 64 squares cover it with peices of paper as small as 1 square and as big as 64 (can be of any shape but should not exceed chessboard boundaries).
If choosen a random square from the 64 squares, what is the least number of pieces of paper is required area to cover the remaining board and their shape? (you can rotate pieces of paper)
Also give a generalized solution for a board of size 2^k. Report Duplicate  Flag  PURGE
Monitor Group Software Engineer / Developer Algorithm
I did, this was long time ago..
so deleted my post
subsequences if the array is sorted??
if so, why not 2 4 5, 2 4 6....etc..??
if no, then why is 1 2 6 an answer?
Yep, this is good
 chennavarri February 10, 2011I believe internally the compiler would still be passing n references for the complete recursion cycle. anyways, the solution by S is the best one I think.
 chennavarri February 10, 2011@Salmok: a small modification. you could just set the value of the key in the hashtable instead of using a separate bitset. That should reduce some space. but ya, as u mentioned hashtable could take space more than O(n)
 chennavarri February 10, 2011doesn't work, try on this 5,12,3,13,10,9,4,6,23,8,7. The answer should be 3,4,5,6,7,8,9,10.
A simpler example would be 3,1,4,2,5. answer 1,2,3,4,5
Look at Animation of NN searching with a KD Tree in 2D on wiki
that might help visualize. thanks
If you unroll the recursion what's happening is the algo is creating a 'n' additional pointers by passing head>link.
so basically all the algo is doing is constructing an array of additional pointers to each element and is visiting them in the reverse order and simultaneously comparing by to element at 'h1' in the forward order.
i.e. using an additional space of O(n) {array of n pointers}
Also a small suggestion on the terminology, people usually refer to next element as "head>next" rather than "head>link"
thanks
ya, as @gekko says; thats not a good answer.
 chennavarri February 09, 2011Here's a O(n) without any extra space and without multiplication or addition (because factorial requires special datatype/datastructure)
// since we know there are n numbers in an array of size n all we want is to swap the numbers to their corresponding positions i.e. move '1' to 0th position, move '2' to 1st position ...etc.
if the number already exists in its position then its a duplicate and we set it to (n+1) or 1 i.e. something we can identify. Basically 2 traversals will give u the missing spot.
> for(i=0;i<n;++i){
if(array[i]<0) //is less than zero only when we set the duplicate to 1, look below
continue;
if array[i]==i+1 //in the right position
continue;
else{
if(array[i]==array[array[i]1]) //then its a duplicate, set it to 1
array[i] = 1
else
swap(array[i],array[array[i]1])
}
}
//by the end of the above loop we have all elements in their corresponding positions and 1 in the place of the missing number
> traverse the array and print out the position+1 of the the element with value == 1
//complexity analysis: no matter what the for loop will run 'n' times > (n)
//traversal for finding the missing spot > (n)
total complexity: O(n)

chennavarri
February 09, 2011 @Sathya, yep as gekko pointed out this solution can have cycles and one way to avoid cycles is by using extra space. This question is a duplicate and I posted a similar solution which had the same issue, can't find the duplicate question using CC's search
 chennavarri February 09, 2011Traversing hash tables might be O(n) but traversing doesn't happen in sorted order i.e. if 13,4,25,6,5,7 are inserted into the hash table then while traversing it doesn't traverse 4,5,6,7 in consecutive order.
 chennavarri February 09, 2011so from the example I undertand that the question is : given an unsorted array, find the longest consecutive sequence if the array was sorted? in O(n) time?
This can be done in O(max(array)) time with O(max(array)/8) space.
1. Find the max of array. Create a bitset of size=MAX
2. As we traverse the input array set the position in the bitset to 1.
3. Now traverse the bitset for the consecutive 1's.
Not sure if this can be done in O(n)
find 1st minimum O(n)
find 2nd minimum O(n)
total = O(n)
you could also do these together in one loop which is again O(2n) ==> O(n)
space = O(1)
thanks.
what kind of tree is it? and how is the tree stored?
 chennavarri November 17, 2010well.. if we modify the binary search algo we can make it O(logn) i.e. the worst case happens only when num1 is repeated till the starting and num2 is repeated till the end.
so once we find num1 using binary search we can still do binary search to the left of num1 to find the first occurence of num1, which is again log(n) complexity
so on the whole the worst complextiy would be O(2(logn+logn)) ==> O(logn). Ex:
//The worst case scenario is as shown below
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
num1 = 4, num2 = 8
First binary search and find num1 at array[15]
Second binary search to left the of num1 to find first occurrence of num1, we find num1 at positions 7, 3, 1, 0
so two binary searches to find the first occurrence of num1, similarly for num2.
And we get O(4logn) == O(logn)
If we do a linear search most cases tend to O(n).
Feel free to make suggestions. Thanks
Given num1&num2 , num1<num2. Array A
Do a binary search for num1
If found then move towards A[0] until A[i]==num1 because there can be dups
Else get lower bound (STL has lower bound for binary search)
Repeat for num2
Return values between these indices
Complexity worst case O(n) best case O(logn)
Worst case example : num1: 4 num2: 8
Array: 4,4,4,4,4,4,4,4,4,4,4,4,8,8,8,8,8,8,8,8,8,8,8
@Kannan: I prefer your solution but interviewers wont accept it because the solution has to be successful in all cases when compared to a worser complexity algorithm. Sort and compare for this problem will work for a case like below
a1 = [ (2^128−1) , 2^127 , 4, 1, 2, 10]
a2 = [ 2 , 4, 1, 10, (2^128−1), (2^128−1)]
If you sort both and compare then it would definitely work.
But your code would fail. The algo you wrote is a really good approach. But as blue_skin points out, there are constraints to your solution as >0 and datatype range
Thanks
@shashi: Well, merge sort can be done inplace but complicated. thomas baudel has a variant of inplace merge sort.
But if there's a simpler inplace sort for merging k sorted arrays then please suggest. Thanks
I think you got confused.
There are n/k sorted arrays of length k. (you are thinking the other way i.e. there are k arrays of length n/k. thats wrong understanding)
So merging two arrays of length k is O(k), it's basically merge sort. For example, in merge sort you start of with k=1, so complexity is O(n/1 log (n/1)) ==> O(n logn). Thanks.
I'll try a heuristic,
the middle boxes are surrounded with more number boxes, our goal is to not to have neighbors. so lets take a number from 1 to 8 that has less neighbors which is either 1 or 8.
place it in the middle 4 boxes then alternatively place continuous elements
 1    1  2  1  2  1  2
         3    3  4
and then
5 1  2 5 1 6 2 5 1 6 2 5 1 6 2
 3  4  3  4 7 3  4 7 3 8 4
you could try selecting different box for 1 as below:
          3  4  3 
  1  2  1  2  1  2  1 
and then
4  3  4  3  4  3 7 4 8 3 7
2  1 5 2 6 1 5 2 6 1 5 2 6 1 5
feel free to suggest advanced heuristics. thanks
 chennavarri November 11, 2010so The question is find and delete duplicates in an array of size N with a max value N in time complexity O(N), and space O(1).
I wrote the right solution, there's no 'n'. There's only N which is the size of the array and max of the array.
damn it.. someone got me confused somewhere
buddy..you are not getting the point. the point is not about n or N. The point is whatever may be the size of array, the algorithm doesn't use any extra space.
For example: consider n = n1, if the program takes n1+k bytes of memory. then for n = n2, the program takes n2+k bytes of memory, the algorithm takes k bytes of memory irrespective of value of n. so the space complexity = O(k) ==> O(1). I hope this helps
Hash tables have high insertion complexity but other operations are constant time depending on the hash function. hashmaps or unordered are implemented using this.
RBTrees is the widely used balanced binary tree which has logn for all operations. and not so easy to implement. Maps are implemented using this structure
So it depends on the application, if you know approx. what the size of your data would be then hashmaps are the best if not you need to choose.
An easier alternative to RBTrees are skip lists which are much easier to implement but same performance.
anyways, please reply your perspective on this problem. Thanks
From a perspective this is a sorting problem and whose solution is nlogn
5log5 = 7 or 8, it depends on the input order. correct me if wrong. Thanks
A hash table is an associative container that maps a key to a value. a key can be a string or anything that has a operator==() and hash() function defined.
In addition, to ensure maximum performance, the hash function should be designed in such a way that if x != y
Very useful when insertion is done once and primarily used for searching using a key.
For implementing a hash table, things to keep in mind:
Choosing a hash function.
Data structure which can dynamically resize, [vectors or array lists]
Taking care of collisions
A possible solution but maybe not the best would be using a hashmap.
Time: O(n)
Space: O(n)
if only computational complexity is important then this would be the best. Thanks
what??/ how ??
 chennavarri November 09, 2010yep.. as Anon pointed out, the question is incomplete without the measurement mechanism,
if measured using a balance i.e. comparison of weights then it would take lesser measurements in some cases
if measured using a digital scale then its different again.
Thanks
ashpiy: thats not totally true. I changed the solution a little bit but anyways, as Anon commmented, the problem is given 10 coin stacks, 9 of them are 100gms and 1 is 90 gms,
if stack 6 is 90gms then (55005440)/(10090) = 6
if stack 1 is 90gms then (55005490)/(10090) = 1
thanks
Sieve of eratosthenes is a really simple implementation. A person asking this question should be aware of this solution. i explained this in my interview and the interview got it right away because it doesn't make sense if you dont know the optimal solutions
 chennavarri November 09, 2010yep.. I gave the same solution today. One is a fast pointer and the other is a slow one
 chennavarri November 09, 20102. Take 1 coin from the first, 2 from second, 3 from third..., and weigh them all together
if total weight = x grams, then (5500x)/10 is the stack number.
All assuming a digital scale. If we have a weighing balance then I believe its much easier problem
1. Reverse
//!Function reverses an input list
void reverseList(Node*& head){
Node* curr = head;
Node* nxt = head>next;
curr>next = NULL;
while(true){
head = nxt;
if(head>next==NULL){
head>next = curr;
break;
}
nxt = nxt>next;
head>next = curr;
curr = head;
}
}
2. Check if the current value is less for every node and insert
 chennavarri November 09, 2010/*Solution Code to algorithm suggested by lanse.cse
1. reverse the lists.
2. add them digit by digit and construct the result list.
3. reverse the result list.
NOTE: This code demonstrates the solution. The code will fail for invalid or no input and maybe other cases. Output for the following code : 9,1,3,1,3,8
*/
#include <iostream>
using namespace std;
//! Node to store digits
struct Node{
short digit; //doesn't make a difference if I use short or int
Node* next;
};
//!Function reverses an input list
void reverseList(Node*& head){
Node* curr = head;
Node* nxt = head>next;
curr>next = NULL;
while(true){
head = nxt;
if(head>next==NULL){
head>next = curr;
break;
}
nxt = nxt>next;
head>next = curr;
curr = head;
}
}
//! Function to compute the sum of two input lists. Complexity: O(m+n), sizes of lists m,n
void sumOfLists(Node*& list1, Node*& list2, Node*& result){
// Reverse lists: Time: O( m + n). operating on input lists to save space complexity
reverseList(list1);
reverseList(list2);
Node* ptr;
ptr = new Node();
result = ptr;
int n1=0,n2=0,sum=0,carry=0;
bool n1flag=true,n2flag=true;
while(n1flag  n2flag){
n1= n1flag?list1>digit:0;
n2 = n2flag?list2>digit:0;
sum = n1+n2+carry;
carry = (sum>=10)?1:0;
ptr>digit = (sum10*carry);
if(n1flag)
if(list1>next==NULL)
n1flag = false;
else
list1 = list1>next;
if(n2flag)
if(list2>next==NULL)
n2flag = false;
else
list2 = list2>next;
if(n1flag  n2flag){
ptr>next = new Node();
ptr = ptr>next;
}else
ptr>next = NULL;
}
reverseList(result);
}
void printListValues(Node*& list){
Node* ptr=list;
do{
cout<<ptr>digit<<",";
ptr = ptr>next;
}while(ptr>next!=NULL);
cout<<ptr>digit<<endl;
}
int main(){
//construct two lists, replace the below digits to test your values
int myNum1[] = {9,1,2,3,2,9};//First list 912329,
int myNum2[] = {0,8,0,9}; //second list 0809
Node *newNd1, *num1, *num2, *result;
newNd1=new Node;num1 = newNd1;
int sz = sizeof(myNum1) / sizeof(int);
for(int i=0;i<sz;++i){
newNd1>next = (i==sz1)?NULL:(new Node);
newNd1>digit = myNum1[i];
newNd1=newNd1>next;
}
newNd1 = new Node;num2 = newNd1;
sz = sizeof(myNum2) / sizeof(int);
for(int i=0;i<sz;++i){
newNd1>digit = myNum2[i];
newNd1>next = (i==sz1)?NULL:(new Node);
newNd1=newNd1>next;
}
//Find sum
sumOfLists(num1,num2,result); //. Result should be 913138
printListValues(result);
}

chennavarri
November 09, 2010 Code based on comment from Anonymous' comment
//dp[i][j] = max(dp[i1][j],dp[i][j1])+a[i][j];
/* //! Complexity for a nxn matrix is O(nxn) i.e. Linear (since nxn elements)
*/
#include <iostream>
#include <vector>
using namespace std;
int main(){
int arr[4][4] =
{ { 1,7,5,2 },
{ 5,12,3,6 },
{ 100,9,23,16 },
{ 16,4,5,9 },
};
int n=4;
vector<vector<int> > maxRoute(n,vector<int> (n,0)); //initialize vector
//dp[i][j] = max(dp[i1][j],dp[i][j1])+a[i][j]; //Dynamic programming //from Anonymous
for(int i=0;i<n;++i){ //move right
for(int j=0;j<n;++j){ //move down
if(i==0 && j==0)
maxRoute[i][j] = arr[i][j];
else if(i==0 && j!=0)
maxRoute[i][j] = arr[i][j]+maxRoute[i][j1];
else if(i!=0 && j==0)
maxRoute[i][j] = arr[i][j]+maxRoute[i1][j];
else
maxRoute[i][j] = max(maxRoute[i1][j],maxRoute[i][j1])+arr[i][j];
}
}
cout<<"Max grass ::"<<maxRoute[n1][n1]<<endl;
}
please suggest if any thing's wrong,Thanks.
 chennavarri November 08, 2010Okay. so my bad.. i was assuming a binary matrix, thought the goat traverses only connected components in a binary matrix. Thanks Ankur
 chennavarri November 08, 2010I've edited the comment to change complexity analysis, it didnt change. Complexity would be
==> O(n/k * (k+log(n/k) ) )
Best case would be O(n/k * log(n/k))
Hey, just saw your comment.
Ya. It would make a difference. If the length of sequences are 'k' then there are n/k subsets which monotonically increase and then decrease. So once we find where the shift happens for a subset, now we can split this into two sorted arrays and merge. total: operations for every subset would be 2k (worst case)
In this way, we get all n/k subsets sorted in (n/k)*2k => 2n operations, now we merge n/k sorted arrays which should take (n/k)log(n/k). So total complexity would be O(2n + (n/k)log(n/k))
==> O(n/k * (2k+log(n/k) ) )
Best case would be O(n/k * log(n/k))
All of this with the condition that every k subset increases to a point and then decrease once. (Ex: the whole array can be a sine curve)
Correct me if am wrong. Thanks
@extinct: I was just lazy to write the deletion code, but anyways, added the code for moving duplicates to the end of the array, now, you can delete or truncate or .... anything.
again the complexity remains the same O(n) or O(4n), space complexity O(1).
papaya says, "the problem says numbers are in range of 1...N, but not necessary contain all number from 1 to N."
Yes, I know that. I am not assuming that.
what am saying is if there are numbers between 1 to N in an array and complexity is O(N) that means the size of array cannot be greater than N and no element is greater than N, right?
Now, if no duplicates exist then the array has to be of size N right?
Now if duplicates exist then after moving the elements to their correct positions you should be left with duplicates. If you try the following array
{3,3,3,3,3,2,2,2,2,2,2,4};
The algorithm will give,
Final Array :15,2,3,4,15,15,14,14,14,14,14,15,
Duplicates are :: 3,3,3,2,2,2,2,2,3,
Correct me if am wrong.
I have a feeling that the question is not complete. because here's a bruteforce O(n) solution.
Assume 'n' elements in each linked list,
construct an array from each linked list,
start from the end of the arrays and keep adding elements and storing into another array with carry. The max size of the second array can be 2n.
Build another linked list from the result array.
Time complexity: O(n + n + 2n + 2n) => O(6n) => O(n)
Space complexity: O(n + n + 2n) => O(4n) => O(n)
so what are we trying to optimize? space , time ? or something else?
 chennavarri November 07, 2010To make it n^2, you have to construct hashfunction that can compute a unique index for every unique input string. And then you can do direct indexing because every unique string would have a unique index in the hashmap. which should give you O(1) for finding/inserting in a hashmap
 chennavarri November 07, 2010Not n^3 but O(N^2*(logN))
Explanation:
The elements in a map are sorted and any operation for map takes logarithmic time.
Construction of Map:
Find operation takes logn because there are n strings.
But for finding, we need to match strings so matching operation takes n (because n elements in each row) total complexity of find operation = nlogn and for inserting = nlogn.
The first for loop runs n times and its inner loop runs n times, then find and insertion takes 2nlogn
total computations for constructing map=> n * (n + 2nlogn)
Searching if column matches any key in the map:
The same way computations => n * (n + nlogn)
Total complexity => O( (n*(n+2nlogn)) + (n*(n+nlogn)) ==> O(2n^2 + 3n^2(logn)) ==> O(n^2*(logn))

chennavarri
November 07, 2010 Pseudo Code:
Create a map that takes a string as key and vector<int> as data
For every row construct a string using the values. (for ex: "4:5:10:9:2:"
Check if your map already contains the key,
if yes then retrieve and add the row index
else insert a new item with this key and data as rowIndex
For every column construct a string using the values.
Check if your map contains the key
if yes then this column matches with all the indices in the 'data' for this key
else no rows exist that are same as this column
///Complexity: O(N^2 + N^2) => O(N^2)
#include <map>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
int main()
{
map<string, vector<int> > valStrings;
map<string,vector<int> >::iterator it;
string str;
int n = 4;
int matrix[][4] = { {2,2,2,15},
{2,2,5,5},
{15,5,2,2},
{15,5,2,2}};
vector<int> indxs;
for(int i=0;i<n;++i) //for every row
{
char bfr[4];
str="";
for(int j=0;j<n;++j){
sprintf(bfr,"%d",matrix[i][j]);
str.append(bfr);str.append(":");
}
it=valStrings.find(str);
if(it!=valStrings.end())
indxs = (*it).second;
indxs.push_back(i);
valStrings[str] = indxs;
indxs.clear();
}
for(int i=0;i<n;++i) //for every column find if there's a key already inserted
{
char bfr[4];
str="";
for(int j=0;j<n;++j){
sprintf(bfr,"%d",matrix[j][i]);
str.append(bfr);str.append(":");
}
it=valStrings.find(str);
if(it!=valStrings.end()){ //if key already exists then obtain row values
cout<<endl<<"Column "<<i<<" matches row(s) : ";
indxs = (*it).second;
for(int k=0;k<indxs.size();++k)
cout<<indxs[k]<<",";
indxs.clear();
}
}
}
//Column 1 matches row(s) : 1,
//Column 3 matches row(s) : 2,3,

chennavarri
November 06, 2010 got me .. :D
I didnt think about same values...
my bad... I didnt rebuild before running.. sorry :D
it is 1
Actually, it doesn't make sense. any random set of numbers can be said as increasing and decreasing. For example, I just pressed numbers randomly on the keyboard and,
2 8 0 5 4 2 3 8 0 4 8
If you observe then, it increases to 8 then decreases to 0 then increases to 5 then decreases to 2..so on
any set of random numbers will have the behavior described in this problem. So its just a sort problem?
wrong
 chennavarri November 06, 2010
Look at connected component labeling problem
 chennavarri November 04, 2011en.wikipedia.org/wiki/Connectedcomponent_labeling