bluesky
BAN USERbasically using array of struct pointer.
//pseudo code
Struct Node {
int begin; //end can be inferrred due to fixed size and contiguous.
}
Struct*[] arr; //array of struct pointers.
int size = 10; //fixed given size
void insert(int begin) {
if(arr[begin] == null && arr[begin+size] == null) {
Struct s = new Struct();
s.begin = begin;
for(int i = 0; i <size; i++) {
arr[i+begin] = s;
}
}else {
raise "Cannot be inserted"
}
}
Struct* find(int v) {
return arr[v]
}
void delete(v) { //assuming v is the begin
for(int i=0; i < size; i++) {
arr[i+v] = null;
}
}

bluesky
October 16, 2012 Instead of using HashMap:
if 1) numbers are nonnegetive
2) a known upper limit
We can use an int[] and solve the problem.
Initially int[] is zeros. When we meet a number(num) use that as index and flag it to '1' and check if there is another arr[(keynum)] and check if that is also flagged as 1. If so, then we have a pair.
It is of order O(n).
If the content of excel sheet, i.e number of cells used, doesn't increase or decrease..then..to minimize the amount of buffer (proportional to number of used cells)
we can use one extra array for keeping the index of each row's beginning (index into the one dimensional buffer)
then a[i][j] = data[arr[i]+j]
Approach is to collect the words which start with same 'first 3 characters' into separate files. The size of these files will be in the range of MB's. Number of files = 26*26*26(assuming only case insensitive and only alphabets)
Then sort and collect top N words from each of the files and finalize on top N words.
Kind of 'Divide and Conquer' approach.
Worst case: if each word occurs only once!!.
#python code
s = [2,1, 3, 5, 7,6]
even_index = 0
odd_index = 1
while(len(s) > even_index and len(s) > odd_index):
if s[even_index]%2 == 0:
even_index += 2
else:
if(s[odd_index]%2 == 0):
temp = s[even_index]
s[even_index] = s[odd_index]
s[odd_index] = temp
even_index += 2
odd_index += 2
print s

bluesky
October 03, 2012 How about using graph traversal approach?. (BFS, DFS)
Visit the next node only if its value less than the current. (like water flowing down). Here 'next' means any of neighbouring node(east, west, north, south)
If there are multiple lower neighbouring nodes choose the one with greatest descent (water fall).
If the traversal stops, that means we have reached lowest element in that neighbourhood.
@kira: few corrections:
if x < (n*m/2):
return 1  sum_of_probs(m .... (xm))
else:
x = (n*m)x
return sum_of_probs(m....(xm))
Since the problem asked for probability of win, We need to sum of all probs for every sum greater than x. i.e equal to 1 minus sum of probs less than x.
Request corrections.
#python
import random
n = 100
blacklist = [2,3,59,99]
max_rand = nlen(blacklist)
blackhash = {}
for i, b in enumerate(blacklist):
blackhash[b] = i+1
def gen_random():
r = random.randint(1, max_rand)
if (blackhash.has_key(r)):
r = max_rand + blackhash[r]
return r
print gen_random()

bluesky
September 28, 2012 #something in python
number = [1,9,9,9]
def add_one(number):
i = len(number)1
carry = 1
while(carry and i >= 0) :
n = number[i]
if n == 9:
number[i] = 0
else:
number[i] = n + carry
carry = 0
i = i1
if carry == 1:
number.insert(0, 1)
return number
print add_one(number)

bluesky
September 28, 2012 the problem states that search should be of order O(1).
Using Hashtable might cost O(n).
I feel, along with doubly linked list of nodes, an array of nodes should be used. the insert 'value' can be index and value is the 'node' in the doubly linked list.
The doubly linked list will help in maintaining 'Recent' and 'Oldest' node.
This will result in insert, delete, search ops in the O(1)
numbs = [1,2,4,5,1,0]
min = numbs[0]
max = numbs[0]
missing = 1
for n in numbs[1:]:
if (n <= 0):
continue
if (n < min):
if(n+1 < min):
missing = n+1
else:
min = n
if (n > max and missing == 1):
if(max+1 < n):
missing = max+1
max = n
if missing == 1:
missing = max+1
print missing

bluesky
September 28, 2012 n = 4
EAST, SOUTH, WEST, NORTH = range(4)
STEP = [(0, 1), (1, 0), (0, 1), (1, 0)]
out = [[0 for x in range(n)] for x in range(n)]
def move(direction, count, max_count, r, c, run_count):
if(max_count < 0):
return
if (run_count > n*n):
return
if (count > 0):
delta_r, delta_c = STEP[direction]
r = r+delta_r
c = c+delta_c
out[r][c] = run_count
count = count1
move(direction, count, max_count, r, c, run_count+1)
else:
#change in direction
direction = (direction+1)%4
if (direction == SOUTH):
max_count = max_count1
if (direction == NORTH):
max_count = max_count1
count = max_count
move(direction, count, max_count, r, c, run_count)
move(EAST, n, n, 0, 1, 1)
print out

bluesky
September 28, 2012 #python code
#works for any sized matrixes
EAST, WEST, NORTH, SOUTH = range(4)
step = [(+1,0), (1,0), (0,1), (0, +1)]
data = [[1,2,3], [8,9,4], [7,6,5]]
#data = [[1,2,3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 8]]
rows = len(data)
cols = len(data[0])
movements = []
def gen_movements(rows, cols):
steps_east = cols1
steps_south = rows1
steps_west = steps_east
steps_north = steps_south1
movements.extend([EAST for x in range(steps_east)])
movements.extend([SOUTH for x in range(steps_south)])
movements.extend([WEST for x in range(steps_west)])
movements.extend([NORTH for x in range(steps_north)])
if((cols2) > 0 or (rows2) >0):
movements.append(EAST)
gen_movements(rows2, cols2)
gen_movements(rows, cols)
print movements
r = 0
c = 0
print data[r][c]
for i in movements:
delta_c, delta_r = step[i]
r = r+delta_r
c = c+delta_c
print data[r][c]

bluesky
September 26, 2012 ## python code
#for longest subsequence with asending order
data = [3,5,8,9,3,1,2, 4,5,6]
# 0index for size, 1index for index in the array where subsequence starts
best = [1, 1]
curr = [1, 1]
#data.reverse() #uncomment for descending
#start from the end
for i in range(len(data)2, 1, 1):
#if less then add to the current state
if data[i] <= data[curr[1]]:
curr[0] = curr[0]+1
curr[1] = i
else:
#if the run breaks..then compare with the current best
if(best[0] < curr[0]):
best[0] = curr[0]
best[1] = curr[1]
#resetting the current run
curr[0] = 1
curr[1] = i
if(best[0] > curr[0]):
print best
else:
print curr

bluesky
September 26, 2012 python code
#dictionary of fileid:Node where Node is { id, parent, children}
#then do a preorder traversal on the root Node (id = '0')
class Node:
def __init__(self, id, name=None, parent=None):
self.id = id
self.name = name
self.parent = parent
self.children = []
def __str__(self):
return "%s:%s" % (self.name, self.id)
f = open("input.txt", 'r')
files = {}
def preorder(n, tab_count):
print "%s %s" % (" "*tab_count, n)
for child in n.children:
preorder(child, tab_count+1)
for l in f.readlines():
id, pid, name = map(lambda x: x.strip(), l.split(","))
if(files.has_key(id)):
n = files[id]
n.name = name
n.parent = pid
else:
n = Node(id, name, pid)
files[id] = n
if (not files.has_key(pid)):
files[pid] = Node(pid)
files[pid].children.append(n)
roots = filter(lambda x: x.parent is None, files.values())
map(lambda root: preorder(root, 1), roots)

bluesky
September 26, 2012 #code in python
bus_timings = [[100, 15],[110, 10], [120, 3], [122, 5], [150, 25], [150, 20], [152, 30]]
platforms = []
for arrival in bus_timings:
found_slot = False
for p in platforms:
last_bus = p[1]
if(last_bus[0] + last_bus[1] < arrival[0]):
p.append(arrival)
found_slot = True
break
if not found_slot:
new_platform = []
new_platform.append(arrival)
platforms.append(new_platform)
for p in platforms:
print p

bluesky
September 24, 2012 def subset(numbers, size):
if (size == 0):
raise Exception("size is 0")
if size == 1:
return [[x] for x in numbers]
if len(numbers) < size:
raise Exception("Invalid: len(%s) < size(%d)" % (str(numbers), size))
if len(numbers) == size:
return [numbers]
first = numbers[0]
rest = numbers[1:]
ss = subset(rest, size1)
[x.append(first) for x in ss]
ss2 = subset(rest, size)
ss.extend(ss2)
return ss

bluesky
September 22, 2012 Open Chat in New Window
0 0 1 1
 bluesky October 17, 20120 0 1 1
1 1 1 0
How many groups does this have? is it one ?