Skip to main content

Cracking the coding interview: Stacks and Queues(3.2)

In this post, we are going to go over my notes while solving a coding question


Today I am sharing my thoughts on the Cracking the coding interview question for chapter 3 Stacks and Queues, Q3.2


Below are my personal notes and working while solving the problem.

I might be correct, wrong, or totally wrong, but I wanted to have a working copy of my train of thoughts while solving the problem.



Notes section

**************************************

what operations will the stack have?

push,pop,getTop and isEmpty. Here all the operations will have a time complexity of O(1).


while performing push operation we can maintain the min value. While performing the pop operation, how do we find the next min value? - When we are pushing the element, we can push the item and the min value, up to that item in the stack. 


In that way, we will have a track of min value up to a particular item when we start popping.


For the pop operation, we can also have the min function work in O(1).




push

===

1. check if the min var has a bigger or smaller value. If small take the var else update the var


pop

===

1. get the top element after pop, and update the min var 



This problem can also be asked to keep a track of max, running average, a value with certain characteristics


7 steps for coding interview

===

1. clarifying the question - we need to add an additional function to keep track of min value

2. confirming the inputs - the inputs will only be a valid integer number. Even if the number is a floating-point, the solution will work. This methodology would work for binary and hexadecimal numbers too but we would have to convert the hex numbers into strings.


3. test cases - 1,2,-5,0,infinity, -infinity


4. brainstorming - like the top pointer, we will also have a min pointer. The values pushed to the stack will be a list and it can be manipulated.


The min value will be updated for both the push and pop operation.


O(1) means that the operation will take a constant amount of time or fixed time and not a single step.


5. runtime analysis - O(1) for all the operations.


6. coding


7. debugging


Resource


Thank you!!

Labels:
Location: Toronto, ON, Canada

Comments

Post a Comment

Popular posts from this blog

PyMuPDF vs PDFMiner

 As a developer , I was tasked to extract specific data from a PDF. Upon analysing it further, certain patterns were found based on keywords in the document. Since I was using Python language for the task I found 2 tools quite useful which are PyMuPDF and PDFMiner. These tools can then be used to extract the text from a page on which regular expression can be applied to further extract relevant data.     Next, we are going to take a deeper look into these tools, specifically focusing on the pros and cons of each.     PyMuPDF   Docs , PIP package Pros Simple and understandable API Extensive tools to work with text, images, and graphics Available as a PIP package (pip install PyMuPDF) Better support for a range of symbols comparer to PyPDF2   Cons Parsed text is not in sequence Dependency on other package-Fitz Text sequence information lost during extraction     PDFMiner   Docs ,  PIP package ...
Post a Comment
Read more

Finding difference between 2 files in Python

In this post, we will take a look at how to compare two files using Python.   I was tasked to compare 2 files and then list the differences between them using Python. Initially, I started with filecmp module, but even with the function parameter ‘ shallow’ set to false, the Boolean result was not enough. Sure, it can act as an indicator to take some action, but it will not list the differences.   I was looking for something more visual, something like color coding and not like the git diff output, which is not very user-friendly. But, another Python internal module, difflib helped me to get the job done.   Inside Difflib, HtmlDiff is what I was looking for. The differences were highlighted with 3 different colors and also the line numbers were indicated in a table to locate the differences. The results are quite self-explanatory and it is easier to explain the differences to other people. Code for generating the above difference table: Note: File1...
Post a Comment
Read more

Adding existing Anaconda environment to Jupyter notebook

In this post we are going to take a look at adding Anaconda environment to Jupyter notebook. Recently, I was working on a CSV file and wanted to work with Pandas package for tabular data manipulation using Python. The problem was even if I install Pandas package, I would have to install other Data Science package as needed. But, the Anaconda environment was already setup on my laptop, which I want to reuse.   Today, we will look into how to reuse the Anaconda environment within the Jupyter Notebook.   There are 4 basic steps to be followed for adding the environment: 1. Create a conda environment Go to Conda command prompt(Run in Admin mode) Run the following command: conda create –-name newenv O/P:   What if there is an existing conda environment? Go to Conda command prompt(No need for Admin mode) Run the following command: conda env list O/P: Since there was only one environment, only one entry was displayed. ‘*’ indicates the cur...
Post a Comment
Read more