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
Given n array sequence,
Construct a binary tree and count elements in each level.
number of ways of arranging the sequence without changing the structure is basically changing the order of nodes in each level i.e. permutations using nodes in each level. which is P(k,k) i.e. k! for k nodes in each level
Answer = ((numOfNodes[level1])! * (numOfNodes[level2])! * (numOfNodes[level3])! ...* (numOfNodes[levelm])! )
For Example: Input array: 6,4,8,3,5,7 builts a tree as
6
/ \
4 8
/ \ /
3 5 7
Combinations = 2!*3! = 2*6 = 12 ways
[648357,648375,648537,648573,648735,648753],[684357,684375,684537,684573,684735,684753]
Another Example:
given a sequence10,8,4,9,6,2,1,3,5,7
number of combinations = 2! * 2! * 4! = 96
Given n array sequence,
Construct a binary tree and count elements in each level.
number of ways of arranging the sequence without changing the structure is basically changing the order of nodes in each level i.e. permutations using nodes in each level. which is P(k,k) i.e. k! for k nodes in each level
Answer = ((numOfNodes[level1])! * (numOfNodes[level2])! * (numOfNodes[level3])! ...* (numOfNodes[levelm])! )
For Example: Input array: 6,4,8,3,5,7 builts a tree as
6
/ \
4 8
/ \ /
3 5 7
Combinations = 2!*3! = 2*6 = 12 ways
[648357,648375,648537,648573,648735,648753],[684357,684375,684537,684573,684735,684753]
consider the tree is organized in an array as below;
a[0]
/ \
a[1] a[2]
/ \ / \
a[3] a[4] a[5] a[6]
/ \ /
a[7]a[8]a[9]...........
then the elements in n'th level from top will be from a[(2^n)-1] ...to...a[(2(n+1)-2)]. For Example:
2nd level elements are from a[3] to a[6]
I've posted code below. Hope that helps
- chennavarri October 12, 2010/*! Find the minimum triplet given three sorted arrays
Given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
Distance is defined like this :
If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
Algorithm:
Merge these three arrays using a merge from merge sort approach. While merging check for the distance and save the ones that keep it min.
The distance between consecutives is always min.
NOTE:: Code was not written in a quick and dirty way.
Complexity:: O(i+j+k)
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<typename T, int size>
int length(T(&)[size]){return size;}
int distance (int a,int b,int c){
return max(max(abs(a-b),abs(a-c)),abs(b-c));
}
int main(){
vector<int> mergeArray;
//initialization
int a[] = {-33,-24,-14,-1,4,5,6,7,8,35,106,109,112,128,224,228,335,439,1100,1120,1302,4019,4299,5666,5999,8888,9999,10000};
int b[] = {-4,-3,1,6,19,33,64,79,84,112,15,24,35,39,100,120,127,1002,4001,4002};
int c[] = {-1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
int a_len= length(a),b_len= length(b),c_len= length(c);
int maxElement = max(max(a[a_len-1],b[b_len-1]),c[c_len-1])+1; //max of all arrays
int amin = a[0], bmin = b[0], cmin = c[0]; //initial minimums
int a_curr,b_curr,c_curr,a1,b1,c1,currMin,currDistance,minDistance=maxElement+1;
int i=0,a_indx=0,b_indx=0,c_indx=0; //counters
long numOfLoopings = 0;
while(true){
numOfLoopings++;
//!Step1: get current element, if not max, current is set to max when end of array is reached in Step-4
if(a_curr!=maxElement) a_curr = a[a_indx];
if(b_curr!=maxElement) b_curr = b[b_indx];
if(c_curr!=maxElement) c_curr = c[c_indx];
//!Step2: Find current minimum element that is to be inserted into the final mergeArray
currMin = min(min(a_curr,b_curr),c_curr);
if(currMin==maxElement) break; //if min element is maxElement then all arrays have reached end
mergeArray.push_back(currMin); //push into merging array
i = (currMin==a_curr)?1:((currMin==b_curr)?2:3); //i=1 if a , i=2 if b , i=3 if c
//!Step3: Find the distance between the consecutive triplet.
a1=((a_curr==maxElement)?a[a_len-1]:a_curr);
b1=((b_curr==maxElement)?b[b_len-1]:b_curr);
c1=((c_curr==maxElement)?c[c_len-1]:c_curr);
currDistance = distance(a1,b1,c1);
if(minDistance>currDistance) {amin=a1;bmin=b1;cmin=c1;
// cout<<"Dist:: "<<currDistance<<"[ "<<a1<<","<<b1<<","<<c1<<"]"<<endl;
minDistance=currDistance;} //if distance is less than store values
//!Step4: Increment the array index that has current min and if out-of-bounds then set current element to maxElement+1 of all arrays
if(i==1)if(a_indx<(a_len-1)) ++a_indx;else a_curr=maxElement;
if(i==2)if(b_indx<(b_len-1)) ++b_indx;else b_curr=maxElement;
if(i==3)if(c_indx<(c_len-1)) ++c_indx;else c_curr=maxElement;
}
cout<<" Minimum Triplet:: [A: "<<amin<<" , B: "<<bmin<<" ,C: "<<cmin<<"]"<<endl;
cout<<" Merged Array:: ";
for(int i=0;i<mergeArray.size();++i)cout<<" "<<mergeArray[i];
cout<<endl<<" Number of times the loop was run:: "<<numOfLoopings-1<<". which is O("<<a_len<<"+"<<b_len<<"+"<<c_len<<") = O("<<a_len+b_len+c_len<<")";
}
a greedy approach is usually used
- chennavarri October 12, 2010quick question, using int's for looping over or recursive functions for referring to index is allowed or not??
- chennavarri October 11, 2010Why not just sort and add ascendingly??
given 3,2,4,1. The minimal cost is 19 for sequence (((1+2) +3) +4).
And a generalized observation could be made, if lengths are sorted as s1,s2,s3...sn
minimal cost is given by, (n-1)*s1 + (n-1)*s2 + (n-2)*s3 +..+(n-k)*s(k+1)+..+ 1*sn
in the above example=> 3*1 + 3*2 + 2*3 + 1*4 = 19
Another example: given lengths: 7,5,6,5 then sort => 5,5,6,7
minimal cost = 3*5 + 3*5 + 2*6 = 1*7 = 49 , complexity is O(nlogn + n)
i was asked the same question in my interview with Amazon. I gave a hash based algorithm and the interviewer was fine with it. The solution is not O(n) space complexity. It is infact O(SUM) because you insert or retrieve elements that are less than SUM. if SUM >max(n) then space complexity is O(n).
- chennavarri October 09, 2010Yep.. hashing should do it with an array storing indices of k frequent numbers.
- chennavarri October 09, 2010if number of bits set is 1 then it is a power of two
- chennavarri October 08, 2010return ((pow(2,log2(n))-pow(2,floor(log2(n))))==0)
- chennavarri October 08, 2010int NumberOfSetBits(int i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
Ship speed is x/100 units per hour where x is the distance between A and B.
Consider: ship 1 and 2 start on opposite ends, so they meet at x/2 distance which takes 50 minutes for either ship. ship 3 and 4 start when ships 1 &2 have travelled 60% of the distance. ship 3 meets ship 1 at (100-60)/2 = 20 minutes and similarly 4 meets 2 at 100-20 = 80 minutes
6 binary trees, 1 binary search tree
- chennavarri October 08, 2010Magic square solution.
you can use magic squares and when a player inserts into a position just add it to previous sum. if sum == n(n^2+1)/2 then the player has won. the only problem is how to construct a magic square.
Ex for a 3x3 tic-tac-toe
8 1 6
3 5 4
4 9 2
when a player makes a move just add the value at that position. whenever the sum of three positions is 15 then the player won.
Merge these three arrays using a merge from merge sort approach. While merging check for the distance and save the ones that keep it min.
- chennavarri October 08, 2010/*! Find longest palindrome given a string
Algorithm:
-> Sort ASCII values of the string
-> Separate into two sets doubles and non-doubles (triples are treated as a double and a single
-> push an element from single set into a deque. Then push elements from doubles set into the deque alternatively front and back.
-> Various combinations are possible but this shud give you one longest string for sure.
*/
#include <iostream>
#include <cstdlib>
#include <vector>
#include <math.h>
#include <deque>
#include <algorithm>
#include <string.h>
#include "stdio.h"
using namespace std;
int main(int argc, char *argv[])
{
vector<int> str1vec,singlesVec,doublesVec;
//strings
string str1 = "Monster Asian Army!";
//store strings as ascii values into an integer vector
for(int i = 0; i<str1.size();i++)
str1vec.push_back(int(tolower(str1[i])));
//sort vectors
sort(str1vec.begin(),str1vec.end());
//split the vector into doubles and singles
for(int i=0;i<str1vec.size()-1;i++){
//if a[0]-a[1]==0 then a double pair, push both of them into doubles set
if(str1vec[i]==str1vec[i+1]){
doublesVec.push_back(str1vec[i]);
doublesVec.push_back(str1vec[i+1]);
i++;
}else //else push a[0] into single pair
singlesVec.push_back(str1vec[i]);
}
//print doubles
cout<<"doubles"<<":: ";
for(int k=0;k<doublesVec.size();k++)
cout<<char(doublesVec[k])<<",";
cout<<endl<<"singles"<<":: ";
for(int k=0;k<singlesVec.size();k++)
cout<<char(singlesVec[k])<<",";
deque<int> palind;
palind.push_front(singlesVec[0]);
int c = 0,k=0;
int len = doublesVec.size();
while(k<len-1 && len>=2){
c=(doublesVec[k]);
palind.push_back(c);
c=(doublesVec[k+1]);
palind.push_front(c);
k+=2;
}
cout<<endl<<"Longest Palindrome combination"<<":: ";
for(int k=0;k<palind.size();k++)
cout<<char(palind[k]);
}
First step in Bubble sort
- chennavarri October 06, 2010int strlength(char *s){
++s;
return ((s[0]=='\0')?1:(1 + strlength(s)));
}
It's basically find kth element of two sorted arrays when merged. In you case, find the mid point i.e. (m+n)/2 th element. (m,n being sizes of arrays). Worst case complexity would be just merging until we get (m+n)/2 elements i.e. O((m+n)/2). Am working on a better algo. has a complexity
O(m/2 + log2m).
Insertion and deletion would still take atmost log(k).
So in your case, algorithm complexity is O(nlogk). I would prefer Fibonacci heaps since they can insert and peek at the maximum priority element in amortized constant time and deletions take O(logk). if k <<< n then this wud be very useful. else if k > n/2 then quick sort would give similar performance.
I shud have mentioned that.. its in 12 hr format since it is analog clock. so 12:00 angle wud be 360 which is accepted as 0. so 190 is accepted as 170
- chennavarri October 04, 2010Anyways, I've posted solution on optionsbender dot com. Leftside section algorithms
- chennavarri October 04, 2010What are the inputs?? Are we talking about using Boost Graphs? adjacency_list?
The question vague, you need someway to input graphs what is it exactly?
anyways, this was my answer:
Given 'hr' hours and 'min' minutes, angle = modulus( 0.5*(60*hr-11*min) )
Quick question,
what if the weight is 50.. where would you put it/?? 25-50 or 50-75??
Destructors cannot have parameters so cannot overload!
Error: destructors may no have parameters.
Theta(n) space complexity for merge sort
A million numbers would be a million bytes i.e. a megabyte. hmmmm thats the size of a picture on my camera.
Anyways stackoverflow has more discussion on Merge vs Quick. Check it out
Algorithm:
(a,b) are positions between 0-63
1. store a-b
2. store a-2b or b which ever is less and set a flag bit approriately
Result:
Total average number of bits required is 9.645 i.e. totalbits/allPossibleCombinations
Atmost 12 bits are required
At the least 2 bits are sufficient
#include<stdio.h>
#include <iostream>
using namespace std;
int numComputs=0;
long factorial(int n, int k=1){
if(n<=k)
return k;
else
{
numComputs++;
return n*factorial(n-1,k);
}
}
long nChooseK(int n, int k){
//n!/(n-k)!k!
return factorial(n,k+1)/factorial(n-k);
}
int main()
{
int m=9, n = 9;
long nPaths = nChooseK(m-1+n-1,m-1);
cout <<"No. of paths = " << nPaths<< endl;
cout<<"=> Number of multiplications using combinations formula: "<<numComputs<<endl; //generally (m-1+n-1)-2 multiplications
}
hash is best in this case, O(n)
- chennavarri October 12, 2010Insert into hash with key = number and data = key.count++, //initially count is zero
if count>1 then dont print because it is already inserted and printed.