Programming Solutions

DBMS Interview Questions and Answers

2021-07-08T18:53:00.003+05:30

DBMS Interview Questions and Answers

Data: It is raw, just a set of facts that by itself doesn't convey anything.

Eg: Student scores 90 marks.

Information: We need to understand the pattern between factual data and give it meaning.

Eg: Student got an A grade.

Knowledge: Synthesis of data and information lead us to answer the HOW question and take business decision.

Eg: Student is a Top Performer.

Database: It is a shared collection of logically related data, design to meet the needs of an organization.

DBMS: Collections of programs to access data. It is a software system that enables the users to define, create, maintain and control access to the database.

Functions of DBMS:

Data management: Store, retrieve and update
Transaction support: Modify in the database in successful or not
Recovery
Security
Integrity: Maintain accuracy
Concurrency control: Simultaneous access provided to users
Utilities: Import, export, manage, backup, etc

Keys: It is used to identify any record or row of data from the table. It is also used to establish and identify relationships between tables.

Candidate Key: It is a minimal set of attributes (columns) that can be used to uniquely identify a single tuple (row) in a relation.

Primary Key: It is a candidate key that is selected to uniquely identify a tuple in a relation.

Foreign Key: It is a set of one or more columns in the child table whose values are required to match with the corresponding columns in the parent table.

Data Integrity

Entity Integrity (row): Primary Key
Domain Integrity (column): Datatypes, check constraint
Referential Integrity: Foreign Key

ER Model: It is a graphical representation of entities and their relationship which help in understanding data independent of the actual database implementation.

Entity: Real-world object which has an independent existence.

Attribute: Property that describes an entity.

Cardinality of Relationship

1-1: 1 Employee allocated one computer and not shared.
1-M: 1 Employee allocated many computers and not shared.
M-M: Many Employees allocated many computer and shared.

Normalization

It is a technique to remove or reduce redundancy (duplicate) from a table.

First Normal Form (1NF)

Table should not contain any multivalued attribute.

Second Normal Form (2NF)

Table must be in 1NF.
All non-prime attributes should be fully functionally dependent on the candidate key.
OR
There should be no partial dependency.

Third Normal Form (3NF)

Table must be in 2NF.
There should be no transitive dependency in the table.

Need for 2NF: Insert, update, delete anomalies

Need for 3NF: Cause problem in duplicate rows.

Eg: If 2 students score the same marks then their grades will also be the same, here the rows will be duplicates.

Transaction: It is a set of operations used to perform a logical unit of work. A transaction generally represented a change in the database.

ACID Properties

Atomicity: Either all the statements will run or none.
Consistency: Before and after transactions, sum of money should be the same.
Isolation: Convert parallel transaction into the serial transaction, because the serial schedule is consistent.
Durability: Changes made in the database must be permanent.

DDL: Data Definition Language

It changes the structure of the table like creating, deleting, altering, etc.

create
alter
drop
truncate

DML: Data Manipulation Language

It is used to modify the database tables.

insert
update
delete

DCL: Data Control Language

It is used to grant and revoke authority for any database user.

grant
revoke

TCL: Transaction Control Language

TCL commands can only use with DML commands like INSERT, DELETE and UPDATE only.

commit
rollback
savepoint

Delete vs Drop vs Truncate

Delete is used to remove a complete table or a particular row (using where clause).

Drop is used to remove the complete table or database.

Truncate is used to delete tables and set constraints to default.

Stored Procedure: It is a SQL statement that you can save and can be reused again.

Eg: Create Procedure Procedure_Name AS SQL_Statement GO;

DBMS Abstraction

View: User Interface with which users interact.
Logical: Fields, attributes, relations.
Physical: Block of storage where data actually stored.

CompareKarein

OOPs Interview Questions and Answers

2021-07-06T12:50:00.003+05:30

OOPs Interview Questions and Answers

Class

It is a collection of objects of the same type.

It is a blueprint or prototype that defines the variables and methods common to all objects of a certain kind.

Eg. Human

Object

It is a real-world entity or instance of a class.

Eg. Men and women

Abstraction

An act of representing the task to be done in a system in such a way that anyone can use the system without having any internal knowledge of the workings of the system.

Eg: We use readLine() without knowing how it takes input from the Keyboard.

Encapsulation

The wrapping of code and data into a single unit.

It acts as a protective layer by ensuring that access to wrapped data is not possible by any code defined outside the class.

Eg: Acess Specifier, getter, setter.

Polymorphism

It is a process that allows one thing to have many forms.

It is the process that allows classes to respond to messages in different ways.

Eg:

Function Overloading: Process having more than one function with the same name but with different numbers or datatype parameters.
Function Overriding: Process of redefining any function in a derived class. The redefined function in the derived class should have the same signature (parameter) in a base class.

Inheritance

A process by which one object acquires the property of another object.

Eg:

Single Inheritance: From one base class only one derived class is created. Eg. Fan <= Cooler
Hierarchical Inheritance: From one base class more than one derived class is created. Eg. Person <= Student, Player
Multilevel Inheritance: From one base class one derived class is created and this derived class will act as a base class from one more derived class. Eg. A <= B <= C
Multiple Inheritance: A class inherits more than one class. Eg. Parent1, Parent2 <= Child
Hybrid Inheritance: It is a combination of multiple and multilevel inheritances.

Abstract Class and Method

An abstract class can be considered a blueprint of another class.

An abstract method is a method that has a declaration but does not have an implementation.

RealWorld Example of OOPs

Abstraction: TV Remote - We press a button and the channel changes, we don't know how it internally works.
Encapsulation: Car - There are multiple parts like steering, wheels, etc. All are bound together to drive a car.
Inheritance: Parent-Child - Child inherits parents properties.
Polymorphism: Person - One behaves differently in front of elders and shows different behaviour in front of friends.

Want to check about the Latest Electronic Devices: CompareKarein

super, this, self

super keyword is used to refer to the immediate parent class object.

this keyword stores the reference of the object on which the function was invoked.

this keyword is used to access instance variables when the name of the instance variable is the same as any local or formal variable of the function.

self is a reference to an object

Compiler / Interpreter / ByteCode

A compiler reads the program, checks for syntax errors and creates an executable file that can be executed at any time. There is no need to recompile every time to execute the program.

An interpreter reads the program line by line, checks for errors and executes immediately. Source code has to be interpreted each time to execute the program.

Bytecode is a machine instruction given to JVM.

Java has the advantage of both Compiler and Interpreter.

Python has only an Interpreter.

ClassLoader

It is a subsystem of JVM used to load class files.

PEP-8 (Python Enhancement Proposal)

It is a set of rules used to increase Python code reusability.

Lambda Function

It is used when the function is of one line and has no return type and no iteration problem.

Shallow and Deep Copy

A shallow copy passes a reference to an object.

Deep copy creates new objects and copies.

Constructor

2021-07-03T15:21:00.003+05:30

Constructor

Constructor is a special method of the class whose name is the same as the class name and it runs automatically when an object is created.

Use of Constructor

It is used to initialize instance variables immediately after the creation of an object.

Properties of Constructor

It has no return type not even void

Its name is same as that of class

It runs automatically after creation of an object

Compiler automatically creates a default constructor when no constructor is defined

Types of Constructor

Constructor which does not take any argument is known as a default constructor.

Default constructor is of two types

Created by Programmer

Automatically created by the compiler (when no constructor is defined)

Constructor that can take arguments is known as parameterized constructor.

Constructor Overloading

Defining two or more constructors in a class is known as Constructor Overloading. All

constructors should have different parameter declarations.

Difference between Constructor and Function

Constructor	Function
Its name is same as class name	Its name is different from class name
It cannot return any value	It can return values
It gets invoked when an object is created	It has to be called explicitly after creation of an object
It is used to initialize instance variables	It is used to perform other tasks

Points to remember

Constructor is always defined in public section of the class so that objects can be created in functions of any class.

When no constructor is defined, compiler automatically creates a default constructor to initialize instance variables.

Default constructor automatically created by the compiler initializes integer variables by 0, floating-point variables by 0.0, boolean variables by false, String and all non-primitive by null.

Arrays

2021-07-02T19:47:00.003+05:30

Arrays

An array can be defined as a set of homogeneous data elements stored in contiguous memory locations.

Declaring an Array

datatype arrayname[]; Eg: int a[];
datatype[] arrayname; Eg: int[] a;

Creating an Array

To create blank array

arrayname = new datatype[size];
Eg: ar[] = new int[5];

To create filled array

arrayname = {value1, value2, ...};
Eg: ar = {3, 4, 5};

Array Initializer

An array initializer is a list of comma-separated values surrounded by braces.

Eg: {3, 4, 5, 2, 8}

Getting the size of the Array

We can get the size of the array using its length property.

Eg: int ar[] = new int[10];

int len = ar.length;

System.out.println(len);

Advantages of using Arrays

We can define as many variables as we want in a single statement.
We can access each element using the loop. This reduces the size of the program.

Disadvantages of using Arrays

Once an array is created we cannot change its size.

Difference between Linear Search and Binary Search

Linear Search	Binary Search
It searches all the elements in a sequential way	It checks the middle element and then according to its value it checks either on the left side or right side and leaves the other part
It can work on an unsorted array	It works on sorted arrays only
It is slower than binary search	It is faster than linear search

Difference between Bubble Sort and Selection Sort

Bubble Sort	Selection Sort
It compares adjacent elements, if they are not in order, swap them	It finds the smallest element of the array and swaps it with the first element
It is slower than selection sort because a number of swapping are to be done in each pass.	It is faster than bubble sort because only one swapping has to be done in each pass.

Linked List Cycle II Program (Leetcode)

2021-01-13T08:24:00.007+05:30

Linked List Cycle II Program (Leetcode):

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        first = head
        second = head
        
        while first != None and second != None:
            if first.next == None or second.next == None:
                return None
            
            first = first.next
            second = second.next.next
            
            
            if first == second:
                first = head
                break
        if first == None or second == None:
            return None
        while first != second:
            first = first.next
            second = second.next
        return first

Reorder List Program (Leetcode)

2020-12-26T10:33:00.005+05:30

Reorder List Program (Leetcode:

You are given the head of a singly linked list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

The number of nodes in the list is in the range [1, 5 * 104].
1 <= Node.val <= 1000

print 'hello world!'# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return
        
        temp = head
        mid = head
        
        while temp != None and temp.next != None:
            mid = mid.next
            temp = temp.next.next
            
        rev = self.reverseList(mid)
        
        new = head
        while rev.next != None:
            temp_new = new.next
            new.next = rev
            
            temp_rev = rev.next
            rev.next = temp_new
            
            new = temp_new
            rev = temp_rev
            
    def reverseList(self, head):
        p1 = None
        p2 = head
        
        while p2 != None:
            p3 = p2.next
            p2.next = p1
            p1 = p2
            p2 = p3
        return p1

Counting Bits Program (Leetcode)

2020-12-16T17:57:00.005+05:30

Counting Bits Program (Leetcode):

The Counting Bits program on LeetCode is a dynamic programming problem designed to calculate the number of 1 bits in the binary representation of all numbers from 0 to a given integer n. The goal is to efficiently generate an array where each element represents the count of set bits (1s) in the binary representation of its corresponding index. The dynamic programming approach involves observing patterns in binary numbers to determine the number of set bits. By using previously computed results and bitwise operations, the program optimally computes the count of set bits for each number in the range. This problem challenges programmers to develop efficient algorithms that minimize time complexity and memory usage while accurately counting the bits for large integers.

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

0 <= n <= 105

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time? O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Want to check about the Latest Electronic Devices: CompareKarein

class Solution:
    def countBits(self, num: int) -> List[int]:
        
        ans = [0] * (num + 1)
        for i in range(num + 1):
            if i % 2 == 0:
                ans[i] = ans[i//2]
            else:
                ans[i] = ans[i - 1] + 1
        return ans

Linked List Cycle Program (Leetcode)

2020-12-09T15:15:00.008+05:30

Linked List Cycle Program (Leetcode):

The Linked List Cycle program is a classic problem in computer science, often encountered in technical interviews and coding challenges. The task involves detecting whether a linked list contains a cycle, where a cycle occurs if any node in the list points back to a previous node, creating a loop. The challenge lies in efficiently determining whether such a cycle exists within the linked list. The typical approach involves using two pointers, known as the slow and fast pointers, to traverse the list. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If there is a cycle, the fast pointer will eventually catch up to the slow pointer. By detecting this collision, the program can conclude that a cycle exists. Implementing this algorithm effectively requires careful consideration of edge cases and pointer manipulation to ensure accuracy and efficiency.

Given head, the head of a linked list, determines if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that the tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Want to check about the Latest Electronic Devices: CompareKarein

# Definition for singly-linked list.

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        first = head
        second = head
        
        while first != None and second != None:
            if first.next == None or second.next == None:
                return False
            
            first = first.next
            second = second.next.next
            
            if first == second:
                return True
            
        return False

Remove Nth Node From End of List Program (Leetcode)

2020-12-04T17:17:00.003+05:30

Remove Nth Node From End of List Program (Leetcode):

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

Follow up: Could you do this in one pass?

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        count = 1
        start = head
        last = head
        
        while count <= n:
            count += 1
            last = last.next
            
        if last == None:
            head = head.next
            return head
            
        while last.next != None:
            start = start.next
            last = last.next
            
        start.next = start.next.next
        return head

Linked List

2020-11-30T21:57:00.002+05:30

Linked List Python:

class Node:
    def __init__(self, val = None):
        self.val = val
        self.next = None
        
class LinkedList:
    def __init__(self):
        self.head = Node()
        
    def addLast(self, val):
        newNode = Node(val)
        cur = self.head
        while cur.next != None:
            cur = cur.next
        cur.next = newNode
    
    def addBeg(self, val):
        new = Node(val)
        cur = self.head
        last = cur
        
        cur = cur.next
        last.next = new
        new.next = cur
        
    def addPos(self, val, pos):
        new = Node(val)
        cur = self.head
        count = 0
        while True:
            last = cur
            cur = cur.next
            if pos == count:
                last.next = new
                new.next = cur
                return
            count += 1
            
    def removeVal(self, val):
        cur = self.head
        while True:
            last = cur
            cur = cur.next
            if cur.val == val:
                last.next = cur.next
                return
            
    def removeIndex(self, index):
        cur = self.head
        count = 1
        while True:
            last = cur
            cur = cur.next
            if count == index:
                last.next = cur.next
                return
            count += 1
        
    def printList(self):
        l = []
        temp = self.head
        while temp.next != None:
            temp = temp.next
            l.append(temp.val)
        print(l)
        
linked = LinkedList()
linked.addLast(1)
linked.addLast(2)
linked.addLast(3)
linked.addLast(5)
linked.printList()

linked.addBeg(0)
linked.printList()

linked.addPos(4, 1)
linked.printList()

linked.removeVal(4)
linked.printList()

linked.removeIndex(3)
linked.printList()

Remove All Adjacent Duplicates In String Program (Leetcode)

2020-11-17T19:07:00.005+05:30

Remove All Adjacent Duplicates In String Program (Leetcode):

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Example 2:

Input: s = "azxxzy"
Output: "ay"

Constraints:

1 <= s.length <= 105
s consists of lowercase English letters.

class Solution:
    def removeDuplicates(self, S: str) -> str:
        if not S:
            return S
        
        res = [S[0]]
        for i in S[1:]:
            if res and i == res[-1]:
                res.pop()
            else:
                res.append(i)
                
        return "".join(res)

Interview Questions | Easy | List | Leetcode

2020-11-07T16:26:00.006+05:30

Interview Questions | Easy | List | Leetcode:

344. Reverse String

 class Solution:
    def reverseString(self, s: List[str]) -> None:
        s.reverse()

136. Single Number

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        check = nums[0]

        for i in nums[1:]:
            check = check ^ i
            
        return check

237. Delete Node in a Linked List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        to_del = node.next
        node.next = node.next.next
        del(to_del)

46. Permutations

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        from itertools import permutations
        per = list(permutations(nums))

        return per

206. Reverse Linked List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:

        root = None
        while head != None:
            root = ListNode(head.val, root)
            head = head.next

        return root

78. Subsets

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        from itertools import combinations
        comb = []
        for i in range(len(nums) + 1):
             comb.append(list(combinations(nums, i)))

             ans = []
             for i in comb:
                 for j in i:
                     ans.append(j)

        return ans

412. Fizz Buzz

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        ans = []
        for i in range(1, n + 1):
            if i % 15 == 0:
                ans.append("FizzBuzz")
            elif i % 3 == 0:
                ans.append("Fizz")
            elif i % 5 == 0:
                ans.append("Buzz")
            else:
                ans.append(str(i))

        return ans

Longest Palindromic Substring Program (Leetcode)

2020-10-28T13:58:00.003+05:30

Longest Palindromic Substring Program (Leetcode):

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case).

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        if length == 0:
            return ''
        
        dp = [[0]*length for j in range(length)]
        for i in range(length):
            dp[i][i] = 1    
  
        count = length
        val = s[0]
        for i in range(1, length):
            x = 0
            y = i
            for j in range(i, length):
                if count > (2 * length - 1):
                    if s[x] == s[y] and dp[x + 1][y - 1] == 1:
                        dp[x][y] = 1
                        val = s[x: y + 1]
                else:
                    if s[x] == s[y]:
                        dp[x][y] = 1
                        val = s[x: y + 1]       
                x += 1
                y += 1
                count += 1

        return val

Count Negative Numbers in a Sorted Matrix Program (Leetcode)

2020-10-15T17:04:00.004+05:30

Count Negative Numbers in a Sorted Matrix Program (Leetcode):

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0

Example 3:

Input: grid = [[1,-1],[-1,-1]]
Output: 3

Example 4:

Input: grid = [[-1]]
Output: 1

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

Follow up: Could you find an O(n + m) solution?

class Solution:
    def binarySearch(self, nums):
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] >= 0:
                left = mid + 1
            else:
                right = mid - 1
                
        return len(nums) - left
    
    def countNegatives(self, grid: List[List[int]]) -> int:
        count = 0
        for row in grid:
            count += self.binarySearch(row)
            
        return count

Find First and Last Position of Element in Sorted Array Program (Leetcode)

2020-10-09T22:12:00.006+05:30

Find First and Last Position of Element in Sorted Array Program (Leetcode):

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109

#check move left or not
def binarySearch(self, nums, target, check):  
        left = 0
        right = len(nums)
        
        while left < right:
            mid = (left + right) // 2
            if (nums[mid] > target or (check and target == nums[mid])):
                right = mid
            else:
                left = mid + 1
        return left
   
def searchRange(self, nums: List[int], target: int):
        left = self.binarySearch(nums, target, True)
        if left == len(nums) or nums[left] != target:
            return [-1, -1]        

        right = self.binarySearch(nums, target, False) - 1
        return [left, right]

Longest Substring Without Repeating Characters Program (Leetcode)

2020-10-03T18:30:00.003+05:30

Longest Substring Without Repeating Characters (Leetcode):

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols, and spaces.

dict = {}
length = 0
start = 0
        
for i in range(len(s)):
        if s[i] in dict:
                start = max(start, dict[s[i]] + 1)
        if length < i - start + 1:
                length = i - start + 1
        dict[s[i]] = i
        
print(length)

Search a 2D Matrix Program (Leetcode)

2020-09-30T20:57:00.006+05:30

Search a 2D Matrix Program (Leetcode):

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

if(matrix.length == 0)
     System.out.println(false);     

int row = 0;
int col = matrix[0].length - 1;        

while(row < matrix.length && col >= 0)
{
     if(matrix[row][col] > target)
          col -= 1;
     else if(matrix[row][col] < target)
          row += 1;
     else                   
          System.out.println(true);
}
System.out.println(false);

Longest Increasing Subsequence Program (Leetcode)

2020-09-24T14:00:00.006+05:30

Longest Increasing Subsequence Program (Leetcode):

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

1) O(n^2)

if len(nums) == 0:
    return 0

length = [1 for i in range(len(nums))]        
for i in range(len(nums)):
    for j in range(i):
        if nums[j] < nums[i] and length[j] + 1 > length[i]:
            length[i] = length[j] + 1
                    
return (max(length))

2)O(n log(n))

def binarySearch(start, end, val, nums, index):
    if start > end:
        return start
    mid = (start + end) // 2
    if nums[index[mid]] < val:
        start = mid + 1
    else:
        end = mid - 1
        
    return binarySearch(start, end, val, nums, index)

size = 0
index = [None for i in range(len(nums) + 1)]
for i in range(len(nums)):
        val = nums[i]
        bin_val = binarySearch(1, size, val, nums, index)
        index[bin_val] = i
        size = max(size, bin_val)
        #print(index)

return size

Interview Questions Asked in TCS & Infosys

2020-09-21T21:28:00.002+05:30

Interview Questions Asked in TCS & Infosys

(You will get the video explanation at the bottom of page)

1) Prime Numbers using Sieve of Eratosthenes:

# https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

def prime(n):
    prime_list = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if prime_list[True]:
            for i in range(p * 2, n + 1, p):
                prime_list[i] = False

        p += 1
    prime_list[0] = False
    prime_list[1] = False
    return prime_list

ans = prime(20)
for i in range(len(ans)):
    if ans[i]:
        print(i, end = " ")

2) Frequency Count:

s = 'aabbcaabc'

#Using Counter
from collections import Counter
freq = Counter(s)
print(freq)


#Using Dictionary 
d = dict.fromkeys(s, 0)
print(d)
for i in s:
    d[i] = d[i] + 1

print("Frequency :", d)

3) Nth Largest Number:

val = [4, 9, 5, 6, 1, 2, 7]
import heapq
heapq.heapify(val)
print(heapq.nlargest(2, val))

4) Combinations:

comb = [1, 2, 3]
from itertools import combinations

#print(list(combinations(comb, 1)))
ans = []
for i in range(1, len(comb) + 1):
    ans.append(list(combinations(comb, i)))
print(and)

#Binary
bin_val = [str(bin(i))[2:] for i in range(1, 2 ** len(comb))]
val = list(map(str,comb[:]))
print(bin_val)

for i in bin_val:
    temp = ''
    for j in range(len(i)):
        if i[j] == '1':
            temp += str(comb[j])
    val.append(temp)

print(set(val))

5) Middle Element of Linked List in Single Loop:

class Node:  
    def __init__(self, data, next = None):  
        self.data = data  
        self.next = next                

def print_List(List):
    l = []
    while List != None:
        l.append(List.data)
        List = List.next

    print(l)
              
array = [1, 2, 3, 4, 5, 6, 7]
List = None

for i in array:
    List = Node(i, List)
#print_List(List)
ptr1 = List
count = 1

while count != len(array) - 1:
    if count & 1 == 1:
        ptr1 = ptr1.next
    count += 1
print(ptr1.data)

Programming Solutions

2020-09-21T15:30:00.011+05:30

Programming Solutions

Hi,

Programming Solutions provides a free concept for Computer Programs. It contains videos lectures of competitive programming as well as a basic concept for beginners. It will help the user to practice competitive level programming asked in Product Based companies like Facebook, Google, Amazon, Netflix, Apple, Microsoft and others.

Sharing you some programs like:

1) Edit Distance:

In this, you have been given two strings and now you have to convert one string to another, and you can only perform three operations like Insert, Replace, Delete.

This program is done by Dynamic Programming.

Please click on image for an explanation

2) Coin Change:

In this program, you have been given some coins and an amount. Now, you have to find the minimum numbers of coins needed to reach that amount.

Find the number of combinations that make up that amount.

Example: Coin : [1, 2, 5] Amount : 5

We can take one Rs 5, two Rs 2 and one Rs 1 and so on. There is four possible way. It seems to be confusing by writing similar numbers.

You can check the explanation by clicking below image:

3) Longest Mountain in Array:

In this program, given a list and you have to find the longest mountain.

Example: [1, 2, 2, 4, 5, 3, 2, 1, 10, 7]
Longest Mountains is: 6 [2, 4, 5, 3, 2, 1].

Because aa mountain has a peak and its left and right side must be in decreasing order. There are some more mountains like [1, 2], [1, 10, 7], but the longest is of 6 lengths.

Check the explanation here:

Partition Equal Subset Sum Program (Leetcode)

2020-09-18T19:10:00.005+05:30

Partition Equal Subset Sum Program (Leetcode):

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100

total = sum(nums)
if total & 1 == 1:
     return False

def subset(nums, index, target):
     if target == 0:
          return True

     if target < 0 or index == len(nums):
          return False

     if subset(nums, index + 1, target - nums[index]):
          return True
            
     i = index + 1
     while i < len(nums) and nums[i] == nums[index]: 
     #100 100 100 ... multiple times
          i += 1
     
return subset(nums, i, target)

print(subset(nums, 0, total // 2))  
#total // 2 because for 2 subset, sum must be half.

This program is similar to Combination Sum 2 or Sum of Subset.

Jump Game Program (Leetcode)

2020-09-16T22:04:00.004+05:30

Jump Game Program (Leetcode):

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

ans = 0
for i in range(len(nums)):
    if i + nums[i] >= ans:
        ans = i + nums[i]
    if i == ans:
        break
print(ans >= len(nums) - 1)

Coin Change 2 Program (Leetcode)

2020-09-11T22:46:00.007+05:30

Coin Change 2 Program (Leetcode):

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10]
Output: 1

Constraints:

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000

dp = [0 for i in range(amount + 1)]
dp[0] = 1        

for i in coins:
    for j in range(1, amount + 1):
        if i <= j:
            dp[j] += dp[j - i]            

print(dp[amount] if dp[amount] != 0 else 0)

Coin Change Program (Leetcode)

2020-09-11T22:28:00.006+05:30

Coin Change Program (Leetcode):

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Example 4:

Input: coins = [1], amount = 1
Output: 1

Example 5:

Input: coins = [1], amount = 2
Output: 2

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

num = [float("inf") for i in range(amount + 1)]
num[0] = 0

for i in coins:
    for j in range(amount + 1):
        if i <= j:
            num[j] = min(num[j], 1 + num[j - i])

#print(num)
return num[amount] if num[amount] != float("inf") else -1

Combination Sum II Program (Leetcode)

2020-09-09T18:24:00.011+05:30

Combination Sum II Program (Leetcode):

The Combination Sum II program on LeetCode is a problem that involves finding all unique combinations in a candidate set where the candidate numbers sum up to a given target. However, each number in the candidates may only be used once in each combination. This challenge extends the classic Combination Sum problem by adding the constraint of using each number only once. To solve this problem efficiently, candidates are sorted, and a backtracking algorithm is typically employed to explore all possible combinations while ensuring uniqueness. The program must handle duplicates in the candidate set and avoid generating duplicate combinations in the final result. This problem requires careful consideration of edge cases and proper handling of duplicates to produce the correct output efficiently.

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Constraints:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

#s sum of current set, k index, r  remaining sum
def subset(s, k, r): 
    x[k] = 1
    if s + nums[k] == target:
        p = []
        for i in range(k + 1):
            if x[i] == 1:
                p.append(nums[i])

            val.append(p)

    elif s + r >= target and s + nums[k] <= target:
    subset(s + nums[k], k + 1, r - nums[k])
    if s - nums[k] + r >= target and s + nums[k + 1] <= target:
        x[k] = 0
        subset(s, k + 1, r - nums[k])

x = [0 for i in range(len(nums))] #index
nums.sort()

val = []
subset(0, 0, sum(nums))        
ans = []
for i in val:
    if i not in ans:
        ans.append(i)

return ans