|
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 31 2016 11:16 Blisse wrote:
:p
when you have problems like this, i think it helps to manually count.
so for the inside loop, can you manually count the number of iterations?
at i = 0, j = n, j >= i, j-- will loop... n times
at i = 1, j = n, j >= i, j-- will loop... ? times
? = n-1
at i = ...
at i = n-1, j = n, j >= i, j-- will loop... ? times
that should get you started
? = n-(n-1)
I guess it's (n^2+n) / 2
I had to look it up... didn't actually know how to solve that.. so I googled "factorial but with sum" and found the answer lol
This is O(n^2) ?
another question:
is an array a list? I understand that in java an array is an object that is NOT an implementation of the list interface, but it is a sequential data type and seems to fit the abstract definition of a list. So I am wondering if say, I was asked on a test, "is an array a list", would I say yes or would I say no?
yet another question:
review sheet says, "Describe how a queue is typically implemented using sequential allocation."
By sequential allocation, it means an array? So in this case I am guessing the answer is "add to the back, remove from the front, and make the array circular". I guess you would also need to expand and copy over the array as necessary.
yet another question, hashcode question:
okay so if I have a hashcode function, my professor taught our class a method to "scatter" our hash table is this:
( hashcode-function * a-large-prime-number ) % table size .
This is supposed to scatter the hashcode results throughout the table, but I don't really understand why and he didn't really explain why. Can someone explain why you do this?
|
disclaimer: I'm just answering as an exercise for myself, I graduated 3 years ago and wasn't a very good student especially on theoretical courses 
is an array a list?
as a java guy I'd directly say no because if array was a list it would implement the list interface. other than that doesn't it become a little political question? does a list have a formal definition independent of the language? biggest difference is a list can grow as much as memory but an array is fixed. plus when you remove an element at index(i) you need to shift other elements, hence a wrapper is needed for an array to become a list. wrap everything and you get an ArrayList. maybe the thing called "dynamic array" is more list-like?
"Describe how a queue is typically implemented using sequential allocation."
like a finite tube full of gumballs?
yet another question, hashcode question:
if I remember correctly this is done to prevent too many values with the same key. Imagine like this, if you put all the values to one key it becomes a linked list, so not a good thing. 1 value for 1 key is ideal. if you have a good enough hash function I guess you won't need this?
edit: related to last question stackoverflow.com
|
On November 01 2016 05:05 mantequilla wrote:yet another question, hashcode question: if I remember correctly this is done to prevent too many values with the same key. Imagine like this, if you put all the values to one key it becomes a linked list, so not a good thing. 1 value for 1 key is ideal. if you have a good enough hash function I guess you won't need this? edit: related to last question stackoverflow.com
I think you mean too many keys that link to the same bucket
but either way, I don't actually get how it helps to scatter it.
I guess maybe the issue is that if we don't multiply by a large prime, then taking hashfunction % T is more likely to result in duplicates.
yes... I think that's it. If we were taking hashfunction%100 (as a weak example), then every multiple of 100 will result in the same bucket. But if we do (hashfunction*large prime) % 100 then that definitely does scatter it.
|
An array is different things in different programming languages. In java an array is very similar to an array in C and C++. It is a continuous block of memory which is fixed in size and can hold multiple elements of the same type. Arrays are usually very very fast compared to other data structures because working with continuous blocks of memory complements current processor architecture.
The "default" List implementation in java is the ArrayList which is a List that is implemented using an array in the background. Since a list can grow but an array cant the array has to be reallocated every time the size of the list grows above the capacity of the array.
An alternative List implementation is a LinkedList which does not use an array and is significantly slower than an ArrayList in most common use-cases.
In java arrays are objects and lists are objects but arrays are still something special. Their class does not exist at compile time but is instead dynamically generated at run time the first time a certain type of array is used.
About the hashcodes and prime numbers:
I dont know the big theory behind it but multiplying with prime numbers above a certain size has simply been proven to be a simple yet effective way of scattering hashcodes.
|
my tip for you is to study heaps
they teach 50 different data structures but always ask the fking heaps all the time...
or I'm unlucky. I don't like heaps.
|
If the hashcode is already decent, multiplying by a prime does nothing at best, and potentially causes problems if the prime and the table size are in an unfortunate relation.
For example with hashes 0 through 5, a prime 37 and a table size 74. Without multiplication by that prime, everything slots perfectly into buckets 0 through 5. With the prime, you only use the buckets 0 and 1, with 3 objects each.
Typically you only use primes (along with bitshifts, xors and lookup tables) to generate the hashcode from multiple input values like a byte array, not to slot the hashes into the hashtable. A good hashing algorithm is a carefully chosen sequence of operations. Blindly multiplying something with a random prime is NOT a good idea.
|
On November 01 2016 03:46 travis wrote:Show nested quote +On October 31 2016 11:16 Blisse wrote:
:p
when you have problems like this, i think it helps to manually count.
so for the inside loop, can you manually count the number of iterations?
at i = 0, j = n, j >= i, j-- will loop... n times
at i = 1, j = n, j >= i, j-- will loop... ? times
? = n-1 Show nested quote +
at i = ...
at i = n-1, j = n, j >= i, j-- will loop... ? times
that should get you started
? = n-(n-1) I guess it's (n^2+n) / 2 I had to look it up... didn't actually know how to solve that.. so I googled "factorial but with sum" and found the answer lol This is O(n^2) ?
So basically you have
at i = 0, j = n, j >= i, j-- will loop... n times (see that i=0, so n-0 = n)
at i = 1, j = n, j >= i, j-- will loop... n-1 times (see that i=1, so n-1, etc)
at i = 2, j = n, j >= i, j-- will loop... n-2 times
...
at i = n-2, j = n, j >= i, j-- will loop... n-(n-2)=2 times
at i = n-1, j = n, j >= i, j-- will loop... n-(n-1)=1 time
If you're trying to count the inner loop, you have this summation.
n + (n-1) + (n-2) + ... + 2 + 1
which is the same as this more recognizable form
1 + 2 + ... + (n-2) + (n-1) + n
This is known as, the sum of numbers from 1 to n.
This has an exact value, (n (n+1)) / 2.
So the inner loop happens (n*(n+1))/2 times, which is O(n^2).
The outer loop happens n times, which is O(n).
So the whole thing is O(n^3)
|
Normally for the queue implemented as an array you keep track of a current index and the current data size. The current pointer is the index of the item that is next in the queue. The current pointer plus the size (modulo the length of the array) tells you where the next insert should go. This way you never have to shift the array unless you're moving the data from a smaller array to a larger array.
|
On November 01 2016 06:57 Blisse wrote:
So the inner loop happens (n*(n+1))/2 times, which is O(n^2).
The outer loop happens n times, which is O(n).
So the whole thing is O(n^3)
ahh thank you
yeah my mistake in not multiplying it by the outer loop value
|
On November 01 2016 08:07 travis wrote:Show nested quote +On November 01 2016 06:57 Blisse wrote:
So the inner loop happens (n*(n+1))/2 times, which is O(n^2).
The outer loop happens n times, which is O(n).
So the whole thing is O(n^3) ahh thank you yeah my mistake in not multiplying it by the outer loop value
No. This is counting the outer loop twice.
We're talking about this, right?
for (int i = 0; i < n; i++) {
for (int j = n; j >= i; j--) { constant }
}
Two simple iterations bound by n can never be slower than O(n^2). I'll make the inner loop a little slower and at the same time make it easier to see:
Iterate all the way down to 0 instead of i:
for (int i = 0; i < n; i++) {
for (int j = n; j >= 0; j--) { constant }
}
Change the iteration order, from n->0 to 0->n:
for (int i = 0; i < n; i++) {
for (int j = 0; j <= n; j++) { constant }
}
To make this even simpler, use <= in both loops:
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) { constant }
}
None of these transformation made anything faster, and now it is clearly O(n^2).
|
Holy brain fart, you are right, I even did the summation there with the outer loop too lmao
|
ORACLE SPATIAL...
For those who think the only way to make a regular well known text geometry compatible with a spatial column is to convert that spatial column into well known text and convert the resulting well known text and the well known text in the start of the sentence back to sdo geometry (spatial column format). I don't even know whether what I just said makes sense grammatically or not.
|
On October 24 2016 20:06 Manit0u wrote:
Would be thankful if anyone could double-check this code as valid for encrypting/decrypting sensitive data for storage purposes (like personal data inside a database):
Couple of issues:
You seem to be doing MAC-then-encrypt, which is OK, but Encypt-then-MAC is the more standard way of doing things. See http://crypto.stackexchange.com/a/205
You don't check the "strong" value from openssl_random_pseudo_bytes. If the system PRNG is not seeded or there is another issue with it, you could be using insecure random numbers. Also since you're working with old systems, your openssl_random_pseudo_bytes might not be secure at all: https://bugs.php.net/bug.php?id=70014. You may want to look at https://github.com/paragonie/random_compat if this is the case.
|
On November 01 2016 23:13 R1CH wrote:Show nested quote +On October 24 2016 20:06 Manit0u wrote:
Would be thankful if anyone could double-check this code as valid for encrypting/decrypting sensitive data for storage purposes (like personal data inside a database):
Couple of issues: You seem to be doing MAC-then-encrypt, which is OK, but Encypt-then-MAC is the more standard way of doing things. See http://crypto.stackexchange.com/a/205You don't check the "strong" value from openssl_random_pseudo_bytes. If the system PRNG is not seeded or there is another issue with it, you could be using insecure random numbers. Also since you're working with old systems, your openssl_random_pseudo_bytes might not be secure at all: https://bugs.php.net/bug.php?id=70014. You may want to look at https://github.com/paragonie/random_compat if this is the case.
Thanks a lot. Fixed those issues.
|
anyone with ability in java and understanding of OOP/data structures willing to help me study over skype (not a call just text chat) for a couple hours? either tonight or tomorrow night (I am EST).
I'd be willing to pay 20 bucks for 2 hours. 10 dollars an hour. you'll be rich
|
On November 01 2016 05:49 mantequilla wrote:my tip for you is to study heaps they teach 50 different data structures but always ask the fking heaps all the time... or I'm unlucky. I don't like heaps.
Most of the interview questions i got were about stacks or binary trees.
On another note, in my latest interview i had to find the exit from a maze while collecting as many gold sacks as possible. I haven't done anything like that before so it felt pretty hard
|
On November 03 2016 00:48 travis wrote:
anyone with ability in java and understanding of OOP/data structures willing to help me study over skype (not a call just text chat) for a couple hours? either tonight or tomorrow night (I am EST).
I'd be willing to pay 20 bucks for 2 hours. 10 dollars an hour. you'll be rich
will you be implementing data structures with plain java or use structures in the standard library?
|
Does anyone know how I can compile the simplest possible Hadoop MapReduce program (aka the word count) using gradle? Is that even possible? Or do I have to compile using the Hadoop stuff that people download on their computers and shit. If latter, how am I supposed to know which classes belong to which packages and shit?
I am just getting started with Hadoop and I could really use some help with this shit.
|
On November 03 2016 04:40 mantequilla wrote:Show nested quote +On November 03 2016 00:48 travis wrote:
anyone with ability in java and understanding of OOP/data structures willing to help me study over skype (not a call just text chat) for a couple hours? either tonight or tomorrow night (I am EST).
I'd be willing to pay 20 bucks for 2 hours. 10 dollars an hour. you'll be rich will you be implementing data structures with plain java or use structures in the standard library?
both, like a mix
|
Hey, I have a question about writing recursive methods
the single biggest problem I have with recursion is "keeping count" in order to know when I reached a stopping case
example: one of the questions on my review says "Write a recursive method takes two (non-negative) int parameters and returns their product.
But… you may only use +, not * in your code."
I kind of understand what I need to do
something like
private int product(int one, int two) {
if(two > 1) {
two--;
return one + (product(one, two));
} else {
return one;
} }
so.. I think this works
but It required a lot of thought to come up with this
if I could just keep "count" of how many times I called my method it would be a lot easier to solve most of these methods
is there a way to keep count of how many times I call my recursive method without writing a helper method?
the problem for me is if I do something like (as a simplistic non-functional example)
recursiveMethod() {
count = 0;
count++;
recursiveMethod();
}
clearly this doesn't work because every time, count becomes 0 again. so how do you keep count?
edit: shit my way above doesn't work anyways huh. well... hrrmph lol
edit2: ok i fixed it
|
|
|
|
|
|
EPT
