Transform A,B,…AA,AB,.. to 1,2,..27,28,..

NOTE: Below code is Python 3.

base = 26
def transform(row):
res = []
for field in [tmp.strip() for tmp in row.split(',')]:
ival = 0
power = 0
for c in field[::-1]:
ival += pow(base,power)*(ord(c)-ord('A')+1)
power += 1
res.append(ival)
return res

print(transform("A, B, Z, AA, AB, AAA"))



Output:

[1, 2, 26, 27, 28, 703]


Brain Teaser

T : Number of test cases

M: value of M

N: Number of strings

For each string, ascii value of each character of the string is raised to M and multiplied together. For each test case the sum of above values  is ODD or EVEN

Input:

1

10    2

ac ab

Output:

ODD

TIP: Challenge lies in finding the solution without doing all the mathematical operations mentioned in the question. (yes, also called optimizing..!)

Solution:

#!/usr/bin/python

T = int(raw_input())
while T>0:
T = T - 1
tmp = raw_input()
M = int(tmp.split()[0])
K = int(tmp.split()[1])
tmp = raw_input()
final_odd = False
for s in tmp.split():
odd = None
for i in s:
if ord(i)%2==0:        # the power is even
odd = False
else:                # the power is odd
if odd==None:            # if odd is True, odd*odd=odd
odd = True
# odd + odd = even
# odd + even = odd
# even + even = even
if final_odd != odd:
final_odd = True
else:
final_odd = False
if final_odd:
print "ODD"
else:
print "EVEN"

Count Inversions in an array

This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.

Tips:

If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Eg: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

You can get working program from here

Input files :     Input1            Input2

Answer for input1 :

Answer for input 2: 25

Algorithm Puzzles

Q:

You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative, or zero. You want to decide whether or not there is an index i such that A[i] = i. Design the fastest algorithm that you can for solving this problem.

Ans.

Input: Array a[0..n-1] of n elements

pseudocode:

func(a, i, k) {
j = (i + k)/2
if      (a[j]==j)    return True
else if (a[j]<j)   =”” return=”” <span=”” class=”hiddenSpellError” pre=”return ” data-mce-bogus=”1″>func(a, j, k)       // since all numbers are distinct, a[x]
else                 return func(a, i, j)        // since all numbers are distinct, a[x]>x for all x > j
}