Leetcode random challenge

[Cicero]

Leetcode random challenge Wk1 & 2

I've started doing a 'Leetcode challenge' with a mate of mine. Its quite fun, challenging and a little competitive at times, so thought perhaps some people here would be keen on doing the same, a mybb leetcode challenge.

How it works:

• We use the random question picker, and all attempt it.
• Then only move on once everyone's done, or perhaps give it max a week for people struggling with time.
• No cheating/looking at the editorial solution until your soln is accepted, and you're convinced you can't get it any quicker.
• Language is up to you, this may help people appreciate other languages as well
• Only post your time taken, language, and percentage of submissions beaten at first. Until such a time as the majority of people are done. Then post code, compare, discuss and help.

I'm an embedded programmer, so I do them all in C, and for me I've found its really helped my algorithm knowledge and dynamic programming so far - something which isn't really taught in EE. Its also highlighted some shortcomings of mine, especially with time optimisation.

If anyone is keen, comment here and we can begin.

 

[Cicero]

Actually, lets start with the first one to get you warmed up.

(11-7-2017 to 17-11-2017) Two sum: - https://leetcode.com/problems/two-sum/#/description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My result for C:
Runtime: 59 ms, beats 83.49% of submissions

Spoiler

My first brute force attempt.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int *retVals = malloc(2*sizeof(int));
    int i,j,k,num2;
    for (i=0,k=1; i<numsSize-1; i++,k++) {   
        num2 = target - nums[i]; 
        for (j=k;j<numsSize;j++) {
            if (num2 == nums[j]) {
                retVals[0] = i;
                retVals[1] = j;
                goto ret;
            }
        }
    }
    ret:
    return retVals;
}

So far our times are as follows:
1. Two Sum

C

1. cguy - 3ms
2. Cicero - 59ms

Js

1. John_Phoenix - 105ms

Java

1. Johnatan56 - 27ms

Swift

1. [)roi(] - 2ms

 

[John_Phoenix]

It's On like Donkey Kong!

 

[cguy]

Interesting. It's a pretty trivial question, but making it fast (in upper percentiles) would be quite challenging.

 

[Cicero]

Interesting. It's a pretty trivial question, but making it fast (in upper percentiles) would be quite challenging.

Yup, thats it. Hopefully thats a challenge accepted? Keen for a fellow c guy...cguy.

 

[cguy]

Yup, thats it. Hopefully thats a challenge accepted? Keen for a fellow c guy...cguy.

Heh - will see if I have some time after work. I do have some ideas - I expect that the key thing for performance here is to come up with an expected time O(N) algorithm. O(N^2) is trivial.

 

[SBSP]

I had my go at it. Did it in VB.NET sure I can do it in C using my Arduino IDE. But how do I get the execution time ?
Looks like getting it right is not the challenge its all about efficiency ?

 

[John_Phoenix]

Javascript Entry

Meh, JS is slow...

 

[Johnatan56]

Java brute force:
19 / 19 test cases passed.
Status: Accepted
Runtime: 39 ms


I look at the stuff people beat me with and I just give up.

Actually Droid was trying to explain it to me at one point as it was quite a bit faster than what I was doing (the 8ms solution).

8ms (seems the norm):

Spoiler

public class Solution {
public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(target - numbers[i])) {
            result[1] = i;
            result[0] = map.get(target - numbers[i]);
            return result;
        }
        map.put(numbers[i], i);
    }
    return result;
}
}

3ms (leader):

Spoiler

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        short[] map = new short[20050];
        int size = 50;
        for (int i = 0; i < nums.length; i++) {
            map[nums[i] + size] = (short) (i + 1);
            int diff = target - nums[i + 1] + size;
            if (diff < 0) continue;
            short d = map[diff];
            if (d > 0)
                return new int[]{d - 1, i + 1};
        }
        return null;
        
        
    }
}

EDIT:
I accidentally resubmitted the same solution, now it's 27ms. :wtf:
I think server loads is important in this case.

 

[cguy]

First attempt (it's O(n)):

19 / 19 test cases passed.
Status: Accepted
Runtime: 3 ms
Faster than 92.29% of C submissions.

Spoiler

int* twoSum(int* nums, int numsSize, int target) {
    int indexof[32768];
    int * result = (int*)malloc(2*sizeof(int));
    memset(indexof,0,32768*sizeof(int));
    for( int i=0; i < numsSize; i++ ) {
        int n     = nums[i];
        int delta = target - n;
        if ( indexof[delta + 16384] || ( nums[0] == delta && i > 0 ) ) {
            result[0] = indexof[delta + 16384];
            result[1] = i;
            return result;
        }
        indexof[n+16384] = i;
    }
    return NULL;
}

I have another solution that should be much faster, but it's not reporting as faster on their system. My suspicion is that the launch overhead is dominating the run when you get below 3ms.

This also appears to be some sort of managed environment - I can't even use SIMD instructions.

 

[SBSP]

If you are not using any of the languages available on the dropdown its pointless comparing speeds.

In VB.NET If I datediff from the time taken before and after my code I get between 1s and 500 ms using the brute force method.

 

[John_Phoenix]

I noticed the same thing in Js, my jsfiddle test runs where coming in below 10ms and I was testing on a fibonacci array(100), figured it took the average of the 19 test runs...

 

[Cicero]

Nice attempts everyone.

I also find the timing can be a little erratic, even on the same submission. For the final time grade it has to be an average, or weighted average for the test set.

But its good enough as a rough benchmark.

 

[Cicero]

I had my go at it. Did it in VB.NET sure I can do it in C using my Arduino IDE. But how do I get the execution time ?
Looks like getting it right is not the challenge its all about efficiency ?

Why worry about Arduino IDE's? Just select C as the language and test your submission.

 

[SBSP]

Why worry about Arduino IDE's? Just select C as the language and test your submission.

Will try.
I cant compete with my brute force attempt though. I eventually looked at the awnser and I dont understand the O(n) concept neither do I get the the whole Hash map thing!. When i looked at the answer i was amazed It was a bit unexpected.

So I will be sitting out this round and see what everyone came up with.

 

[Cicero]

Will try.
I cant compete with my brute force attempt though. I eventually looked at the awnser and I dont understand the O(n) concept neither do I get the the whole Hash map thing!. When i looked at the answer i was amazed It was a bit unexpected.

So I will be sitting out this round and see what everyone came up with.

Nah brother, that's why we do this. To learn and get better over time, eventually the more you do and see how others do it, the more those faster solutions will pop into your head earlier. You'll surprise yourself at times I bet.

My attempt wasn't an O(n) solution, I mean look at my time for C, pretty poor compared to cguy who's matched the top time. Just give it a go, no judging.

 

[SBSP]

Regarding the differences computing time. Are you absolutely sure your code isnt the cause ? Depending on the order of the Array and the target , your code should take more and less time to calculate every time you run it.maybe worth sorting it to improve your luck?

Besides that.

I think I found a cheaper way to get this done! :crylaugh:
It should reduce the computing time by more than half compared to my original attempt (In theory). Only problem is I cant get my code to work with Leet code, I wrote it out and compiled it using an online compiler http://cpp.sh/ But I lack the know how to construct it to be acceptable by LeetCodes submission box.

Anyone willing to help me reconstruct the code to be acceptable ? (Please only check it without submitting it I would like to submit it on my LeetCode Profile)

Cheers!

 

[Cicero]

Regarding the differences computing time. Are you absolutely sure your code isnt the cause ? Depending on the order of the Array and the target , your code should take more and less time to calculate every time you run it.maybe worth sorting it to improve your luck?

Besides that.

I think I found a cheaper way to get this done! :crylaugh:
It should reduce the computing time by more than half compared to my original attempt (In theory). Only problem is I cant get my code to work with Leet code, I wrote it out and compiled it using an online compiler http://cpp.sh/ But I lack the know how to construct it to be acceptable by LeetCodes submission box.

Anyone willing to help me reconstruct the code to be acceptable ? (Please only check it without submitting it I would like to submit it on my LeetCode Profile)

Cheers!

PM me, I'll check it out.

 

[SBSP]

pm sent thanks!

 

[cguy]

Will try.
I cant compete with my brute force attempt though. I eventually looked at the awnser and I dont understand the O(n) concept neither do I get the the whole Hash map thing!. When i looked at the answer i was amazed It was a bit unexpected.

So I will be sitting out this round and see what everyone came up with.

As a brief explanation, the brute force approach goes through n values in the array, and for each one of these values (call it x) checks another n values to see if one of these values when added to the x, will equal the target. The inside part of the two for loops can run up to n*n times, so it is O(n*n). If you can avoid doing the second loop entirely, it will be O(n).

The purpose of the hash maps, is that they can look up the value "target - x", where x is the number for the current loop iteration, to see if it has been seen already in the current iteration - if it has, that value and the current value are the pair we want, and we are done. This lookup can be done without a loop (since hash maps typically have expected time O(1)).

What I did with the big "indexof" array, was essentially implement a very big, very fast hashmap, with worse case O(1) complexity, and a trivial hash function, so that it would be very fast. The downside of this, is that if the range of numbers was larger, the array could easily become too big, in which case, I would go for a more traditional hash map data structure.

Amusingly, the leading solution posted earlier did something similar, but must have submitted a bunch of times to narrow down the array range of the test set inputs as closely as possible.