next »

[King Tetiro]

I will admit it. I have a new crack in my armour. I used to think it was networking but now algorithms has become a new weakness of mine. I was using this website to train in preparation for a job interview test

https://codility.com/train/

And I just can't do it. I can't get past the Lesson 2 batch at all. I just suck. And it's gotten to the point I gave into stress. So I just admit it. I can't do algorithms. It's fair to say I'll be withdrawing my job application if the test is just like the practice tests as I can't complete them. But I can at least try and fix this weakness. Can someone point me in the right direction to a tutorial-for-dummies? I want to learn algorithms but I just can't find any decent tutorials.

[Netsu]

The book by Cormen (http://en.wikipedia.org/wiki/Introduction_to_Algorithms) is considered by many to be the bible of algorithm and data structure basics. I recommend you check it out, even if you have very little time it might help with specific problems you encounter.
Algorithms are a very vast field and I doubt a tutorial could help you, it's not like learning the basics of a new language.

If you have any specific questions feel free to ask them here too.

EDIT: Also, what kind of job are you applying for? It usually influences the kind of things they ask you to do at an interview. Unless they first require you to complete a codility test, those are pretty general I'd say and related to what you linked.

[King Tetiro]

The book by Cormen (http://en.wikipedia.org/wiki/Introduction_to_Algorithms) is considered by many to be the bible of algorithm and data structure basics. I recommend you check it out, even if you have very little time it might help with specific problems you encounter.
Algorithms are a very vast field and I doubt a tutorial could help you, it's not like learning the basics of a new language.

If you have any specific questions feel free to ask them here too.

EDIT: Also, what kind of job are you applying for? It usually influences the kind of things they ask you to do at an interview. Unless they first require you to complete a codility test, those are pretty general I'd say and related to what you linked.

From the looks of the role, it doesn't look like Algorithms are the key aspect. However what does concern me is that the Codility tests are ALL Algorithms. I do think that is unfair because I feel confident in programming software. But the tests aren't really showing my abilities because it is in a field I don't know. But that debate is for another day.

What I would like is to be able to complete at least 1 test from each of the lessons. I'd take that as a victory based on the circumstances. The main problem with the tests I am having is that the questions are very hard to understand. Any tips on that?

I will have to find a cheap copy of the book. Very pricey. Do you know of any e-books?

[Netsu]

You could try a library (or a torrent ).
Not sure what you mean by hard to understand, they seem really detailed and straightforward to me, but maybe that's because I'm used to such specifications. Could you give an example of what you couldn't understand? Are you having difficulties with the training lessons and exercises or only with the tests?

[RandyGaul]

Well what kind of algorithms are you wanting to understand? Maybe I can share a small bit of insight I was lucky to have gained: a senior developer at Microsoft recently said something to me along the lines of "When I interview people I just want to know if they understand data structures, can traverse them, and understand everything that is happening in memory".

So if you do come across a silly interview question like this one: http://en.wikipedia.org/wiki/Maximum_subarray_problem, then it's really not your fault but the interview just asked a bad question.

Maybe you would like this book: http://www.amazon.com/Cracking-Coding-Interview-Programming-Questions/dp/098478280X. To me it seems like fairly good quality and it did indeed help me with preparing for interviews.

[King Tetiro]

I have looked through all of the tutorials and it is only really Lessons 9-12 that I have absolutely NO idea about. The rest I understand, but fail to be able to use.

Perhaps we could start at Lesson 2's? I can do FrogRiverOne. But that's the only one I can do. I just can't dissect the other 2 tests to find out what I am supposed to be doing. I think that is another issue. I just can't dissect these questions to find the info I need and translate.

EDIT: I should also state I have difficulties dissecting questions like this.

[Netsu]

So if you do come across a silly interview question like this one: http://en.wikipedia.org/wiki/Maximum_subarray_problem, then it's really not your fault but the interview just asked a bad question.

I think the ability to solve algorithmic problems is a great measure of a programmer's worth. You can always learn a new data structure or language or quickly check how something works in case you forget, but if you can't solve a problem then someone has to solve it for you.

Sorry but I don't see how maximum subarray problem is silly, it's a great question because it has many different complexity solutions. You can quickly come up with a brute force method but solving it in linear time is not that easy.

By the way, a good advice for interviews is not trying too hard to come up with the optimal solution. As soon as you have ANY way of solving the problem - tell it to them, even if it's just brute force. Then if you think you can solve it faster tell them and try.

Perhaps we could start at Lesson 2's? I can do FrogRiverOne. But that's the only one I can do. I just can't dissect the other 2 tests to find out what I am supposed to be doing. I think that is another issue. I just can't dissect these questions to find the info I need and translate.

I'll try and go through the 'PermCheck' one.

First they tell you what a permutation is, it's one of those things many people would just expect you to know, but in case you don't they quickly explain it. Whenever you have a problem with a mathematical term like this wikipedia is actually really helpful (http://en.wikipedia.org/wiki/Permutation).

Then they give you a function specification, what are the arguments and what output is expected. I guess this shouldn't be problematic. The N is the length which isn't said explicitly. This is what you must actually do.

Then they give you examples of input and output, if you understood what a permutation is this should be clear, those are actually the same examples as before.

They tell you the bounds on the arguments - what are the minimum and maximum values of N and of the array elements. This can be important when you might encounter an integer overflow for example.

Lastly they give you bounds on space and time complexity, those are explained in the lessons. Worst-case means that even in the worst possible situation the program should run in O(n).

[King Tetiro]

I managed to do PermCheck because there was an article on what a Permutation was. I am stuck on MaxCounters (but that's because I can't loop through vectors. A tutorial on that would be helpful but optional).

I'm looking at the Lesson 3 batch now.

PassingCars - I can't work out the logic. What on earth are these pairs and where do they come from?

GenomicRangeQuery - I honestly have no idea what I am meant to do in this one.

MinAvgTwoSlice - What are slices? How do I find them?

Actually, whilst typing this it would seem vectors are used non-stop in these tests. Can anyone provide a for-dummies tutorial on vectors? I just can't get them to loop.

[motorherp]

Just had a look and here's what I came up with for PermCheck if it's any use to you:

Code:

#include <algorithm>
 
int solution(vector<int> &A)
{
   std::sort(A.begin(), A.end());
   for(int i = 0; i < A.size(); ++i)
   {
      if(A[i] != i + 1)
         return 0;
   }
   return 1;
}

Interesting site

(I see you beat me to it)

[King Tetiro]

Just had a look and here's what I came up with for PermCheck if it's any use to you:

Code:

#include <algorithm>
 
int solution(vector<int> &A)
{
   std::sort(A.begin(), A.end());
   for(int i = 0; i < A.size(); ++i)
   {
      if(A[i] != i + 1)
         return 0;
   }
   return 1;
}

Interesting site

(I see you beat me to it)

I did mine using C. But I have yet to do it in C++. Can you help? I my vector just won't loop.

http://stackoverflow.com/questions/23034950/c-for-loop-and-vectors/

EDIT: Still drowning in Lesson 3. Funny how it says how I'll end up loving programming. Right now I hate it

Any help on Lesson 3 is widely appreciated. As well as to why it would trip people up.

[Netsu]

PassingCars - I can't work out the logic. What on earth are these pairs and where do they come from?

GenomicRangeQuery - I honestly have no idea what I am meant to do in this one.

MinAvgTwoSlice - What are slices? How do I find them?

The pairs are pairs of cars that are travelling in opposite directions i.e. they are passing each other. A car going east must pass every car that goes west.

A slice is just a range within the array. It is represented by a pair where the first element is the start and the second is the end of the range.

[King Tetiro]

PassingCars - I can't work out the logic. What on earth are these pairs and where do they come from?

GenomicRangeQuery - I honestly have no idea what I am meant to do in this one.

MinAvgTwoSlice - What are slices? How do I find them?

The pairs are pairs of cars that are travelling in opposite directions i.e. they are passing each other. A car going east must pass every car that goes west.

A slice is just a range within the array. It is represented by a pair where the first element is the start and the second is the end of the range.

I see. But I fail to see where the values are coming from. For example, these pairs.

For example, consider array A such that:
  A[0] = 0
  A[1] = 1
  A[2] = 0
  A[3] = 1
  A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

This is what is frustrating me. I have values and I don't know where they are coming from.


Slice - Hmm. Does that mean that it can be at any position and any given length? If so, doesn't that mean that you'd have to perform 2 loops for MinAvgTwoSlice? One for the start position of the slice and the second loop for length of the slice?

[Cheesegrater]

Sorting the list for PermCheck is O(N lg N), not O(N). You just want to loop over the array and count the values. That they give you O(N) memory space is a clue.

I don't mean to sound harsh, but if you can't write something like looping over a STL vector off the top of your head, I wouldn't hire you for a C++ job. I suggest you worry about basic STL first.

[King Tetiro]

Sorting the list for PermCheck is O(N lg N), not O(N). You just want to loop over the array and count the values. That they give you O(N) memory space is a clue.

I don't mean to sound harsh, but if you can't write something like looping over a STL vector off the top of your head, I wouldn't hire you for a C++ job. I suggest you worry about basic STL first.

That's ok. I'm not going to sugar coat it either. I haven't learned about vectors yet. Somehow that fell through the cracks at university. I am trying to find a tutorial to cover this. I can't find anything though. I don't know everything. Today has taught me that. But at please don't comment like that unless you can provide a tutorial. How does commenting like that help anyone if you don't provide the means to assist?

As for the PermCheck, that's what I did in my C practice. Got a good % on that.

[Cheesegrater]

Cprogramming.com isn't terrible.

Here's my permcheck, using STL iterators for the looping:

Code:

int solution(vector<int> &A) {
    // write your code in C++98
    vector<int> aCount(A.size(), 0);
    vector<int>::iterator iter;
    
    for(iter = A.begin(); iter != A.end(); ++iter)
    {
        //*iter deref potentially expensive
        int val = *iter;
        if(val > aCount.size())
            return 0;
    
        aCount[val - 1] += 1;
    }
    
    for(iter = aCount.begin(); iter != aCount.end(); ++iter)
    {
        if((*iter) != 1)
            return 0;
    }
    
    return 1;
}

It could be faster, but it's clear (I hope).

[Netsu]

I see. But I fail to see where the values are coming from. For example, these pairs.

For example, consider array A such that:
  A[0] = 0
  A[1] = 1
  A[2] = 0
  A[3] = 1
  A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

This is what is frustrating me. I have values and I don't know where they are coming from.


Slice - Hmm. Does that mean that it can be at any position and any given length? If so, doesn't that mean that you'd have to perform 2 loops for MinAvgTwoSlice? One for the start position of the slice and the second loop for length of the slice?

The values in the pairs are array indexes.

Yes, you could do MinAvgTwoSlice in two loops, which is the brute force solution of O(n^2) complexity. It can be done in linear time too though. You might want to check out the link posted by RandyGaul earlier, it's pretty much the same basic problem and can be solved in a similar way.

[King Tetiro]

I think the brute force approach. It's better I learn the basics before going for efficiency.

Right I'm on the MinAvgTwoSlice exercise. I have the idea and the theory sorted. However I am having difficulty implementing it. What I need is to use the iter that Cheesegrater detailed about to divide my total (to get the slice average). However this is an incompatible variable. Can anyone help?

Is it possible for anyone to do MaxProductOfThree? I thought I got it right but I only got 44%. So obviously I missed something but I can't see what.

[Netsu]

You said you feel confident programming software, what experience do you have with that?
To be honest the problems you are having seem like problems of someone with no formal programming education and no professional experience. If that is the case I would suggest looking for a C++ course. Where I live lectures at universities are open to everyone, a book or an online tutorial on C++ wouldn't hurt either, and whenever you don't understand anything you can check www.cplusplus.com which has specifications for all standard and STL functions/classes.

[King Tetiro]

You said you feel confident programming software, what experience do you have with that?
To be honest the problems you are having seem like problems of someone with no formal programming education and no professional experience. If that is the case I would suggest looking for a C++ course. Where I live lectures at universities are open to everyone, a book or an online tutorial on C++ wouldn't hurt either, and whenever you don't understand anything you can check www.cplusplus.com which has specifications for all standard and STL functions/classes.

Honestly, went to university. Studied hard and left pretty high up in my class. Left with a great grade as well. I think somewhere since then my skills have dwindled. Perhaps a C++ course is needed to refresh my memory. It's been 2 years since university.

Sometimes it's hard to program with a learning disability. I do my best. After this weekend I've decided to go back to my university to relearn my skills. Hopefully on friday I will be back to where I left university.

Sorry to be a burden to you all.

[motorherp]

Sorting the list for PermCheck is O(N lg N), not O(N). You just want to loop over the array and count the values. That they give you O(N) memory space is a clue.

Good catch, I missed that.  Strangely enough using sort still gave 100% in the test so I guess you should take the results with a pinch of salt.