The Big Programming Thread - Page 376

Prev 1 374 375 376 377 378 1032 Next

Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.

EscPlan9

United States2777 Posts

October 19 2013 15:04 GMT

#7501

On October 19 2013 15:55 wherebugsgo wrote:
You're given an array of numbers such that every element in the array is duplicated except for one. Provide an efficient algorithm to determine the singleton element.

I probably would have given the hash table answer. Though I'm not sure if my implementation was the same as what you were describing:


var arr = [1,1,2,2,3,3,4];
var hash = {};

// build hash - give the value 1 when initially found, and add 1 for each duplicate
for (var i = 0; i < arr.length; i++) {
    if (hash[ arr[i] ] { 
        hash[ arr[i] ] = 1 + hash[ arr[i] ]; 
    } else {
        hash[ arr[i] ] = 1;
    }
}

// iterate through hash until found a key with a value of 1 indicating no duplicates
for (var k in hash) {
   if (hash[k] === 1) {
       print "Unique element found: " + k;
   }
}

What would be pseudocode for your implementation you mentioned with keeping track of a separate sum variable? I just used the value of the hash-key as the "sum".

freelander

Hungary4707 Posts

October 19 2013 15:14 GMT

#7502

please help with c++ (templates + friends).
I'm getting the following error:
+ Show Spoiler +

C:\semester\OAF\2\bag\include\bag.h|34|warning: friend declaration 'std::ostream& operator<<(std::ostream&, const Bag<T>&)' declares a non-template function|
C:\semester\OAF\2\bag\include\bag.h|34|note: (if this is not what you intended, make sure the function template has already been declared and add <> after the function name here) |
C:\semester\OAF\2\bag\include\bag.h||In function 'std::ostream& operator<<(std::ostream&, const Bag<T>&)':|
C:\semester\OAF\2\bag\include\bag.h|149|error: 'curr' was not declared in this scope|
||=== Build finished: 1 errors, 1 warnings ===|

my multiset class (implemented with a single linked ordered list):
+ Show Spoiler +

template <class T>
class Bag{
private:

    struct Node{
        T val;
        unsigned int mult;
        Node *next;

        Node(T e, unsigned int m=1)
            :val(e), next(0), mult(m){}

        Node(T e, Node *n, unsigned int m=1)
            :val(e), next(n), mult(m){}
        };

    Node * head;

public:
    Bag();
    Bag (const Bag<T>& b);
    virtual ~Bag();

    bool is_empty();
    void insert(T e, unsigned int n=1);
    void erase(T e);
    bool contains(T e);
    unsigned int count(T e);
   
   friend std::ostream& operator<<(std::ostream& os, const Bag<T>& b);
};

the << operator's definition:
+ Show Spoiler +

template <class T>
std::ostream& operator<<(std::ostream& os, const Bag<T> &b){
    os << "{ ";
    Bag<T>::Node* curr=b.head;
    while (curr){
        //...
    }
    os << " }";
    return os;
}

I don't get it. I declared the variable 'curr' (a pointer for iterating the list's nodes) right there.

Amnesty

United States2054 Posts

October 19 2013 15:38 GMT

#7503

On October 20 2013 00:14 freelander wrote:
please help with c++ (templates + friends).
I'm getting the following error:
+ Show Spoiler +

my multiset class (implemented with a single linked ordered list):
+ Show Spoiler +

template <class T>
class Bag{
private:

    struct Node{
        T val;
        unsigned int mult;
        Node *next;

        Node(T e, unsigned int m=1)
            :val(e), next(0), mult(m){}

        Node(T e, Node *n, unsigned int m=1)
            :val(e), next(n), mult(m){}
        };

    Node * head;

public:
    Bag();
    Bag (const Bag<T>& b);
    virtual ~Bag();

    bool is_empty();
    void insert(T e, unsigned int n=1);
    void erase(T e);
    bool contains(T e);
    unsigned int count(T e);
   
   friend std::ostream& operator<<(std::ostream& os, const Bag<T>& b);
};

the << operator's definition:
+ Show Spoiler +

template <class T>
std::ostream& operator<<(std::ostream& os, const Bag<T> &b){
    os << "{ ";
    Bag<T>::Node* curr=b.head;
    while (curr){
        //...
    }
    os << " }";
    return os;
}

I don't get it. I declared the variable 'curr' (a pointer for iterating the list's nodes) right there.

template<class T>
friend std::ostream& operator<<(std::ostream& os, const Bag<T>& b);

spinesheath

Germany8679 Posts

October 19 2013 15:40 GMT

#7504

On October 20 2013 00:14 freelander wrote:
please help with c++ (templates + friends).
I'm getting the following error:
+ Show Spoiler +

my multiset class (implemented with a single linked ordered list):
+ Show Spoiler +

template <class T>
class Bag{
private:

    struct Node{
        T val;
        unsigned int mult;
        Node *next;

        Node(T e, unsigned int m=1)
            :val(e), next(0), mult(m){}

        Node(T e, Node *n, unsigned int m=1)
            :val(e), next(n), mult(m){}
        };

    Node * head;

public:
    Bag();
    Bag (const Bag<T>& b);
    virtual ~Bag();

    bool is_empty();
    void insert(T e, unsigned int n=1);
    void erase(T e);
    bool contains(T e);
    unsigned int count(T e);
   
   friend std::ostream& operator<<(std::ostream& os, const Bag<T>& b);
};

the << operator's definition:
+ Show Spoiler +

template <class T>
std::ostream& operator<<(std::ostream& os, const Bag<T> &b){
    os << "{ ";
    Bag<T>::Node* curr=b.head;
    while (curr){
        //...
    }
    os << " }";
    return os;
}

I don't get it. I declared the variable 'curr' (a pointer for iterating the list's nodes) right there.

You probably should first resolve your warnings. It's been a while since I worked with templates and friends, and they certainly are a bit tricky to deal with. This link might help you though, the example implements an

friend std::ostream& operator<< (std::ostream& o, const Foo<T>& x);

(it basically boils down to what Amnesty posted, but there is a bit of an explanation provided as well)

With templates it is not rare that the actual error is reported as a warning.

DeltaX

United States287 Posts

October 19 2013 15:47 GMT

#7505

On October 19 2013 20:07 wherebugsgo wrote:

Show nested quote +

I paraphrased, but basically you can expect to encounter two of every element in the array except for one element. The array is unsorted and the duplicates can appear anywhere. There won't be multiple (read: more than 2) instances of the same number, though the answer would remain the same for even-number duplicates-i.e. you could have 4 of the same number and 2 of another and 6 of another and finding the singleton still works the same.

There is no specification on the range of the numbers, though you can assume that you won't need multiple data structures to represent a single number. i.e. if it makes it easier for you, assume they are 32 bit ints or whatever.

My first solution required O(nlogn) time, and O(1) space. I pretty quickly realized that the time complexity can be improved to O(n) time and there's a relatively simple way of doing that by adding a data structure that takes O(n) space, but the "brilliant" answer (as the interviewer described it-I'd call it elegant) requires no additional space and is also O(n) time.

+ Show Spoiler [my shitty answer] +

Sort the array, then step through the array until you find that two consecutive elements are not the same. Sorting takes O(nlogn) time and stepping through the array takes O(n) time; O(nlogn + n) is in O(nlogn).

You could use radix sort and get an O(n) sort, I suppose.

+ Show Spoiler [an approximately equally shitty answer] +

Instead of sorting the array, maintain a hash table and a second sum variable. Iterate through the array and for each integer, check if it's in the hash table. If it isn't, then add it to the sum, and store it. If it is, then subtract it from the sum. When we've gone through the entire array, the singleton is the only element we never subtracted, thus the sum variable is the singleton.

This works in O(n) time since hash accesses are O(1), and we need O(n) space for the hash table.

+ Show Spoiler [the model answer] +

Just iterate through the array and XOR everything together. A[0] XOR A[1] XOR .... XOR A[n]. The result of this computation is the singleton element.

This works since XOR is commutative and associative. a XOR a is just 0, and 0 XOR a is a. Since all of the elements are duplicated except one of them, all the duplicates will XOR out to 0 and then the singleton will be left at the end.

This holds true also for arrays in which you have even multiples of elements, not just duplicates, though it fails when there are odd multiples.

If you guys like this sort of stuff or need interview practice, here's a few more interesting problems I encountered at career fairs/interviews and company visit sessions:

1. This problem is similar to the one I posed before, but it has a pretty major twist.

The problem statement is to find the missing integer in the array with the following rules:

a. An array A contains every integer from 0 to N except for one of them.
b. The elements of the array A may appear in any order.
c. We can't actually access an entire element of the array all at once. In other words if you index the array you won't get back the whole element. + Show Spoiler +

in other words, normally if you access an array element at index i, you would call A[i] and you would be returned the element at the ith position in A. In this problem you can't do that.

Instead, what you can do is ask for the jth bit of the ith element of the array. In other words, I could ask for the 4th bit of the first element of A, and I would be returned the bit in the 4th position of the element ordinarily given by A[0].
d. The algorithm must return the missing integer by looking through at most O(N) bits.

2. Give an approach (or code) to writing an equivalent of the C function atoi. + Show Spoiler +

I've also been asked how to implement strlen

If you're not a C programmer, atoi is a function that converts an ASCII string to an integer. Describe the limitations or shortcomings of your approch (or code) in as much detail as you can.

3. Suppose we have a function that computes rand2() (i.e. a fair coin toss-it outputs 1 or 2 with equal probability). Design an algorithm that uses this function to simulate a fair die roll, i.e. a function that should output a random number from 1 to 6 with equal probability.

I don't think that an approach using a hashset or hashmap is really all that bad. It could easily be extended to different amounts (3 of each, find the 5 that have 7 instead) and it would be much easier for people to understand what you are doing.

Mostly tho I came from a math background instead of CS, so XOR is not an operation I have ever really had to use or learn about it and its uses.

As for the other problems:
+ Show Spoiler [1] +

I would sum the array bit by bit and then missing = (n*(n+1))/2 - total. Should still be O(n) time as you inspect a constant 32 bits per number. Can be a bit more efficient by inspecting each bit until you get the maximum number of 0's or 1's it can have for n, so you know what that bit is in n. Then just keep moving to the next bit up until you determine n.

+ Show Spoiler [2] +

For atoi, is there a requirement that you are given ASCII characters that are numbers or does it have to work for any character? I think you want to do (psudo code):


int runningTotal = 0
for each char in string
 if(charCode.isNumber)
  runningTotal *= 10
  runningTotal += charCode - codeOfZero
 else
  //do something for non-number character

You would also want to take into account whitespace and +- too.
For strlen, I think you just count the number of characters in the char[] until you hit the end of string character.

+ Show Spoiler [3] +

Call rand 3 times and use one result per bit. If you rolled a 0 or 7, reroll

freelander

Hungary4707 Posts

October 19 2013 15:53 GMT

#7506

On October 20 2013 00:40 spinesheath wrote:

Show nested quote +

friend std::ostream& operator<< (std::ostream& o, const Foo<T>& x);

(it basically boils down to what Amnesty posted, but there is a bit of an explanation provided as well)

With templates it is not rare that the actual error is reported as a warning.

Thanks, I look into that link. I'm not sure what Amnesty meant though..

edit:
The more primitive solution worked, where I put the definition of the operator inside the class declaration.
The other "solution" generated errors.

gedatsu

1286 Posts

October 19 2013 16:03 GMT

#7507

On October 20 2013 00:04 EscPlan9 wrote:

Show nested quote +

I probably would have given the hash table answer. Though I'm not sure if my implementation was the same as what you were describing:


var arr = [1,1,2,2,3,3,4];
var hash = {};

// build hash - give the value 1 when initially found, and add 1 for each duplicate
for (var i = 0; i < arr.length; i++) {
    if (hash[ arr[i] ] { 
        hash[ arr[i] ] = 1 + hash[ arr[i] ]; 
    } else {
        hash[ arr[i] ] = 1;
    }
}

// iterate through hash until found a key with a value of 1 indicating no duplicates
for (var k in hash) {
   if (hash[k] === 1) {
       print "Unique element found: " + k;
   }
}

What would be pseudocode for your implementation you mentioned with keeping track of a separate sum variable? I just used the value of the hash-key as the "sum".

Suppose arr = [2000000000,2000000000,1]
Your hash vector will get really long.

sundersoft

91 Posts

October 19 2013 17:04 GMT

#7508

On October 20 2013 00:14 freelander wrote:
please help with c++ (templates + friends).
I'm getting the following error:

In addition to changing the friend statement, change

Bag<T>::Node* curr=b.head;

typename Bag<T>::Node* curr=b.head;

Any time you have an expression of the form "a<T>::b" where b is a type and T is a template argument of the class/function where the expression appears, you have to put "typename" before the expression.

The reason is because the compiler has to know whether 'b' is type or a variable in order to unambiguously parse your code. Depending on the definition of 'a' and what T is, 'b' could be either a type or a varible. The compiler will assume that 'a' is a variable, and you have to explicitly tell it that 'a' is a type.

Also, if you have a nested template class inside of a template class, you have to use the "template" keyword. For example, if you had a variable declaration of the form "a<T>::b<T> v;" where T is a template argument of the enclosing function or class and a and b are classes, then you would have to write it as "typename a<T>::template b<T> v;". So, you have to tell the compiler that a<T>::b is a template and you also have to tell it that a<T>::b is a class.

This only applies when T is a template argument of the code you're writing (i.e. the compiler doesn't know what T is when it's compiling your template definition). You can write an expression of the form "a<c>::b" without using the typename keyword if a and c are not template arguments for the enclosing function or class. If the compiler knowns what a and c are then it can decide if b is a type or a variable by itself.

phar

United States1080 Posts

October 19 2013 17:07 GMT

#7509

On October 20 2013 01:03 gedatsu wrote:

Show nested quote +

On October 20 2013 00:04 EscPlan9 wrote:

I probably would have given the hash table answer. Though I'm not sure if my implementation was the same as what you were describing:


var arr = [1,1,2,2,3,3,4];
var hash = {};

// build hash - give the value 1 when initially found, and add 1 for each duplicate
for (var i = 0; i < arr.length; i++) {
    if (hash[ arr[i] ] { 
        hash[ arr[i] ] = 1 + hash[ arr[i] ]; 
    } else {
        hash[ arr[i] ] = 1;
    }
}

// iterate through hash until found a key with a value of 1 indicating no duplicates
for (var k in hash) {
   if (hash[k] === 1) {
       print "Unique element found: " + k;
   }
}

What would be pseudocode for your implementation you mentioned with keeping track of a separate sum variable? I just used the value of the hash-key as the "sum".

Suppose arr = [2000000000,2000000000,1]
Your hash vector will get really long.

(editing for brevity & clarity)

Not only that, but the function will fail due to hash collisions (after you solve the problem in the quote). So two open things to solve:

1) What if input is larger than memory
1a) (make a better hash function)
1b) (what if input really doesn't even fit in memory - a 1TB array)
2) What if two numbers hash to the same hash value

1a) you have to solve first.
2) you have to solve second

1b) you only need to solve if the assignment explicitly calls for it - likely you don't have to

You may want to read up on actual hash functions to use, instead of just using the identity function. Find a good one to use - it's generally a horrible idea to implement your own hash function. Very close to the top of the list of "things that programmers should never implement by themselves" is hash functions, below maybe only basic algorithms and crypto, lol.

freelander

Hungary4707 Posts

October 19 2013 17:18 GMT

#7510

On October 20 2013 02:04 sundersoft wrote:

Show nested quote +

In addition to changing the friend statement, change

Show nested quote +

thanks, that makes a lot of sense. actually it works now!

gedatsu

1286 Posts

October 19 2013 17:38 GMT

#7511

On October 20 2013 02:07 phar wrote:

Show nested quote +

Not only that, but the function will fail due to hash collisions. So two open things to solve:

1) What if input is larger than memory
2) What if two numbers hash to the same hash value

He can't get hash collisions as he is using the value itself as its hash. But yeah, with a more sane hash function you can get collisions. Use the built-in hash table here.

obesechicken13

United States10467 Posts

October 19 2013 18:54 GMT

#7512

On October 19 2013 20:07 wherebugsgo wrote:

Show nested quote +

+ Show Spoiler [an approximately equally shitty answer] +

the model answer
Just iterate through the array and XOR everything together. A[0] XOR A[1] XOR .... XOR A[n]. The result of this computation is the singleton element.

This works since XOR is commutative and associative. a XOR a is just 0, and 0 XOR a is a. Since all of the elements are duplicated except one of them, all the duplicates will XOR out to 0 and then the singleton will be left at the end.

This holds true also for arrays in which you have even multiples of elements, not just duplicates, though it fails when there are odd multiples.

If you guys like this sort of stuff or need interview practice, here's a few more interesting problems I encountered at career fairs/interviews and company visit sessions:

1. This problem is similar to the one I posed before, but it has a pretty major twist.

The problem statement is to find the missing integer in the array with the following rules:

a. An array A contains every integer from 0 to N except for one of them.
b. The elements of the array A may appear in any order.
c. We can't actually access an entire element of the array all at once. In other words if you index the array you won't get back the whole element. + Show Spoiler +

in other words, normally if you access an array element at index i, you would call A[i] and you would be returned the element at the ith position in A. In this problem you can't do that.

I've also been asked how to implement strlen

How does this work? What are you XORing together?

Are you XORing 0 with every element or the previous element with the next element or what?
Diagrams would be helpful.

Also it still seems like you're doing this in O(n) time and I liked your previous solutions better since they were more intuitive. I don't think of using XOR when I want to solve a problem like this. That's something you learn to see in (?) programming competitions.

The only advantage I see with XOR over radix sort is that if you have really large integers then Radix sort would be slow.

spinesheath

Germany8679 Posts

October 19 2013 19:26 GMT

#7513

On October 20 2013 03:54 obesechicken13 wrote:
How does this work? What are you XORing together?

Are you XORing 0 with every element or the previous element with the next element or what?
Diagrams would be helpful.

Also it still seems like you're doing this in O(n) time and I liked your previous solutions better since they were more intuitive. I don't think of using XOR when I want to solve a problem like this. That's something you learn to see in (?) programming competitions.

The only advantage I see with XOR over radix sort is that if you have really large integers then Radix sort would be slow.

What he does is

cur = 0;
foreach(n in array)
    cur = cur XOR n;
return cur;

Does radix sort work in situ? And even if it does, you might not be allowed to modify the array. So XOR has the memory advantage.

I personally was thinking of alternating sums as in Sum a[i] * (-1)^i, which would work in the case of adjacent duplicates. XOR is pretty much the same concept.

phar

United States1080 Posts

October 19 2013 19:33 GMT

#7514

On October 20 2013 02:38 gedatsu wrote:

Show nested quote +

He can't get hash collisions as he is using the value itself as its hash. But yeah, with a more sane hash function you can get collisions. Use the built-in hash table here.

Yea sorry I was getting a step ahead of himself. I meant that after he solves the problem you pointed out (identity hash function), he will then have to solve the problem of hash collisions.

spinesheath

Germany8679 Posts

October 19 2013 19:58 GMT

#7515

On October 20 2013 04:33 phar wrote:

Show nested quote +

Yea sorry I was getting a step ahead of himself. I meant that after he solves the problem you pointed out (identity hash function), he will then have to solve the problem of hash collisions.

The idea is to not try to implement the hashtable yourself, but to just use an existing one instead. Those come with built in strategies for collisions.

opsayo

591 Posts

October 19 2013 23:37 GMT

#7516

if (mHashTable.containsKey(array[i]))
  mHashTable.remove(array[i]));
else
  mHashTable.put(array[i], 1);
uniqueElement = mHashTable.keys().nextElement();

O(n) time O(n/2) space

Cyx.

Canada806 Posts

October 20 2013 00:05 GMT

#7517

Even if it's technically constant time it's still a lot faster probably since bitwise operations are so quick ^^ also it takes up no memory which is a bonus. In terms of efficiency it doesn't get much better than XORing a bunch of things together.

EscPlan9

United States2777 Posts

October 20 2013 00:18 GMT

#7518

On October 20 2013 04:58 spinesheath wrote:

Show nested quote +

The idea is to not try to implement the hashtable yourself, but to just use an existing one instead. Those come with built in strategies for collisions.

I'm very confused by the responses here. I wasn't implementing a hash table myself. I was using built-in hash structures found in most languages, in the code above it was Javascript. If a key is found, you can detect it and handle it however you want - in this case all I do is change the value because I found another instance of the element. If a key is not found, one is created. Pretty simple...

As to "what if two numbers hash to the same hash value"? How does that even matter. Like if you run the code above, you'll find out the Keys '1', '2', and '3' all have a value of 2, and the Key '4' has a value of 1. The crux of the problem was to find non-duplicate elements in an array. So all non-duplicate elements would have a value of 1... and that's it. It doesn't matter if they hash to the same value - as long as the value is 1 in my solution, then we found a unique element in the array.

phar

United States1080 Posts

October 20 2013 02:57 GMT

#7519

On October 20 2013 09:18 EscPlan9 wrote:

Show nested quote +

You are correct that if you use the identity function has your hash, you will never have a collision. Your code completely fails for large input, because you'll run out of memory and die.

Since you didn't really give us much background information we just have to guess as to what your requirements are.

If your requirements are like

1) Input array will never be >10k/100k ish items

Then sure, use identity as your hash and be done with it.

If you're confused just in general about what a hash table is, I suggest you pick up a data structures textbook (or find some resources online). It's one of the most useful data structures in programming.

obesechicken13

United States10467 Posts

October 20 2013 03:07 GMT

#7520

On October 20 2013 09:05 Cyx. wrote:

Show nested quote +

I guess this is true.

Still, the solution is not something I'd understand if I just saw the code with little. When you think of duplicate problems, or you gave a 4th gradera piece of paper with a bunch of numbers on them, they'd solve it using sorting algorithms (in their head). I still remember sorting stuff in elementary math to get modes.

Prev 1 374 375 376 377 378 1032 Next

Please or register to reply.

The Big Programming Thread - Page 376

Completed

Ongoing

Upcoming