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
okay finally understood where my pascal was behaving wrong. here's the code using pascal method verified against bruteforce method.
Output:
Final Probability using Pascal triangle method: 0.055252. . Number of iterations: 29
Final Probability using brute force method: 0.055252. . Number of iterations: 1000000
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
//!computes sum of digits of a three digit number
inline long sumofdigits(const long& val){
return ((val/100) + ((val%100)/10)+val%10);
}
int main(){
int sumOfDigits=0,numOfDigits = 3, maxOfDigit=9;
double totalSum = 0,triVal=0,k=0,totalNumbersWithEqualSum = 0,numOfIters=0;
long totalNumLotTickets = 1000000; //0 to 999999
vector<long> thirdRowPascal(15,0);
for(;k<15;++k,++numOfIters) //take 14 values of 3rd row of pascal triangle
thirdRowPascal[k]=((k+1)*(k+2)/2);
for(;sumOfDigits<14;++sumOfDigits,++numOfIters){
if(sumOfDigits>9) //if sum>9 then two digits cannot be zero at same time so
triVal = pow((double)(thirdRowPascal[sumOfDigits]-3*thirdRowPascal[sumOfDigits-10]),2);
else
triVal = pow((double)thirdRowPascal[sumOfDigits],2);
totalSum+=triVal;
}cout<<"Final Probability using Pascal triangle method:"<<(totalSum*2)/totalNumLotTickets
<<". Number of iterations: "<<numOfIters<<endl;
//verification using brute force method
vector<long> totalSums(28,0);long firstdig=0,lastdig=0;numOfIters=0;
for(long ii=0;ii<totalNumLotTickets;++ii,++numOfIters){
firstdig = ii/1000; lastdig = ii%1000;
if(sumofdigits(firstdig)==sumofdigits(lastdig))
++totalNumbersWithEqualSum;
}cout<<"Final Probability using brute force method:"<<totalNumbersWithEqualSum/totalNumLotTickets
<<". Number of iterations: "<<numOfIters<<endl;
}
we know N-bits is the length, P of them are 1's.
so write all permutations using (N-P) 0's and P 1's
its just a permutations problem.
It looks like a superset of the problem at the below link with some constraints.
careercup.com/question?id=6591674
if '(' is 0 and ')' is 1 then effectively we want to find integers with equal 0's and 1's and number of 0's >= number of 1's before every 1 in the bit representation.
For ex: ()(()) is 010011 and ((())) is 000111
LOL.. i bet you just made a couple bloombergers spend time (effectively bloomberg's money) on searching for what is clause 28.8. (I did too)
- blueskin.neo December 01, 2010How does that improve the complexity?
- blueskin.neo November 30, 2010#include <iostream>
#include <vector>
using namespace std;
template <typename T> vector<T> findLongestOrderedArray(const vector<T> &a);
int main(){
vector<int> a {1,2,3,8,10,5,6,7,12,9,4,0}; //{1,2,3,4,5,6,7,8,9,10};
vector<int> longestPath = findLongestOrderedArray(a);
cout<<"Longest Ordered Subsequence ::"<<endl;
for(int i=0;i<a.size();++i)
if(longestPath[i])
cout<<","<<a[i];
}
//!Find the longest ordered string in a sequence of numbers, returns a vector with bits set for longest path
template <typename T>
vector<T> findLongestOrderedArray(const vector<T> &a){
int finalIndx=0,finalMax=0,maxCurr=0,sz = a.size();
vector<T> maxElemArr(sz,0),maxSumArr(sz,0),longPath(sz,0);
int numComputs = 0;
for(int i=0;i<sz;++i){
maxCurr = 1; maxElemArr[i] = i; maxSumArr[i] = 0;
for(int j=i-1;j>=0;--j){ //go reverse. this improves the worst case
++numComputs;
if (a[i]>a[j]){
if(maxCurr < maxSumArr[j]+1){
maxCurr = maxSumArr[j]+1;
maxElemArr[i] = j;
}
}
if(maxCurr==j+2) break; //optimization
}if(finalMax<maxCurr){
finalMax = maxCurr;
finalIndx = i;
}maxSumArr[i] = maxCurr;
}
for(int indx=finalIndx;finalMax>0;--finalMax){
longPath[indx] = 1; //set
indx = maxElemArr[indx];
}
cout<<"numcomputes"<<numComputs<<endl;
return longPath;//longest path bits are set to 1
}
one possible solution using dynamic programming.
For every element i
{
maxcurr = 1; maxElemArr[i] = i; maxSumArr[i] = 0;
for every element j<i
{
if a[i]>a[j]{
if(maxcurr < maxSumArr[j]+1)){
maxcurr = maxSumArr[j]+1
maxElemArr[i] = j
}
}
}
maxSumArr[i] = maxcurr; //max sum
}
For sequence 1 2 3 8 10 5 6 7 12 9 4 0,
i=0; a[i]=1 maxSumArr = {1,0,0,....} maxElemArr = {0,0,0,0...}
i=1; a[i]=2 maxSumArr = {1,2,0,....} maxElemArr = {0,0,0,0...}
i=2; a[i]=3 maxSumArr = {1,2,3,....} maxElemArr = {0,0,1,0...}
i=3; a[i]=8 maxSumArr = {1,2,3,4...} maxElemArr = {0,0,1,2...}
i=4;a[i]=10 maxSumArr = {1,2,3,4,5..} maxElemArr = {0,0,1,2,3..}
i=5;a[i]=5 maxSumArr = {1,2,3,4,5,4,0,..} maxElemArr = {0,0,1,2,3,2,...}
i=6;a[i]=6 maxSumArr = {1,2,3,4,5,4,5,..} maxElemArr = {0,0,1,2,3,2,5.}
...and so on
ya, that handles negatives and saves computations.
- blueskin.neo November 30, 2010gotcha! power set of 3 rats:
{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}
ignoring the first one we have 7.
if none die then bottle 8.
A different perspective:
How many bits are required to store 1:n-1 numbers?
log2(n) bits required to store n-1 elements.
thanks Rayden
hmm. how?
- blueskin.neo November 30, 2010.......
- blueskin.neo November 30, 2010//! Code for nth row of pascal triangle. implements naive iterative approach.
#include <iostream>
#include <vector>
using namespace std;
typedef double Datatype;
typedef vector<Datatype> Array1D;
void printVector(vector<T> &a);
Array1D nthRowPascal(int row){
int i=0,indx =0;
Array1D prevRow, currRow{1};
if(row==1) return prevRow;
row-=1;
while(row>0){
prevRow = currRow;
currRow.clear();
currRow.push_back(1);
i=prevRow.size()+1;
indx = 0;
while(i>2){ //compute i-2 elements
currRow.push_back(prevRow[indx]+prevRow[indx+1]);
++indx;--i;
}
//push 1 in the end
currRow.push_back(1);
--row;
}
}
int main(){
Array1D nthRow = nthRowPascal(10);
printVector(nthRow);cout<<endl;
}
/*!
* \fn printVector(vector<T> &a);
* \brief print contents of a vector
*/
template<typename T>
void printVector(vector<T> &a){
int sz = a.size();
for(int i=0;i<sz;++i)cout<<", "<<a[i];
}
//feed 4 rats with the following bottles
Rat1 1 4 6 7 8
Rat2 2 5 6 7
Rat3 3 4 5 6 8
Rat4 7 8
The sum of the rat numbers is the bottle number. For example, 6 is poison then rats 1,2,3 will die. 1+2+3 = 6
We need 4 four rats upto 10 bottles because 1+2+3+4 = 10. and we can make arrangement of numbers as above
Actually A* would be a lot better
- blueskin.neo November 22, 2010Dijkstra's algorithm or BFS
-> consider each element is a node.
-> each node value represents connections to the next k nodes. so connect edges to next k nodes.
-> edge weights are '1'.
-> find the shortest path after constructing the graph
(or maybe mapreduce can be used?)
I think this should work. thanks codebuddy
- blueskin.neo November 21, 2010NULL <-------1 -------> [Node2]
/ \
[Node1]<- 2 <--------------> 3 -> [Node4]
/ \ / \
[Node3]<- 4<---->5<--------->6<------>7 -> [Node8]
/ \ / \ / \ / \
[Node7]<-8<-->9<->10<->11<->12<->13<->14<->15->NULL
Are we looking at something like this? if not feel free to use the above and explain.
If this is the case then we might need a pointer to go back to the parent, do we have that?
//Taylor Series Approximation
double theta = 45; //45 degrees
double PIby180 = 3.14159265358979323846264338327950/180;
double x = theta*PIby180;
double sinx = x*(1 - (x*x)*(1 - (x*x)*(1 - (x*x)/(6*7) ) / (4*5) ) /(2*3) );
x = (theta+90)*PIby180;
double cosx = x*(1 - (x*x)*(1 - (x*x)*(1 - (x*x)/(6*7) ) / (4*5) ) /(2*3) );
pstree is a Unix command that shows the running processes as a tree. It is used as a more visual alternative to the ps command. The root of the tree is either init or the process with the given pid.
- blueskin.neo November 21, 2010The members of a union cannot be declared as static. An anonymous union declared globally must be explicitly declared static
- blueskin.neo November 21, 2010#include <iostream>
#include <string.h>
using namespace std;
class A{
public:
virtual int foo(void)=0;
virtual ~A()=0;
};
int A::foo(void){
int i=1;
cout<<"Pure virtual function:: foo"<<endl;
}
A::~A(){
cout<<"Pure virtual destructor. Base"<<endl;
}
class B:public A{
public:
virtual int foo(void){
cout<<"Pure virtual implementation in base"<<endl;
}
virtual ~B(){
cout<<"Derived destructor"<<endl;
}
};
int main(){
A* ptr;
ptr = new B();
B b1;
delete ptr;
}
Output:
Derived destructor
Pure virtual destructor. Base
Derived destructor
Pure virtual destructor. Base
Virtual member functions declared with keyword virtual: allow dynamic binding of member functions. There would be exactly one v-table associated with a class that has at least one virtual function. The v-pointer of all of the class' objects would point to the class' v-table. The v-table itself has pointers to each of the virtual functions in the class. During a dispatch of a virtual function, the run-time system follows the object's v-pointer to the class's v-table, then follows the appropriate slot in the v-table to the method code.
The compiler resolves non-virtual functions exclusively at compile-time based on the type of the pointer. The compiler adds a hidden pointer (typically also a machine-word) to each object of class. the compiler initializes this->__vptr within each constructor. The idea is to cause each object's v-pointer to point at its class's v-table
Virtual member functions declared with keyword virtual: allow dynamic binding of member functions. There would be exactly one v-table associated with a class that has at least one virtual function. The v-pointer of all of the class' objects would point to the class' v-table. The v-table itself has pointers to each of the virtual functions in the class. During a dispatch of a virtual function, the run-time system follows the object's v-pointer to the class's v-table, then follows the appropriate slot in the v-table to the method code.
- blueskin.neo November 21, 2010Initialization List is a better approach for initializing the member variables and base class objects of a class upon construction of an instance of it's own. make your code execute faster as a result. order of initializing the member variables in the Initialization List must match the order of their declarations inside the class. initialization list is the only place that reference and const members can be initialized at all.
- blueskin.neo November 21, 2010You can declare them virtual but there wont be any use of the virtual keyword.
- blueskin.neo November 21, 2010map: elements are sorted. most operation complexities O(logn).
hashmap: elements are random. most operation complexities amortized O(1), worst case O(n)
Retrieval Insertion Prepending Appending Deletion
LinkedList<T> O(n) O(1) O(1) O(1) O(n)
Vector<T> O(1) O(n) O(n) Amort. O(1) O(1)
Inline functions are parsed by the compiler, whereas macros are expanded by the preprocessor.
Inline functions follow all the protocols of type safety, Expressions passed as arguments to inline functions are evaluated once. In some cases, expressions passed as arguments to macros can be evaluated more than once.
STL provides several data structures/containers. These containers require ability to change size during runtime. Allocators handle all the requests for allocation and deallocation of memory for a given container (dynamic memory allocation)
- blueskin.neo November 21, 2010A container is a holder object that stores a collection other objects (its elements). They are implemented as class templates,
- blueskin.neo November 21, 2010The compiler cannot inline a function if:
The function has a variable argument list;
is recursive;
is virtual (direct calls to virtual functions can be inlined);
uses inline assembly, (unless compiled with /Og, /Ox, /O1, or /O2);
if the program takes the address of the function and the call is made via the pointer to the function (direct calls to functions that have had their address taken can be inlined);
the function and the caller use different types of exception handling (C++ exception handling in one, structured exception handling in the other).
Answer: A
http: // msdn.microsoft. com/en-us/library/z8y1yy88%28v=VS.80%29.aspx
"Inline expansion alleviates the function-call overhead at the potential cost of larger code size."
/* A generic code implementing Dutch Flag Problem solution. Let me know if there are any bugs. Thanks*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/*!
* \fn void DFPBuckets(vector<T> &a, T bktBound1, T bktBound2)
* \brief Rearrange the elements of an array into buckets
* \param a A vector containing the elements that need to be
* \param bktBound1 the value that separates lower buckets from mid bucket
* \param bktBound2 the value that separates mid buckets from higher bucket
*/
template<typename T>
void DFPBuckets(vector<T> &a, T bktBound1, T bktBound2){
int sz = a.size();
int low=0,mid=0,high=sz-1;
while(mid<=high){
if(bktBound1 >= a[mid]){ //case 1st bucket
swap(a[low],a[mid]);//cout<<"swap: "<< a[low] << " , " << a[mid]<<endl;
++low; ++mid;
}else if(bktBound2<=a[mid]){ //case 3rd bucket
while(high>mid && a[high]>bktBound2)
--high;
swap(a[mid],a[high]);//cout<<"swap: "<<a[mid]<<" , "<<a[high]<<endl;
--high;
}else//case 2nd bucket
++mid;
}
}
/*!
* \fn printVector(vector<T> &a);
* \brief print contents of a vector
*/
template<typename T>
void printVector(vector<T> &a){
int sz = a.size();
for(int i=0;i<sz;++i)cout<<", "<<a[i];
}
int main(){
vector<char> arrayC {'A','b','3','C','1','d','c','4','2','B','a'};
vector<double> arrayF {11.2, 0.1, 15.4, 0.0, 3.2, 2.8, 6.2};
cout<<"Input: ";printVector(arrayC);cout<<"\t\t\t\t";
DFPBuckets(arrayC, '9','Z');
cout<<"Output: ";printVector(arrayC);cout<<endl;
cout<<"Input: ";printVector(arrayF);cout<<"\t\t\t";
DFPBuckets(arrayF, 5.0,10.0);
cout<<"Output: ";printVector(arrayF);cout<<endl;
}
//Output: final string : abc__def_987654321_xyz_123abc_hi
#include <iostream>
#include <string.h>
using namespace std;
//!function to reverse string from strt to end
void reverseStr(string &s, int strt, int end) {
while(strt<end){
s[strt] = s[strt]+s[end];
s[end] = s[strt]-s[end];
s[strt] = s[strt]-s[end];
++strt;--end;
}
}
void reverseBuckets(string &str){
int start=0,end=0,tmp=0,sz = str.size();
size_t pos;
while(end<sz){
pos = str.find_first_of("_",start);
if(pos>0)
if(pos>=sz && end<sz)
end = sz;
else
end = pos;
reverseStr(str,start,end-1);
if(end>=sz)
break;
pos = str.find_first_not_of("_",end);
if(pos>0){
end = pos;
start=end;
}++end;
}
}
int main(){
string s = "cba__fed_123456789_zyx_cba321_ih";
reverseBuckets(s);
cout<<"final string : "<<s<<endl;
return 0;
}
missing numbers are more than one or just one?
- blueskin.neo November 20, 2010hey hamepal, here you go
/* Algorithm to count words in a file. Please dont reply opinions on the code, comments on complexity analysis is appreciated
For each word check if the word exists in the hash, if it doesnt then insert the word with a count 1
if it does then increment the value
For each word in the hashmap, print word and its count
Complexity: Linear insertion and space
NOTE:The code only compiles with newer C++ use the switch -std=c++0x in your Makefile*/
#include <iostream>
#include <vector>
#include <unordered_map>
typedef std::unordered_map<std::string, int> MyHashMap;
void printMyHashMap(MyHashMap::const_iterator itr,MyHashMap::const_iterator enditr){
while(itr!=enditr){
std::cout<<(*itr).first<<" : "<<(*itr).second<<std::endl;
++itr;
}
}
int main(){
MyHashMap wordsMap; //declare unordered map
//vector of strings
std::vector<std::string> strings {"count","words","in","a","file",
"and","print","words","with","their","count",
".","more","words","file"};
int len = strings.size();
std::vector<std::string>::const_iterator wordsItr;
wordsItr = strings.begin();
MyHashMap::iterator mapItr = wordsMap.begin();
for ( wordsItr=strings.begin(); wordsItr!=strings.end(); wordsItr++ ){
mapItr = wordsMap.find(*wordsItr);
if(mapItr==wordsMap.end()){ //if word not found then
wordsMap.insert(MyHashMap::value_type(*wordsItr, 1));
}else{
(*mapItr).second = ++(*mapItr).second; }
}
std::cout<<"words and their count :"<<std::endl;
printMyHashMap(wordsMap.begin(),wordsMap.end());
return (0);
}
you are ignoring the word "amortized",
amortized O(1) means average running time per operation over a worst-case sequence of operations is constant.
It depends on what operations on the data structure you are interested in. Two alternatives: hashmap , trie. If you just want the count then a hash map with value = count
time: amortized O(1)
space: depends on the hash function, best case: O(unique_words)
"OS releases mutex by itself" - if possible can you provide a reference.
And "WaitForSigleObject" looks like a windows based function, we prefer something that works for unix/linux, (windows hides a lot of details).
Thanks
lets look at the complexity:
1: O(1) //assume
2: A loop that runs for each element i.e. n ==> O(n)
3. A loop that traverses through each element of arr whose size is n^2, no matter what the datatype of arr is the loop will run sizeof(arr) times i.e. n^2 => O(n^2)
total complexity: O(n) + O(n^2) ==> O(n^2)
please reply if my understanding is wrong or if there's something missing in the algo. thanks
Thanks Rayden. So it means the buckets dont have to be sorted. i.e.
given input - aA1B23Cbc4
the output can be bcaABC2134... doesn't have to be abcABC1234 (in the latter case buckets are also sorted)
Couple of questions,
when you say numbers that means digits from 0-9? or real numbers? because real numbers cannot be sorted in O(n) without any constraints.
Are there duplicates?
An array something like, a 1 b B A 11 a . is this allowed?
Deepest Common Ancestor: Tarjan's off-line least/lowest common ancestors algorithm.
- blueskin.neo November 18, 2010are you looking for a deque? double ended queue? or an array list?
- blueskin.neo November 18, 2010classic coin flipping problem.
divide 100 coins into 29 and 71 piles.
flip all 29 coins in the first pile. DONE!
how? Consider we have a bit string of length 100, 29 bits are set and 71 are 0's.
if we split the string into 29 and 71 strings randomly, we should have 29-k bits set in the first pile and k bits set in the pile, i.e. bit count for these piles is (29-k) and k. what we want same bit count on both sides or consider we want precisely k on both sides because we dont know 'k'. :D
you can observe that if you flip (n-k) bits then you get k bits
Ex: if 3 out of 5 bits are 1's then the flipping all would give you 2 1's
so flip all in the first pile and you're done
Hash table or hash map; data structure; uses hash function to map values known as keys (e.g., a person's name) to associated values (e.g., their telephone number).
Hash tables are particularly efficient when the maximum number of entries can be predicted in advance, so that the bucket array can be allocated once with the optimum size and never resized. I
With a good hash function, the average lookup cost is nearly constant as the load factor increases from 0 up to 0.7 or so. deally, hash function should map each possible key to a unique slot index, but this ideal is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are never added to the table after creation).
Am trying a really faster method here.
sum of squares of third row of pascal triangle with some modification /1000000,
= 55252/1000000 = .055252
Detailed Explanation:
so we want how many numbers are there such that given abcdef a+b+c = d+e+f where a,b,c,d,e,f <= 9 --> a+b+c <= 27.
Feel free to ask questions/ Thanks
- blueskin.neo December 03, 2010