Interview-Bit

Question 1

kth row of pascal

take a initial row of result size with all 1’s

then starting from 2nd index:
update all the elements before it to 1 in revese order by adding that element to element before it.

Answer 1

ans = [1] * (rowIndex + 1)

    for i in range(2,rowIndex+1):

        for idx in reversed(range(1,i)):
            print(idx,i)

            ans[idx]=ans[idx]+ans[idx-1]
    return ans

Question 2

Merge intervals with new merge

Answer 2

def insert(self, intervals, new_interval):

    initial=len(intervals)

    for i in range(len(intervals)):

        if intervals[i].start>new_interval.start:

            if i>0 and intervals[i-1].end>new_interval.start:
                intervals[i-1].end=max(intervals[i-1].end,new_interval.end)
                break

            else:
                intervals.insert(i,new_interval)
                break

        elif intervals[i].start==new_interval.start:
            intervals[i].end=max(intervals[i].end,new_interval.end)
            break

    if initial==len(intervals):

        intervals.append(new_interval)

    res=[]

    for i in range(len(intervals)):

        if not res:
            res.append(intervals[i])
        else:

            if res[-1].end>=intervals[i].start:
                res[-1].end=max(res[-1].end,intervals[i].end)
            else:
                res.append(intervals[i])
    return res

Question 3

Plus one

just convert list to integer and print numbers
no need of edge cases

Answer 3

def plusOne(self, A):

    num=0

    for j in range(len(A)):

        num=num*10+A[j]
    return  [int(x) for x in str(num+1)]

Question 4

repeat Number

Just counter and loop through dict1 if found return and break

no edge cases

Answer 4

def plusOne(self, A):

    num=0

    for j in range(len(A)):

        num=num*10+A[j]
    return  [int(x) for x in str(num+1)]

Question 5

Max distance

store old index and array in tuple

then get max index from right and iterate through all elements from reverse and store max ans

Answer 5

class Solution:
    # @param A : tuple of integers
    # @return an integer
    def maximumGap(self, A):

    dict1=[]
    for i,j in enumerate(A):

        dict1. append((j,i))
    dict1. sort()

    ans=0
    maxindex=dict1[-1][1]
    for j in range(len(dict1)-2,-1,-1):

        ans=max(ans,maxindex-dict1[j][1])

        maxindex=max(maxindex,dict1[j][1])

    return ans

Question 6

Wave array

middle element less than other two

sort array
and swap every two elements in array

Answer 6

A.sort()

    i=1

    while i

Question 7

Median of two sorted arrays

Answer 7

class Solution:
    # @param A : tuple of integers
    # @param B : tuple of integers
    # @return a double
    def findMedianSortedArrays(self, A, B):

    counter=(len(A)+len(B))//2
    counter+=1

    if not A and not B:
        return 0
    if (len(A)+len(B))==1:
        return A[0] if A else B[0]

    prev=0
    pres=0
    i=0
    j=0

    while i

Question 8

smallest index of substring in string

Answer 8

def strStr(self, A, B):

    if not B:
        return -1

    for i in range(len(B),len(A)+1):

        if B in A[:i]:
            return i-len(B)
    return -1

Question 9

Longest common prefix

make sure that after every letter comparision length of dict should be less than 1

Answer 9

def longestCommonPrefix(self, A):

    dict1={}

    j=1
    while j:

        for i in range(len(A)):

            if j