Cracking Dream Interview-Part 1
A super useful guide for every interviewee 🚀💖
In this blog I will summarise the most important questions (technical, non technical) that will surely help you crack the interviews.
There are several roles like software engineer, android developer, programmer, analyst, python developer etc. For all these roles the common and most important points are :
- Basic knowledge of Data Structure and Algorithms
- Good command on 1 at least one programming language
- Good problem solving, logical, reasoning, verbal ability etc
- Subject or domain specific question e.g if it is android profile job then you may be asked questions of android.
Commonly asked DSA interview questions
1. What are Data Structures?
Data structures are the methods and techniques used to maintain data in an organized fashion. This is primarily done to ensure that data can be manipulated and accessed in an efficient manner.
2. What are algorithms?
Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output.
For an example, if you have to write a program to add two integers then the algorithm for it would be as follows-
- Input first integer a
- Input second integer b
- Store the sum of a and b in variable sum
- Print sum variable
3. What are various data structures available?
Commonly available data structures are arrays, linked lists, stacks, queues, trees, heap, hash maps, graphs etc
4. What are linear and non linear data structures?
- Linear: A data structure is said to be linear if its elements form a sequence or a linear list. Examples: Array. Linked List, Stacks and Queues
- Non-Linear: A data structure is said to be non-linear if traversal of nodes is nonlinear in nature. Example: Graph and Trees.
5. What are common operations that can be performed on a data-structure?
- Insertion: Add a new data item in the given collection of data items.
- Deletion: Delete an existing data item from the given collection of data items.
- Traversal: Access each data item exactly once so that it can be processed.
- Searching: Find out the location of the data item if it exists in the given collection of data items.
- Sorting: Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.
6. Briefly explain the approaches to develop algorithms.
There are three commonly used approaches to develop algorithms −
- Greedy Approach − Finding solution by choosing next best option
- Divide and Conquer − Diving the problem to a minimum possible sub-problem and solving them independently
- Dynamic Programming − Diving the problem to a minimum possible sub-problem and solving them combinedly
7. Give some examples of greedy algorithms.
The below given problems find their solution using greedy algorithm approach −
- Travelling Salesman Problem
- Prim’s Minimal Spanning Tree Algorithm
- Kruskal’s Minimal Spanning Tree Algorithm
- Dijkstra’s Minimal Spanning Tree Algorithm
- Graph — Map Coloring
- Graph — Vertex Cover
- Knapsack Problem
- Job Scheduling Problem
8. How is an Array different from Linked List?
- The size of the arrays is fixed, Linked Lists are Dynamic in size.
- Inserting and deleting a new element in an array of elements is expensive, Whereas both insertion and deletion can easily be done in Linked Lists.
- Random access is not allowed in Linked Listed.
- Extra memory space for a pointer is required with each element of the Linked list.
- Arrays have better cache locality that can make a pretty big difference in performance.
9. What are some examples of divide and conquer algorithms?
The below given problems find their solution using divide and conquer algorithm approach −
- Merge Sort
- Quick Sort
- Binary Search
- Strassen’s Matrix Multiplication
10. What are the types of searching?
The two primary methods of searching are linear search and binary search.
Linear search involves iterating over a data unit in order to perform the required operation.
Binary search is more efficient in a way that it has the ability to split the data unit into chunks and then perform a search operation.
11. Explain binary search. What is the complexity?
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one.
Binary search seems very simple and easy topic, but some of the questions of binary search are very popular in coding interviews.
Do checkout this list- Most important binary search questions ✍🏻
12. What is Stack and where it can be used?
Stack is a linear data structure. It operates the data in LIFO fashion.
LIFO- Last In First Out. Basic operations of stack are : Push, Pop , Peek/Top
Best thing about stack is that all operations (insertion, deletion) occur in constant time i.e O(1).
13. What is a Queue, how it is different from stack and how is it implemented?
Queue is a linear structure which follows the order is First In First Out (FIFO) to access elements. Mainly the following are basic operations on queue: Enqueue, Dequeue, Front, Rear.
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added. Both Queues and Stacks can be implemented using Arrays and Linked Lists.
14. Give real life applications of queue data structure.
15. What is a Linked List and What are its types?
Linked List is a linear data structure (like arrays) where each element is a separate object.
Each element is a node consisting of two items- data and a reference to the next node in the list.
16. What is the difference between void and null in Data Structures?
Void is a data type identifier in data structures, while null is considered to be a value with no physical presence. When void is used, it indicates that there is no size while initializing the data structure.
17. Which Data Structure Should be used for implementing LRU cache?
We use two data structures to implement an LRU Cache.
- Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).The most recently used pages will be near rear end and least recently pages will be near front end.
- A Hash with page number as key and address of the corresponding queue node as value.
18. What is difference between Binary Tree and Binary Search Tree?
19. How to check if a given Binary Tree is BST or not?
If inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do inorder traversal and while traversing keep track of previous key value. If current key value is greater, then continue, else return false.
20. What is OOP?
OOP stands for Object-Oriented Programming.
Procedural programming is about writing procedures or functions that perform operations on the data, while object-oriented programming is about creating objects that contain both data and functions.
- OOP is faster and easier to execute
- OOP provides a clear structure for the programs
Main features of OOP-
Encapsulation
Polymorphism
Inheritance
21. Which data structures are used for BFS and DFS of a graph?
- Queue is used for BFS
- Stack is used for DFS. DFS can also be implemented using recursion (Note that recursion also uses function call stack).
22. What is an AVL Tree?
AVL trees are height balancing binary search tree. AVL tree checks the height of left and right sub-trees and assures that the difference is not more than 1. This difference is called Balance Factor.
BalanceFactor = height(left-sutree) − height(right-sutree)23. What is a spanning tree?
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. A spanning tree does not have cycles and it can not be disconnected.
Sorting Algorithms Complexity Cheat Sheet
Top tips any interviewee must have in mind
1. Make your resume carefully
A resume is your first impression and thus, it should be impactful. candidates often include things in a resume that look good but they hardly know it in-depth and that is not a good sign. So, add only those things which you can completely justify in an interview.
2. Just before your next Online Interview:
Keep a pen and paper ready, you never know 📝
Keep a water bottle with you
Put your phone on silent
Keep your laptop on charging 🔋
Use an external mic/earphone 🎧
Login 5 minutes before (very important) ✅
Speak out loud few Tongue-Twisters, it’s a great speaking exercise for clear speech
Get a smile on the face, a BIG one, brain releases endorphins which helps you set the mood (thanks to a LinkedIn user for the quick tips :))
3. Interview is a conversation
You just need to be able to convince that you can contribute in your best possible way along with willingness to learn, if need be. Be humble if you know something and honest if you do not. Also, speak up if you do not know something. Nobody is expected to know everything . The interviewer should be able to understand that you can be a right fit in the company with the right push.
4. Research the industry and company
5. Ask yourself why you are the perfect candidate for that job
6. Score a success in the first five minutes
Some studies indicate that interviewers make up their minds about candidates in the first five minutes of the interview — and then spend the rest of the interview looking for things to confirm that decision!
7. Make the most of the “Tell me about yourself” question
8. Don’t give up!
If you’ve had a bad interview for a job that you truly think would be a great fit for you, don’t give up!
All the best for your next interview 🚀
Do clap 👏🏻👏🏻 50 times and share the article if you like it. Thank you for giving your valuable time
