blueskin.neo
BAN USERElegance is not a dispensable luxury but a factor that decides between success and failure.
-Dijkstra
blueskin.neo@gmail.com
- 0of 0 votes
AnswersGiven N arrays containing values between 0 to x, what data structure would you use to store these arrays so that when given a test array 't' find the closest array in N that has highest number of elements in 't'? Also what algorithm would you use to find the closest array. N could be in the order of 1000. x could be between [100,1000]
- blueskin.neo| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat is a futex?
- blueskin.neo| Report Duplicate | Flag | PURGE
Morgan Stanley Computer Architecture & Low Level
Classic interview question, XOR solution.
stackoverflow.com/questions/2605766/how-to-find-a-duplicate-element-in-an-array-of-shuffled-consecutive-integers
LOL!! "There's an idiot for that"
- blueskin.neo September 21, 2011This is a tower of hanoi problem, where the size of the disk can be indicates the position of the element.
-> For example, consider you have 1 stack for storing elements and 2 temporary stacks you can use to move elements and the size of the queue is 'N'.
Then once the queue is full i.e. you kept pushing into the 1st stack. You would have to move the elements (2^N)-1 times inorder to remove the first element in the stack.
-> Am not sure if there is an existing solution for 'K' towers of hanoi problem but I have the solution (in constant time ha haa :D ). So if creating a stack has an overhead then we can compute (using my solution) the maximum number of stacks we can use and keep the complexity low at the same time. But if there's no complexity in creating more and more Stacks then we can use the below solution.
// Create an array of Stack objects and use it as a regular array for implementing queue.
Queue
{
public:
Queue(int queueSize) : m_queueSize(queueSize), m_currentIndex(0), m_startIndex(0)
{
if(m_queueSize == 0)
{
m_queueSize = 0;
}
}
void Push()
{
if(m_data[m_currentIndex].empty())
{
m_data[m_currentIndex].Push();
m_currentIndex = (m_currentIndex+1) % m_queueSize;
}
else
{
Pop();
m_currentIndex = m_startIndex;
m_data[m_currentIndex].Push();
m_currentIndex = (m_currentIndex+1) % m_queueSize;
}
}
void Pop()
{
if(!m_data[m_startIndex].empty())
{
m_data[m_startIndex].Pop();
m_startIndex = (m_startIndex+1) % m_queueSize;
}
else
{
//empty queue;
}
}
bool IsEmpty()
{
return m_data[m_startIndex].IsEmpty();
}
private:
Stack m_data[n];
int m_queueSize, m_currentIndex, m_startIndex;
};
you mean Dijkstra's quote?
- blueskin.neo February 19, 2011okay given an array like this
9009, 664, 64, 19, 7, 9, 24, 964, 99
@Kishore:
can u demonstrate the answer with ur algo
@Sathya: Its said right but the statement was not complete. I changed it. So we basically set all 6*n+(1|5) as a primes and then eliminate their multiples so we should be left with primes in the end. for example: For all primes below 50
set 5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49
eliminate their multiples. i.e.
-> eliminate multiples of 5: 25,35
-> eliminate multiples of 7: 49
so on... we should be left with primes in the end
@Saimok:
the code was posted at this link
ideone.com/WOGVb
number of bits == 2 && first bit == 1
optimization: when number of bits count exceeds 2 break, the number is not the answer
@arba: if gives an answer for n=312: 5040
and n=314: rounds = 84150
but for n=313 it takes forever. maybe there's something mathematically
www dot optionsbender.com/technologybending/algorithms/primenumbers
- blueskin.neo February 17, 2011alrite, looks like it takes forever.
Code here:
ideone.com/WOGVb
puzzles.nigelcoldwell.co.uk/nineteen.htm.
you could generalize it to :: (floor)(n/25) + (floor)(n/5)
en.wikipedia.org/wiki/Longest_common_subsequence_problem#Example
- blueskin.neo February 17, 2011looks like a good approach
- blueskin.neo February 17, 2011//WRONG solution
:It takes 313 steps to get the original order.
after each round we'll have ordering changed to {even cards on top and then odd cards in reverse order}
Ex:
if you take 12345 (1 is on top)
after one round we get 2 4 5 3 1. Here's a complete process for 5 cards
12345 --> 24531 --> 43152 --> 35214 --> 51423 --> 12345
5 steps for 5 cards. 313 steps for 313 cards
well, I literally thought of replacing 'a1','a2' characters with '1','3'... and changing back. such as k%2==0 replace with 'b(k/2)' else replace with 'a(k/2-1)'
Yep, u r right, we would need to consider the case where a1,b1 are objects and not just characters. I guess "Insertion Sort" will definitely work and has a known complexity.
I assume "Insertion" is pushing and "Deletion" is popping.
-> Given an array of elements construct a Queue which is implemented using a linked list.
-> For insertion/ pushing into the queue;
add the node at the end of the list if queueCapacity doesn't exceed.
if it does then delete element at first and insert the new element at end. //FIFO
#include <iostream>
using std::cout;using std::endl;
template<typename _Tp>
class Node{
_Tp d;
public:
Node<_Tp>* next;
explicit Node(_Tp obj):d(obj),next(NULL){}
Node(const Node& rhs):d(rhs.d),next(rhs.next) {}
Node& operator=(const Node& rhs){d = rhs.d; next = rhs.next;return *this;}
~Node(){}
_Tp data(){return d;}
};
template<typename _Tp,typename NodePtr = Node<_Tp>* >
class Queue{
private:
NodePtr ll; //the first element of the queue is
int qcapacity, numElements;
NodePtr first, last; //pointers to first and last nodes of linked list
public:
//construct queue from array of input elements. If input array size is > capacity then increase automatically
explicit Queue (const _Tp* &t_arr, int t_arr_sz, int cpct):ll(NULL),
qcapacity(cpct),numElements(0),first(NULL),last(NULL){
if(t_arr!=NULL && t_arr_sz>0){
ll = new Node<_Tp>(t_arr[0]);++numElements;
first = ll;last = ll;
for(int i=1; i<t_arr_sz;++i){
ll->next = new Node<_Tp>(t_arr[i]);++numElements;
ll = ll->next;last = ll;
}ll = first;
qcapacity = qcapacity<t_arr_sz?t_arr_sz:qcapacity;
}
}
~Queue(){while(ll!=NULL){ ll=ll->next; delete first; first = ll; }}
//Insert element at the end, if more than capacity then pop the first element
void push(const _Tp& newObj){
if(qcapacity==numElements)//Queue capacity full, pop from front and push at back
pop();
last->next = new Node<_Tp>(newObj);
last = last->next; ++numElements;
}
//If list not empty, remove the first element
void pop(){
if(first!=NULL){
ll = ll->next; delete first;
first = ll;--numElements;
}
}
void print(){
NodePtr tmp = ll;
while(tmp!=NULL){ cout<<tmp->data()<<":"; tmp=tmp->next; }
}
inline NodePtr begin(){return first;}
inline NodePtr end(){return last;}
inline int size(){return numElements;}
inline int capacity(){return qcapacity;}
};
int main(){
int *d, n = 10, maxQ_size = 10;
d = new int[n];
for(int i=0;i<n;++i) d[i] = i+1;
const int* d1 = d;
Queue<int> q(d1,n,maxQ_size);
q.push(11); q.push(12); q.pop();
q.print();
}
@Code Saviour: The algorithm basically moves 2n/2 elements for 2n/2 elements. i.e. has a complexity of O(n*n) . And looks very similar to insertion sort. Since you observe that the problem is a subset of a sorting problem,
we get Complexity: O(nLogn)
-> change the array values from [a1,a2,a3...,an,b1,b2...bn] to [1,3,5,7....2n-1, 2,4,6,8,....2n]
-> now sort using any inplace sorting algorithm. For quick sort, take sizeof(array)/2 as the initial pivot.
Not sure if there's a linear algorithm, even if there is it might not be complete.
I didn't get the algorithm behind your code but an Arraylist has O(n) complexity for insertions. the following article explains a array list container
doc.qt.nokia.com/qq/qq19-containers.html#sequentialcontainers
and its complexity:
doc.qt.nokia.com/latest/containers.html#algorithmic-complexity
as ftfish pointed out flaws in gekko's algorithm, I've modified the algorithm it a little bit. This is bounded by a quadratic complexity:
///a. Split array into two arrays array1 and array2. Sort them.
//Now the general idea of the algorithm is to move elements from heavier array to lighter array,
//if direct move is not possible, then swap. Also assume sum(array1)>sum(array2) and we always
// move/swap smaller or equal elements from array1 to array2
///LOOP 1. Move as many elements as possible from array1 to array2 minimizing the difference
find lowerbound of 'diff/2' in array1 in array1 and move to array2,
break loop when (diff/2 < min(array1) & diff > 0.0)
///LOOP 2. Swap as many elements as possible between array1 & array2 minimizing the difference
For every element 'x' in array2 we find (lowerbound of x+(diff/2)) in array1 and
swap with the 'x' in array2 which minimizes difference the most.
Complexity: // for simplicity sake even though we split 'n' elements into two arrays for complexity analysis I just use 'n' rather than 'n/2'
a : O(n)
Loop 1: O(n) because we always find the lower bound in array1 and at some point either diff==0 or ((diff/2) < min(array1) & diff>0).
The second condition is bound by 'n' iterations or array1.size()
Loop 2: O(n*(n*log(n))): because for every element in array2 we do a lowerbound search in array1 --> n*logn
and since we always try to find lower bound in array1 the loop should terminate in array1.size()--> n*n*logn
Total Complexity: O(n + n + n*(n*log(n))) --> O((n^2)*log(n)))
@manu:
split: [1,3,4] [2,5]
sort: already sorted
sums: 8,7, difference = 1;
find lower bound of (difference/2) i.e. 0.5,
nothing found , so terminate
by swapping
- blueskin.neo February 01, 2011As others pointed out I changed the post.
If n*logn >>> max(array)-min(array)
or if max(array)-min(array) is approximately close to n then the following algorithm gives better complexity
Space complexity: O(max(array)-min(array))
Time complexity: O(max(array)-min(array))
-> Find 'max' and 'min' of the array = O(n)
-> Create a bitset 'B' of size 'max'-'min' initialized to 0's = O(1)
-> For every element 'i' in the array = O(n)
set B[array[i]-min] = 1
-> Find the closest distance between 1's in the bitset 'B'. = O(max(array)-min(array))
that is the minimum difference
if k <= logn , Nonlinear general selection algorithm: O(kn)
or in general Median of Medians algorithm
Good thinking. at first it looks like it is faster but theoretically it has the same complexity as scanning the entire list and traversing to the median.
Because the number of element accesses is the same. i.e. for every iteration, slow pointer accesses 1 element and fast pointer accesses 2 elements --> total accesses 3n/2
which is same as normal traversing. i.e. same complexities but
Practically the time and space you are saving is any overhead for every iteration such as incrementing, checking conditions, any variable retrieval etc..
Sort the smaller array and for every element in the larger array check if the element exists.
Take 2 pivots to the larger array, *begin and *end
for every element
if element exists then increment begin pivot
else swap with *end and decrement end pivot.
elements from start to begin pivot of the larger are the common elements
Complexity: O(m*log(m) + n*log(m)) where m<n { ==> O(n*log(m)) }
Space : O(1)
@Panda; nope. the solution by V is correct. S[i-1] is the neighbour of S[i] so we cannot use that.
- blueskin.neo January 20, 2011@Raja: yep, I gave a more generic solution which should work even if there's a cost associated in going from house 'i' to 'j'. In this case the cost is 'none' so they don't have to be connected to all other nodes i.e. order of visiting these houses doesn't matter. solution provided below by V should work
- blueskin.neo January 20, 2011-> Each house is a node and is connected to nodes other than the neighbors.
-> Each node has a cost (money) and edge weight '1'.
-> Apply Dijkstra's for finding the path with maximum cost.
-> For n houses, Complexity using Dijkstra's O(n*(n-2) + n*log(n))
-> NOTE: This can be improved using other path search algorithms. suggestions ?
Another suggestion would be, maybe modifying an adaptive sorting algorithm might work.
- blueskin.neo January 09, 2011Applying a modified quicksort would give a best case of O(nlogk + k) k=1000 in this case
Consider a simpler example below, n = 10, k = 2, array = 9,3,1,14,10,13,18,16,15,21
so from the problem statement we can visualize the problem as: ('-' means available positions, 'x' means not available
09 - - x x x x x x x [this means 9 cannot move beyond 3rd position]
- 03 - - x x x x x x
- - 01 - - x x x x x
x - - 14 - - x x x x
x x - - 10 - - x x x
x x x - - 13 - - x x
x x x x - - 18 - - x
x x x x x - - 16 - -
x x x x x x - - 15 -
x x x x x x x - - 21
Now applying quick sort for the first k+1 elements with '9' as pivot we get '9' in the 3rd position and all elements before it as lesser, so none of the next occurring elements can lie before 3rd position. Hence, for the remaining elements we get
x x 09 x x x x x x x
03- x x x x x x x x
- 01 x x x x x x x x
x x x 14 - - x x x x // 14 cannot move left beyond '9' s position
x x x - 10 - - x x x
x x x - - 13 - - x x
x x x x - - 18 - - x
x x x x x - - 16 - -
x x x x x x - - 15 -
x x x x x x x - - 21
Now sort elements leftside of '9' using any efficient sorting algo.
Next, take 14 as pivot and apply the same procedure.
Applying this recursively, in the best case, we get atmost k comparisons for every (n/k) pivots and sort the elements on leftside for each pivot we get (n/k)*klogk = nlogk. Total complexity = O(nlogk + k ) ==> O(nlogk) (since n>k)
NOTE: the numbers are chosen in such a way that we get the best case complexity i.e. O(nlogk+k)
Of course the worst case complexity is O(nk) i.e. when we have input already sorted.
Thanks. Let me know if any mistakes or questions.
LOL
- blueskin.neo December 21, 2010I think this is just a behavioral question to understand how you behave under stress where you don't know the answer.
- blueskin.neo December 19, 2010...
- blueskin.neo December 19, 2010Well, the complexity is O(x*N) no matter what the matrix contains. what if the matrix is sparse? i.e. you don't have the check every element?
what we want to find is the array k'th from N given arrays which contains most of the elements.
An alternative solution whose worst case is O(x*N) but a lot faster for sparse matrix:
1. Create x arrays containing the values
2. Create a count array 'C' of size N.
3. for every element in the test array 't', access the x arrays and increment the count in array 'C'.
Ex:
given 5 arrays containing elements 1 to 9
arr1: 1,5,3,2
arr2: 2,8,3,4
arr3: 4,6,2,7,1
arr4: 5,1,4
arr5: 7,8,9
testArray: 2,4,6
1. create 9 arrays
x1 x2 x3 x4 x5 x6 x7 x8 x9
1 1 1 2 1 3 3 2 5
3 2 2 3 4 5 5
4 3 4
2. create count array C of size N: [0,0,0,0,0]
3. for each element in test array count.
for first element '2'. access x2. increment C[x2[...]] --> C: [1,1,1,0,0]
next element '4', access x4 increment C[x4[...]] --> C: [1,2,2,1,0]
next element '6', access x6 increment C[x6[...]] --> C: [1,2,3,1,0]
max(C) --> 3 i.e. 'arr3' is the closest to test array which is true
so, in this case we are only accessing 7 elements from the 'x' arrays
if we do a two dimensional matrix approach then we would access 9*5 = 45 elements
Thanks.
- blueskin.neo December 19, 2010A good approach would be using class diagrams. Lets analyze the problem.
A deck is a collection of cards; it has behaviors as shuffle, pop, push, sort etc....
All the behaviors can be implemented by differently in various ways and they can change later, so we want the interface to deck of cards to be separated from implementation. A handle-body idiom!
//NOTE: this is NOT a good diagram for understanding class diagrams.
Card
-----------
value
suite
..etc..
Handle<>---------->Body
^ ^
| |
Deck DeckData
---------- -----------
DeckData friend Deck
shuffle() DeckData();
pop() ~DeckData();
push()
..etc..
// separating the way a deck data is implemented gives an advantage of changing it without affecting interface
class DeckData{
friend class Deck;
DeckData();
~DeckData();
//other data members
};
class Deck{
public:
Deck();
//define copy constr. and assignment oper
~Deck();
private:
DeckData *d;
};
I dont know if I invented it, it might be there already.
The way I looked at the problem was if you have two numbers say 16 and 4 in binary form 010000 and 00100. dividing these two would be finding the difference between their left most bit '1' positions i.e. 5-3 = 2. so 16/4 should be <= 2^2 and greater than 2^1.
I applied this recursively, for example:
703/7 is (64+32+4)=100 and remainder 3.
for the decimal part, multiply remainder with 10000 and apply again i.e.
3*10000/7 is (4096+256+32+16+8+4+1) = 4285.
Answer: 100.4285
gekko's code is good. But it won't handle multiple writers because if multiple writers are waiting on a single variable and all are notified and only one proceeds into Critical section. after that the other writers would have equal priority as readers because requestCS is set to false by first writer. So changing the requestCS variable to a counting variable will assure all writers are done before readers proceed.
- blueskin.neo December 17, 2010Hey, i havent worked with TRIEs at all but is TRIE the actual solution for this problem in reality? what general issues/problems do people have with TRIEs? I just curious n want to learn more about it
- blueskin.neo December 17, 2010given a odd digit number abcdefghi. the next palindrome ,
1. if efghi < edcba abcdedcba
2. else abcd(e+1)dcba
For a even digit number abcdefgh
1. if dcba > efgh then next palindrome is abcddcba
2. else next palindrome is abc(d+1)(d+1)cba
Ex: given 234167889, from the above 67889 is not less than 61432 so the next palindrome is 234171432 i.e. 2341(6+1)1432
O(k) time (k digits). let me know if am missing anything
yep.. I missed a word "amortized". fixed
- blueskin.neo December 08, 2010Do you mean a hash map for each array in N?
- blueskin.neo December 07, 2010it doesn't fail actually, after sum>9, only one of the digits can be zero i.e. the number goes down by
[don't have a clear explanation for why this pattern happens but it's the same pattern for 4th row]
pascalRowNumber*pascalRow(0)
for ex: if Row ==> 0=1, 1=3, 2=6, 3=10, 4=15, 5=21, 6=28, 7=36, 8=45, 9=55,
10=(66-3*Row(0))--> 63
11=(78-3*Row(1))--> 69
12=(91-3*Row(2))--> 73
13=(105-3*Row(3))-->75
14=(this is the mid point so it starts going down repeating)
=Row(27-13)
15=Row(27-15)=Row(12)-->73.
so on..
the first post is code, second post is explanation. it gives explanation with clear example, I dont know how else I can explain. If you have any questions please feel free to ask, I will answer them. thanks
- blueskin.neo December 06, 2010Using a hash_map. complexity depends on hash function but in general recent hash functions give a amortized O(1) insertion and amortized O(1) retrieval.
Assuming the values in the hash_map are all positive.
-> For every value 'val' in the array,
if sum-val >=0
if sum-val exists in the hash_map, add to the matching pairs vector.
else insert 'val' in the hash_map
-> print all elements of the matching pairs vector.
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using std::cout;using std::vector;using std::endl;
typedef int DataType;
typedef std::unordered_map<DataType, int> MyHashMap;
void printVecPair (vector<DataType> v) {
cout << v[0]<<" : "<<v[1]<<endl;
}
int main(){
MyHashMap valsMap; //declare unordered map
vector<DataType> array {12,20,13,4,1,2,8,6,7,7,3,5,9};
DataType sum=14,val=0;
vector<vector<DataType> > matches; //vector to store pairs of values whose sum = sum
DataType len = array.size();
vector<DataType>::const_iterator arrItr;
MyHashMap::iterator mapItr = valsMap.begin();
//for every val in the array if (sum-val) >0 see if there exists a value (sum-val)
for ( arrItr=array.begin(); arrItr!=array.end(); arrItr++ ){
val = *arrItr;
if((sum-val)<0)
continue;
mapItr = valsMap.find((sum-val));
if(mapItr==valsMap.end()){ //if sum-val not found then insert
valsMap.insert(MyHashMap::value_type(val, 1));
}else //else add it to the matches vector
matches.push_back(vector<DataType>{val,(sum-val)});
}
cout<<"value pairs whose sum = "<<sum<<endl;
for_each (matches.begin(),matches.end(),printVecPair);
}
Let me know if there are any bugs. Thanks
- blueskin.neo December 06, 2010wiki: "The usual implementation is a self-balancing binary search tree".
stl_map.h: "/// This turns a red-black tree into a [multi]map. "
stackoverflow.com/questions/3674876/why-is-this-not-allowed-in-c
- blueskin.neo December 03, 2010not sure about a set but map is implemented using a redblack tree. complexity for all operations is O(logn)
- blueskin.neo December 03, 2010Same as singleton but create two instances in the getinstance method and return alternatively using a boolean flag
- blueskin.neo December 03, 2010
- blueskin.neo September 21, 2011