Google_imp_medium

Question 1

Encode and Decode TinyURL

use the random function to
generate a 6 letter word which is a combination of lower and upper and digits and return as shortcode

when longurl is inputted to encode if longurl in dict1 return shorturl

else then call random and get 6 digit word if that word is not in dict then append that with prefix and push to dict1 with value and return prefix+shortcode

in decode return dict1(shorturl)

decode(encode(longurl))
resulting is again longurl

Answer 1

import random
import string
class Codec:
    def \_\_init\_\_(self):
        self.dict1={}

def get_random(self):

    return ''.join(random.choice(string.ascii_uppercase+string.ascii_lowercase+string.digits) for _ in range(6))

    def encode(self, longUrl):
        """Encodes a URL to a shortened URL.

        :type longUrl: str
        :rtype: str
        """
        prefix="http://tinyurl.com"
        for k,v in self.dict1.items():
            if v==longUrl:
                return prefix+str(k)
        tiny_code=self.get_random()

    while tiny_code in self.dict1.keys():
        tiny_code=self.get_random()

    self.dict1[prefix+str(tiny_code)]=longUrl
    return prefix+str(tiny_code)

    def decode(self, shortUrl):
        """Decodes a shortened URL to its original URL.

    :type shortUrl: str
    :rtype: str
    """
    return self.dict1[shortUrl]

Question 2

Queue Reconstruction by Height

need to sort in decreasing order by height and increasing order by number of persons

Answer 2

class Solution(object):
    def reconstructQueue(self, people):
        res=[]
        for p in sorted(people, key=lambda x :(-x[0],x[1])):
             res.insert(p[1], p)
        return res

Question 3

Wiggle Sort
reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]….

sort the nums
fill the odd places of nums by poping them from end until len(nums) range

Answer 3

nums.sort()
for i in range(1,len(nums),2):
nums.insert(i,nums.pop())

Question 4

Daily Temperatures

start from last index

       if stack then find if there is any element greater than this in stack by popping and once if it is found then subtract that index with this index if found ans store it in index of element place ins ans array.

now append this element index to stack

finally return ans

Answer 4

class Solution:
    def dailyTemperatures(self, T):
        """
        :type T: List[int]
        :rtype: List[int]
        """

    ans=[0]*len(T)
    stack=[]

    for i in range(len(T)-1,-1,-1):            
        while stack and T[i]>=T[stack[-1]]:
            stack.pop()
        if stack:
            ans[i]=stack[-1]-i
        stack.append(i)
    return ans

Question 5

Generate Parentheses
if n=3 then ()()() or ()(()) or ….is ans

backtrack

Answer 5

ans=[]
        def backtrack(s='',left=0,right=0):
            if len(s)==2*n:
                ans.append(s)
                return 
            if left

Question 6

Game of life
According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population.
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Answer 6

class Solution:
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        r=len(board)
        c=len(board[0])

    x=[-1,-1,-1,0,0,1,1,1]
    y=[0,1,-1,-1,1,0,1,-1]

        for i in range(r):
            for j in range(c):
                count=0
                for k in range(8):
                    nx=i+x[k]
                    ny=j+y[k]

                if nx>=0 and nx=0 and ny 3:
                newstate = 0

            board[i][j] = board[i][j] | (newstate << 1)

    for i in range(r):
        for j in range(c):
            board[i][j] = board[i][j] >> 1

Question 7

Meeting Rooms II

make a sorted list of start times and endtimings

loop through start timings

if you find start timings> end timing then room is emptied and now comapre with next meeting end timing.

if not increase rooms by 1 an start ptr by 1

Answer 7

class Solution:
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        room=0
        if len(intervals)==0:
            return 0
        starttimings=sorted([i.start for i in intervals])
        endtimings=sorted([i.end for i in intervals])

    str_ptr=end_ptr=0

    while str_ptr=endtimings[end_ptr]:

                room=room-1
                end_ptr+=1
            room=room+1
            str_ptr+=1
        return room

Question 8

Fruit Into Baskets

start with starting tree and collect fruits of type and maintain a ductionary of type and count.

if you find any time this dict>2 length then move n i value so that you are deleting starting values

maxcount alwayd maintain max of length of list (j=i+1) at any point of time when two type of fruits available.

Answer 8

max_count=0
        i=0
        basket={}
        for j,x in enumerate(tree):
            if x in basket:
                basket[x]+=1
            else:
                basket[x]=1
            while len(basket)>2:
                basket[tree[i]]-=1

                if basket[tree[i]]==0:
                    del basket[tree[i]]
                i=i+1
            max_count = max(max_count, j - i + 1)
        return max_count

Question 9

Find Peak Element(logn time complexity)

here we find mid and compare with mid+1 if slopw is decreasing then increasing will be in left so r=mid
else if slope is increasing then decreasing will be in right hence l =mid+1

Answer 9

l,r=0,len(nums)-1
        while lnums[mid+1]:
                # slope is slanting so peak must be in left
                r=mid
            else:
                l=mid+1
        return l

Question 10

Search a 2D Matrix II

start with 1st row and last column

if value ==target :
    return True
elif value>target
     row+1
else .  col-1

Answer 10

if len(matrix)==0:
            return False
        row=0
        col=len(matrix[0])-1

    while row=0:

            val=matrix[row][col]
            if val==target:
                return True
            elif target>val:
                row=row+1
            else:
                col=col-1
        return False

Question 11

Perfect Squares

append all perfect squares less than n

then looping through this and n

fill the result array which is of size n+1

using
arr1[j]=min(arr1[j],1+arr1[j-psquare[i]])

Answer 11

if n==1:
            return 1
        if n==0:
            return 
        psquare=[]
        for i in range(1,n):
            if i*i>n:
                break
            psquare.append(i*i)
        max_sum=float('inf')
        arr1=[max_sum for i in range(n+1)]
        arr1[0]=0

    for i in range(len(psquare)):

        for j in range(n+1):

            if j>=psquare[i]:
                arr1[j]=min(arr1[j],1+arr1[j-psquare[i]])        
    return arr1[-1]

Question 12

Phone Number

Answer 12

class Solution:
    def \_\_init\_\_(self):
        self.digitmap={
            "2": ["a", "b", "c"],
            "3": ["d", "e", "f"],
            "4": ["g", "h", "i"],
            "5": ["j", "k", "l"],
            "6": ["m", "n", "o"],
            "7": ["p", "q", "r", "s"],
            "8": ["t", "u", "v"],
            "9": ["w", "x", "y", "z"]
        }

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if len(digits)==0:
            return []
        results=[]
        def dfs(digits,i,word):
            if i==len(digits):
                results.append(word)
                return 
            for c in self.digitmap[digits[i]]:
                word=word+c
                dfs(digits,i+1,word)
                word=word[:-1]
        dfs(digits,0,'')
        return results

Question 13

Number of Islands

Answer 13

class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if len(grid)==0:
            return 0
        x=[-1,0,0,1]
        y=[0,1,-1,0]

    r=len(grid)
    c=len(grid[0])
    count1=0

    def dfs(i,j,grid,x,y):   

        grid[i][j]='#'

        for k in range(4):

            nx=i+x[k]
            ny=j+y[k]
            if nx>=0 and nx=0 and ny

Question 14

Longest Absolute File Path

fill the stack by counts of strings until . extension is found. once it is found count te stack len and . file length

while loop i used when u go into sublevels and if u find a parallel level subsirectors with the help of count u will pop o stack and maintain the count

Answer 14

stack,max_len=[],0

    for i in input.split('\n'):

        while stack and len(stack)>i.count('\t'):
            stack.pop()

        if i.count('.')==0:
            stack.append(len(i.strip('\t'))+1)

        else:
            max_len=max(max_len,sum(stack)+len(i.strip('\t')))

    return max_len

Question 15

Merge Intervals

Answer 15

k=[]
for i in sorted(intervals, key=lambda i: i.start):
print(i)

            if len(k)==0:
                k.insert(len(k),i)
            elif k[-1].end>=i.start:
                k[-1].end=max(k[-1].end,i.end)
            else:
                k.insert(len(k),i)
        return k

Question 16

Word Break
Take an resultant array and fill it will all false upto n+1 length. similar to coin change prob

condition:

if res[j] and s[j:i] in wordDict:
res[i]=True
break
make sure that till split the word exists in list and after that sibscript in worddict and hence total word exist

Answer 16

n=len(s)
res=[False]*(n+1)

    res[0]=True

    for i in range(1,n+1):
        for j in range(i):

            if res[j] and s[j:i] in wordDict:

                res[i]=True
                break

    return res[-1]

Question 17

Next Permutation o(n) Tc and o(1) space

start from reverse
find the index where you find the decreasing order index to left
then from that index to right now find the elemnet which is just greater than index-1
once found swap
now reverse all the numbers after index

Answer 17

#>right
        i = len(nums)-1
        while i-1>=0 and nums[i-1]>=nums[i]:
            i -=1
        #>left
        if i-1>=0:
            j = i
            while jnums[i-1]:
                j +=1
            #swap the min-max number
            nums[i-1],nums[j-1] = nums[j-1],nums[i-1]
        nums[i:]=nums[i:][::-1]

Question 18

Spiral Matrix

Answer 18

def spiral(r1,c1,r2,c2):
            for c in range(c1,c2+1):
                yield r1,c
            for r in range(r1+1,r2+1):
                yield r,c2

        if r1

Question 19

power(x,n) . o(logn)

if n is negative will convert it to positive nad then x=1/x

here if n is positive then we multiple x by x and the divide n by 2 when n is odd then we multiply the whole x gathered till now to pow1

Answer 19

if n<0:
x=1/x
n=-n

    pow1=1

    while n:

            if n%2==1:
                pow1=pow1*x
            x=x*x
            n=n//2
        return pow1

Question 20

Clone graph

Answer 20

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):

    if not node:
        return 

    nodecopy=UndirectedGraphNode(node.label)

    dict1={node:nodecopy}

    self.dfs(node,dict1)

    return nodecopy

def dfs(self,node,dict1):

    for neighbour in node.neighbors:

        if neighbour not in dict1:

            neighbourcopy=UndirectedGraphNode(neighbour.label)

            dict1[neighbour]=neighbourcopy
            dict1[node].neighbors.append(neighbourcopy)
            self.dfs(neighbour,dict1)

        else:
            dict1[node].neighbors.append(dict1[neighbour])