Browsing posts in: algorithms

Two Number Sum (optimized from O(nlogn) to O(N))

One of the most famous interview questions that you can expect to get in your next interview: Two Number Sum, and that given a non-sorted array, find 2 numbers that make a given sum. So, for example given an array: [10, 3, 2 , 9, -1, 8, 13], sum: 7, should give an output of [-1, 8]

One way to solve this problem is to sort the array first and then have a Left and Right pointers and iterate the array in 1 run. The code for this approach is as below:

The above approach will cost us O(n log n) time and O(1) space. That is because of the initial sort that we have done and that is why we have O(n log n) time.

If we try to optimize it then there is a way that we have to give up O(N) space in worst case and that is by using a HashMap and track the numbers while we iterate through the array in one go. The HashMap will obviously be using O(1) time for each check.


The Fibonacci Problem

The Fibonacci problem is the first thing you will hear about in any Dynamic Programming lecture or chapter (maybe not!) You can solve this problem using recursive iteration but that would create a lot of stacking in the memory. A lot of these stacks (sub problems) are reputations. For example the Fib(6) = Fib(0) + Fib(1) + Fib(2) + Fib(3) + Fib(4) + Fib(5) + Fib(6). If we look at Fib(4) & Fib(5) then you will see that they both have one in common and that is Fib(3) and Fib(2). So in the following algorithm we basically skip the Fibs that already have been calculated by just memorizing them in some variables (a & b). So instead of O(2^N) time complexity we do it in O(N) time. and O(1) space.


Balanced Brackets “{()}()” algorithm

This is a very common interview question and I personally faced it before on a technical phone interview with one of the top 5 tech companies in the world! The concept is easy but tricky. You need to use a stack and a HasMap to solve it. The stack is simply an array but you need to know what to store in it and how to pop items from it. The HasMap will store all the brackets and their adjacent matching closing vs opening brackets. So the idea is just to add a closing bracket when you see an opening bracket and when you see a closing bracket then you need to pop out a closing bracket from the stack. If at the end you see the stack is not empty then your string has a wrong brackets string.


Check if Tree is a Binary Search Tree

A Binary Search Tree is the tree that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.

Binary Search Tree

Binary Search Tree

source: wikipedia

 

 

 


Detect a Cycle in a Linked List

This is one way of how to detect if a Linked List is a cyclic or not. The basic idea is to make 2 pointers to the head and then make one of them move slow (one hop at a time) and the other move faster (2 hops at a time). They will be in a loop until they collide which means there is a cycle!

 


Do we need to know Algorithms as programmers?

There are two different kinds of programmers. The ones who went to school and spent some years learning skills like science, maths , physics and algebra, and there are others who learned “coding” to do their day to day jobs. The second group are most likely like learning stuff by themselves, and did not have the opportunity to go to school. Algorithms are done at school most of the time and most of the classes used some kind of programming languages to teach algorithms.  That doesn’t mean that self taught programmers don’t know about them but these things can be learned from the books.

When it comes to hiring software engineers from a pool of many skilled and junior applicants, some these skills (algorithms) are counted in most places. That does not mean that you will be using algorithms in your daily front end JavaScript job. Some take it as a deep learning of computer science.

So, is it important to know it? yes it is but you can also get a job without them. However, the top 5 silicon valley companies for sure will ask about the algorithms. As a software engineer, i think you should know and have a good knowledge about them.

At the end , algorithms are there to make things better, and when it comes to technology, we talk speed/time and space. Whats the best way and more effecient way to solve a problem. So, yes whatever you do in the tech industry and wherever you are coming from, you need to know the basics of the Big O and other algorithms.

There are companies that made it to the market just because they had smart people to create great algorithms to transfer bits from point A to point B.