SDE - 1

The gardener wants to water the garden by opening the minimum number of taps. The garden is one-dimensional along the x-axis of length N i.e. the garden starts from point 0 and ends at point N. There are N + 1 tap located at points [0, 1, 2, …, N] in the garden.

You are given an integer N, and an array named “ranges” of size N + 1(0-indexed). The ith tap, if opened, can water the gardener from point (i - ranges[i]) to (i + ranges[i]) including both. The task is to find the minimum number of taps that should be open to water the whole garden, return -1 if the garden can not be watered.

Example :

Follow Up:

Can you solve the problem in O(N) time?

What is a BST, what are other types of trees?
Theoretical questions based on the Graph data structure. 
Where graph traversals algorithms are used? 

Tell about different traversal algorithms and write the order of printing of nodes.

You are given a Singly Linked List of integers. Return true if it has a cycle, else return false.

A cycle occurs when a node's next points back to a previous node in the list.

Example:

In the given linked list, there is a cycle, hence we return true.

You have been given a string STR. Your task is to find the total number of palindromic substrings of STR.

Example :

If the input string is "abbc", then all the possible palindromic substrings would be: ["a", "b", "b", c", "bb"] and hence, the output will be 5 since we have 5 substrings in total which form a palindrome.

Note :

A string is said to be a 'Palindrome' if it is read the same forwards and backwards. 
For example, “abba” is a palindrome, but “abbc” is not.

A 'Substring' is a contiguous sequence of characters within a string. 
For example, "a", "b", "c", "ab", "bc", "abc" are substrings of "abc".

Write a SQL query: Employee and department table is given you need to find the salary of employees in each department
Which databases have you used? 
Difference between SQL and NoSQL? (Learn)
What is the CAP theorem?

- Switch vs Hub
- Which data structure is used in switches?
- TCP vs UDP

1. Asked about the previous rounds.
2. Favourite programming language?
4. How hashing is done in maps?
5. What is the Hash function? What will happen if a hash function returns 1 always?
6. Difference between a map and an unordered map?
The interviewer discussed a lot about map data structure.
7. Discussed the automation project which was mentioned in my resume.
8. What are the challenges that you've faced till now?
9. What technology you've worked on? Why you choose Django? What is ORM?
10. Which databases have you used? Where have you used it?