Google Kickstart

[parinjoy]

I am participating in this year's google kickstart but I have no idea about what to do. I watched the introduction video on youtube but they were talking of some O(N²) complexity. Couls anyone who have participated in kickstart provide my guidelines. Thank You.

 

[Eigenvektor]

What kind of guidelines in particular are you looking for? This is a coding competition, so essentially you're given a task and are expected to write some code to solve it. How much experience as a developer do you have? O(n) is a fairly standard notation for the complexity of an algorithm (how will it run-time increase with more work to do)

 

Since this is intended as a challenge/competition, asking for outside help kind of goes against the spirit. Since Google also uses this to find potential candidates for a job interview, don't expect too much help with specific tasks from people participating in it.

 

https://codingcompetitions.withgoogle.com/kickstart/about/

[shadow_ray]

1 hour ago, Eigenvektor said:

O(n) is a fairly standard notation for the complexity of an algorithm (how will it run-time increase with more work to do)

Time complexity is often time less well-known among self taught devs. Bootcamps also tend focus way more on technologies than on math/algorithms.

 

Quote

The three-hour rounds feature a variety of algorithmic challenges, all developed by Google engineers so that you get a taste of the technical skills needed for a career at Google (the top competitors from our Kick Start rounds may be invited to interview at Google!).

Hehe, in lot's of positions it is not something people have to deal with on a daily basis. Sure it's more important on projects where the user base is huge  or there is a huge amount of data to be processed, both cases apply to google but I still think it's funny.

[Eigenvektor]

21 minutes ago, shadow_ray said:

Hehe, in lot's of positions it is not something people have to deal with on a daily basis. Sure it's more important on projects where the user base is huge  or there is a huge amount of data to be processed, both cases apply to google but I still think it's funny.

Yeah, lot's of job interviews do that. It's more about how you approach problems and how you handle stress rather than normal work situations. Which kind of makes sense. They need someone they can rely on in critical situations, not just everyday work.

[DeadlyHippo]

56 minutes ago, shadow_ray said:

Time complexity is often time less well-known among self taught devs. Bootcamps also tend focus way more on technologies than on math/algorithms.

 

Hehe, in lot's of positions it is not something people have to deal with on a daily basis. Sure it's more important on projects where the user base is huge  or there is a huge amount of data to be processed, both cases apply to google but I still think it's funny.

I find this funny as well.

 

I write n^2 stuff all the time. When your data set is tiny it doesn't matter. Maintainability is WAY more important. You can usually find a library that does what you need in a the correct time complexity necessary. I have never liked this coding challenges and now refuse to do them in interviews. I wouldn't be caught dead at a job that required that level of complexity in day to day work. I can google the maths and then google and import the lib that does the thing I need (or if necessary recreate the maths in whatever language I am restricted to).

[Wictorian]

1 hour ago, DeadlyHippo said:

I write n^2 stuff all the time

redflag

[DeadlyHippo]

2 hours ago, Wictorian said:

redflag

How much software have you worked on in your life that has made it to production?

 

I find it really sad that you followed me from your own thread to make this comment. Get a life kid.

[shadow_ray]

18 hours ago, DeadlyHippo said:

How much software have you worked on in your life that has made it to production?

 

I find it really sad that you followed me from your own thread to make this comment. Get a life kid.

Back to time complexities. There are problems that cannot be solved in polynomial time to begin with (given P != NP), furthermore every O(n) problem is also in O(n^2) and even in O(n!), so saying that O(n^2) is a red flag doesn't make much sense.

 

In some cases software don't have to deal with  huge amount of data. For example the front end javascript code usually only keeps as much data as necessary for displaying stuff on a screen and if an operation is needed on a collection with multiple billion elements (not an exaggeration), that usually happens on beefy back end servers. In this case it doesn't make financial sense to spend days on developing super efficient and convoluted algorithms to save 1-2 ms.

[Takumidesh]

On 8/23/2022 at 5:19 PM, Wictorian said:

redflag

immediately discounting something like that is never a good idea.

 

if you have a list of 5 things, why would you waste time trying to save a microsecond during runtime, if you spent even one second trying to optimize that code it would only pay off in a strict time sense after 1,000,000 executions.

 

I still use linq even when iterating over collections with 100k plus items, because the time spent optimizing it is not worth the gains, especially since 99% of the time there is a larger bottleneck somewhere else in the code.

 

design time vs runtime efficiencies are a balancing act.

[DeadlyHippo]

Well said both @shadow_rayand @Takumidesh.

 

Recently I got to write a Java library that did some annotation processing and effectively serialized a graph of generic method calls to disk to be packaged with the app and later used at run time. Luckily I knew enough graph theory to know what I was looking for and there was a great library to leverage. Sure the time complexity is very low at theta (e+v)log v but I know that the data set will never even reach the hundreds so that was never the concern anyway. In fact I made a mistake in the way I wrote part of the code and the object initialization was almost doubling the runtime of the method chaining. Fixing that was way more worth the effort than would have been trying to make the most performant version of Dijkstra's shortest path.

 

FWIW, there is nothing wrong with trying to optimize for fun. But rarely in a business context does it make sense to start out thinking "I need to have the most performant code possible" unless that is specifically driven by a constraint.

 

The attached image is a solution I made with primitives only. If I were to read that code now, even with comments, I would not be able to mess with it. If I wrote a more maintainable solution I could fix a bug in the code. Not mention I saved a whole 1-2ms over most other solutions. Granted my memory performance was significantly better (again, primitives).

 

@parinjoy doing leetcode/kickstart type challenges time complexity is what you are going for. If you are not familiar check out this wiki article. Basically try to write code using primitives only and you will be far more memory efficient and time efficient than most other solutions.

 

 

 

EDIT: I looked at the solution to the above leetcode challenge... what a freakin' nightmare it is to read. LOL
 

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1.next == null && l2.next == null) {
            if(l1.next == null) {
                l1.next = new ListNode(0);
            }
            if(l2.next == null) {
                l2.next = new ListNode(0);
            }
            int thisDigit = l1.val + l2.val;
            int remainder = thisDigit - 10;
            if(remainder >= 0) {
                l1.next.val += 1;
                thisDigit -= 10;
                return new ListNode(thisDigit, addTwoNumbers(l1.next, l2.next));
            }
            return new ListNode(l1.val + l2.val);
        }
        if(l1.next == null) {
            l1.next = new ListNode(0);
        }
        if(l2.next == null) {
            l2.next = new ListNode(0);
        }
        int thisDigit = l1.val + l2.val;
        int remainder = thisDigit - 10;
        if(remainder >= 0) {
            l1.next.val += 1;
            thisDigit -= 10;
        }
        return new ListNode(thisDigit, addTwoNumbers(l1.next, l2.next));
    }
}

 

Edited August 25, 2022 by DeadlyHippo

[Wictorian]

2 hours ago, Takumidesh said:

immediately discounting something like that is never a good idea.

 

if you have a list of 5 things, why would you waste time trying to save a microsecond during runtime, if you spent even one second trying to optimize that code it would only pay off in a strict time sense after 1,000,000 executions.

 

I still use linq even when iterating over collections with 100k plus items, because the time spent optimizing it is not worth the gains, especially since 99% of the time there is a larger bottleneck somewhere else in the code.

 

design time vs runtime efficiencies are a balancing act.

ofc sometimes it makes sense. but he said he did it all the time. and you know the pain if you have been calculating primes using python.

[Franck]

18 minutes ago, Wictorian said:

if you have been calculating primes using python.

Funny that I have been programming for 31 years and never had to calculate prime numbers 

[Eigenvektor]

1 hour ago, Wictorian said:

ofc sometimes it makes sense. but he said he did it all the time. and you know the pain if you have been calculating primes using python.

All the time doesn't mean every time.

[Wictorian]

58 minutes ago, Eigenvektor said:

All the time doesn't mean every time.

idk im not native american 

so can we say americans do genocides all the time? 

[Eigenvektor]

8 hours ago, Wictorian said:

idk im not native american 

so can we say americans do genocides all the time? 

That's a bit of a weird example (not a native speaker myself btw)

 

All the time means you do something with a certain regularity/very often but not constantly. So if someone says they write inefficient algorithms "all the time", it means they do it with some regularity, but it doesn't necessarily mean that every algorithm they write is inefficient (e.g. they still put effort into writing an efficient algorithm when it matters).

[Wictorian]

8 hours ago, Eigenvektor said:

That's a bit of a weird example (not a native speaker myself btw)

 

All the time means you do something with a certain regularity/very often but not constantly. So if someone says they write inefficient algorithms "all the time", it means they do it with some regularity, but it doesn't necessarily mean that every algorithm they write is inefficient (e.g. they still put effort into writing an efficient algorithm when it matters).

if you wanna remember something it should either really matter to you or should be absurd. Either really or artificially. Which means you can imagine absurd things to remember something. (tip by Elon Musk) 

 

However this example isnt much absurd I guess.

[wasab]

 

On 8/25/2022 at 11:15 AM, Takumidesh said:

if you have a list of 5 things, why would you waste time trying to save a microsecond during runtime, if you spent even one second trying to optimize that code it would only pay off in a strict time sense after 1,000,000 executions

In my experiences, network speed bottlenecks more often than say a bad alorigthm or a slow hardware. If your softwares, and hardwares (harddrives, cpu, ect) can process 100gb of data per second for example, and your internet speed only allows you to download 50gbps, doesnt matter how fast your hardware and softwares are, you are bottleneck at 50gbps.