python interview questions

https://leetcode.com/problems/range-module/description/

# Sorting technique internals:
- if n elements are iterated n x n with one way comparison (> or <) and swapping, each time at least one element will be sorted - as the comparison is one way, one or some sorted items will be left even though there is numerous swapping. So key is: 1. n x n iteration, 2. one way comparison and swaping

# Worst sorting: iteration = n x n = n^2
a = [5,3,4,2]
for x in range(len(a)):
    for y in range(len(a)):
        if a[x] < a[y]: swap(a, x, y) # This is dumb logic because it appears a[x] is understood to be fixed, but that is not the case. due to swapping a[x] keep changing during comparison. may be better way to do is store the value of a[x] in another variable if that is intended so.




https://www.codementor.io/python/tutorial/essential-python-interview-questions

https://www.google.com/search?q=python+interview+questions&oq=python+interview+questions&aqs=chrome..69i57j0l5.5566j0j4&sourceid=chrome&ie=UTF-8

# Insertion Sort
http://stackoverflow.com/questions/12755568/python-insertion-sort

http://www.geekviewpoint.com/python/sorting/insertionsort

Basic algorithm: Bubble, Insertion, selection: Bubble is worst than insertion and selection
Efficient Algorithm: quick, heap, merge, binary

# Bubble sort:
# Key is 1. compare immediate two numbers, 2. iterate through all list elements, 3. No need to iterate for already confirmed smallest element in its correct location - so save few iterations

# bubble down the smallest number to the left in each iteration and sub iteration
# at the end on first complete iteration, the smallest number bubbles down to the correct place
# at the end on 2nd complete iteration, the next smallest number bubbles down to the correct place
# so in every sub iteration, checking one place less from the left is safe
# at the end of all main iterations, all elements are are correct place

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html


# In the example below, the sorted element goes to the left and that element is untouched by
decreasing stop value of the range
def bubblesort( A ): # iteration = n(n-1)(n-2)...1 = n!
  for i in range( len( A ) ): # ensure iteration for all numbers done
    for k in range( len( A ) - 1, i, -1 ): # In every iteration one element from the left gets correct place
      if ( A[k] < A[k - 1] ):
        swap( A, k, k - 1 ) #

 # Even if decereasing, range always leave the last value of the right argument. for decrement, if the arg = 0, the recursion will happen only till one higher value - depending on the step value

def swap(a, x, y):
    temp = a[x]
    a[x] = a[y]
    a[y] = temp

# Insertion Sort: # No swapping
http://interactivepython.org/runestone/static/pythonds/SortSearch/TheInsertionSort.html

#
# Maintain a sorted sublist in each iteration for given elements of a list
# the current item is checked against those in the already sorted sublist
# As we look back into the already sorted sublist, we shift those items that are greater to the right.
# When we reach a smaller item or the end of the sublist, the current item can be inserted.

Approach:

#  Insertion sort is good for collections that are very small

#  or nearly sorted. Otherwise it's not a good sorting algorithm:

#  it moves data around too much. Each time an insertion is made,

#  all elements in a greater position are shifted.

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

 def insertionsort( aList ):

for i in range( 1, len( aList ) ): tmp = aList[i] # Current element k = i while k > 0 and tmp < aList[k - 1]: # do sorting on the sorted list aList[k] = aList[k - 1] k -= 1 aList[k] = tmp # k will be reduced to one less when while loop will break or at least # will be initialized to same number ; equivalent to no change

# insertion sort from end
def insertion_sort_x(ar):
    for i in range(len(ar) - 2, -1, -1): # len(ar) - 2 represent last number but one in the list ar
        temp = ar[i] # select the element next to the sorted number e
        k = i
        while k < (len(ar) -1) and temp > ar[k+1]:
            ar[k] = ar[k+1]
            k += 1
        ar[k] = temp
        print str(ar)


# Selection sort
http://interactivepython.org/runestone/static/pythonds/SortSearch/TheSelectionSort.html

def selection_sort_x(aList):
    for i in range( len( aList ) ):
        least = i
        for k in range( i + 1 , len( aList ) ):
            if aList[k] < aList[least]:
                least = k

        swap( aList, least, i )

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheQuickSort.html

# Quick sort -1

 import random

def quicksort( aList ):

    _quicksort( aList, 0, len( aList ) - 1 )

def _quicksort( aList, first, last ):

    if first < last:

      pivot = partition( aList, first, last )

      _quicksort( aList, first, pivot - 1 )

      _quicksort( aList, pivot + 1, last )

def partition( aList, first, last ) :

    pivot = first + random.randrange( last - first + 1 )

    swap( aList, pivot, last )

    for i in range( first, last ):

      if aList[i] <= aList[last]:

        swap( aList, i, first )

        first += 1

    swap( aList, first, last )

    return first

def swap( A, x, y ):

  A[x],A[y]=A[y],A[x]

# Quick sort -2
def quicksort(alis):
    _quicksort(alist, 0, len(alist)-1)
 
def _quicksort(alist, first, last):
    if first < last:
        splitpoint = partition(alist, first, last)
        _quicksort(alist, first, splitpoint-1)
        _quicksort(alist, splitpoint+1, last)
     
def partition(alist, first, last):
    pivot = alist[first]
    leftmark = first + 1
    rightmark = last
    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivot:
            leftmark += 1
     
        while rightmark >= leftmark and alist[rightmark] >= pivot:
            rightmark -= 1
         
        if rightmark < leftmark:
            done = True
        else:
            swap(alist, leftmark, rightmark)
    swap(alist, first, rightmark)
    return rightmark
       
def swap(A, x, y):
    A[x],A[y] = A[y], A[x]

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

==========
# 12 hr time to 24 hour time:

t_splt = time.split(':')
if t_splt[2][2:] == 'PM' and t_splt[0] != '12':
    t_splt[0] = str(12+ int(t_splt[0]))
elif int(t_splt[0])==12 and t_splt[2][2:] == 'AM':
    t_splt[0] = '00'
t_splt[2] = t_splt[2][:2]
print ':'.join(t_splt)

# Fill python list
http://stackoverflow.com/questions/5908420/how-to-fill-a-list-with-0-using-python

# float number precision formatting
"{0:.2f}".format(13.949999999999999) # precision upto 2 decimal place
"{0:.nf}".format(13.949999999999999) # precision upto n decimal place

"{0:>2}h {1:>2}m {2:>2}s".format(hrs, mts, sec)  :: first 0, 1, 2 are positional values of hrs, mts, sec

print '%5s' % 'aa'

http://stackoverflow.com/questions/20309255/how-to-pad-a-string-to-a-fixed-length-with-spaces-in-python

http://stackoverflow.com/questions/8450472/how-to-format-print-output-into-fixed-width

http://stackoverflow.com/questions/339007/nicest-way-to-pad-zeroes-to-string

'{x:y<z}'.format(p,q,r)   :: x = positional variable from format(...): y = fill in character, z = total reserved place for the variable it is associated with: >/< : angle nose is starting point of the reserved
space: > => reservation starts from the right side: < => reservation starts from the leftside
"{0:>2} {1:>2} {2:>2}".format(2, 3, 4)

"{0} {1} {2}".format(2, 3, 4)    :: 0,1,2 are positional variables

>>> "{:0>2}".format("1")  # Works for both numbers and strings.
'01'
>>> "{:02}".format(1)  # Only works for numbers.
'01'

width = 10
x = 5
print "%0*d" % (width, x)
> 0000000005

>>> print '{0:03d}, {1:03d}'.format(1,2) >>> 001, 002 

"".ljust()

>>> t = 'test'
>>> t.rjust(10, '0')
>>> '000000test'

>>> n = 4
>>> print '%03d' % n
>>> 004
>>> print format(4, '03') # python >= 2.6
>>> 004
>>> print '{0:03d}'.format(4)  # python >= 2.6
>>> 004
>>> print('{0:03d}'.format(4))  # python 3
>>> 004

>>> n = '4'
>>> print n.zfill(3)
>>> '004'

>>> name = 'John'
>>> name.ljust(15)
'John           '

>>> a = "John"
>>> "{:<15}".format(a)
'John           '

"The {structure} sank {0} times in {1} years.".format(
...   3, 2, structure='castle')
'The castle sank 3 times in 2 years.'

print 'as %d %s' % (2, 3)

print "A list: %s" % mylist

%s - String (or any object with a string representation, like numbers)
%d - Integers
%f - Floating point numbers
%.<number of digits>f - Floating point numbers with a fixed amount of digits to the right of the dot.
%x/%X - Integers in hex representation (lowercase/uppercase)

key formatting:

1. 'my name is %s singh' % ('gopal')
2. 'my name is {} singh'.format('gopal')
3. 'my name is {name} singh'.format(name='gopal')
4. 'gopal'.ljust(15)
5. 'gopal'.rjust(15)
6.  my name is %(name)s singh'%locals()  : When name = 'gopal' is defined
7. '0:.nf'.format(decimal_number) : n = nth number precision of decimal mumbers
8. print '%5s' % 'aa'

# factorial calculation
def factorial(n):return reduce(lambda x,y:x*y,[1]+range(1,n+1))

#
def factorial(number):
    if number <= 1: return 1
    return number*factorial(number - 1)

print factorial (5)

#
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1) # key technique is factorial(n-1), where n-1 is gets reduced on every recursion compared to factorial(n)
 
print factorial(4)


# Fibonacci sequence: next sequence is sum of the earlier two numbers
nth Fibonacci
>>> def fib(n):
# Get first two values hard coded as 1,1, .. The rest will be calculated per easy pattern
...     a,b = 1,1  # variable 'a' is of interest
...     for i in range(n-1): # n-1 max value is selected to exclude 1st and second values: range (n-1) will                                        #   exclude nth and (n-1)th numbers from the iteration list
            a, b = b, a + b
...     return a
...
>>> fib(2)
1
>>> fib(12)
144

#
def fib(n):
    a = b = 1
    for x in range(n-1):
        a, b = b, a + b
    print a
 
fib(6)  

#
def fib(n):
    f = [1,1]  
    for x in range(n-2):
        s = f[0] + f[1]      
        f[0] = f[1]
        f[1] = s

        print s
     
fib(7)

# 

def fib(n):
    a = b = 1  
    for x in range(n-2):
        s = a + b      
        a = b
        b = s
        print s
fib(7)
# reversed list:
WARNING: reverse() or reversed(list) works unusual way:
-[1,2,3].reverse()   returns None and just modified the given list
-reversed([1,2,3]) returns iterable object (not the reversed list)

So, DO NOT use count that reverse() or reversed(list) give a list

Elegant way to reverse a list is using negative step:
def reverse3(nums):
  return nums[::-1]

# using lambda, map, filter, reduce: List comprehension is alternative of using lambda, map, filter, reduce. The python creator 'Guido van Rossums prefers using list comprehension

lambda: inline function, no need to use the keyword 'def', no indentation, one liner function, no need to parenthesis, do not need to use the keyword 'return'. It is also used for an expression substitution as in filter.

filter accepts an expression that needs to be true to filter or retrieve only those values for which the given expression is true.

all of map, filter, reduce accepts the argument (function, list). map can accept more than one list.

-map() applies the function func to all the elements of the sequence seq. It returns a new list with the elements changed by func. map can take multiple lists per applied function's number of arguments
-The function filter(function, list) offers an elegant way to filter out all the elements of a list, for which the function function returns True. 

-The function reduce(func, seq) continually applies the function func() to the sequence seq. It returns a single value. 

map(lambda x: x*x, [1,2,3])

>>> def a(x, y):

...     return 5

>>> map(a, [1,2,3], [1,2,3,4])

>>> filter(None, [1,2,3, '', None])

[1, 2, 3]

#Calculating the sum of the numbers from 1 to 100:
>>> reduce(lambda x, y: x+y, range(1,101))
5050

# sum of all elements in a integer list:
def sum3(nums):
  return reduce(lambda x, y: x + y, nums)

http://www.secnetix.de/olli/Python/lambda_functions.hawk
http://www.python-course.eu/lambda.php

>>> f = lambda x,y: x + y
>>> f(1,1)
2

>>> def make_incrementor (n): return lambda x: x + n

>>> 

>>> f = make_incrementor(2)

>>> g = make_incrementor(6)

>>> 

>>> print f(42), g(42)

44 48

>>> 

>>> print make_incrementor(22)(33)

55

output = filter(None, error.split('\n'))

list comprehension: an easy way to create pattern based list.

my_numbers = [x for x in range(5)]

# string formatting:
>>> 'a {2} {0}'.format('1', '2', '3')
'a 3 1'
>>> 'a {} {}'.format('1', '2', '3')
'a 1 2'

str_heading = "{ts:12}, {name:50},{q:<15},{b:<15},{t:<15}".format(ts='Date', name='Description.number', q='Waiting', b='Building', t='Total time')

str_heading_html = "{ts:23} {name:50}{q:<15}{b:<15}{t:<15}".format(ts='\n<tr><td>Date', name='&nbsp;&nbsp;&nbsp;</td><td>Description.number', q='</td><td>Waiting', b='</td><td>Building', t='</td><td>Total time</td></tr>')

def format_time (msTime):

sec = msTime / 1000

mts, sec = divmod(sec, 60)

hrs, mts = divmod(mts, 60)

if hrs > 0:

return "{0:>2}h {1:>2}m {2:>2}s".format(hrs, mts, sec)

elif mts >0:

return "{0:>2}m {1:>2}s".format(mts, sec)

else:

return "{0:>2}s".format(sec)

# ONE LESS value for range and LIST Splice: range(1,3) => [1,2] :: [1,2,3][:2] => [list[0],list[1]] - then higher index is ONE LESS than the higher argument

# Logical operators: and / or : && and || are not used as is the case with some common languages like C/C++. && => and: || => or
# BitWise operator in python: AND => & : OR => |
# any and all: these operates on a list. all returns true when all element are True or non-empty (non-null). any returns if any element is True, or non-empty(non-null)
# range value: highest value of the list created by range is ONE LESS than the stop argument. range(start, stop, step)

# primary number: 0 and 1 are not primary numbers: a natural number greater than 1, divisible by self and 1 only.

You need to check all numbers from 2 to n-1 (to sqrt(n) actually, but ok, let it be n). If n is divisible by any of the numbers, it is not prime. If a number is prime, print it.

for num in range(1,101): #Need to exclude 1
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print num

>>> def a(n1, n2):   #Need to exclude 1
...     for n in range(n1, n2+1):
...         if all(n%i != 0 for i in range(2, n)): print n

# Optimized by using square root:

import math
>>>
import math
for num in range(1,101):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print num

#
def is_prime(number):
    if number > 1:
        if number == 2:
            return True
        if number % 2 == 0:
            return False
        for current in range(3, int(math.sqrt(number) + 1), 2):
            if number % current == 0:
                return False
        return True
    return False

# replace string letter at an index

def missing_char(str, n):
  return str.replace(str[n], '')

# check subset
def array123(nums):
  return set([1,2,3]).issubset(set(nums))

#
def string_bits(str):
  return ''.join([str[x] for x in range(0,len(str),2)])

#
def array_count9(nums):
  return len([x for x in nums if x == 9])

# python generators:
https://jeffknupp.com/blog/2013/04/07/improve-your-python-yield-and-generators-explained/

yield with respect to coroutines, cooperative multitasking and asynchronous I/O

# matching substring of length 2
def string_match(a, b):
  count = 0
  shorter = min(len(a), len(b))
  for i in range(shorter -1):
    if a[i:i+2] == b[i:i+2]: count += 1

  return count

# String formatting:
def hello_name(name):
  return 'Hello {}!'.format(name)

# Split string
def make_out_word(out, word):
  #split the out string in two parts
  out1 = out[:2]
  out2 = out[2:]
  return out1 + word + out2

# Return first half of a string
def first_half(str):
  return str[:(len(str))/2]

# list splice from last:
def extra_end(str):
  return str[-2:] + str[-2:] + str[-2:]

# rotate string
http://stackoverflow.com/questions/9457832/python-list-rotation

def rotate(l,n):
    return l[-n:] + l[:-n]

left: n = +ve

# python ternary operation
http://book.pythontips.com/en/latest/ternary_operators.html

def first_two(str):
  return str[:2] if len(str) > 2 else str

#=====
# RangeModule Solution
# Complete the methods below.

class RangeModule:
    def __init__(self):
        self.range_list = []
   
    def CheckOverlap(self, min2, max2):
        overlap_index = -1     
        counter = 0
        for range in self.range_list:       
            min1 = range[0]
            max1 = range[1]
            if max(min1, min2) <= min(max1, max2): break
            overlap_index += 1   
        return overlap_index   
   

    def CheckContains(self, min2, max2):
        contain = False       
        for range in self.range_list:           
            min1 = range[0]
            max1 = range[1]
            if ((min1 <= min2) and (max1 >= max2)):
                contain = True
                break
        return contain
   
    def AddRange(self, lower, upper):
        if len(self.range_list) == 0:
            self.range_list = [(lower, upper)]
            return
        if self.CheckContains(lower, upper): pass
        overlap_index = self.CheckOverlap(lower, upper)
        if overlap_index > -1:
            self.range_list[overlap_index][0] = min(self.min, lower)
            self.range_list[overlap_index][1] = min(self.min, lower)
        else:
            self.range_list.append((lower, upper))
       
    def QueryRange(self, lower, upper):
        if (lower, upper) in self.range_list: return True
        else: return False

    def RemoveRange(self, lower, upper):
        counter = 0       
        for range in self.range_list:
            # if existing range is contained in the given range           
            if min(range[0], lower) >= lower and max(range[1], upper) <= upper:
                self.range_list.remove(range)             
            # if given range overlap           
            if lower >= range[0] and lower <= range[1]:
                if upper < range[1]:
                    self.range_list[counter] = (range[0], lower-1)
                    self.range_list.append((upper+1, range[1]))
                else:
                    self.range_list[counter] = (range[0], upper-1)
            else:
                if upper >= range[1]:
                    self.range_list.remove(range)
                else:
                    self.range_list[counter] = (upper+1, range[1])
            counter += 1  
           
           
rm = RangeModule()
rm.AddRange(10, 100)
print rm.range_list
rm.QueryRange(10, 10)
rm.RemoveRange(25,44)
print rm.range_list

# Fizzbuzz question:


# Fibonacci numbers using generator

#! /usr/bin/env python

def fibo(number):

    a,b = 1,1

    for i in xrange(number):

        a,b = b, a + b

        yield b

for item in fibo(10): print item


# RangeModule-2
# RangeModule
# addRange[left, right)
# queryRange[left, right)
# removeRange[left, right)

class RangeModule(object):
    def __init__(self, rmrange=[]):
        self.rmrange = rmrange
    def get_range(self):
        return self.rmrange
    def set_range(self, rmrange):
        self.rmrange = rmrange
    def addRange(self, left, right):
        self.rmrange += range(left, right)
        self.rmrange = list(set(self.rmrange)) #.sort()
    def queryRange(self, left, right):
        l1 = range(left, right)
        l1.sort()
        l2 = self.rmrange
        l2.sort()
        if len(set(l1) & set(l2)) >= len(l1): return True
        else: return False
    def deleteRange(self, left, right):  
        self.rmrange = list(set(self.rmrange).difference(set(range(left, right))))
     
     
     


     
rm = RangeModule()
rm.addRange(1,10)
rm.addRange(1,3)
#rm.addRange(1,3)
print rm.rmrange
rm.deleteRange(2, 4)
rm.deleteRange(2, 5)
print rm.rmrange

print rm.queryRange(5,7)



# Linked List:
- It is a list of node object : a node object has two items - data & points to next node object