Algorithms

[Wictorian]

about which algorithms am I supposed to know other than searching and sorting algorithms?

[Zalosath]

12 minutes ago, Wictorian said:

about which algorithms am I supposed to know other than searching and sorting algorithms?

Too generic of a question. There's an infinite number of algorithms.

Usually if you need an algorithm, you make it yourself to custom fit the application, or use StackOverflow to find a base that works for you.

[Wictorian]

Just now, Zalosath said:

Too generic of a question. There's an infinite number of algorithms.

Usually if you need an algorithm, you make it yourself to custom fit the application, or use StackOverflow to find a base that works for you.

I mean what are the algorithms to get a job.

[Zalosath]

7 minutes ago, Wictorian said:

I mean what are the algorithms to get a job.

Most companies look for problem solving skills as oppose to knowing an algorithm off by heart, don't worry about it too much, so long as you have a good understanding of how to write an algorithm, and how the basic sorting and searching algorithms work, you're fine.

[wanderingfool2]

6 minutes ago, Wictorian said:

I mean what are the algorithms to get a job.

Everything depends on what employer you are going for and what position (e.g. software engineer vs programmer would be 2 different things).  I know of some people who have been asked regarding sorting algos (standard bubble sort kind of thing) and write pseudo code to do it.

 

In general the biggest thing is the problem solving and being able to come up with algorithmns or adapt algorithms (and program them).  Just look up general programming interview questions and you will see roughly the kinds of things some employers ask for.  It doesn't help to just memorize them though, you need to understand the concepts behind them because they could easily tweak it and make it a completely different question but having a similar thought process how to solve it.

 

Some employers even ask questions that they don't expect you to get the optimal solution immediately, instead they let you work through with a quick case and then let you think to see if it can be optimized.  So it all really depends on where and what you plan to do.

 

Honestly a good approach to get a job would be trying to contribute to open source communities, so that you can develop a portfolio of your work.  It lets you practice algo design and implementation but also lets you keep up with stuff.

[Wictorian]

6 minutes ago, wanderingfool2 said:

Everything depends on what employer you are going for and what position (e.g. software engineer vs programmer would be 2 different things).  I know of some people who have been asked regarding sorting algos (standard bubble sort kind of thing) and write pseudo code to do it.

 

In general the biggest thing is the problem solving and being able to come up with algorithmns or adapt algorithms (and program them).  Just look up general programming interview questions and you will see roughly the kinds of things some employers ask for.  It doesn't help to just memorize them though, you need to understand the concepts behind them because they could easily tweak it and make it a completely different question but having a similar thought process how to solve it.

 

Some employers even ask questions that they don't expect you to get the optimal solution immediately, instead they let you work through with a quick case and then let you think to see if it can be optimized.  So it all really depends on where and what you plan to do.

 

Honestly a good approach to get a job would be trying to contribute to open source communities, so that you can develop a portfolio of your work.  It lets you practice algo design and implementation but also lets you keep up with stuff.

thanks. i know. i appreciate the extra information. i really do. but it would be neat if you also actually answered the question. maybe the answer is "there are no more algorithms you need to know about"¿

 

about the open source thing i tried to contribute but couldnt even find a project to contribute to. now i would really appreciate it if you explained how exactly i would go about doing that or linking a tutorial or something is fine too.

[Eigenvektor]

Are you asking what should you know about to pass a job interview, or which ones you actually need to be able to do your work?

 

In most work environments, you'll never need to write "standard" algorithms. They are a solved problem. For example, if you need to sort something, use the sort functionality that's part of your programming language or use a common library. Reinventing the wheel just wastes time.

 

You should have a general understanding of how to approach and solve problems, but that pretty much never involves writing your own sort or other basic algorithms.

[Wictorian]

25 minutes ago, Eigenvektor said:

Are you asking what should you know about to pass a job interview, or which ones you actually need to be able to do your work?

 

both¿

[wanderingfool2]

2 hours ago, Wictorian said:

but it would be neat if you also actually answered the question. maybe the answer is "there are no more algorithms you need to know about"¿

I did answer your question.  The answer is the same that @Zalosath has said.  It depends, it's too vague and ultimately it's best to understand the concepts.  The general statement is true that it's about being able to build up an algorithm.

 

The it depends is like this,

e.g.  Going into router development it's be handy to brush up on Dijkstra's algo.

Gaming AI it'd be good brushing up on A*

General backend...well this is more like SQL work.

 

Programming/Software engineering is very much about being able to apply logic and problem solving.  Interview questions/knowledge will vary drastically between sectors (healthcare,industrial, software company, gaming, backend dev, frontend dev, etc)

[Guest]

depends on the use case.

One algorithm in graphics is called Phong or something.

Another is to determine if all nodes are on the same tree/connected.

 

Study the big ones of searching & sorting to begin, then study math.

[mariushm]

At an interview, they won't ask you to sort 10 numbers using the quicksort method and make you write the code. 

So it's pointless to learn / memorize specific algorithms. 

 

It's important to know the basics really well ... by basics I mean data types, arrays, structures (ex in python what's dictionary, what's list , what's tuple, what's the difference between them, why would you use one over another, when would one be better to use vs another etc) ,  what is a function , what is a class, what is recursivity,  how do you work with loops ( while , for , repeat until , what's the difference between them)  ,  logical  bitwise operators  ( & , ||  ,  difference between & and && in the programming language you chose)

 

You may get questions like  .....  for a given string , print the position in the string where "abc" shows up for the last time. 

Or ... check if the string given is a palindrome 

Or question like this which demonstrates programmer knows to use arrays and how to loop through a string : https://leetcode.com/problems/zigzag-conversion/

Or a question like this :  https://leetcode.com/problems/trapping-rain-water/

 

You may be asked to write a small program that solves calculates the result of a formula entered as a string ex  5+ [ 20 - 4*(75+10/3)-1]  / 2 

Basically it would show you know how to tokenize something, skipping whitespace, treating what's inside paranthesis as formulas within formulas which have to be solved first,  it would show you are aware of operation order  ( PEMDAS - https://en.wikipedia.org/wiki/Order_of_operations ) , you may resort to recursivity to solve the "deepest" parts first ex solve 10/3 first, then solve the paranthesis (75 + 10/3) , then multiply 4 with the result and so on...

 

At an interview, nobody will care how you sort some things ... if you have to you can use the most basic sort ex 

sorted = false

while sorted == false 

  sorted = true

  for i = 1 to count of elements  

     if  element i-1  > element i  then  

         swap element i-1 and element i 

         sorted = false

     end if 

 end for   

end while 

 

but they may ask you is there any more efficient way to sort and you can say "yes, I'm aware of other sorting algorithms like mergesort, radix sort, whatever sort, but I don't memorize them, I can quickly look them up if a custom implementation is needed that's not built into the programming language libraries.

You have to prove you know how to program, not how to repeat or copy paste.

 

If you want to practice and learn various algorithms  I'd suggest checking out adventofcode.com , it starts from 2015 and it's a different content for every year : https://adventofcode.com/2015

For each day of December they had a two part problem and you use your skills to solve the problem ... you submit the result for first part and they give you the second part which is a bit more complicated.. It's fun and you can learn a lot.

No shame if you can't solve some of the last days' problems, I personally didn't solve some as they require use of very specific algorithms to solve in reasonable amount of time, but it's worth doing the puzzles.

 

There's other sites like leetcode I linked above which have various problems that are similar to what's asked at interviews. But like I said, know the basics of programming not specific algorithms 

 

[Wictorian]

7 minutes ago, mariushm said:

At an interview, they won't ask you to sort 10 numbers using the quicksort method and make you write the code. 

So it's pointless to learn / memorize specific algorithms. 

 

It's important to know the basics really well ... by basics I mean data types, arrays, structures (ex in python what's dictionary, what's list , what's tuple, what's the difference between them, why would you use one over another, when would one be better to use vs another etc) ,  what is a function , what is a class, what is recursivity,  how do you work with loops ( while , for , repeat until , what's the difference between them)  ,  logical  bitwise operators  ( & , ||  ,  difference between & and && in the programming language you chose)

 

You may get questions like  .....  for a given string , print the position in the string where "abc" shows up for the last time. 

Or ... check if the string given is a palindrome 

Or question like this which demonstrates programmer knows to use arrays and how to loop through a string : https://leetcode.com/problems/zigzag-conversion/

Or a question like this :  https://leetcode.com/problems/trapping-rain-water/

 

You may be asked to write a small program that solves calculates the result of a formula entered as a string ex  5+ [ 20 - 4*(75+10/3)-1]  / 2 

Basically it would show you know how to tokenize something, skipping whitespace, treating what's inside paranthesis as formulas within formulas which have to be solved first,  it would show you are aware of operation order  ( PEMDAS - https://en.wikipedia.org/wiki/Order_of_operations ) , you may resort to recursivity to solve the "deepest" parts first ex solve 10/3 first, then solve the paranthesis (75 + 10/3) , then multiply 4 with the result and so on...

 

At an interview, nobody will care how you sort some things ... if you have to you can use the most basic sort ex 

sorted = false

while sorted == false 

  sorted = true

  for i = 1 to count of elements  

     if  element i-1  > element i  then  

         swap element i-1 and element i 

         sorted = false

     end if 

 end for   

end while 

 

but they may ask you is there any more efficient way to sort and you can say "yes, I'm aware of other sorting algorithms like mergesort, radix sort, whatever sort, but I don't memorize them, I can quickly look them up if a custom implementation is needed that's not built into the programming language libraries.

You have to prove you know how to program, not how to repeat or copy paste.

 

If you want to practice and learn various algorithms  I'd suggest checking out adventofcode.com , it starts from 2015 and it's a different content for every year : https://adventofcode.com/2015

For each day of December they had a two part problem and you use your skills to solve the problem ... you submit the result for first part and they give you the second part which is a bit more complicated.. It's fun and you can learn a lot.

No shame if you can't solve some of the last days' problems, I personally didn't solve some as they require use of very specific algorithms to solve in reasonable amount of time, but it's worth doing the puzzles.

 

There's other sites like leetcode I linked above which have various problems that are similar to what's asked at interviews. But like I said, know the basics of programming not specific algorithms 

 

tbh i know these. what happens is sometimes i see a leetcode question and i dont have the motivation to do it. or i do it and after it fails some cases i lose motivation to debug it. 

 

i had tried making a calculator back a few months and didnt quite finish but i will retry. 

 

i am not perfect with recursion but i will practice. 

 

your comment is really valuable. but i know. i know memorization has no value. but why do we memorize syntax? you need to understand some algorithms. i know about some, i am asking if there are others.

[Guest]

4 hours ago, Wictorian said:

tbh i know these. what happens is sometimes i see a leetcode question and i dont have the motivation to do it. or i do it and after it fails some cases i lose motivation to debug it. 

Some questions are really hard. But you can't ask what if for scenario in life. That's a terrible way to live. 

4 hours ago, Wictorian said:

i had tried making a calculator back a few months and didnt quite finish but i will retry. 

Some projects are bigger than we expect. 

Learn to plan projects and pace yourself. 

The only people that #grind are in the movies. 

Not to say programming doesn't have a grind, because the work has to get done. 

4 hours ago, Wictorian said:

 

 

4 hours ago, Wictorian said:

 

Ignore these last two quotes. Can't delete them on mobile

[Fourthdwarf]

You need to be able to build algorithms using well known strategies, and know when it's appropriate to use them. Strategies like:

• Greedy Algorithms
• Memoization
• Dynamic Programming
• Monte Carlo Methods
• Divide and Conquer
• Exhaustive searches

[Wictorian]

2 hours ago, Fourthdwarf said:

You need to be able to build algorithms using well known strategies, and know when it's appropriate to use them. Strategies like:

• Greedy Algorithms
• Memoization
• Dynamic Programming
• Monte Carlo Methods
• Divide and Conquer
• Exhaustive searches

THANKS A LOT 

[shadow_ray]

It won't be a disadvantage if you know (at least in theory) how the common algorithms works and what is their time complexity. These might include: sorting, searching, graph traversal, path finding, data compression, parsing. The data structures that these algorithms work on usually taught during the same course.

[Eigenvektor]

22 hours ago, Wictorian said:

both¿

As others have said, it depends on what type of job you're after.

 

My current job position is probably best described as full-stack developer. I mostly work on our server (Java), but I also get to work on our web frontend (Angular/TS), as well as our mobile Android client (Java/Kotlin).

 

Being able to write a "well known" algorithm like sort from scratch has never been needed in my position (nor was it relevant when I interviewed for this job a decade ago). As I said above, that's built into the language or part of some standard library.

 

If you want to learn useful stuff, learn about things that should be applicable to a lot of positions:

• Learn about (un)popular programming patterns (e.g. which ones to avoid and which ones to use)
• Learn about types of algorithms rather than specific algorithms
• Learn how to write testable code and good tests
• Learn about code management tools (e.g. Git & GitLab/GitHub)
• Learn about automated builds and tests (e.g. GitLab, Jenkins, …)
• Learn about common technologies used to run code and deploy services (e.g. Docker)

[wasab]

Breath first search and dynamic programming. Important data structures to to implement these are map, hash, stack/queue, and trees. Just go on leetcode and start doing these problems. Once you've done enough you will see a pattern and can generally realize what type of alogrithm and data structures are used for which. 

23 hours ago, Zalosath said:

Most companies look for problem solving skills as oppose to knowing an algorithm off by heart

That is true but most company have no idea on how to test you on this but to leetcode you with algorithm. How well you do on these can sometimes be down to luck and chance; whether or not the interview question is one of the alogrithm you memorize. 

 

In my experience, recent college graduate tend to perform better on these than senior engineers. They are just out of school with most of the textbook materials still fresh on their minds. People who have been working in the field on the other hand will generally need to go back and practice quite a bit to refresh their memory on the subject. It is just an example that these questions are by no means a good metric to assess how good a developer you are. 

 

[Zalosath]

12 minutes ago, wasab said:

That is true but most company have no idea on how to test you on this but to leetcode you with algorithm. How well you do on these can sometimes be down to luck and chance; whether or not the interview question is one of the alogrithm you memorize. 

While I agree that knowing the answer to a question in advance is definitely a better way to do well in your interview, any good company is going to want to see your process and (generally) optimizations for algorithms that you suggest. If you go in balls blazing with the answer right away then all merit of the question is gone, a recruiter will probably realise that which could be a good or bad thing depending.

 

So I suppose the "best of best" is to, yes, study some algorithms that could come up, but remember to show the process of getting to your answer, even if you already know the perfect solution, it's really a much more critical skill.

[Guest]

19 hours ago, shadow_ray said:

It won't be a disadvantage if you know (at least in theory) how the common algorithms works and what is their time complexity. These might include: sorting, searching, graph traversal, path finding, data compression, parsing. The data structures that these algorithms work on usually taught during the same course.

Learning time complexity is useful. 

Dang, all the important stuff I learned in college was the algorithm class... Haha. 

 

So how long does it take to do something? 

1 paragraph time complexity lesson:

 

Say you have 10 elements in an array and you want to check which number is the biggest. If the biggest number is the last element (10) then you use a for loop and check every element once; time complexity is 10. If you wanted to abstract this since you can use a for loop for a 3 element array or even a 1,000 element array, the time complexity would be "n" where n is the number of checks. 

Say you do a terrible sort with a for loop in a for loop, this time complexity would be n^2. A loop inside a loop is *usually* (not always) n^2 which is one of the worst time complexity. 

10^2 is 100 checks if you were to sort the worst ordered array of 10 elements. 

 

When coding though, it might be wiser to leave time complexity to be really bad and get work done, BUT you MUST make sure you make time for optimizations. 

Don't leave too much nonsense unfixed though. 

[Wictorian]

20 minutes ago, fpo said:

Learning time complexity is useful. 

Dang, all the important stuff I learned in college was the algorithm class... Haha. 

 

So how long does it take to do something? 

1 paragraph time complexity lesson:

 

Say you have 10 elements in an array and you want to check which number is the biggest. If the biggest number is the last element (10) then you use a for loop and check every element once; time complexity is 10. If you wanted to abstract this since you can use a for loop for a 3 element array or even a 1,000 element array, the time complexity would be "n" where n is the number of checks. 

Say you do a terrible sort with a for loop in a for loop, this time complexity would be n^2. A loop inside a loop is *usually* (not always) n^2 which is one of the worst time complexity. 

10^2 is 100 checks if you were to sort the worst ordered array of 10 elements. 

 

When coding though, it might be wiser to leave time complexity to be really bad and get work done, BUT you MUST make sure you make time for optimizations. 

Don't leave too much nonsense unfixed though. 

yeah i know these