06/14/16

# Martinkysel.com is now HTTPS

I would like to give a quick shoutout to the folks at Let’s Encrypt that have done a great job at making the web a better place. Do you ask why I care about SSL protected web pages?

Because HTTPS:

• prevents possible intruders from tampering with the communications between this website and you, my fellow readers. Intruders include intentionally malicious attackers, and legitimate but intrusive companies, such as ISPs or hotels that inject ads into pages.
• prohibits intrusions. It is possible to exploit unprotected communications and to trick users into giving up sensitive information or installing malware, or to insert their own advertisements into website resources. For example, some third-parties inject advertisements into websites that potentially break user experiences and create security vulnerabilities. It is probably not my case, but the greater Encrypt the web initiative is a cause worth pursuing.
• protects resources that travel between this website and your browser. Images, cookies, scripts, HTML… they’re all exploitable. Intrusions can occur at any point in the network, including a user’s machine, a Wi-Fi hotspot, or a compromised ISP, just to name a few.

Would you give your PC to a complete stranger in Starbucks and leave? I would not and therefore I will not do the same to my page. I agree that reading some page on the web is different than giving someone access to your Facebook pictures. But is it really? How often do you open web pages over a insecure Wi-fi? Do you trust each and every wire you are connected over?

Letsencrypt is a free SSL certificate authority by the folks from Mozilla, Cisco, Akamai, Facebook and many others. If you own, manage or run a page, give them a try. Make the web a better place.

Without further ado I announce that martinkysel.com is now HTTPS.

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/30/15

Solving new challenges can be hard. The harder it is, the more rewarding a solution feels. Sometimes, solutions written by other people work as a miraculous food for thought that opens doors into concepts you never thought of before. I would like this blog to be more than a reference that you know to visit when you are on search for solutions that you can copy-paste into the appropriate test window. I first started it as a self reference to keep track of my learning. The user base grows with every day and I think that we can do something positive with it. Not only will it support our learning process, but it will create interesting networking opportunities as well. Continue reading

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

08/5/16

# HackerRank ‘Non-Divisible Subset’ Solution

##### Short Problem Definition:

Given a set S of n distinct integers, print the size of a maximal subset S’ of S where the sum of any 2 numbers in S’ are not evenly divisible by k.

Non-Divisible Subset

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

This is by all means not an easy task and is also reflected by the high failure ratio of the participants. For a sum of two numbers to be evenly divisible by k the following condition has to hold. If the remainder of N1%k == r then N2%k = k-r for N1+N2 % k == 0. Let us calculate the set of all numbers with a remainder of r and k-r and pick the larger set. If the remainder is half of k such as 2 % 4 = 2 or exactly k such as 4 % 4 = 0, just one number from each of these sets can be contained in S’.

##### Solution:
def solveSubset(S, k, n):
r = [0] * k

for value in S:
r[value%k] += 1

result = 0
for a in xrange(1, (k+1)//2):
result += max(r[a], r[k-a])
if k % 2 == 0 and r[k//2]:
result += 1
if r[0]:
result += 1
return result

n, k = map(int, raw_input().split())
S = map(int, raw_input().split())
print solveSubset(S, k, n)


use std::io;

fn get_numbers() -> Vec<u32> {
let mut line = String::new();
line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn calculate_nondivisible(a: Vec<u32>, n: usize, k: usize) -> u32 {
let mut result = 0;

let mut r = vec![0; k];
for val in a {
r[(val as usize)%k] += 1;
}

for idx in 1..(k+1)/2 {
result += std::cmp::max(r[idx as usize], r[(k-idx) as usize]);
}

if k % 2 == 0 && r[k/2] != 0 {
result += 1;
}
if r[0] != 0 {
result += 1;
}

result
}

fn main() {
let line = get_numbers();
let a = get_numbers();

println!("{}", calculate_nondivisible(a, line[0] as usize, line[1] as usize) );
}


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

08/4/16

# HackerRank ‘Flatland Space Station’ Solution

##### Short Problem Definition:

For each city, determine its distance to the nearest space station and print the maximum of these distances.

Flatland Space Station

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

This is a two pass algorithm. First, measure the distance to the last station on the left. And on the second pass measure the distance to the nearest station on the right. Pick the minimum of both values. Remember that the first and last position are not necessarily stations.

##### Solution:
use std::io;
use std::cmp;

fn get_numbers() -> Vec<u32> {
let mut line = String::new();
line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn find_distance(c: Vec<u32>, n: usize) -> u32 {
let mut solution = 0;
let mut distances = vec![n as u32; n];

// first pass
let mut last_seen = 0;
let mut seen_one = false;
for i in 0..n {
if c[i] == 1 {
seen_one = true;
last_seen = 0;
} else {
last_seen += 1;
}
if seen_one {
distances[i] = last_seen;
}
}

// second pass
let mut last_seen = 0;
let mut seen_one = false;
for i in (0..n).rev() {
if c[i] == 1 {
seen_one = true;
last_seen = 0;
} else {
last_seen += 1;
}
solution = cmp::max(solution,
match seen_one {
true => cmp::min(last_seen, distances[i]),
false => distances[i],
}
);
}

solution
}

fn main() {
let line = get_numbers();
let n = line[0] as usize;
let c = get_numbers();
let mut v = vec![0; n];
for station in c {
v[station as usize] = 1;
}
println!("{}", find_distance(v, n));
}


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

08/3/16

# HackerRank ‘Kangaroo’ Solution

##### Short Problem Definition:

There are two kangaroos on an x-axis ready to jump in the positive direction (i.e, toward positive infinity). The first kangaroo starts at location x1 and moves at a rate of v1 meters per jump. The second kangaroo starts at location x2 and moves at a rate of v2 meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they’ll ever land at the same location at the same time?

Kangaroo

##### Complexity:

time complexity is O(1)

space complexity is O(1)

##### Execution:

There is no need to simulate the movement. We can reason that the two kangaroos either meat at the smallest common multiply or never.

##### Solution:
use std::io;
fn get_numbers() -> Vec<u32> {
let mut line = String::new();
line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn main() {
let numbers = get_numbers();
let x1 = numbers[0];
let v1 = numbers[1];
let x2 = numbers[2];
let v2 = numbers[3];

if x1 == x2 && v1 == v2 {
println!("YES");
}
else if x1 == x2 && v1 > v2 {
println!("NO");
}
else if x1 <= x2 && v1 <= v2 {
println!("NO");
}
else {
if (x2 - x1) % (v1 - v2) == 0  {
println!("YES");
}
else {
println!("NO");
}
}
}


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

08/2/16

# HackerRank ‘Save the Prisoner!’ Solution

##### Short Problem Definition:

A jail has N prisoners, and each prisoner has a unique id number,S , ranging from 1 to N. There are M sweets that must be distributed to the prisoners. But wait—there’s a catch—the very last sweet S is poisoned! Can you find and print the ID number of the last prisoner to receive a sweet so he can be warned?

Save the Prisoner!

##### Complexity:

time complexity is O(1)

space complexity is O(1)

##### Execution:

This challenge is painlessly trivial.

##### Solution:
use std::io;

fn get_number() -> u32 {
let mut line = String::new();
line.trim().parse::<u32>().unwrap()
}

fn get_numbers() -> Vec<u32> {
let mut line = String::new();
line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn solve_prisoner(n: u32, m: u32, s: u32) -> u32 {
((s - 1 + m - 1 ) % n) +1
}

fn main() {
let t = get_number();
for _ in 0..t {
let line = get_numbers();
println!("{}", solve_prisoner(line[0], line[1], line[2]));
}
}


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

08/2/16

# HackerRank ‘Jumping on the Clouds’ Solution

##### Short Problem Definition:

Emma is playing a new mobile game involving clouds numbered from 1 to n. There are two types of clouds, ordinary clouds and thunderclouds. The game ends if Emma jumps onto a thundercloud, but if she reaches the last cloud, she wins the game!

Jumping on the Clouds

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

Theoretically your solution can depend on the fact that the win condition is guaranteed, but I don’t like such solutions. Here I present a semi-DP approach that keeps track of the optimal number of jumps it takes to reach each cloud.

##### Solution:
use std::io;
use std::cmp;

fn get_number() -> u32 {
let mut line = String::new();
line.trim().parse::<u32>().unwrap()
}

fn get_numbers() -> Vec<u32> {
let mut line = String::new();
line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn calculate_jumping(a: Vec<u32>, n: usize) -> u32{
let mut v = vec![100; n];
v[0] = 0;

for i in 1..n {
//println!("{} {} {:?}", i, a[i], v);
if a[i] == 1 {
continue;
}

if i == 1 {
v[i] = v[i-1] + 1;
} else {
v[i] = cmp::min(v[i-1], v[i-2]) + 1;
}
}

v[n-1]
}

fn main() {
let n = get_number() as usize;
let a = get_numbers();

println!("{}", calculate_jumping(a, n) );
}


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

08/1/16

# HackerRank ‘Jumping on the Clouds: Revisited’ Solution

##### Short Problem Definition:

Aerith is playing a cloud game! In this game, there are clouds numbered sequentially from 1 to n. Each cloud is either an ordinary cloud or a thundercloud. Given the values of n and k the configuration of the clouds, can you determine the final value of e after the game ends?

Jumping on the Clouds: Revisited

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

Simulate the game in a loop.

##### Solution:
#!/bin/python

def solveCloudRevisited(c, n, k):
pos = 0
cnt = 0

while cnt == 0 or pos != 0:
pos += k
pos %= n
if c[pos] == 0:
cnt += 1
else:
cnt += 3

return 100 - cnt

if __name__ == '__main__':
n,k = map(int,raw_input().strip().split(' '))
c = map(int,raw_input().strip().split(' '))
print solveCloudRevisited(c, n, k)


use std::io;

fn get_numbers() -&gt; Vec&lt;u32&gt; {
let mut line = String::new();
line.split_whitespace().map(|s| s.parse::&lt;u32&gt;().unwrap()).collect()
}

fn calculate_jumping(a: Vec&lt;u32&gt;, n: usize, k: usize) -&gt; u32 {
let mut e = 0;
let mut pos = 0;

while e == 0 || pos != 0 {
e += match a[pos] {
0 =&gt; 1,
1 =&gt; 3,
_ =&gt; panic!("invalid input"),
};

pos += k;
pos %= n;
}

100 - e
}

fn main() {
let line = get_numbers();
let (n, k) = (line[0], line[1]);
let a = get_numbers();
println!("{}", calculate_jumping(a, n as usize, k as usize) );
}


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

07/3/16

# HackerRank ‘Divisible Sum Pairs’ Solution

##### Short Problem Definition:

You are given an array of n integers and a positive integer, k. Find and print the number of (i,j) pairs where i < j and ai + aj is evenly divisible by k.

Divisible Sum Pairs

##### Complexity:

time complexity is O(N^2)

space complexity is O(1)

##### Execution:

Brute force search.

##### Solution:
n,k = raw_input().strip().split(' ')
n,k = [int(n),int(k)]
a = map(int,raw_input().strip().split(' '))
count=0
for i in xrange(len(a)):
for j in xrange(i+1,len(a)):
if (a[i]+a[j]) % k == 0:
count+=1

print count


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

06/24/16

# Demystifying Virtual Tables in C++ – Part 3 Virtual Tables

## Introduction

In the previous parts of the series we look at Trivial cases and Non-virtual inheritance. Now, it is time to look at the actual content of the series. I repeat the citation we are verifying here:

Whenever a class itself contains virtual functions or overrides virtual functions from a parent class the compiler builds a vtable for that class. This means that not all classes have a vtable created for them by the compiler. The vtable contains function pointers that point to the virtual functions in that class. There can only be one vtable per class, and all objects of the same class will share the same vtable. [1]

We have shown that classes without a virtual function indeed contain no virtual pointer and no virtual table is constructed. A virtual table is an array of function pointers although other data types are also possible. The layout is generally compiler-specific (or ABI-specific where multiple C++ compilers share an ABI) and somewhat stable. All the virtual function tables are in the memory associated with your process. In case of GDB all your virtual function tables are stored in read-only memory which protects it from unintentional overwrites. The functions themselves (their assembly instructions) are stored in the .text section of the elf binary.

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

06/22/16

# HackerRank ‘Lisas Workbook’ Solution

##### Short Problem Definition:

Lisa just got a new math workbook. A workbook contains exercise problems, grouped into chapters.

• …..

Lisa believes a problem to be special if its index (within a chapter) is the same as the page number where it’s located. Given the details for Lisa’s workbook, can you count its number of special problems?

Lisa’s Workbook

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

This brute force solution iterates over all pages in the final book keeping track of the page(offset) and chapter it is on. There can only be one special problem per page and therefore I check if there is any problem that would match the criteria.

##### Solution:
def findPages(N, K, P):
cnt = 0
offset = 1
for chapter in P:
pages = (chapter + K -1)/K
for idx in xrange(pages):
if offset >= (idx * K)+1 and offset <= min((idx+1)*K, chapter):
cnt += 1
offset += 1

return cnt

if __name__ == '__main__':
N, K = map(int, raw_input().split())
P = map(int, raw_input().split())
print findPages(N, K, P)


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

06/21/16

# HackerRank ‘Sherlock and The Beast’ Solution

##### Short Problem Definition:

Sherlock Holmes suspects his archenemy, Professor Moriarty, is once again plotting something diabolical. Sherlock’s companion, Dr. Watson, suggests Moriarty may be responsible for MI6’s recent issues with their supercomputer, The Beast.

Shortly after resolving to investigate, Sherlock receives a note from Moriarty boasting about infecting The Beastwith a virus; however, he also gives him a clue—a number, . Sherlock determines the key to removing the virus is to find the largest Decent Number having digits.

Sherlock and The Beast

##### Complexity:

time complexity is O(1)

space complexity is O(1)

##### Execution:

I am presenting two solutions. The naive brute force solution executes in O(N) and passes all the tests. Yet further optimisations and a runtime complexity of O(1) are possible.

When observing the possible output space we realise that there can only be 0, 5 or 10 threes in the output. If there would be 15 threes, it is better to use fives instead. The number of trailing threes can therefore be defined by K = 5*((2*N)%3). Let us plug some numbers into the equation:

• 1 -> 5*(2%3) = 10 -> INVALID
• 2 -> 5*(4%3) = 5 -> INVALID
• 3 -> 5*(3%3) = 0 -> 555
• 4 -> 5*(8%3) = 10 -> INVALID
• 5 -> 5*(10%3) = 5 -> 33-33-3
• 8 -> 5*(16%3) = 5 -> 555-33-33-3
• 10 -> 5*(20%3) = 10 -> 33-33-33-33-33
• 15 -> 5*(30%3) = 0 -> 555-555-555-555-555
##### Solution:
def sherlockBeast(N):
K = 5*((2*N)%3)
if K > N:
return -1
else:
return '5' * (N-K) + '3'*K

if __name__ == '__main__':
t = input()
for _ in xrange(t):
n = input()
print sherlockBeast(n)

def sherlockBeastNaive(N):
if (N < 3): return "-1" three_cnt = N//3 five_cnt = 0 while three_cnt >=0:
rem = N - three_cnt*3
if rem % 5 == 0:
five_cnt = rem/5
break
three_cnt -= 1

if three_cnt <= 0 and five_cnt == 0:
return "-1"

return "555"*three_cnt + "33333"*five_cnt

if __name__ == '__main__':
t = input()
for _ in xrange(t):
n = input()
print sherlockBeastNaive(n)


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.