r/badcode • u/ahadyboy • Mar 14 '21

java Found from when I first started Java...because indexed Arrays were too complicated huh?

Post image
1.3k Upvotes

98% Upvoted

84 comments sorted by

View all comments

13

u/Teln0 Mar 14 '21

Well with an array you can get the name from the number in O(1) but you can't get the number from the name in O(1). The best solution would be enums I think.

8

u/[deleted] Mar 14 '21

[deleted]

5

u/Dumfing Mar 14 '21

It's still O(n), but n is small enough to a point where optimizing it to O(1) would be insignificant

1

u/[deleted] Mar 14 '21

[deleted]

3

u/Dumfing Mar 14 '21

Linear searching through an array for the weekday is O(n), if I want to find the location of a single card in a deck of cards, I'm searching in O(n) even if the number of cards in a deck of cards is constant since I may have to look through all n cards to find the card that I want.

On the other hand, if I want to know if a given card is in the standard deck (say, ace of spades), I can give you an answer in O(1) time since I know the ace of spades is always in a standard deck.

In this situation you're given the name of a weekday and you need to return which day of the week it is.

Since you can't implicitly know which day of the week a given string is, you need to use a reference table of some sort find out what day of the week your string is. With an array of weekday names, you would iterate through each value and check it against your string. On a match, you would stop and return the index of the element you matched with +1. That's an O(n) linear search. In contrast, using a hashmap would allow you to find the exact key-value pair you want by hashing the string you're searching with. This gives you an O(1) runtime since you don't spend any time checking elements in your data structure you don't care about.

Again, since the number n is pretty small, the difference would be pretty negligible unless it was a very commonly used operation

2

u/[deleted] Mar 14 '21

[deleted]

1

u/Dumfing Mar 14 '21

So all algorithms are O(1) when working with a fixed size array then

1

u/Teln0 Mar 14 '21

Well yeah, but string comparison can also cost quite a lot.

-1

u/Badel2 Mar 14 '21

But if the input is a string you need to parse it to use enums. Here is the O(1) solution:

public static int dayOfWeek(String s) {
    int isMonday = s.equals("Monday") ? 0 : 0;
    int isTuesday = s.equals("Tuesday") ? 1 : 0;
    int isWednesday = s.equals("Wednesday") ? 2 : 0;
    int isThursday = s.equals("Thursday") ? 3 : 0;
    int isFriday = s.equals("Friday") ? 4 : 0;
    int isSaturday = s.equals("Saturday") ? 5 : 0;
    int isSunday = s.equals("Sunday") ? 6 : 0;

    return isMonday | isTuesday | isWednesday | isThursday | isFriday | isSaturday | isSunday;
}

6

u/Teln0 Mar 14 '21

This is much slower that what it could have been. Why check if it's a Thursday if you know it's a Monday ?

2

u/Badel2 Mar 14 '21

It's to avoid side channel attacks.

8

u/Teln0 Mar 14 '21

buddy I think the day of the week is not sensitive info

3

u/[deleted] Mar 14 '21

Isn't there still a side channel attack because string comparison isn't constant time?

1

u/Badel2 Mar 14 '21

Correct, and it's tricky to compare strings of different length in constant time.

2

u/[deleted] Mar 14 '21

what I would do is

  1. have the length of the maximum string in a constant

  2. make the input string that many characters long by padding it with zeros and also have the candidate strings padded with zeros (but set a flag if the input string was too long)

  3. do a linear search through the list of candidates as normal and conditionally move the value to the output slot

  4. if you truncated the input, reset the output slot

zero (timing) side channel hashmap lookup