DSA Questions As Per Interview Prep SE

-

Let's see some of the Important Basic to Advanced Questions Regarding Data Structure & Algorithm

Array Questions

1. Given a square matrix (2D array), calculate the sum of the primary diagonal and the secondary diagonal.

    [[1, 2, 3], [4, 5, 6], [9, 8, 9]]    
  • Primary Diagonal: 1 + 5 + 9 = 15
  • Secondary Diagonal: 3 + 5 + 7 = 15
2. Find out the duplicate elements from array.

    const numArr = [1, 2, 1, 3, 2, 1, 2, 3, 4, 5]
    const strArr = "data structure and algorithm discussion"

3. The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. Write the program for it

    Example: 0,1,1,2,3,5,8,13,21,34,55,…
    Time complexity should be O(n)
    Formula: F(n)=F(n−1)+F(n−2)

4. Flatten the below given array without using array.flat() method.

    [1, [2, 3], [4, 5, 6, [7, 8]]]
    Output should be: [1, 2, 3, 4, 5, 6, 7, 8]

5. Write a program Insert element in mid of the array.

    Array: [1,2,3,5,6,7]
    Missing Value: 4

6. Write a program to remove 3rd element from array.

    Array: [1, 2, 3, 4, 5, 6, 7, 8]

7. Write a program to check is number is prime or not.

    Prime Numbers: 2,3,7,11,13,17,19

8. Write a program to multiple two numbers without using * sign.

9. Determine if the sum of two integers is equal to the given value.

    [2, 7, 11, 15], 9 = 2+7
    [2, 8, 11, 14], 20 = Not found, should be false
    [5, 7, 1, 2, 8, 4, 3], 10 = 2+8
    
    Time complexity should be O(n)

10. Find all subsets of a given set of integers.

Example Input: [2, 3, 4]
Output: {
  [],
  [ 2 ],
  [ 2, 3 ],
  [ 2, 3, 4 ],
  [ 2, 4 ],
  [ 3 ],
  [ 3, 4 ],
  [ 4 ]
}


String Questions

1. Write a program to check if a string or word or number is palindrome.
    
    input: racecar - output: true
    input: 121 - output: true
    input abc - output: false
    input 1212 - output: false

2. Reverse the order of words in a given sentence (a string of words) and remove special chars as well.
    
    Should be Time Complexity: O(n) and Space Complexity : O(1)
    Input: "Hello World" - Output: "World Hello"
    Input: "How are you?" - Output: "you are How"

3. Write a program to get total vowel and consonants count from String.

4. Write a string rotational program

Examples:
Input: s1 = "abc",  s2 = "cab" | Output: true
Input: s1 = "mightandmagic",  s2 = "andmagicmigth" | Output: false

Sorting Questions

1. Write a program to merge 2 sorted arrays in sorted order.
    
2. Write a program to do bubble sort.

3. Write a program to do merge sort.

4. Write a program to do quick sort.

5. Write a program to do radix sort.

Dynamic Programming (DP - Subproblems/Overlapping Subproblems)

1. How many ways can you make change with coins and a total amount?

    Suppose we have coin denominations of [1, 2, 5] and the total amount is 7. We can make changes in the     following 6 ways:
    1, 1, 1, 1, 1, 1, 1
    1, 1, 1, 1, 1, 2
    1, 1, 1, 2, 2
    1, 2, 2, 2
    1, 1, 5
    2, 5

    Total Methods 6 Possible

2. You are given a dictionary of words and a large input string. You have to find out whether the input string can be completely segmented into the words of a given dictionary. The following two examples elaborate on the problem further. (DP)
    
    ['apple','pear','pie','baby','sweet']
    applepie - true
    babygirl - false
    sweetgirl - true


Let's see some of the basic definitions as well regarding data structure & programming

### Fequency Counter

Many times you need to compare between 2 arrays in that situation simplest solution is use Nested loops or Linear Searching, which eventually has an Big O n(Square) O(n^2) Time Complexity, For solving this problem we can use Frequency Counter, In which we found first Frequency of both arrays then simple run loop of any 1 Frequency object/array and compare it directly.

### Multiple Pointers

Many times in **Sorted Array** we need to compare and we generally do nested loop so for solving this we can use this Multiple Pointer magic, in which we generally use **Binary Search Algorithm**. We 1st have to analyse our pointer it could be 1st or Last indexs or 1st or 2nd _Indexes_.

### Sliding Window Pattern

When we have **String** or **Array** which creating a WINDOW from one position to another position depending upon certain condition and a new window is created. It is very useful for keeping track of a subset of data in an array/string etc.

### Divide and Conquer Pattern

It is related to our search and sorting algorithms, such as in Binery Search we divide the array from mid then search the element.

### Recursion

Keeps calling same function until didn't get expected result. Here few Points are so important otherwise our Call Stack will be infinite and size exceeding error comes:

- Identify base case such as if (statement) return x;
- It basically depends upon call stack, you can check call stack example in Examples directory.

### Bubble Sort

Runs two loops for sorting the Integer arrays and swap the numbers basis upon comparisions. This "works well with small items of array only" as we know that Wrost and Average case time complexity for it is O(nSquare), only best case goes to O(n) time complexity.

### Merge Sort

It's an combination of two things - merging and sorting. Merge sort works really well with big size of Integer arrays as well and give response so faster as compare to Bubble/Insertion/Selection sort algorithms. It improves time complexity from O(nSquare) to O(n-log-n) stable in each scenario.

### Quick Sort

Quick sort works by selecting a pivot element and partitioning the array into elements less than the pivot and elements greater than the pivot. This process is then recursively applied to the sub-arrays.

- Pivot: Select an element as the pivot.
- Partition: Reorder the array so that elements less than the pivot are on the left, and elements greater than the pivot are on the right.
- Apply quick sort recursively to the left and right sub-arrays.

#### Time & Space Complexity

- Best & Averate Case - O(n log n)
- Wrost Case - O(nSquare)
- Space - O(log n) for the recursion stack in the average case and in wrost case O(n).

### Radix Sort

Radix sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. It’s particularly efficient for sorting integers or strings where you want to sort based on digit or character positions rather than direct comparisons.

- Determine the Maximum Number of Digits
- Sort Digits by Place Value
- Repeat for Each Digit Place






Location: New Delhi, Delhi, India

Comments

Post a Comment

Popular posts from this blog

JavaScript Logical Output Based Interview Questions

-
Image
You mostly seen in JavaScript interviews there interviewers must asks output based questions in which candidate stuck mostly so here in this blog I'm telling you most commonly asked output based JavaScript interview questions. By Education Funda Most Commonly Asked JavaScript Output Based Questions Question: 1 function sum(){      let a = 8;      const b=2;      var c=a+b; } console.log(a) // Reference error: a is not defined console.log(b) // Reference error: b is not defined console.log(c) // Reference error: c is not defined sum() console.log(a) // Reference error: a is not defined console.log(b) // Reference error: b is not defined console.log(c) //Output: undefined ---------------------------------------------------------------------------- Question: 2 let arr=[1,2,3,4,5]; console.log(arr[2], arr.length); //Output: 3 5 arr.length=0; console.log(arr[2], arr.length); //Output: undefined 0 Note:  As we can see in above code 1st ques...
Read more

Deploy Angular Build With Express JS Project

-
Image
Deploy Angular Build in Node JS (Express JS) Server Mean Stack - Education Funda Firstly Create Angular Production Ready Build: ~ ng build (run in command line when directory is projectFolder). ~ Compress using Brotli compression the resources using the following command for i in dist/*/*; do brotli $i; done Deployment Check Angular Build: You can get a preview of your application using the ng serve --prod command that starts a local HTTP server such that the application with production files is accessible using http://localhost:4200. This is not safe to use for production usage. For a production usage, you have to deploy all the files from the dist folder in the HTTP server of your choice. Node JS/Express JS Server File Changes: //enabling CORS app . use ( cors ()); app . use ( express . static ( path . resolve ( './public' ))); //api v1 base route set app . use ( '/api/v1' , router ); //angular front site app . use ( express . static ( path . resolve ( './public/a...
Read more

Postman Collection APIs to Swagger Docs

-
Image
Being an back-end developer we generally works with APIs, for storing the APIs mostly developers are using the Postman, So in this blog will discuss how to covert postman collection APIs to swagger APIs documentation. Express Js Project Convert Postman Collection APIs to Swagger Docs Step 1: You should have proper APIs postman collection for your project. Step 2: Install swagger ui in your node project via ~ npm i swagger-ui-express . Step 3: Put below code in your Routes index file OR app.js wherever you maintained your express routes as per your requirements: Here you also need to create 1 json file for storing the details of your APIs docs just like we create swagger-output.json . import express from "express" ; import swaggerUi from "swagger-ui-express" ; const swaggerDocument = JSON . parse ( await readFile ( new URL ( "../../../../swagger-output.json" , import .meta. url )) ); const router = express . Router (); // adding swagger docs...
Read more