Interview Preparation Blog

Road Map To A High Package Job

Why data structures,algorithms & system design is necessary for interview

Data Structures and Algorithms are the identity of a good Software Developer. The interviews for technical roles in some of the tech giants like Google, Facebook, Amazon, Microsoft is more focused on measuring the knowledge of Data Structures and Algorithms of the candidates. The main reason behind this is Data Structures and Algorithms improves the problem-solving ability of a candidate to a great extent

“Choosing the best possible data structure or algorithm to solve a problem affects the time and space complexity of the solution, which the interviewer is looking for”
These skills not only help a student in getting a highly-paid job but helps him to sustain in this ever-growing software industry.

Why does Software Developer interviews at Tech Giants more focused towards Data Structures and Algorithms

If you are going for an interview with some of the Tech Giants like Amazon, Google, Flipkart etc. or some other high paying companies for the role of a Software Developer or Backend Developer then you must be good at problem-solving. The interviews in these companies are more focused on analysing your problem-solving abilities

Algorithm and designing skills can lead to enhance salary 10 folds

Ecommerce organization(Flipkart,Amazon,WalmartLabs), finance organization(Morgan Stanley, goldman sache) Technology Giants(Google,Facebook,Microsoft) are only looking for algorithmic skills during interview. They dont care for programming language or technology a candidates previously worked on because they know that if candidates have problem solving skills then he/she can understand any technology/programming languages

Components of Distributed System

When interviewer asked system design problems, there main intention is to check the candidates distributed system understanding

  1. Scalability
  2. Sharding or Data Partitioning
  3. Load Balancing
  4. Caching
  5. Indexes
  6. Proxies
  7. Queues
  8. Redundancy and Replication
  9. SQL vs. NoSQL
  10. CAP Theorem
  11. Consistent Hashing
  12. Security
  13. Analytics

All the above components is discussed in details in logicmojo system design lectures

Microservice architecture components

These point should be remember while solving system design interview questions

  • Be absolutely sure you understand the problem being asked, clarify on the onset rather than assuming anything
  • Use-cases. This is critical, you MUST know what is the system going to be used for, what is the scale it is going to be used for. Also, constraints like requests per second, requests types, data written per second, data read per second
  • Solve the problem for a very small set, say, 100 users. This will broadly help you figure out the data structures, components, abstract design of the overall model
  • Write down the various components figured out so far and how will they interact with each other
  • As a rule of thumb remember at least these
    1. processing and servers
    2. storage
    3. caching
    4. concurrency and communication
    5. security
    6. load balancing and proxy
    7. CDN
    8. Monetization: if relevant, how will you monetize? eg. What kind of DB (Is Postgres enough, if not why?), do you need caching and how much, is security a prime concern?
  • Special cases for the question asked. Say designing a system for storing thumbnails, will a file system be enough? What if you have to scale for facebook or google? Will a nosql based database work?
  • Check with the interviewer is there any other special case he is looking to solve? Also, it really helps if you know about the company you are interviewing with, what its architecture is, what will the interviewer have more interest in based on the company and what he works on?

Few More Tips on System Design Interview Questions

Now a days most of the developers have queries regarding system design interview prepration, here are few more tipsand steps while solving problems

  • Requirement Gathering (Discuss with interviewer for 2 minutes)
  • System interface definition (Take a pause for 1 or 2 minute , note down your thoughts and explain what do you have on it in 5 minutes)
  • Capacity estimation (Write down your big guns, its show time for 10~15 minutes)
  • Defining the data model(Fire everything for 10~15 minute, Points to cover: Entities, Interaction with each other, Data management like storage, transfer, encryption, etc)
  • High-level design (Show case your drawing skills in 3~5 minutes and try to wrap it)

Architecture evolution with time

Interview Diificulty level of top tech giants

What kind of traffic can load balancers handle

Load balancer administrators create forwarding rules for four main types of traffic

  • HTTP — Standard HTTP balancing directs requests based on standard HTTP mechanisms. The Load Balancer sets the X-Forwarded-For, X-Forwarded-Proto, and X-Forwarded-Port headers to give the backends information about the original request
  • HTTPS — HTTPS balancing functions the same as HTTP balancing, with the addition of encryption. Encryption is handled in one of two ways: either with SSL passthrough which maintains encryption all the way to the backend or with SSL termination which places the decryption burden on the load balancer but sends the traffic unencrypted to the back end
  • TCP — For applications that do not use HTTP or HTTPS, TCP traffic can also be balanced. For example, traffic to a database cluster could be spread across all of the servers
  • UDP — More recently, some load balancers have added support for load balancing core internet protocols like DNS and syslogd that use UDP

What do you mean by a good Algorithm?

There can be many algorithms for a particular problem. So, how will you classify an algorithm to be good and others to be bad? Let's understand the properties of a good algorithm:

  • Correctness: An algorithm is said to be correct if for every set of input it halts with the correct output. If you are not getting the correct output for any particular set of input, then your algorithm is wrong
  • Finiteness: Generally, people ignore this but it is one of the important factors in algorithm evaluation. The algorithm must always terminate after a finite number of steps. For example, in the case of recursion and loop, your algorithm should terminate otherwise you will end up having a stack overflow and infinite loop scenario respectively
  • Efficiency: An efficient algorithm is always used. By the term efficiency, we mean to say that:

    • 1. The algorithm should efficiently use the resources available to the system

    2. The computational time (the time taken to generate an output corresponding to a particular input) should be as less as possible

    3. The memory used by the algorithm should also be as less as possible. Generally, there is a trade-off between computational time and memory. So, we need to find if the time is more important than space or vice-versa and then write the algorithm accordingly.

    So, we have seen the three factors that can be used to evaluate an algorithm. Out of these three factors, the most important one is the efficiency of algorithms. So let's dive deeper into the efficiency of the algorithm

Algorithm Efficiency

The efficiency of an algorithm is mainly defined by two factors i.e. space and time. A good algorithm is one that is taking less time and less space, but this is not possible all the time. There is a trade-off between time and space. If you want to reduce the time, then space might increase. Similarly, if you want to reduce the space, then the time may increase. So, you have to compromise with either space or time. Let's learn more about space and time complexity of algorithms

  • Space Complexity: Space Complexity of an algorithm denotes the total space used or needed by the algorithm for its working

    Even when you are creating a variable then you need some space for your algorithm to run. All the space required for the algorithm is collectively called the Space Complexity of the algorithm.

    Note:In normal programming, you will be allowed to use 256MB of space for a particular problem. So, you can't create an array of size more 10^8 because you will be allowed to use only 256MB. Also, you can't create an array of size more than 10^6 in a function because the maximum space allotted to a function is 4MB. So, to use an array of more size, you can create a global array

  • Time Complexity:The time complexity is the number of operations an algorithm performs to complete its task with respect to input size (considering that each operation takes the same amount of time). The algorithm that performs the task in the smallest number of operations is considered the most efficient one.

    The time taken by an algorithm also depends on the computing speed of the system that you are using, but we ignore those external factors and we are only concerned on the number of times a particular statement is being executed with respect to the input size. Let's say, for executing one statement, the time taken is 1sec, then what is the time taken for executing n statements, It will take n seconds