Alien Dictionary

code:

 from collections import defaultdict

class Solution:

    def __init__(self):

        self.graph=defaultdict(list)

        

        

    def addEdge(self,u,v):

        self.graph[u].append(v)

        

    

    def topUtil(self,visited,i,stack):

        visited[i]=True

        

        for k in self.graph[i]:

            if visited[k]==False:

                self.topUtil(visited,k,stack)

        

        stack.append(i)    

        

        

        

    def findOrder(self,dict, N, k):

        

        for i in range(len(dict)-1):

            w1=dict[i]

            w2=dict[i+1]

            

            for j in range( min(len(w1),len(w2)) ):

                if w1[j]!=w2[j]:

                    #print(w1[j],w2[j])

                    self.addEdge(ord(w1[j])-97,ord(w2[j])-97)

                    break

                    

        #print(self.graph)

                

                    

    # top(self,k):

        visited=[False]*k

        stack=[]

        for i in range(k):

            if visited[i]==False:

                self.topUtil(visited,i,stack)

                

        ans=[]        

        while stack:

            ans.append(stack.pop())

        

        for l in range(len(ans)):

            

            ans[l]=chr(ans[l]+97)

            

        print(ans)

        

        

N = 5

K = 4

dict = ["baa","abcd","abca","cab","cad"]

g=Solution()       

g.findOrder(dict,N,K)

        

Find whether it is possible to finish all tasks or not from given dependencies Using Python

code:

from collections import defaultdict

class graph:

    def __init__(self,v):

        self.v=v

        self.graph=defaultdict(list)

        

    def addEdge(self,u,v):

        self.graph[u].append(v)

        

    

        

    def isCycleUtil(self,visited,i,recStack):

        visited[i]=True

        recStack[i]=True

        

        for j in self.graph[i]:

            if visited[j]==False:

                if self.isCycleUtil(visited,j,recStack)==True:

                    return True

            elif recStack[j]==True:

                return True

                

        recStack[i]=False

        return False

        

    def isCycle(self):

        visited=[False]*self.v

        recStack=[False]*self.v

        

        for i in range(self.v):

            if visited[i]==False:

                if self.isCycleUtil(visited,i,recStack)==True:

                    return True

                    

        return False

        

    

    def find(self):

        if self.isCycle()==True:

            return False

            

        inDegree=[0]*(self.v+1)

        

        for i in self.graph:

            for j in self.graph[i]:

                inDegree[j]+=1

               

        

        

        done=[False]*(self.v+1)

        q=[]

        

        for k in range(self.v+1):

            if inDegree[k]==0:

                q.append(k)

                done[k]=True

        

        print(inDegree)

        while q:

            t=q.pop(0)

            

            for node in self.graph[t]:

                

                done[node]=True

                inDegree[node]-=1

                if inDegree[node]==0:

                    q.append(node)

            

            

        

        for p in done:

            if p==False:

                

                return False

        return True

                

                

#Driver Code               

g=graph(4)

g.addEdge(1,0)

g.addEdge(2,1)

g.addEdge(3,2)

print(g.find())

                    

Rat in a Maze Solution

code:

 def pathUtil(maze,visited,sol,x,y,N,possible):

    #print(sol)

    if x<0 or y<0 or x>N-1 or y>N-1 or maze[x][y]==0 or visited[x][y]==1:

        return

    

    if x==N-1 and y==N-1 and maze[x][y]==1:

        possible.append(sol)

        return

    

    visited[x][y]=1

    

    pathUtil(maze,visited,sol+'D',x+1,y,N,possible)

    pathUtil(maze,visited,sol+'U',x-1,y,N,possible)

    pathUtil(maze,visited,sol+'R',x,y+1,N,possible)

    pathUtil(maze,visited,sol+'L',x,y-1,N,possible)

    

    visited[x][y]=0

    

def path(maze,N):

    visited=[[0 for i in range(N)] for j in range(N)]

    sol=''

    possible=[]

    pathUtil(maze,visited,sol,0,0,N,possible)

    

    print("possible path : ",possible)

    

N = 4

maze = [[1, 0, 0, 0],

         [1, 1, 0, 1], 

         [1, 1, 0, 0],

         [0, 1, 1, 1]]

         

path(maze,N)

Competitive Programming vs Development

Competitive programming vs development which would be good for our career this question arise in every IT Student. Every Would suggest you to go for competitive programming because it opens great opportunity in jobs. Their are many platform where you can practice your coding skills or do competitive programming like Hackerrank,Topcoder,codechef,codeforces..etc.. The development is also important but not necessary if you pro in Data structure and algorithm.

If you want to do startup or business in IT field then it will be ok to do more projects so you can understand how Software are developed but for job in Product Based company you have to crack competitive programming.

If you are in 1st or 2nd year then highly recommend you to try competitive Programming and learn Data Structure and algorithm , increase your programming level to advance or intermediate. If you are able to do this then you can continue this in 3rd or 4th year easily.

If you are start Competitive Programming in 3rd year or 4th year you just learn topics at least topics of data structure . Then focus on making one big project related to any trending technology.

Here you can get you project idea : https://www.codementor.io/projects

In My coding journey what mistake I have done I will explain you and you should not do that.. 

Best Platform For Competitive Programming

Actually Here many student get confuse that which competitive programming platform is best for practice and I have also wasted my 1st and 2nd year of college in this things but it is just wastage of time. Their is nothing like best platform through which if you practice on that you become pro in less time it is not like that rather than that programming is about how much you have practice it , you just have to solve more and more question ,start with easy level do  100-150 question of each topic related to Data structure and algorithm then switch into intermediate level and then into Advance level. Initially you can able to solve only one question in one day or more. but don't demotivate just continue your count of failure , Try to solve then see solution from editorials understand them.

Don't Confuse Too Much

I just recommend you to do practice in hackerrank And do competition in codechef ,You can use  Codechef rating into you resume to show case your Programming Skills.

Doing only Easy Problem

Here if you have done 50 question of easy level of each topic then it means you have done with easy level you have to switch into another level . It is necessary for you to understand when to switch to higher  level otherwise you cant progress you will be always into you comfort zone.

At The End I just Want to say Don't lose Focus your Time investment in CP will be worth for you in career. It will frustrating , depressing but don't give up.  

I will post Topic For Data structure and algorithm in future posts

Thank you.

Knapsack(0/1) Problem Solution Using Python

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0-1 property).

Code :

w=10 n=4 val=[10,40,30,50] wt=[5,4,6,3] row,col=(n,w) arr=[[0 for i in range(col+1)]for j in range(row+1)] for item in range(row): item=item+1 for capacity in range(col): capacity=capacity+1 maxWithCurr=0 maxWithoutCurr=arr[item-1][capacity] if capacity >= wt[item-1]: remaining=capacity-wt[item-1] maxWithCurr=val[item-1] maxWithCurr+=arr[item-1][remaining] arr[item][capacity]=max(maxWithCurr,maxWithoutCurr) print(arr[row][col]) print(arr)

The Flight Plan - Hackerearth Problem Solution Using Python

Here , To solve this problem we have use the BFS algorithm using python in which we just add a "dist" list in which we store distance of every node from its parent node. And we have use dictionary named "dd" in which we store its parent node if we print that dictionary we get the path for for each node from source given node.

For the Problem goto below link and search for problem: The Flight Plan

Code :

from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def addEdge(self,u,v): self.graph[u].append(v) def BFS(self, s,l): dist=[0]*100 dd=defaultdict(list) dd[s].append(0) visited = [False] * 100#(len(self.graph)+1) queue = [] queue.append(s) visited[s] = True while queue: s = queue.pop(0) for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 dd[i].append(s) for j in dd[s]: dd[i].append(j) queue.append(i) visited[i] = True print(dist[l]+1) return dd[l] def main(): l=list(map(int,input().split())) g=Graph() for i in range(l[1]): l2=list(map(int,input().split())) g.addEdge(l2[0],l2[1]) g.addEdge(l2[1],l2[0]) l3=list(map(int,input().split())) ans=g.BFS(l3[0],l3[1]) ans.reverse() for i in ans: if i==0: continue print(i,end=' ') print(l3[1],end=' ') main()

Social Networking Graph - Hackerearth Problem Solution Using Python

Here , To solve this problem we have use the BFS algorithm using python in which we just add a "dist" list in which we store distance of every node from its parent node. And then we see count nodes which are at a given distance from given source node.

For the Problem goto below link and search for problem: Social Networking Graph

Code :

from collections import defaultdict from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def addEdge(self,u,v): self.graph[u].append(v) def BFS(self, s,a): dist=[0]*100 visited = [False] * 100#(len(self.graph)+1) queue = [] queue.append(s) visited[s] = True while queue: s = queue.pop(0) for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 #this is the dist list queue.append(i) visited[i] = True return dist.count(a) def main(): ml=[] l=list(map(int,input().split())) g=Graph() for i in range(l[1]): l2=list(map(int,input().split())) g.addEdge(l2[0],l2[1]) g.addEdge(l2[1],l2[0]) #graph is bidirectional n=int(input()) for j in range(n): ll=list(map(int,input().split())) ans=g.BFS(ll[0],ll[1]) ml.append(ans) for i in ml: print(i) main()

Monk and the Islands - Hackerearth Problem Solution Using Python

Here , To solve this problem we have use the BFS algorithm using python in which we just add a "dist" list in which we store distance of every node from its parent node.

For the Problem goto below link and search for problem: Monk and Islands

Code :

from collections import defaultdict from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def addEdge(self,u,v): self.graph[u].append(v) def BFS(self, s,l): dist=[0]*10000000 visited = [False] * 10000000#(len(self.graph)+1) queue = [] queue.append(s) visited[s] = True while queue: s = queue.pop(0) for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 #this is the dist list queue.append(i) visited[i] = True return dist[l[0]] def main(): t=int(input()) ml=[] for i in range(t): l=list(map(int,input().split())) g=Graph() for i in range(l[1]): l2=list(map(int,input().split())) g.addEdge(l2[0],l2[1]) g.addEdge(l2[1],l2[0]) #graph is bidirectional ans=g.BFS(1,l) ml.append(ans) for i in ml: print(i) main()

Shortest Path Using Breadth First Search (BFS)

Shortest Path Using Breadth First Search (BFS)

Here , To find the shortest path using BFS first we have to know that the graph should always be unweighted graph .

If you know about the BFS algorithm then to find shortest path we have to add only one thing that is a dictionary named "dist" which records the distance of every node from given node As shown in below code.

Code :

from collections import defaultdict # This class represents a directed graph # using adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): dist=[0]*10 # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Create a queue for BFS queue = [] # Mark the source node as # visited and enqueue it queue.append(s) visited[s] = True while queue: # Dequeue a vertex from # queue and print it s = queue.pop(0) print (s, end = " ") # Get all adjacent vertices of the # dequeued vertex s. If a adjacent # has not been visited, then mark it # visited and enqueue it for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 queue.append(i) visited[i] = True print(dist) # Driver code # Create a graph given in # the above diagram g = Graph() g.addEdge(0, 1) g.addEdge(1,0) g.addEdge(0, 3) g.addEdge(3,0) g.addEdge(1, 2) g.addEdge(2,1) g.addEdge(3, 7) g.addEdge(7,3) g.addEdge(3, 4) g.addEdge(4,3) g.addEdge(4, 7) g.addEdge(7,4) g.addEdge(4, 6) g.addEdge(6,4) g.addEdge(7, 6) g.addEdge(6,7) g.addEdge(6, 5) g.addEdge(5,6) print ("Following is Breadth First Traversal" " (starting from vertex 2)") g.BFS(2)