Big O Notation - Time and Space complexity

Big O - In simple words, this describes how long an algorithm takes to run and how much space it takes. It expresses how the runtime quickly grows with respect to the input.

This is how we compare different algorithms's efficiency.

Some quick notes -

- N could be the actual input or the size of the input

- We always talk about the worst-case here

- We drop constants and less significant terms since as input grow infinitely large constants and less significant terms do not make much difference

Space complexity talks about memory or space. This measures, how memory grows as the input size increases. Usually, when we talk about space complexity, we're talking about additional space

The link I referred - https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity

Interview tips - Always talk about time and space complexity at the end. This will earn you bonus points!

FAANG companies expect this even if they don't ask explicitly.

Some useful graphs -

Comments

Coding solutions - Amazon card, Data structure, Search and Sort

Amazon card, Data structure, search and sort Hashmap # HASH MAP implementation in python class Node : def __init__ (self, key, value) : self.key = key self.value = value self.next = None class HashMap : def __init__ (self) : self.store = [ None for _ in range( 16 )] def get (self, key) : index = hash(key) & 15 if self.store[index] is None : return None n = self.store[index] while True : if n.key == key: return n.value else : if n.next: ...

Debugging round interview questions

Debugging round interview questions with answers. These are real questions asked in real interviews. 1. When you come in the morning, SLA has increased for the job searching portal (website). It was fine till today morning. How are you going to debug it? There is a matrix that shows service and it’s SLA. What are the steps you are going to take to debug this problem? Answer : If the SLA has gone up suddenly it's definitely a critical issue. I will first report this problem to all stakeholders. I will check listed points to debug the problem - 1. Check what went in the latest release if that is one 2. Check for nodes that are down. If there is an unusual number of nodes that are not reachable then report it to the infrastructure team. 3. Check for database repair which can cause slowness 4. Check its client-side delay or server-side delay to narrow down the issue 5. Check the geolocation of where the website is slow in order to narrow down 6. Check network bandwidth in the da...

Coding round interview questions tips

Tips from the google coding interview video https://www.youtube.com/watch?v=XKu_SEDAykw Always ask for clarifications - some tips below Think out loud Talk about all the solutions before you code out Test a few inputs after writing code by tracing it before saying I am done Talk while coding Talk about time and space complexity at the end to get bonus points Read out the problem loud in a way you understood - Do not code out the wrong solution Clarifying questions Clarify the input & output. E.x. This function accepts 2 arrays and returns an integer, Am I right? Sorting - array already sorted, reverse sorted or not sorted? Can there be -ve elements? Can there be only integers or other types? String - other than English? Can it contain special chars, Unicode, upper case and lower case letters? https://medium.com/@mgtei/how-why-to-ask-clarifying-questions-at-a-whiteboard-interview-for-junior-devs-97571fdc629e Key point to succeed in this round is just don't give up on the problem...

Old SWQA

Search This Blog