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;
}
}
Instead of using HashMap:
if 1) numbers are non-negetive
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[(key-num)] 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
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 .... (x-m))
else:
x = (n*m)-x
return sum_of_probs(m....(x-m))
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 = n-len(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()
#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 = i-1
if carry == 1:
number.insert(0, 1)
return number
print add_one(number)
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
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 = count-1
move(direction, count, max_count, r, c, run_count+1)
else:
#change in direction
direction = (direction+1)%4
if (direction == SOUTH):
max_count = max_count-1
if (direction == NORTH):
max_count = max_count-1
count = max_count
move(direction, count, max_count, r, c, run_count)
move(EAST, n, n, 0, -1, 1)
print out
#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 = cols-1
steps_south = rows-1
steps_west = steps_east
steps_north = steps_south-1
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((cols-2) > 0 or (rows-2) >0):
movements.append(EAST)
gen_movements(rows-2, cols-2)
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]
## python code
#for longest subsequence with asending order
data = [3,5,8,9,3,-1,-2, -4,-5,-6]
# 0-index for size, 1-index 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
python code
#dictionary of file-id:Node where Node is { id, parent, children}
#then do a pre-order 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)
#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
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, size-1)
[x.append(first) for x in ss]
ss2 = subset(rest, size)
ss.extend(ss2)
return ss
Repsalinagray, Development Support Engineer at Atmel
Hi I am Salina Gray,I live in Texas and work as a Design Team Member. I am new to ...
Repkristinedavila9, Android Engineer at ABC TECH SUPPORT
I am Kristine Davila Professor and director at Clinical Psychology. Having experience of 6 years in my career. I have ...
Repkathyrnunez, Area Sales Manager at Advent
I am manager in a Star Bright Investment Group company. I like to solve puzzles for Has excellent problem-solving and ...
Repmartinskrull, Analyst at A9
Hi everyone, I am from new york,USA. I currently work in the Affiliate Marketing industry. I love all things ...
Reppaulaamontalvo, AT&T Customer service email at AMD
I am working as Human Resources Associates, and my duties are for obtaining, recording, and interpreting human resources information within ...
RepAmberBrook, Animator at A9
Hi everyone, Done my master of arts in specialized journalism.Also an member of society of professional journalists since 2015 ...
Repmarkemorgan007, Applications Developer at Big Fish
I am Mark From Fresno city in USA.I working as a tour guide and also help for make a ...
RepLucindaBriella, Accountant at Clean Power Research
Lucinda, I conduct the admissions process and promote school to prospective students and their guardians. I need a spell caster ...
RepAvikaEthan, Data Engineer at Adjetter Media Network Pvt Ltd.
Avika Ethan has five years of experience collecting physical and biological data in California streams and rivers. In the field ...
0 0 1 1
- bluesky October 17, 20120 0 1 1
1 1 1 0
How many groups does this have? is it one ?