Python script to move records from CSV File to a Dynamodb table

Write a python script to move records from a csv file to a dynamo db table. 

Solution

# Script to write csv records into dynamo db table.

# For help on prerequisites and running this script, read this blog.

from __future__ import print_function # Python 2/3 compatibility

from __future__ import division #Python 2/3 compatiblity for integer division

import argparse

import boto3

import csv

import time

# command line arguments

parser = argparse.ArgumentParser(description='Write CSV records to dynamo db table. CSV Header must map to dynamo table field names.')

parser.add_argument('csvFile', help='Path to csv file location')

parser.add_argument('table', help='Dynamo db table name')

parser.add_argument('writeRate', default=5, type=int, nargs='?', help='Number of records to write in table per second (default:5)')

parser.add_argument('delimiter', default='|', nargs='?', help='Delimiter for csv records (default=|)')

parser.add_argument('region', default='us-west-2', nargs='?', help='Dynamo db region name (default=us-west-2')

args = parser.parse_args()

print(args)

# dynamodb and table initialization

endpointUrl = "https://dynamodb." + args.region + ".amazonaws.com"

dynamodb = boto3.resource('dynamodb', region_name=args.region, endpoint_url=endpointUrl)

table = dynamodb.Table(args.table)

# write records to dynamo db

with open(args.csvFile) as csv_file:

    tokens = csv.reader(csv_file, delimiter=args.delimiter)

    # read first line in file which contains dynamo db field names

    header = tokens.next();

    # read second line in file which contains dynamo db field data types

    headerFormat = tokens.next();

    # rest of file contain new records

    for token in tokens:

       item = {}

       for i,val in enumerate(token):

         if val:

           key = header[i]

           if headerFormat[i]=='int':

             val = int(val)

           item[key] = val

       print(item)

       table.put_item(Item = item)

       time.sleep(1/args.writeRate) # to accomodate max write provisioned capacity for table

Preconditions

• Install boto3 python package on your box
• Set up AWS credentials
• Dynamodb field data type is either int or string. New data type will require improvements in code.
• CSV first two lines are always header and header data type.

Script Arguments

Mandatory

• csvFile - Path to csv file location
• table - Dynamo db table name

Optional

• writeRate - Number of records to write in table per second (default:5)
• delimiter - Delimiter for csv records (default=|)
• region - Dynamo db region name (default=us-west-2)

Sample Input

field1|field2|field3|field4|field5

string|string|string|string|int

GZ6MHDMM0IB1IR0P|A27LZ9R92G1SJ|OPEN||1

Sample Run

• python csvToDynamodb.py abc.csv ABC
• python csvToDynamodb.py abc.csv ABC 50 | us-east-1

Future improvements

• Add conversion log for other dynamo db data types. If for concerned table Dynamo db fields have format other than string or int, we will have to convert CSV string value to dynamo db field type required.

Help

• python csvToDynamodb.py -h

TopCoder Dynamic Programming Bad Neighbours Donation Collection Problem

TopCoder Dynamic Programming Bad Neighbours Donation Collection Problem

Problem 

The old song declares "Go ahead and hate your neighbor", and the residents of Onetinville have taken those words to heart. Every resident hates his next-door neighbors on both sides. Nobody is willing to live farther away from the town's well than his neighbors, so the town has been arranged in a big circle around the well. Unfortunately, the town's well is in disrepair and needs to be restored. You have been hired to collect donations for the Save Our Well fund.

Each of the town's residents is willing to donate a certain amount, as specified in the int[] donations, which is listed in clockwise order around the well. However, nobody is willing to contribute to a fund to which his neighbor has also contributed. Next-door neighbors are always listed consecutively in donations, except that the first and last entries in donations are also for next-door neighbors. You must calculate and return the maximum amount of donations that can be collected.

Constraints
- donations contains between 2 and 40 elements, inclusive.
- Each element in donations is between 1 and 1000, inclusive.

Examples
   
 { 10, 3, 2, 5, 7, 8 }
Returns: 19
The maximum donation is 19, achieved by 10+2+7. It would be better to take 10+5+8 except that the 10 and 8 donations are from neighbors.
   
{ 11, 15 }
Returns: 15
   
{ 7, 7, 7, 7, 7, 7, 7 }

Returns: 21

Solution

int badNeighbours(int *a, int size) {

 if(size == 2) {

   int sum = findMax(a[0], a[1]);

   return sum;

 }

 int i, j;

 int *s = (int *)malloc(sizeof(int)*size);

 int *b = (int *)malloc(sizeof(int)*size);

 s[0]=a[0];

 s[1]=a[1];

 b[0]=1;

 b[1]=0;

 for(i=2;i<size;i++) {

    s[i]=0;

    b[i]=0;

 }

 for(i=2;i<size;i++) {

    for(j=0;j<i-1;j++) {

       if(s[i]<s[j]+a[i]) {

        s[i]=s[j]+a[i];

        b[i]=b[j];

       }

    }

 }

 if(b[size-1]==0) {

   return s[size-1];

 } else {

   int min = findMin(a[0], a[size-1]);

   int sum = findMax(s[size-2], s[size-1]-min);

   return sum;

 }

 return 0;

}

TopCoder Dynamic Programming Longest Zig Zag Sequence Problem

Dynamic Programming - Longest Zig Zag Sequence

Problem 

ZigZag - 2003 TCCC Semifinals 3

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Constraints
- sequence contains between 1 and 50 elements, inclusive.
- Each element of sequence is between 1 and 1000, inclusive.

Examples
   
{ 1, 7, 4, 9, 2, 5 }
Returns: 6
The entire sequence is a zig-zag sequence.
   
{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }
Returns: 7
There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8.

Solution

int findLongZigZag(int *a, int size) {

  if(size<=2) {

        printf("%d\n", size);

        return;

  }

  // to track alternate positive and negative sequence.

  int *b = (int *)malloc(sizeof(int)*size);

  // to track length of longest sequence till ith index. 

  int *s = (int *)malloc(sizeof(int)*size));

  int i,j;

  s[0]=1;

  b[0]=a[0];

  b[1]=a[1]-a[0];

  s[1]=2;

  for(i=2;i<size;i++) {

        s[i]=2;

        b[i]=0;

  }

  for(i=2;i<size;i++) {

     for(j=1;j<i;j++) {

        if(b[j]<0) {

           if(a[i] > a[j] && s[i]<=s[j]+1) {

                s[i]=s[j]+1;

                b[i]=a[i]-a[j];

           }

        } else {

          if(a[i] < a[j] && s[i]<=s[j]+1) {

                s[i]=s[j]+1;

                b[i]=a[i]-a[j];

          }

        }

     }

     if(b[i]==0) {

        b[i]=a[i]-a[i-1];

     }

  }

  return s[size-1];

}

Goldbach's conjecture

Goldbach's Conjecture

 

Problem

Goldbach's conjecture : Every even integer greater than 2 can be expressed as the sum of two primes.
Write a function which takes a number as input, verify if is an even number greater than 2 and also print atleast one pair of prime numbers.

Approach

1) Assume the two numbers are equal to half of the given number.

2) Choose two numbers as half of numbers.

3) increment first by one and decrement second by 1.

4) if the current pair is prime no print it.

5) Else start from step 3 again.

Solution

#include<stdio.h>

int isPrime(int no) {

 int i;

 if (no <= 1) return 0; // 0 and 1 are not prime.

 for (i=2; i*i <= no; i++) {

     if(no % i == 0) return 0;

 }

 return 1;

}

int main()

{

 int a, b, c, i;

 printf("Enter the even no to find out two prime no whose sum is no - ");

 scanf("%d", &a);

 if (a%2 != 0) {

    printf("Please enter even no only\n");

    return 0;

 }

 b = a/2-1;

 c = a/2+1;

 while (1) {

   if (isPrime(b) && isPrime(c)) {

        printf("b %d and c %d are the primes you were looking for.\n", b, c);

        break;

   }

   else {

        b--;

        c++;

   }

 }

}

Arithmetic With Precision

                                Arithmetic With Precision

Have you ever used C/C++. Tried to perform simple arithmetic operations on real numbers of considerably longer length. If yes, then you must have known that none of these languages provide you the answers with perfect precision. Even the same may be the case with java. So, here is the task. Just take two numbers (of course real), try to perform any arithmetic operation (+,-,/,*) and then try to simply print it on the console, but with infinite precision.


    987432189374581923.123276453
+ 199283777167383992.383477628
____________________________________________

Take care, answer should look like one of operands, without any exponential notation.

Stack with min operation in O(1)

Stack with push, pop and min,  all in O(1)

 

Problem

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element so far? Push, pop and min should all operate in O(1) time.

Trivia

This is a pretty standard question now. The question has been asked in many interviews in past and will be asked in many interviews in future.

Approach

There can be many ways to approach this problem:
1) One way is to introduce another variable min in data structure 'Node' which keep tracks of min element so far in the stack.

So the new data structure for stack would look something like:
struct Stack_Node {
   int val;
   int min;
   struct Node *next;
}  Node;

Now when you push the element into stack, its local min variable is calculated and updated.
new->min = Minimum(value, top->min);
And while doing the pop operation, the min is already up to date in stack so far. So one can simply delete the top node.

There is just one problem with this approach - if it is a large stack, we will waste a lot of space keeping track of min element. So if space isn't the issue, like it isn't now a days :), this method is perfectly fine. Otherwise we can do better too.

2) The other way to solve a problem is using additional stack which keep tracks of min so far.

So the new push and pop operations for stack would be like:
stack<int> s2;
push {
    if (value <= s2.top())  s2.push(value)
    s1.push(value)
}
pop {
    value = s1.pop()
    if(value=s2.top()) s2.pop()
}
min {
    if(!s2.isEmpty()) s2.top()
}

Time Complexity

Push - O(1)
Pop - O(1)
Min - O(1)


There is a similar question in which you have to design a stack which, in addition to push and pop, also has a function max which returns the maximum element so far.

Tower Of Hanoi - Non-recursive Approach

Tower Of Hanoi

                                                             --  shaikzakir3149@gmail.com

Hello all, this is my first post. Hope you find it useful ...


Implement non-recursive Towers of Hanoi. Given the number n of disks as input, maintain appropriate pegs/rods to simulate the movement of the disks among the three pegs: Source, Auxilary & Destination.
Output the sequence of moves of the disks. Following is an example of the output expected by your program.

No. of disks: 3
Sequence of Moves
1. Source → Destination
2. Source → Auxilary
3. Destination → Auxilary
4. Source → Destination
5. Auxilary → Source
6. Auxilary → Destination
7. Source → Destination

Note: Remember that towers of hanoi can be solved in (2^n - 1) at the best for given n disks.

Algorithm:

While size of Destination is less not equal to n
do
{
If num of disks is even then

       Make legal move between Source and Auxilary
       Make the legal move between pegs Source and Destination

else

        Make the legal move between pegs Source and Destination  
        Make the legal move between pegs Source and Auxilary

endif

Make legal move between pegs Auxilary and Destination



}
end While


Note that a legal move is one which abides by the rules of the puzzle. Only a smaller disk can be moved onto a larger disk.

Running Time Complexity :

 The runtime complexity of this algorithm is O((2^n - 1)/3) which is equivalent to O(2^n). Clearly the stack operations (push, pop and peek) have a runtime equal to O(1).

The code is given in Java.

Source Code :

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
//package tower.of.hanoi;
import java.io.*;
import java.util.Stack;
import java.util.EmptyStackException;
/**
 *
 * @author Shaik
 */
public class TowerOfHanoi {

    
    public static int legalMove(Stack A, Stack B)
    {
        int a,b;
        try {
        a = Integer.parseInt(A.peek().toString());
        }
        catch(EmptyStackException e){
        a = 0;    
        }
        try {
            b = Integer.parseInt(B.peek().toString());
        }
        catch(EmptyStackException e){
        b = 0;    
        }
        if(a==b) return 0;
        if(a == 0)             // If peg A is empty, then pop from B and push the disk onto A
    {
        A.push(B.pop());
            return 2;           // Return 2 as move occurred from B to A
    }
        else if(b == 0)        // If peg B is empty, then pop from A and push the disk onto B
        {
        B.push(A.pop());
        return 1;           // Return 1 since move occurred from A to B
    }
        
        if(a<b)
        {
        B.push(A.pop());
        return 1;               // Return 1 since move occurred from A to B
        }
        else if(a > b)            // value of top disk of peg A is greater than the value of topmost disk of peg B
        {
        A.push(B.pop());
        return 2;               // Return 2 since move occurred from B to A
        }
        return -1;
    }
        
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int stepNumber = 0;
        int status = 0;
        try {
        Stack Source = new Stack();
        Stack Auxilary = new Stack();
        Stack Destination = new Stack();
        
        System.out.println("Enter the number of disks : ");
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine());
        if(n<=0)
        {
            System.out.println("Sorry wrong input, negative numbers not allowed.");
            System.exit(1);
        }
        for(int i=n; i>0; i--)
            Source.push(i);
        int m = n%2;
        do {
            if(m==1)
            {
                if((status = legalMove(Source,Destination)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Destination");
                else if (status == 2)
                    System.out.println((++stepNumber) + ". Destination --> Source");
                
                if((status = legalMove(Source,Auxilary)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Auxilary");
                else if(status == 2)
                    System.out.println((++stepNumber) + ". Auxilary --> Source");
                else 
                    break;
            }
            
            else
            {
                if((status = legalMove(Source,Auxilary)) == 1)  
                    System.out.println((++stepNumber) + ". Source --> Auxilary");
                else if (status == 2)
                    System.out.println((++stepNumber) + ". Auxilary --> Source");
                
                if((status = legalMove(Source,Destination)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Destination");
                else if(status == 2)
                    System.out.println((++stepNumber) + ". Destination --> Source");
                
            }
            
            if((status = legalMove(Auxilary,Destination)) == 1) 
                System.out.println((++stepNumber) + ". Auxilary --> Destination");
            else if(status == 2)
                System.out.println((++stepNumber) + ". Destination --> Auxilary");
        }while(Destination.size()!=n);
        System.out.println("X-----------------------X");
        }         

        catch (Exception e){
        }
        }
    }

Ibibo Interview Questions (Tradus.in, goIbibo.com, payU.in)

Interview Questions for Software Engineer Profile

Ibibo Web Pvt Ltd - May 2012

round1

1. Linked list contain alphabets.find if it is palindrome or not
2. Array of unsorted no. is given, find triplets which satisfy a² + b² = c².
3. Duplicate a linked list.

round2

1. Sorted array cyclically right-shifted unknown no of times. find an element in it.
2. Stack which does push, pop and findMin in O(1).

round3

1. Given 2 arrays unsorted, insert common elements in third array in O(n).
2. Given 2 arrays unsorted, insert unique elements in third array in O(n).
3. Fill n*n matrix clockwise starting from center. Write efficient code.
ex.   7   8  9
        6   1  2
        5   4  3
4. Print 2D matrix in spiral order.

round4

1. Lots of technical questions from Resume.
2. Given three arrays A,B,C containing unsorted numbers.  Find three numbers a, b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum.

Interviewstreet Meeting Schedules - Amazon India Coding Challenge : Solution C++

Interviewstreet Amazon India Coding Challenge 

Meeting Schedules Problem

Problem

Given M busy-time slots of N people, You need to print all the available time slots when all the N people can schedule a meeting for a duration of K minutes.

Event time will be of form HH MM ( where 0 <= HH <= 23 and 0 <= MM <= 59 ), K will be in the form minutes
An event time slot is of form [Start Time, End Time ) . Which means it inclusive at start time but doesn’t include the end time.

Sample Input:                                                       Sample Output:

5 120                                                                    00 00 09 00

16 00 17 00                                                          17 00 20 45

10 30 15 30

20 45 22 15

10 00 13 25

09 00 11 00

Algorithm

1) Create a bit array busy[ ] of size equal to total no of minutes per day which is 24*60=1440.
             busy[i] = 1 mean minute is busy because of some meeting going on.
             busy[i] = 0 mean minute is free and another meeting can be organized.
             i represent that minute from the day, ex: For 10:30, i would be 10*60+30 = 630
2) For each input interval, fill busy[i] array on that interval.
3) After each input interval is processed, start scanning busy[ ] array from 0 to 1440 for k continuous
    free minutes.And whenever you find the interval print the interval. There may be more than 1 such
    interval.

Have a better approach in mind, please share it for our readers in comments section.

Solution

//All test cases passed

#include<iostream>
using namespace std;

void print(int i) {
  if(i==0 || i==1440) cout << "00 00";
  else {
     int j = i/60;
     int k = i%60;
     if(j<10) cout << "0" << j << " ";
     else cout << j << " ";
     if(k<10) cout << "0" << k ;
     else cout << k ;
  }
}

int main()
{

int m,k;
cin>>m>>k;
int busy[1440];
int a1,a2,b1,b2;
int i;
for(i=0;i<1440;i++)
    busy[i]=0;
   
while(m--) {
   
    cin>>a1>>a2>>b1>>b2;
    int start = a1*60+a2;
    int end = b1*60+b2;
    for(i=start;i<end;i++)
        busy[i]=1;

}
int j;
i=0;
while(i<1440) {
    j=i;
    if(busy[j] == 1) {
        i++;
        continue;
    }
    while(j < 1440 && busy[++j]!=1);
    if((j-i)>=k) {
       //cout << i << " " << j << endl;
       print(i);
       cout << " ";
       print(j);
       cout << endl;
    }
    i=j;
}

//cin >> i;
   
}

Time Complexity

Busy array is scanned twice, so O(n)

InterviewStreet Find Strings Solution C++

InterviewStreet Find Strings Solution C++

Problem

https://www.interviewstreet.com/challenges/dashboard/#problem/4efa210eb70ac

Algorithm

Declare a set<string> which will contain strings lexicographically ordered.
For each input string
     generate all its substrings one by one and add them  to set
For each query
     move pointer to require index in set and return the string
     if query no is greater than size of set, print Invalid.

 

 Solution

If you know better solution please post it in comments section.
//4 out of 7 test cases passed
#include<iostream>
#include<set>
#include<string>
typedef unsigned long long int big;
using namespace std;

int main() {

int n,i;
cin >> n;

set<string> s;
set<string>::iterator it;

string s1,temp;
for(i=0;i<n;i++) {   
    cin >> s1;
    int len = s1.length();
    int j,k;
    for(j=0;j<len;j++)
        for(k=len-j;k>0;k--) {
            temp = s1.substr(j,k);
            s.insert(temp);
        }                      
}

it=s.begin();
int curr = 1;
int q;
cin >> q;
big k, len;
len = s.size();
cout << len;
for(i=0;i<q;i++) {
    cin >> k;
    if(k>len) {
       cout << "INVALID\n";
       continue;
    }
    if(curr+(len/2) < k) {
      it = s.end();
      it--;
      curr = len;
    }
    if(curr-(len/2) > k) {
       it = s.begin();
       curr = 1;
    }
    if(k>curr) {
        int j= k-curr;
        while(j) { it++; j--; }
        cout << *it << endl;
        curr = k;
    }
    else if(k<curr) {
        int j=curr-k;
        while(j) { it--; j--;}
        cout << *it << endl;
        curr = k;
    }
    else cout << *it << endl;
}

cin >> i;
}