Felipe Pina
BAN USERI have 18 years as web developer. I'm currently assigned as a full stack computer engineer. I have 18 years in web application development and infrastructure.
I have been worked in big companies as consultant and formal employee, and i entrepreneur in my own company too.
I have solid knowledge in OO, TDD, Java, GO, JavaScript, Angular. I am a certified cloud solutions architect from AWS. I already work with Agile Scrum methodology in various teams with different projects, gaining experience with different technologies
import groovy.transform.EqualsAndHashCode
/**
Given a set of n people, find the celebrity.
Celebrity is a person who:
1. Knows only himself and no one else
2. Every one else knows this person
You are given the following helper function:
bool knows(i, j);
Returns:
True: If i knows j
False: otherwise
I proposed the O(n2) algorithm at first but he wanted me to improve on it. He wanted an O(n) algorithm
Ex: A->B->C
A->C<-D
A->C means A knows C
C<-A means C is Known for A
C is celebrity
* Created by Felipe on 21/03/2015.
*/
class Celebrity {
static class Person {
private String name
List<Person> knows = new ArrayList<>()
List<Person> isknown = new ArrayList<>()
// the ideal would be a structure that was a list and set together
//private static Set<Person> friendsSet = new TreeSet<Person>([compare:{a,b-> b.knows.size() <=> a.knows.size() }] as Comparator)
private static Set<Person> friendsSet = new LinkedHashSet<Person>()
private static List<Person> friendsList = new ArrayList<>()
Person know(Person p) {
knows << p
p.isknown << this
addFriends(p)
addFriends(this)
p
}
Person isKnown(Person p) {
isknown << p
p.knows << this
addFriends(p)
addFriends(this)
p
}
private void addFriends(Person p) {
if (friendsSet.add( p )) {
friendsList.add( p )
}
}
boolean knows(i, j) {
if (i>=0 && j>=0 && i < friendsSet.size() && j < friendsList.get(i).knows.size()) {
friendsList.get(i).knows.get(j) != null
}
false
}
Person findCelebrity() {
// with java 7 using the TimSort Average case performance O(n log n)
//def cmp = [compare:{a,b-> b.knows.size() <=> a.knows.size() }] as Comparator
friendsSet = friendsSet.sort {a,b-> a.knows.size() <=> b.knows.size() }
friendsSet.find { Person p ->
// Every one else knows this person
(p.isknown.size() == friendsSet.size() -1) && (p.knows.size() == 0) //Knows only himself and no one else
}
}
}
static void main (String[] args) {
def personA = new Person(name: "a")
def personC = new Person(name: "c")
def a = personA
.know(new Person(name:"b"))
.know(personC)
.isKnown(new Person(name:"d"))
personA.know(personC)
println "Celebrity is Person ${personA.findCelebrity()?.name}"
}
}
using Groovy way and recursion
class ListOrderNumbersFromMatrix {
def static evaluate(matriz) {
def minQueue = null
def min = null
matriz.each() { Queue row ->
if (min == null)
min = row.peek()
if (row.peek() && row.peek() <= min)
minQueue = row;
}
println minQueue.poll();
if (!matriz.flatten().empty)
evaluate(matriz)
}
static void main(String[] args) {
def matriz = [
[20,40,80] as LinkedList,
[5,60,90] as LinkedList,
[45,50,55] as LinkedList
]
ListOrderNumbersFromMatrix.evaluate(matriz);
}
}
- Felipe Pina March 29, 2015