• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 15:41
CET 21:41
KST 05:41
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #2312[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over6Dark completes military service, returns to SC217[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
Weekly Cups (Nov 9-15): Clem and herO take over SC4ALL: II Indiegogo Campaign Announcement No more SC2 streamers on team liquid? Team Liquid Map Contest #23 StarCraft open world shooter announced at BlizzCon
Tourneys
RSL goes to London! 2026 Offline Finals Nov 21-22 soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16) Sparkling Tuna Cup - Weekly Open Tournament Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 553 Undermined The PondCast: SC2 News & Results Mutation # 552 Secret Storm Mutation # 551 Robotic Revival
Brood War
General
People still play BW? List of top players active on ShieldBattery SC4ALL: II Indiegogo Campaign Announcement XUN appreciation thread BW General Discussion
Tourneys
$3,000 Sijosae Tier 2,3,4 Cup (Nov 23-24 2026) [BSL23] Ro16 Group B - Saturday 21:00 CET 2v2v2v2 Tournament Stage 2: Players KCM Race Survival 2026 Season 4
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Nintendo Switch Thread The PlayStation 5 Stormgate/Frost Giant Megathread Warcraft III: The Frozen Throne Free Space RTS Game, optimised f. Phone/Tablet etc
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread The Games Industry And ATVI Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine Trading/Investing Thread
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Formula 1 Discussion Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
James Bond movies ranking - pa…
Topin
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Customize Sidebar...

Website Feedback

Closed Threads



Active: 10559 users

The Big Programming Thread - Page 789

Forum Index > General Forum
Post a Reply
Prev 1 787 788 789 790 791 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.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2016-10-31 19:41:29
October 31 2016 18:46 GMT
#15761
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?
mantequilla
Profile Blog Joined June 2012
Turkey781 Posts
Last Edited: 2016-10-31 20:11:48
October 31 2016 20:05 GMT
#15762
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
Age of Mythology forever!
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2016-10-31 20:25:23
October 31 2016 20:23 GMT
#15763
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.
RoomOfMush
Profile Joined March 2015
1296 Posts
October 31 2016 20:44 GMT
#15764
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.
mantequilla
Profile Blog Joined June 2012
Turkey781 Posts
October 31 2016 20:49 GMT
#15765
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.
Age of Mythology forever!
spinesheath
Profile Blog Joined June 2009
Germany8679 Posts
October 31 2016 21:22 GMT
#15766
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.
If you have a good reason to disagree with the above, please tell me. Thank you.
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2016-10-31 22:00:13
October 31 2016 21:57 GMT
#15767
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)
There is no one like you in the universe.
Blitzkrieg0
Profile Blog Joined August 2010
United States13132 Posts
Last Edited: 2016-10-31 23:12:54
October 31 2016 22:13 GMT
#15768
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.
I'll always be your shadow and veil your eyes from states of ain soph aur.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
October 31 2016 23:07 GMT
#15769
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
spinesheath
Profile Blog Joined June 2009
Germany8679 Posts
Last Edited: 2016-10-31 23:41:42
October 31 2016 23:39 GMT
#15770
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).
If you have a good reason to disagree with the above, please tell me. Thank you.
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
November 01 2016 01:46 GMT
#15771
Holy brain fart, you are right, I even did the summation there with the outer loop too lmao
There is no one like you in the universe.
Djagulingu
Profile Blog Joined December 2010
Germany3605 Posts
Last Edited: 2016-11-01 10:22:05
November 01 2016 10:20 GMT
#15772
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.
"windows bash is a steaming heap of shit" tofucake
R1CH
Profile Blog Joined May 2007
Netherlands10343 Posts
November 01 2016 14:13 GMT
#15773
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.
AdministratorTwitter: @R1CH_TL
Manit0u
Profile Blog Joined August 2004
Poland17875 Posts
November 02 2016 11:23 GMT
#15774
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/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.


Thanks a lot. Fixed those issues.
Time is precious. Waste it wisely.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
November 02 2016 15:48 GMT
#15775
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
Isualin
Profile Joined March 2011
Germany1903 Posts
November 02 2016 17:03 GMT
#15776
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
| INnoVation | The literal god TY | ByuNjwa | LRSL when? |
mantequilla
Profile Blog Joined June 2012
Turkey781 Posts
November 02 2016 19:40 GMT
#15777
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?
Age of Mythology forever!
Djagulingu
Profile Blog Joined December 2010
Germany3605 Posts
November 02 2016 19:48 GMT
#15778
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.
"windows bash is a steaming heap of shit" tofucake
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
November 02 2016 20:24 GMT
#15779
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
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2016-11-02 20:59:17
November 02 2016 20:53 GMT
#15780
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
Prev 1 787 788 789 790 791 1032 Next
Please log in or register to reply.
Live Events Refresh
BSL
05:00
S23 - Ro16 Group D
Bonyth vs Doodle
Kyrie vs Jimin
ZZZero.O244
LiquipediaDiscussion
IPSL
02:00
Ro16 Group A
Ret vs ggnore13
nOmaD vs Aether
Liquipedia
RSL Revival
22:00
Offline Finals: Playoffs
Serral vs herOLIVE!
Tasteless2691
ComeBackTV 1463
RotterdaM1244
IntoTheiNu 701
TaKeTV 594
IndyStarCraft 472
kabyraGe 262
LamboSC2232
Rex63
3DClanTV 62
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Tasteless 2691
RotterdaM 1244
IndyStarCraft 472
LamboSC2 232
ProTech132
Rex 63
JuggernautJason12
EmSc Tv 9
StarCraft: Brood War
Britney 26705
Shuttle 340
ZZZero.O 244
Noble 6
Dota 2
Gorgc7853
Counter-Strike
pashabiceps1727
gobbtv67
Heroes of the Storm
Khaldor510
Liquid`Hasu436
Other Games
tarik_tv4296
Grubby2739
FrodaN1377
B2W.Neo683
ToD77
Mew2King63
Pyrionflax37
Railgan10
Organizations
Other Games
gamesdonequick964
StarCraft 2
EmSc Tv 9
[ Show 15 non-featured ]
StarCraft 2
• Adnapsc2 13
• maralekos8
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• 80smullet 13
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• WagamamaTV659
Other Games
• imaqtpie975
• Shiphtur378
• tFFMrPink 10
Upcoming Events
Replay Cast
2h 19m
Tournament
11h 19m
WardiTV Weekly
15h 19m
Ultimate Battle
15h 19m
Bisu vs Light
Kung Fu Cup
1d 14h
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
2 days
The PondCast
3 days
KCM Race Survival
3 days
Liquipedia Results

Completed

Proleague 2026-11-17
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
RSL Offline Finals
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3

Upcoming

CSL Season 23: Qualifier 1
Sector 591
Sijosae Cup
CSL Season 23: Qualifier 2
YSL S4
SC4ALL II: Brood War
CSL 2026 Winter (S23) - 3v3
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.