|
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. |
On October 20 2013 09:18 EscPlan9 wrote:Show nested quote +On October 20 2013 04:58 spinesheath wrote:On October 20 2013 04:33 phar wrote:On October 20 2013 02:38 gedatsu wrote:On October 20 2013 02:07 phar wrote:On October 20 2013 01:03 gedatsu wrote:On October 20 2013 00:04 EscPlan9 wrote: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". Suppose arr = [2000000000,2000000000,1] Your hash vector will get really long. 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. 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. 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.
I've never used javascript so I may be wrong, but it seems like you're not using a hash table at all. Instead you're just using a regular array and naming it "hash". That is not what a hash table is.
|
ed: I think I missed reading a page...sry!
|
On October 20 2013 21:58 gedatsu wrote:Show nested quote +On October 20 2013 09:18 EscPlan9 wrote:On October 20 2013 04:58 spinesheath wrote:On October 20 2013 04:33 phar wrote:On October 20 2013 02:38 gedatsu wrote:On October 20 2013 02:07 phar wrote:On October 20 2013 01:03 gedatsu wrote:On October 20 2013 00:04 EscPlan9 wrote: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". Suppose arr = [2000000000,2000000000,1] Your hash vector will get really long. 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. 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. 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. I've never used javascript so I may be wrong, but it seems like you're not using a hash table at all. Instead you're just using a regular array and naming it "hash". That is not what a hash table is.
Lol! If only you spent ten seconds googling before you posted so you could have known just how wrong you indeed are XD
|
Hello everyone...
Okay, so I am new too computer science, and I am just stuck on this problem that I should do as a practice before this quiz!
This is the link to practice problem... https://docs.google.com/file/d/0B17THXdfP8JwTGU1NzNaNWNfNTg/edit?usp=sharing
In general, we just learned array lists, and we have to use it to find maximum, minimum etc.
But, (THIS IS a BIGG BUT <-- :D)
With the problem is - search on arraylist -.
I feel like I know how to use it somewhat, but only function I know from arraylist is list.get();. I've seen .set(); but I don't really know about it... Are there any useful functions in arraylist?
Also if you can / want, could you give me a solution to the practice problems? I just want to see it as a reference and try to understand some part of it so I can reuse that part another time or so
Thank you.
|
No, I won't give you a solution to the problem, that defeats its purpose. You should develop a very good understanding of these, it's essential knowledge.
The problems are all really similar though, and the expected solution probably just involves for loops. You should not need any special functions on arraylist except for add and remove for the last 2 problems as specified in the link.
|
On October 21 2013 01:34 spinesheath wrote:
No, I won't give you a solution to the problem, that defeats its purpose. You should develop a very good understanding of these, it's essential knowledge.
The problems are all really similar though, and the expected solution probably just involves for loops. You should not need any special functions on arraylist except for add and remove for the last 2 problems as specified in the link.
but could you tell me about .set() function?
that's the one i've seen alot, but didn't quiet get it
|
On October 21 2013 01:37 TimKim0713 wrote:Show nested quote +On October 21 2013 01:34 spinesheath wrote:
No, I won't give you a solution to the problem, that defeats its purpose. You should develop a very good understanding of these, it's essential knowledge.
The problems are all really similar though, and the expected solution probably just involves for loops. You should not need any special functions on arraylist except for add and remove for the last 2 problems as specified in the link. but could you tell me about .set() function? that's the one i've seen alot, but didn't quiet get it
Well, sure, although you should just google it, something like "<your programming language> ArrayList set" should bring up a proper documentation of the method.
Anyways, list.set(i, v) simply puts v into the list, replacing the value that was at index i before. After list.set(i, v) is used, get(i) will return v.
|
Programming in Prolog is so refreshing.
Unfortunately I'll have to do some Java soon, fuck this awful language
|
I have some CSS classes that apply dotted 1 pixel bottom borders to individual td tags in a table. It applies them all properly in firefox and chrome. In IE, they show properly EXCEPT for cells which also have a thick solid 2px border on the left or right... which makes IE turn my 1px dotted bottom border into a dashed border for no reason. Any ideas?
The thing that really drives me nuts is that there are no styles or CSS classes that even use a dashed border in the code. Internet Exploder at its finest!
|
On October 20 2013 22:33 Mstring wrote:Show nested quote +On October 20 2013 21:58 gedatsu wrote:On October 20 2013 09:18 EscPlan9 wrote:On October 20 2013 04:58 spinesheath wrote:On October 20 2013 04:33 phar wrote:On October 20 2013 02:38 gedatsu wrote:On October 20 2013 02:07 phar wrote:On October 20 2013 01:03 gedatsu wrote:On October 20 2013 00:04 EscPlan9 wrote: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". Suppose arr = [2000000000,2000000000,1] Your hash vector will get really long. 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. 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. 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. I've never used javascript so I may be wrong, but it seems like you're not using a hash table at all. Instead you're just using a regular array and naming it "hash". That is not what a hash table is. Lol! If only you spent ten seconds googling before you posted so you could have known just how wrong you indeed are XD
He's not entirely wrong. It's not an array, but it's also not a hash table. It's object (why [object Object] of course, what else is there in js? lol), which has a few key differences from an actual hash table. See here for more detail:
http://stackoverflow.com/questions/368280/javascript-hashmap-equivalent
|
On October 20 2013 03:54 obesechicken13 wrote:Show nested quote +On October 19 2013 20:07 wherebugsgo wrote:On October 19 2013 16:33 spinesheath wrote: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. Is that the exact wording of the question? Does "duplicated" mean that the duplicate and the original are in unrelated slots of the array, or are they adjacent? Can there be multiple sets of duplicates of the same number, as in 2, 4, 6 of the number? What range are the numbers from? Then there also is the question how one defines efficient. It's an inefficient use of programmer time if you don't just use some stupid algorithm that works and is easy to read and understand. Unless that piece of code is a performance bottleneck that needs to be faster. But I'm going to assume that low execution time is the goal here anyways. 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. 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.
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. 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.
Basically just start at the beginning of the array,and iterate through, XORing all the numbers together.
In a loop it would be as the guy after you described; you have a variable that stores the running XOR value and you XOR it with the current element of the array.
I'm on my phone, so it's unfortunately a bit hard for me to quote things. However, to whoever attempted the first problem (the one with the array where you can't access the whole element at once) accessing all of the bits does not take O(N) time because you are not guaranteed that the numbers are 32 bits. There is no set bound on the size of N, so think about how many bits that would be.
+ Show Spoiler +examining all the bits is O(NlogN)
|
On October 21 2013 02:07 jarf1337 wrote:
I have some CSS classes that apply dotted 1 pixel bottom borders to individual td tags in a table. It applies them all properly in firefox and chrome. In IE, they show properly EXCEPT for cells which also have a thick solid 2px border on the left or right... which makes IE turn my 1px dotted bottom border into a dashed border for no reason. Any ideas?
The thing that really drives me nuts is that there are no styles or CSS classes that even use a dashed border in the code. Internet Exploder at its finest!
Most likely you'll need to use some hacks to override that in IE. Myself, I've forsaken IE and whenever I make a page I don't even bother to check how it's going to look in it since I don't care (let the bastards suffer). As long as people will include special hacks for IE they'll think it's actually good for anything. When suddenly all the webpages start to look horrific they'll learn and either adapt or die.
|
On October 21 2013 04:42 wherebugsgo wrote:Show nested quote +On October 20 2013 03:54 obesechicken13 wrote:On October 19 2013 20:07 wherebugsgo wrote:On October 19 2013 16:33 spinesheath wrote: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. Is that the exact wording of the question? Does "duplicated" mean that the duplicate and the original are in unrelated slots of the array, or are they adjacent? Can there be multiple sets of duplicates of the same number, as in 2, 4, 6 of the number? What range are the numbers from? Then there also is the question how one defines efficient. It's an inefficient use of programmer time if you don't just use some stupid algorithm that works and is easy to read and understand. Unless that piece of code is a performance bottleneck that needs to be faster. But I'm going to assume that low execution time is the goal here anyways. 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. 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.
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. 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. Basically just start at the beginning of the array,and iterate through, XORing all the numbers together. In a loop it would be as the guy after you described; you have a variable that stores the running XOR value and you XOR it with the current element of the array. I'm on my phone, so it's unfortunately a bit hard for me to quote things. However, to whoever attempted the first problem (the one with the array where you can't access the whole element at once) accessing all of the bits does not take O(N) time because you are not guaranteed that the numbers are 32 bits. There is no set bound on the size of N, so think about how many bits that would be. + Show Spoiler +examining all the bits is O(NlogN)
Are we allowed to modify the array? Or can we only examine its original content?
edit: scratch that, figured it out.
+ Show Spoiler +First look at bit 0 of every number. You know N, so you know how many of these "should" be 0 and how many should be 1. When N is odd, they should be equal, and when N is even, the 0s should outnumber the 1s by one. One of these halves will have contain one less element than is expected, and thus we know the missing number's bit in this position. Recurse on that half and look at bit next bit of these numbers. You can do that by allocating two new arrays, putting all the 0-bit numbers in array A and the 1-bit numbers in array B and then recursing on one of them. Example: 000 0000 1001 0001 1010 0010 1011 0011 1100 0(missing 1001) 101 01-bit: 4, should be 5 0-bit: 6, should be 6 The missing number has a 1 in bit 0. Recurse on the 1-bits. 00 01 00 11 01 01 01 11 1-bit 2, should be 2 0-bit 2, should be 3 The missing number has a 0 in bit 1. Recurse on the 0-bits. 0 001 0 101 0-bit 1, should be 2 1-bit 1, should be 1 The missing number has a 0 in bit 2. Recurse on the 0-bits. 0101 0-bit 1, should be 1 1-bit 0, should be 1 The missing number has a 1 in bit 3. We can now reconstruct the number because we know all of its bits. Total number of inspected bits is sum of N/(2^i), i from 0 to log2(N) = 2N-1 = O(N)
|
On October 21 2013 02:07 jarf1337 wrote:
I have some CSS classes that apply dotted 1 pixel bottom borders to individual td tags in a table. It applies them all properly in firefox and chrome. In IE, they show properly EXCEPT for cells which also have a thick solid 2px border on the left or right... which makes IE turn my 1px dotted bottom border into a dashed border for no reason. Any ideas?
The thing that really drives me nuts is that there are no styles or CSS classes that even use a dashed border in the code. Internet Exploder at its finest!
That's a pretty old bug in IE versions <= 7, or if your page is in quirksmode. Dotted was not supported (automatically replaced by dashed) untill IE7 and in IE7 dotted was only shown when the border was thicker than 1px.
In your case, the bug probably appears because your page is in quirksmode, so set a proper document header, and everything will be fine ;>
(If thats not the case and you want to optimize for IE7, you're screwed and most likely have to fall back to a graphic border [background image] )
|
On October 21 2013 02:34 phar wrote:Show nested quote +On October 20 2013 22:33 Mstring wrote:On October 20 2013 21:58 gedatsu wrote:On October 20 2013 09:18 EscPlan9 wrote:On October 20 2013 04:58 spinesheath wrote:On October 20 2013 04:33 phar wrote:On October 20 2013 02:38 gedatsu wrote:On October 20 2013 02:07 phar wrote:On October 20 2013 01:03 gedatsu wrote:On October 20 2013 00:04 EscPlan9 wrote:[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. 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. 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. 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. I've never used javascript so I may be wrong, but it seems like you're not using a hash table at all. Instead you're just using a regular array and naming it "hash". That is not what a hash table is. Lol! If only you spent ten seconds googling before you posted so you could have known just how wrong you indeed are XD He's not entirely wrong. It's not an array, but it's also not a hash table. It's object (why [object Object] of course, what else is there in js? lol), which has a few key differences from an actual hash table. See here for more detail: http://stackoverflow.com/questions/368280/javascript-hashmap-equivalent
Javascript is pretty lol indeed. Yes, to be 100% accurate, it is not a hash table. It is just an object that can be used similarly to a hash table. I've been using Javascript exclusively at work lately so I happened to write it in Javascript. If I remember correctly, Perl also can make use of hash tables just as simply.
|
Yea, it works great for simple things with small input. You just have to be very careful & aware of the limitations.
|
I'm still trying to figure out composition in practice not theory.
So, for example:
private SomeClass sc;
// constructor
public Main(SomeClass sc) {
this.sc = sc;
}
public int getSomeValue() {
// get some value from SomeClass
return sc.value;
}
Is SomeClass considered part of composition?
|
|
|
Right, thanks. I was wondering if MVC indeed uses composition but I guess that answers my question. The View knows about the Model, while the Controller knows about both. 
|
On October 21 2013 20:44 darkness wrote:Right, thanks. I was wondering if MVC indeed uses composition but I guess that answers my question. The View knows about the Model, while the Controller knows about both.
It depends on the implementation. You don't really need the View to hold the model in a composition pattern, you can use the observer pattern so that the view is only updated by events. Obviously the view still has to know about the model, but it doesn't have to hold the actual model object.
|
|
|
|
|
|
EPT
