upload to nexus

#!/usr/bin/env python
# -*- coding: utf-8

'''
pub2nexus.py - publish to nexus server

Example:
./pub2nexus.py --action publish
               --dir /home/jenkins/workspace/AP-SCG_3.4.0.7_H500/tftpboot/ap-11ac-wasp-wsg
               --keyfile /home/jenkins/nexus.key    
               --server 172.16.200.63
               --target ap/brian/ML/3.4.0.11/
               --run

'''

from __future__ import division
from __future__ import absolute_import
from __future__ import print_function

import os.path
import os
import ConfigParser
import sys
import argparse
import logging
import json
import codecs
import urllib
import urllib2
import urlparse
import base64
import subprocess
import re
import getpass
import traceback
import locale
import pprint
from collections import defaultdict
import signal
from subprocess import Popen, PIPE
import sets
import uuid
import tarfile
import shutil
import hashlib

MIN_CRUCIBLE_VERSION = '3.0.0'
SCRIPT_NAME = os.path.basename(__file__)
SCRIPT_VERSION='b4f0c4942ed8404a9a137f441d0768b6'
VERSION_DATE='Aug 11, 2016 07:00 PM'


def subprocess_cmd2(cmd):
    p = subprocess.Popen(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE, shell=True)
    stdout, stderr = p.communicate()  
    return stdout, stderr

def lsDirs(cmdOpts, folder):
    if cmdOpts.trace:
        print('In lsDirs')
    j = 0
    trace = True
    for item in os.listdir(folder):
        fpn = os.path.join(folder, item)
        if os.path.isdir(fpn) and item[0] != '.':
            j  += 1
            dirFullPathName = folder + '/' + item
            ###print('%3d (%s) -> %s , item[0]=(%s)' %(j, item, dirFullPathName, item[0] ))
            # cd to dir & create tar.gz
            tarName = item + '.tar.gz'
           
            folderFileList = lsFiles(cmdOpts, dirFullPathName)
            ###print('  folderFileList -> %s' %(folderFileList))
            curDir = os.getcwd()
            srcTarname = curDir + '/' + tarName
            dstDirname = folder + '/' + tarName
            ###print('  curDir: %s' %(curDir))
            createTar = False
            if len(folderFileList) != 0:
                # if the tar is exist on cur directory, remove it first.
                if os.path.isfile(srcTarname):
                    print('  * found & remove %s' %(srcTarname))
                    os.remove(srcTarname)

                #os.chdir(dirFullPathName)
                tar = tarfile.open(tarName, 'w:gz')
                print('  Creating tar: %s' %(tarName))
                for fullPathFolderFileName in folderFileList:
                    tar.add(fullPathFolderFileName)
                tar.close()
                #os.chdir(curDir)
                #shutil.move(src, dst)
                createTar = True
            elif len(folderFileList) == 0:
                if trace:
                    print('Noted, the Folder is empty -> %s' %(dirFullPathName))

            if createTar:        
                dstDirname = folder + '/' + tarName
                if trace:
                    print('  srcTarname -> %s' %(srcTarname))
                    print('  dstDirname -> %s' %(dstDirname))
                if os.path.isfile(dstDirname):
                    if trace:
                        print('  * found & remove %s' %(dstDirname))
                    os.remove(dstDirname)
                shutil.move(srcTarname, dstDirname)

def lsFiles(cmdOpts, folder):
    if cmdOpts.trace:
        print('In lsFiles')
    fileList = []
    j=0

    for item in os.listdir(folder):
        fpn = os.path.join(folder, item)
        if os.path.isfile(fpn):
            j += 1
            fpn = folder + '/' + item
            #print('%3d %s -> %s' %(j,item, fpn))
            fileList.append(fpn)
    return fileList

def touch(path):
    with open(path, 'a'):
        os.utime(path, None)

def get_md5(fpn):
md5_val = ''
with open(fpn) as file_handle:
data = file_handle.read()
md5_val = hashlib.md5(data).hexdigest()
return md5_val

def writeMd5(cmdOpts, destDir, fpnList):
    md5StrFileOut = destDir + '/' + 'MD5SUMS'
    md5Str=''

    if len(fpnList) == 0:
        return
    j=0
    trace = False
    for fpn in fpnList:
        j += 1
        if trace:
            print('%3d -> %s' %(j, fpn))
            # hashlib.md5(open('filename.exe','rb').read()).hexdigest()
        #md5sumStr = hashlib.md5(open(fpn,'rb').read()).hexdigest()
        md5sumStr = get_md5(fpn)
        md5Str += md5sumStr + ' ' + fpn + '\n'
    if md5Str != '':
    f =  open(md5StrFileOut, 'w')
    f.write(md5Str)
    f.close()
    print('Write out %s' %(md5StrFileOut))

def createMD5file(destDir):
    md5StrFileOut = destDir + '/' + 'MD5SUMS'
    touch(md5StrFileOut)

def do_publish(cmdOpts):
    if cmdOpts.trace:
        print('In publish')
    # get list of dir first
    trace = cmdOpts.trace
    destdir = cmdOpts.dir
    # working files version
    #print('destdir: %s' %(destdir))
    #files = [ f for f in os.listdir(destdir) if os.path.isfile(os.path.join(destdir,f)) ]
    #print('files: %s' %(files))

    lsDirs(cmdOpts, destdir)
    createMD5file(destdir)
    fpnList = lsFiles(cmdOpts, destdir)
    writeMd5(cmdOpts, destdir, fpnList)
    j=0
    commaSepStr=''
    trace = False
   
    for fpn in fpnList:
        j += 1
        if trace:
            print('%3d -> %s' %(j, fpn))

    commaSepStr = ",".join(fpnList )
    #print('commaSepStr=(%s)' %(commaSepStr))
    httpStr = 'http://'
    nexusPath=':8081/nexus/content/repositories/releases/ruckus/official/'
    httpPath = httpStr + cmdOpts.server + nexusPath + cmdOpts.target
    cmd = 'curl -sL --write-out %{http_code}, --upload-file {' + commaSepStr + '} ' + httpPath + ' --config ' + cmdOpts.keyfile
    #print('cmd=(%s)' %(cmd))

    if cmdOpts.run:
        print('exec %s' %(cmd))
        output, stderr = subprocess_cmd2(cmd)
        lineList = output.split('\n')
        j = 0
        for line in lineList:
            j += 1
            if trace:
                print('%d (%s)' %(j, line))
    else:
        print('--run disabled.')

def get_unique_id(cmdOpts):
    unique_id = str(uuid.uuid4())
    print('unique_id: ', unique_id)
    unique_id_without_dash = unique_id.replace("-", '')
    print('unique_id_without_dash 1 : ', unique_id_without_dash)
    #return unique_id_without_dash

def do_get_id(cmdOpts):
    get_unique_id(cmdOpts)

def help(cmdOpts):
    print('Usage')
    print('  %s --action get_id' %(SCRIPT_NAME))
    print('  %s --action publish --dir xxx ---server 172.16.200.63 --target ap/Xclaim/ML/2.2.0.0/Xi-3/2.2.0.0.6/  --keyfile /home/jenkins/nexus.key [--run] [--trace]' %(SCRIPT_NAME))
    print('  ./pub2nexus.py --action publish --dir /Users/brianpang/crucible --keyfile /home/jenkins/nexus.key --target ap/Xclaim/ML/2.2.0.0/Xi-3/2.2.0.0.6/ --server 172.16.200.63')
    sys.exit(1)

def selectCmd():
    fn = os.path.basename(__file__)
    parser = argparse.ArgumentParser(description='arg parser for %s' % fn)  
    parser.add_argument('--action', action='store', dest='action', help='Store a action value')
    parser.add_argument('--dir', action='store', dest='dir', help='Store a dir value')
    parser.add_argument('--server', action='store', dest='server', help='Store a server value')
    parser.add_argument('--keyfile', action='store', dest='keyfile', help='Store a keyfile value')
    parser.add_argument('--target', action='store', dest='target', help='Store a target value')

    parser.add_argument('--run', action='store_true', default=False, dest='run', help='Set run to true')
    parser.add_argument('--trace', action='store_true', default=False, dest='trace', help='Set trace to true')
    parser.add_argument('--verbose', action='store_true', default=False, dest='verbose', help='Set verbose to true')
    parser.add_argument('--debug', action='store_true', default=False, dest='debug', help='Set debug to true')

    cmdOpts = parser.parse_args()
    return cmdOpts

def main():
    cmdOpts = selectCmd();
    if cmdOpts.action is None:
        help(cmdOpts)
    elif cmdOpts.action == 'help':
    help(cmdOpts)
    elif cmdOpts.action == 'get_id':
        do_get_id(cmdOpts)  
    elif cmdOpts.action == 'publish':
        do_publish(cmdOpts)
    else:
        print('No match found.')
        help(cmdOpts)

if __name__ == '__main__':
    main()

sorting dictionary

http://stackoverflow.com/questions/2548000/sorting-a-dictionary-having-keys-as-string-of-numbers-in-python

converting dictionary to ordereddictionary (ordered dictionary)

http://stackoverflow.com/questions/15711755/converting-dict-to-ordereddict

Note: OrderedDict Will not Sort - it will just create the tuples correctly

python for loop and range: variable on loop line is not reinitialized

for y in range(x, 10):
...     print y
...     x += 1

In the above example the range does not change even if value of x is changing

but the range will change in the example below

for x in range(0, 4):

    for y in range(4, x, -1):

        print y

python recursive function

http://stackoverflow.com/questions/479343/how-can-i-build-a-recursive-function-in-python

def a(n):
    if n == 0: return 0
    else: return n + a(n)

The two key elements of a recursive algorithm are:

• The termination condition: n == 0
• The reduction step where the function calls itself with a smaller number each time: factorial(n - 1)

python exception

https://www.codementor.io/python/tutorial/how-to-write-python-custom-exceptions

python class

https://jeffknupp.com/blog/2014/06/18/improve-your-python-python-classes-and-object-oriented-programming/

- Any class data that is not associated with self - is not used in an instance. It has to do with the data only not with the method

python generators or python yield

Note: Infinite loop is not an issue for generator. It does not take processor time as the generator object is called only during data retrieval:
def my_gen():
    count = 0      
    while True:
        count += 1      
        yield count + 1

Usage: memory optimized iteration (virtually stores calculated values like list without actually consuming memory: the values are retrieved runtime: kind of creates a memory place holder at a place in memory where a calculation is required and then call whenever it is required) and asyncronous operation

# yield is more than return
return is meant to stop/exit function execution when return keyword is reached. the objective of yield is to return continued values indefinitely. usage of return may look same some time but not always. return is mostly used at the end of the function to return a value and end the function, while yield objective is to continue returning when the values are to be retrieved.
yield => "yield a series of values". Function with yield is called generator because it is used to generate a series of values.
-return gets only once chance to return a value
-For infinite series, if we use return - we have to store all the values in a variable which may be out of memory or impossible to hold : but if the function can return one value at a time by doing all the calculation - then we can deal with very large or infinite numbers. - there is no more memory issue with this approach.

IMPORTANT: During 1st element retrieval, all the lines of the function is called, then (2nd onward only yield (kind of return) values are returned.

http://stackoverflow.com/questions/7883962/where-to-use-yield-in-python-best
http://pymbook.readthedocs.io/en/latest/igd.html
https://jeffknupp.com/blog/2013/04/07/improve-your-python-yield-and-generators-explained/

yield is best used when you have a function that returns a sequence and you want to iterate over that sequence, but you do not need to have every value in memory at once.

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

# About generator:
-a function becomes generator when return is replaced by keyword 'yield'
-when a generator is called first time, it creates a object in memory and does not execute and code in the generator or generator function.
-To use generator

# Simple generator example:
def a():
    yield 1

b = a()  # generator initialized: a generator cannot be used without initialization like class. Generator initialization look like function call - but both (function and generator) works/behaves differently.

b.next()  # retrieving values expected from yield. Once a value is retrieved, the generator object points to next element and the object looses that element after retrieval.

# Understand memory optimized operation using yield
- Often we need to collect collected values in a variable by calling a function and use that data into another function or another place in the script.

Example:
-a = call_function_that_gives_a_list(args1)
-b1 = call function_1( args1)
-b2 = call function_2( args2)

# One use of generator
def get_primes(number):
    while True:
        if is_prime(number):
            yield number
        number += 1

python commands keyword

-a.issubset(b)

script for jenkins build failure notification

#!/usr/bin/env python
# coding: utf-8
import re
import subprocess
import shlex
import os
import argparse, sys, collections

import urllib2
import json
import httplib
import time, datetime


# Just server address for all builds, otherwise only for given list of views
# place in jenkins
# get total number of failed builds
# run the job daily
# Create email groups
# Arguments: A. comma separated total number of failed builds - increasing order of builds, B. comma separated email addresses corresponding to the build-number groups




# usage: ./p4_create_user.py user_id manager_id group_id location_id : 4 required arguments


script_objective = '''
Purpose of the script:
Send email to different group of email addresses based on total number of failed builds
'''

# Message display when there are not enough arguments on command line
if len(sys.argv) < 2:
    print "Please run the script with argument -h for help"
    exit(0)

# argument parsing:
parser = argparse.ArgumentParser(formatter_class=argparse.RawTextHelpFormatter,
                                         add_help=True, description = '', epilog = script_objective)

requiredNamed = parser.add_argument_group('required named arguments')

requiredNamed.add_argument('-view_urls', nargs = '?', const = '', help = 'Comma separated Jenkins view(s)/server url', required = True)
requiredNamed.add_argument('-build_nums', nargs = '?', const = '', help = 'Comma separated build mumbers for mapping with email groups', required = True)
requiredNamed.add_argument('-emails', nargs = '?', const = '', help = 'Semicolon separated email groups for mapping with build groups. Emails in a group are comma separated', required = True)

args = parser.parse_args()

view_urls = args.view_urls
build_nums = args.build_nums # group = its number or more
emails = args.emails

email_domain = '@ruckuswireless.com'

email_from = 'releng-team' + email_domain

email_to = 'gopal.singh' + email_domain
email_cc = ''
#email_to = email_from
#email_cc = 'releng-team' + email_domain

email_bcc = ''
subject = 'Build failure notification'


email_msg = '''

-Jenkins build failed

'''

jenkins_server = 'http://jenkins.video54.local'

# Jenkins class
INFO         = 'api/json'
SCRIPT_OBJECTIVE = '''
Purpose of the script: Detects totals builds, failed builds, and automation failures.
'''

class JenkinsException(Exception): pass

class Jenkins(object):
    def __init__(self, url, username=None, password=None):
        server_split = (self.fix_server_url(url)).split('/')
self.server = server_split[0] + '//' + server_split[2] + '/'
self.auth = None

    def fix_server_url(self, urls): # urls may be comma separated server, view, job, or build urls
url = urls.split(',')[0]
if url[-1] != '/':
   url = url + '/'
return url

    def fix_urls(self, urls): # urls may be comma separated server, view, job, or build urls
url_str = ''
for url in urls.split(','):
   if url[-1] != '/':
url_str += url + '/,'
   else:
url_str += url + ','

return url_str.rstrip(',')

    def get_jenkins_server_url(self): # extract server url from list of comma separated urls
        server_url = (self.server).split('')      
        return server_url
   
    def jenkins_open(self, req): # req = HTTP request using urllib2
try:
   if self.auth:
req.add_header('Authorization', self.auth)
   return urllib2.urlopen(req).read()
except urllib2.HTTPError, e:
   # Jenkins's funky authentication means its highly impossible to distinguish errors.
   if e.code in [401, 403, 500]:
raise JenkinsException('Error in request. Possibly authentication failed [%s]'%(e.code))

    def get_info(self, url = None): # get_info gets api/json value for the server url (if server url is provided as jenkinsurl)
if url is None:
   url = self.server
try:
   return json.loads(self.jenkins_open(urllib2.Request(url + INFO)))
except urllib2.HTTPError:
   raise JenkinsException("Error communicating with server[%s]"%url)
except httplib.BadStatusLine:
   raise JenkinsException("Error communicating with server[%s]"%url)
except ValueError:
   raise JenkinsException("Could not parse JSON info for server[%s]"%url)
except:
   raise JenkinsException("Possibly wrong url[%s]"%url)

    @staticmethod
    def valid_view(info_str): # checks if the given url is a view url and has associated jobs
if 'description' in info_str and 'jobs' in info_str and (len(info_str['jobs']) > 0):
   return True
else:
   return False

    @staticmethod
    def valid_job(info_str): # checks if the given url is a job url
if 'builds' in info_str and (len(info_str['builds']) > 0):
   return True
else:
   return False

    @staticmethod
    def valid_build(info_str): # checks if the given url is a view url and has associated jobs
if 'number' in info_str:
   return True
else:
   return False

   
    def get_consecutive_failed_builds_in_job(self, job_url, max_builds_count=None):
jenkins_info = self.get_info(job_url)
builds_list = []
        try:
   first_build = jenkins_info['firstBuild']['number']
except:
   print 'No valid build found: for: ' + job_url
   return 0, job_url
last_build = jenkins_info['lastBuild']['number']
        build_count = 0
for build_num in reversed(range(first_build, last_build + 1)): # range is reversed to start from the latest build
   try:
                build_url = job_url + str(build_num) + '/'
                jenkins_info = self.get_info(url=build_url)
if jenkins_info['result'] == 'SUCCESS': break
if jenkins_info['result'] == 'FAILURE':
   builds_list.append(build_url)                              
                    build_count += 1
   if max_builds_count is not None and build_count >= max_builds_count:
break
   except: continue
return build_count, builds_list

    def get_consecutive_failed_builds_in_views(self, urls_list, max_builds_count=None): # the list of view urls should be comma separated string
        total_failed_builds = []      
list_urls = self.fix_urls(urls_list).split(',')
for url in list_urls:
   try:          
jenkins_info = self.get_info(url)
   except:  
print 'Not a valid view: ' + url
continue
   if self.valid_view(jenkins_info):
failed_builds = []
for job in jenkins_info['jobs']:
                    num, urls = self.get_consecutive_failed_builds_in_job(job['url'], max_builds_count)
                    if num > 0:  
failed_builds.append([job['url'], num])
   print 'Processing JOB: ' + job['url'] + ' ... Failed Builds: ' + str(num)
       total_failed_builds.append({url: failed_builds})  
   else: continue # continue to process next url if the current one is not a valid view url  
return total_failed_builds      

def update_email_data(build_data, build_nums, view_urls, emails):
    email_data = []  
    for x in build_data:
        job_data = []                
        for y in x.values()[0]: # x.values()[0] => list of job and corresponding failed builds, i.e.: [[u'http://jenkins.video54.local/job/ML_DAILY_SCG_AUTO_INIT/', 2]]        
            view_email_groups = select_view_email_groups(x.keys()[0], view_urls, emails) # x.keys()[0] => view_url          
            view_email_groups = fix_builds_email_group(build_nums, view_email_groups)          
            email_group = select_email_group(build_nums, view_email_groups, y[1]) # y[1] => number of failed builds for the job y[0]              
            job_data.append(y + [email_group])
email_data.append({x.keys()[0]:job_data})
    return email_data  
               
def runcmd(cmd):
    cmd =  shlex.split(cmd)
    try:
proc = subprocess.Popen(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
out, error = proc.communicate()
return out + error
    except:
        msg = 'Invalid Command: ' + str(cmd)
print msg
return msg

def parse_buildnums_emails(build_nums, emails):
    list_buildnums = build_nums.split(',')
    a = [int(x) for x in list_buildnums]  
    list_emails = emails.split(':')
    pair = dict(zip(a, list_emails))
    return collections.OrderedDict(sorted(pair.items()))

def parse_views_emails(build_nums, emails):
    list_buildnums = build_nums.split(',')
    a = [int(x) for x in list_buildnums]  
    list_emails = emails.split(':')
    pair = dict(zip(a, list_emails))
    return collections.OrderedDict(sorted(pair.items()))

def select_email_group(build_nums, view_email_groups, failed_builds): # email group will be selected for if number of failed builds >= key
    #view_email_groups = fix_builds_email_group(build_nums, view_email_groups)  
    email_dict = parse_buildnums_emails(build_nums, view_email_groups)
    email_group = None  
    #email_group = email_dict.items()[0][1]
    for key, value in email_dict.iteritems():
        if failed_builds >= key:
   email_group = value
    return email_group


def fix_view_email_groups(view_urls, emails):
    views = view_urls.split(',')
    emails_group = emails.split('|')
    for num in range(len(views)):
        if num < len(emails_group): # use last provided emails group      
            if emails_group[num] == '': emails_group[num] = emails_group[num - 1]    
        else:    
       emails_group.append(emails_group[num - 1])
    return zip(views, emails_group)  

def fix_builds_email_group(build_nums, build_email_groups):
    build_group = build_nums.split(',')    
    email_group = build_email_groups.split(':')
    for num in range(len(build_group)):
        if num < len(email_group): # use last provided emails group      
            if email_group[num] == '': email_group[num] = email_group[num - 1]    
        else:    
       email_group.append(email_group[num - 1])
    return ':'.join(email_group)
       

def select_view_email_groups(view_url, view_urls, emails): # gives view corresponding email groups
    pair_list = fix_view_email_groups(view_urls, emails)  
    view_email_groups = ''  
    for x in pair_list:
        if x[0] == view_url:  
   view_email_groups = x[1]
    return view_email_groups      

def get_failed_builds(views_list, build_duration):
    pass

def verify_email_address(receivers):
    error_message = 'One or more email address is invalid'
    valid_emails = []
    invalid_emails = []
    for email_address in (''.join(receivers.split())).split(','): # Taken care off white spaces in the specified emails list
match = re.match('^[_a-z0-9-\.]+(\.[_a-z0-9-]+)*@[a-z0-9-]+(\.[a-z0-9-]+)*(\.[a-z]{2,4})$', email_address)
if match == None:
   invalid_emails += [email_address]
else:
   valid_emails += [email_address]
    if len(invalid_emails) > 0:
print(error_message)
raise ValueError(error_message)

    return valid_emails    

def send_email(email_from, email_to, email_subject, email_message, email_cc='', email_bcc=''):
    sendmail_location = runcmd('which sendmail').strip() # strip() used to trim line feed
    p = os.popen('%s -t' % sendmail_location, 'w')
    p.write('From: %s\n' % email_from)
    p.write('To: %s\n' % email_to)
    if email_cc is not '':
p.write('Cc: %s\n' % email_cc)
    if email_bcc is not '':
p.write('Bcc: %s\n' % email_bcc)
    p.write('Subject: %s\n' % email_subject)
    p.write('\n') # blank line separating headers from body
    p.write(email_message)
    status = p.close()
    if status is None: status = 'OK'
    print "Sendmail exit status: ", str(status)
    return status

def send_verified_email():
    global email_from, email_to, email_cc, email_bcc, email_msg, subject
    status = None  
    # send email  
    valid_emails_to = ','.join(verify_email_address(email_to)) # sendmail does not need list
    # Validate CC and BCC addresses
    if email_cc is not '':
        valid_emails_cc = ','.join(verify_email_address(email_cc))
    else:
        valid_emails_cc = ''
    if email_bcc is not '':    
        valid_emails_bcc = ','.join(verify_email_address(email_bcc))
    else:
        valid_emails_bcc = ''
    if len(valid_emails_to) > 0:
        send_email(email_from, valid_emails_to, subject, email_msg, email_cc=valid_emails_cc, email_bcc=valid_emails_bcc)
    else:
        print 'No valid email specified'
status = 'Error'

def complete_email_send():
    print '\n' # print line feed for cleaner nessage  
    status = None  
    status = get_failed_builds(views_list, build_duration)
    if status is None:
        status  = send_verified_email()
    return status    

def main():
    global build_nums, view_urls, emails, subject, email_msg
    jenkins = Jenkins('http://jenkins.video54.local/')    
    failed_job_data = jenkins.get_consecutive_failed_builds_in_views(view_urls)
    email_data = update_email_data(failed_job_data, build_nums, view_urls, emails)  
    print "Failed job and Email data: " + str(email_data)
    for x in email_data:
for y in x.values()[0]:
   if y[2] is not None:
email_to = y[2]
email_msg = str(y[1]) + ' continuous builds failed for the job: ' + y[0]
send_verified_email()
   else:
print 'No valid email to notify: ' + email_msg
if __name__ == '__main__':
    main()
   

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