Booking.com Interview Question
Developer Program EngineersCountry: Netherlands
Interview Type: Phone Interview
import UIKit
var names = ["Luis", "Hector", "Selena", "Emmanuel", "Amish"]
var firsts = Dictionary<String, String>()
var lasts = Dictionary<String, String>()
var output = Array<String>()
for name in names {
var key = (name as NSString).substringFromIndex(name.utf16Count-1)
lasts[key] = name
key = (name as NSString).substringToIndex(1).lowercaseString
firsts[key] = name
}
// Pivot
for (key, val) in firsts {
if lasts[key] == nil {
output.append(val)
}
}
while output.count < names.count {
var last = output.last!
var key = (last as NSString).substringFromIndex(last.utf16Count-1)
output.append(firsts[key]!)
}
output
public class SortArray {
public static void main(String[] args) {
String[] input = new String[] { "Luis", "Hector", "Selena", "Emmanuel", "Amish", "Pie", "Rat"};
String[] result = new String[input.length];
Set<Character> set = new HashSet<Character>();
Map<Character, String> map = new HashMap<Character, String>();
// All start char in set.
for (String s : input) {
char[] ch = s.toLowerCase().toCharArray();
set.add(ch[0]);
map.put(ch[ch.length - 1], s);
}
String lastWord = null;
// Trying to find a string whose end char doesn't start a new string.So
// that should be last.
for (String s : input) {
char[] ch = s.toLowerCase().toCharArray();
if (!set.contains(ch[ch.length - 1])) {
lastWord = s;
break;
}
}
result[result.length - 1] = lastWord;
for (int i = result.length - 2; i >= 0; i--) {
result[i] = map.get(result[i + 1].toLowerCase().toCharArray()[0]);
}
// Output
for (String s : result) {
System.out.println(s);
}
}
}
string[] dizi1 = new string[] { "emmanuel", "selena", "hector", "luis", "amish" };
string[] dizi2 = new string[5];
dizi2[0] = dizi1[0];
char harf;
int sayac = 1;
string ilk = dizi1[0];
harf = ilk[ilk.Length - 1];
for (int i = 0; i < 4; i++)
{
foreach (string item in dizi1)
{
if (item[0] == harf)
{
dizi2[sayac] = item;
harf = dizi2[sayac][dizi2[sayac].Length - 1];
sayac++;
}
}
}
foreach (string item in dizi2)
{
Console.WriteLine(item);
}
Console.Read();
void main(void)
{
char input [] [50] = {
"Luis",
"Hector",
"Selena",
"Emmanuel",
"Amish",
};
int pos = 0,i = 0;
int first = 0;
int last;
int input_row = strlen(input)/strlen(int []);
int pos1[input_row]
flag = input[0][last];
//let the first element as sentinel and build the latter string
first = 0; // indext of first character
for( j = 0; j < input_row; )
{
last = strlen(input[j])-1; // indext of last character
if(input[j][first] == flag)
{
pos1[i++] = pos++;
flag = input[j][last];
j = 0;
continue;
}
else
{
j++;
}
}
//let the first element as sentinel and build the former string
int pos2[input_row-i];
if( j >= input_row )
{
flag = input[0][first];
pos = 0;
k = input_row-i-1;
for(j = 0; j < input_row; )
{
last = strlen(input[j])-1; // indext of last character
if(input[j][last] == flag)
{
pos2[k--] = pos--;
flag = input[j][first];
j = 0;
continue;
}
else
{
j++;
}
}
}
//output of the result
for(i = 0; i < input_row-i;i++)
{
printf("%s\n",pos2[i]);
}
for(i = 0; i < input_row; i++)
{
printf("%s\n",pos1[i]);
}
}
Output:
result:Emmanuel
result:Luis
result:Selena
result:Amish
result:Hector
I'm using two maps to identify begin chars and end chars and a list to hold the result:
May I consider this algorithm as O(n) running time?
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <cctype>
#include <map>
#include <utility>
int main() {
std::vector<std::string> vec{
"Luis", "Hector", "Selena", "Emmanuel", "Amish"};
std::map<char, std::string> map_first_char;
std::map<char, std::string> map_last_char;
std::list<std::string> result;
for(auto s: vec) {
map_first_char.insert(
std::pair<char, std::string>(tolower(s[0]), s));
map_last_char.insert(
std::pair<char, std::string>(s[s.length() - 1], s));
}
for(auto s: vec) {
if(result.empty()) {
result.push_back(s);
continue;
}
std::string& front = result.front();
std::string& back = result.back();
char begin = tolower(front[0]);
char end = back[back.length() - 1];
std::map<char, std::string>::iterator it;
if((it = map_last_char.find(begin)) != map_last_char.end()) {
result.push_front(it->second);
map_last_char.erase(it);
}
if((it = map_first_char.find(end)) != map_first_char.end()) {
result.push_back(it->second);
map_first_char.erase(it);
}
}
for(auto it = result.begin(); it != result.end(); ++it) {
std::cout << "result:" << *it << std::endl;
}
return 0;
}
#!/usr/bin/perl -w
use strict;
use Data::Dumper;
my @booking = ('Luis', 'Hector', 'Selena', 'Emmanuel', 'Amish');
my @sorted;
my $first = shift @booking;
my $total = int ( ($#booking/2 ) * ($#booking + 1)); # to track the index by summing all the index
#and substracting it from the used index
push @sorted, $first;
my $cnt = 0;
my $last = lc(chop($first));
for (my $i = 0 ; $i <= $#booking; $i++ ){
for(my $j=0; $j <=$#booking; $j++ ) {
if ($last eq (lc (substr ($booking[$j], 0, 1)))){
$cnt = $cnt + $j;
my $tmp = $booking[$j];
push (@sorted, $booking[$j]);
$last = lc chop($tmp);
}
}
}
my $index = $total - $cnt ;
unshift (@sorted, $booking[$index]);
print Dumper(@sorted);
NSMutableArray* initial = [[NSMutableArray alloc] initWithObjects:@"Luis",@"Hector",@"Selena",@"Emmanuel",@"Amish", nil];
NSMutableArray* output = [[NSMutableArray alloc] init];
NSMutableArray* outputstr = [[NSMutableArray alloc] init];
int beginindex = 0;
for(int i = 0; i<initial.count; i++)
{
NSString* testwith = [initial objectAtIndex:i];
NSString* lastch0 = [[testwith substringFromIndex:testwith.length-1] lowercaseString];
NSString* firstch0 = [[testwith substringToIndex:1] lowercaseString];
bool found0 = false;
bool found1 = false;
for(int j = 0; j<initial.count; j++)
{
if(j == i)
continue;
NSString* testagainst = [initial objectAtIndex:j];
NSString* firstch1 = [[testagainst substringToIndex:1] lowercaseString];
NSString* lastch1 = [[testagainst substringFromIndex:testagainst.length-1] lowercaseString];
if([firstch1 isEqualToString:lastch0])
{
[output insertObject:[NSNumber numberWithInt:j] atIndex:i];
found0 = true;
}
if([firstch0 isEqualToString:lastch1])
{
found1 = true;
}
}
if(!found0)
[output insertObject:[NSNumber numberWithInt:-1] atIndex:i];
if(!found1)
beginindex = i;
}
int count = 0;
while (count<initial.count)
{
NSString* currentStr = [initial objectAtIndex:beginindex];
beginindex = [[output objectAtIndex:beginindex] integerValue];
count++;
[outputstr addObject:currentStr];
}
public static void main(String[] args)
{
boolean sorted = false;
String [] s = new String[] {"Luis","Hector","Selena","Emmanuel","Amish"};
List<String> data = new ArrayList();
LinkedList<String> list = new LinkedList();
for(String b : s)
data.add(b);
list.add(s[0]);
data.remove(0);
while(data.size()>0)
{
String first = beforeD(list.get(0),data);
if(first != null)
list.addFirst(first);
String after = afterD(list.get(list.size()-1),data);
if(after != null)
list.addLast(after);
}
System.out.println(list);
}
public static String beforeD(String s, List<String> l)
{
String t = s.toLowerCase().substring(0,1);
for(int i =0 ; i < l.size();i++)
{
String buff = l.get(i);
if(buff.toLowerCase().substring(buff.length()-1).equals(t))
{
l.remove(i);
return buff;
}
}
return null;
}
public static String afterD(String s, List<String> l)
{
String t = s.toLowerCase().substring(s.length()-1);
for(int i =0 ; i < l.size();i++)
{
String buff = l.get(i);
if(buff.toLowerCase().substring(0,1).equals(t))
{
l.remove(i);
return buff;
}
}
return null;
}
import java.util.ArrayList;
import java.util.List;
public class Main {
private static String[] names = {"Luis", "Hector", "Selena", "Emmanuel", "Amish"};
public static void main(String[] args) {
List<String> linkedNames = new ArrayList<String>();
String firstName = null;
for (int i=0; i<names.length; i++) {
boolean isFirstName = true;
String currentName = names[i];
char prev = currentName.charAt(0);
for (int j=0; j<names.length; j++) {
if (i==j) continue;
String name = names[j];
char end = name.charAt(name.length()-1);
if (Character.toLowerCase(prev) == Character.toLowerCase(end)) {
isFirstName = false;
break;
}
}
if (isFirstName) {
firstName = currentName;
break;
}
}
// if a loop
if (firstName == null) {
firstName = names[0];
}
linkedNames.add(firstName);
String next = firstName;
while(next != null) {
char endChar = next.charAt(next.length()-1);
next = null;
for (String name:names) {
if (linkedNames.contains(name)) {
continue;
}
if (Character.toLowerCase(endChar) == Character.toLowerCase(name.charAt(0))) {
linkedNames.add(name);
next = name;
break;
}
}
}
System.out.println("[");
for (String name : linkedNames) {
System.out.println(name);
}
System.out.println("]");
}
}
#!/bin/python
names = ['Luis', 'Hector', 'Selena', 'Emmanuel', 'Amish']
firsts = {}
lasts = {}
for i in names:
lasts[i[-1]] = i;
for i in names:
firsts[i[0].lower()] = i;
start = list(set(firsts.keys()) - set(lasts.keys()))[0];
i = 0;
while i < len(names):
if i == 0:
print firsts[start];
last = firsts[start][-1];
i = i + 1;
continue
print firsts[last];
last = firssts[last][-1];
i = i + 1;
public List<String> orderWords(List<String> words) {
if(words == null || words.size() <= 1) {
return words;
}
Map<Character, String> begin = new HashMap<Character, String>();
Map<Character, String> end = new HashMap<Character, String>();
for(String word: words) {
begin.put(word.toLowerCase().charAt(0), word);
end.put(word.toLowerCase().charAt(word.length() -1), word);
}
//Find out first word
String beginWord = null;
for(Entry<Character, String> beginEntry : begin.entrySet()) {
if(!end.containsKey(beginEntry.getKey())) {
beginWord = beginEntry.getValue();
break;
}
}
if(beginWord == null) {
// it has circle, randomly pick one
beginWord = new ArrayList<String>(begin.values()).get(0);
}
List<String> orderList = new ArrayList<String>();
String currentWord = beginWord;
orderList.add(currentWord);
words.remove(beginWord);
while(!words.isEmpty()) {
String nextWord = begin.get(currentWord.charAt(currentWord.length() - 1));
if(nextWord == null) {
break;
}
orderList.add(nextWord);
currentWord = nextWord;
words.remove(currentWord);
}
if(!words.isEmpty()) {
return new ArrayList<String>();
}
return orderList;
}
#!/usr/bin/perl -w
use strict;
use Data::Dumper;
&run();
sub run{
my @unsorted_array = ('Luis','Hector','Selena','Emmannual','Amish','Brave','Matlab');
my (%hash_first, %hash_last, @sorted_arr, @first_letter, @back_letter);
foreach my $word(@unsorted_array){
my ($f_key) = $word =~ m!^(.)!;
$hash_first{uc($f_key)} = $word;
push @first_letter, uc($f_key);
my ($l_key) = $word =~ m!(.)$!;
$hash_last{$word} = uc($l_key);
}
print Dumper \%hash_first; ## extract first letter and save as key value pair
print Dumper \%hash_last; ## extract last letter and save as key value pair
my $f_key = ''; ## front letter as key
## find the front letter which is not matching with any of the last letter
foreach my $key (@first_letter){
$f_key = $key if (join('',@back_letter) !~ m!$key!);
}
## loop through all the first letters of each word
for(my $index=0; $index <= $#first_letter; $index++){
## loop through each word
foreach my $word (keys %hash_last){
## if the value of first letter as key is equal to word then add it to array
if ($hash_first{$f_key} eq $word){
push @sorted_arr, $hash_first{$f_key};
($f_key) = $hash_last{$word}; ## word last letter will now be the first letter of any other word
last;
}
}
}
print "\n\nUnsorted array::: @unsorted_array\n\n\nsorted array::: @sorted_arr\n\n";
}
var arri=['Luis','Hector','Selena','Emmanuel','Amish']
var hashobj={}
var hashval={}
var final_array=[]
var j=-1;
for (var i = 0; i < arri.length; i++) {
hashobj[arri[i].substring(0, 1).toLowerCase()]=arri[i];
hashval[arri[i].substring(arri[i].length-1,arri[i].length).toLowerCase()]=arri[i].substring(0,1).toLowerCase()
}
for(prop in hashval){
if (hashobj[prop]===undefined){
form_final_array()
}
}
function form_final_array(){
j++
if (j===arri.length){
return
}
final_array.unshift(hashobj[hashval[prop]])
prop=hashval[prop];
return form_final_array()
}
console.log(final_array)
var arri=['Luis','Hector','Selena','Emmanuel','Amish']
var hashobj={}
var hashval={}
var final_array=[]
var j=-1;
for (var i = 0; i < arri.length; i++) {
hashobj[arri[i].substring(0, 1).toLowerCase()]=arri[i];
hashval[arri[i].substring(arri[i].length-1,arri[i].length).toLowerCase()]=arri[i].substring(0,1).toLowerCase()
}
for(prop in hashval){
if (hashobj[prop]===undefined){
form_final_array()
}
}
function form_final_array(){
j++
if (j===arri.length){
return
}
final_array.unshift(hashobj[hashval[prop]])
prop=hashval[prop];
return form_final_array()
}
console.log(final_array)
var arri=['Luis','Hector','Selena','Emmanuel','Amish']
var hashobj={}
var hashval={}
var final_array=[]
var j=-1;
for (var i = 0; i < arri.length; i++) {
hashobj[arri[i].substring(0, 1).toLowerCase()]=arri[i];
hashval[arri[i].substring(arri[i].length-1,arri[i].length).toLowerCase()]=arri[i].substring(0,1).toLowerCase()
}
for(prop in hashval){
if (hashobj[prop]===undefined){
form_final_array()
}
}
function form_final_array(){
j++
if (j===arri.length){
return
}
final_array.unshift(hashobj[hashval[prop]])
prop=hashval[prop];
return form_final_array()
}
console.log(final_array)
var arri=['Luis','Hector','Selena','Emmanuel','Amish']
var hashobj={}
var hashval={}
var final_array=[]
var j=-1;
for (var i = 0; i < arri.length; i++) {
hashobj[arri[i].substring(0, 1).toLowerCase()]=arri[i];
hashval[arri[i].substring(arri[i].length-1,arri[i].length).toLowerCase()]=arri[i].substring(0,1).toLowerCase()
}
for(prop in hashval){
if (hashobj[prop]===undefined){
form_final_array()
}
}
function form_final_array(){
j++
if (j===arri.length){
return
}
final_array.unshift(hashobj[hashval[prop]])
prop=hashval[prop];
return form_final_array()
}
console.log(final_array)
}}}
here is my code in javascript
var arri=['Luis','Hector','Selena','Emmanuel','Amish']
var hashobj={}
var hashval={}
var final_array=[]
var j=-1;
for (var i = 0; i < arri.length; i++) {
hashobj[arri[i].substring(0, 1).toLowerCase()]=arri[i];
hashval[arri[i].substring(arri[i].length-1,arri[i].length).toLowerCase()]=arri[i].substring(0,1).toLowerCase()
}
for(prop in hashval){
if (hashobj[prop]===undefined){
form_final_array()
}
}
function form_final_array(){
j++
if (j===arri.length){
return
}
final_array.unshift(hashobj[hashval[prop]])
prop=hashval[prop];
return form_final_array()
}
console.log(final_array)
var arri=['Luis','Hector','Selena','Emmanuel','Amish']
var hashobj={}
var hashval={}
var final_array=[]
var j=-1;
for (var i = 0; i < arri.length; i++) {
hashobj[arri[i].substring(0, 1).toLowerCase()]=arri[i];
hashval[arri[i].substring(arri[i].length-1,arri[i].length).toLowerCase()]=arri[i].substring(0,1).toLowerCase()
}
for(prop in hashval){
if (hashobj[prop]===undefined){
form_final_array()
}
}
function form_final_array(){
j++
if (j===arri.length){
return
}
final_array.unshift(hashobj[hashval[prop]])
prop=hashval[prop];
return form_final_array()
}
console.log(final_array)
var arri=['Luis','Hector','Selena','Emmanuel','Amish']
var hashobj={}
var hashval={}
var final_array=[]
var j=-1;
for (var i = 0; i < arri.length; i++) {
hashobj[arri[i].substring(0, 1).toLowerCase()]=arri[i];
hashval[arri[i].substring(arri[i].length-1,arri[i].length).toLowerCase()]=arri[i].substring(0,1).toLowerCase()
}
for(prop in hashval){
if (hashobj[prop]===undefined){
form_final_array()
}
}
function form_final_array(){
j++
if (j===arri.length){
return
}
final_array.unshift(hashobj[hashval[prop]])
prop=hashval[prop];
return form_final_array()
}
console.log(final_array)
def sort(input):
firstLetter = {}
lastLetter = {}
first = None
output = []
for value in input:
firstLetter[value[0]] = value
lastLetter[value[-1]] = value
for value in input:
if value[0] in lastLetter:
continue
else:
first = value
break;
if not first:
first = input[0]
output.append(first)
del firstLetter[first[0]]
next = first[-1]
for value in firstLetter:
output.append(firstLetter[next])
next = firstLetter[next][-1]
return output
print sort(['RAHUK', 'KALLI', 'LUIS', 'HECTOR', 'SELENA', 'EMMANUEL', 'ANISH'])
print sort(['RAHUK', 'KALLI', 'LUIS', 'HECTOR', 'SELENA', 'ANISH'])
def sort(input):
firstLetter = {}
lastLetter = {}
first = None
output = []
for value in input:
firstLetter[value[0]] = value
lastLetter[value[-1]] = value
for value in input:
if value[0] in lastLetter:
continue
else:
first = value
break;
if not first:
first = input[0]
output.append(first)
del firstLetter[first[0]]
next = first[-1]
for value in firstLetter:
output.append(firstLetter[next])
next = firstLetter[next][-1]
return output
print sort(['RAHUK', 'KALLI', 'LUIS', 'HECTOR', 'SELENA', 'EMMANUEL', 'ANISH'])
print sort(['RAHUK', 'KALLI', 'LUIS', 'HECTOR', 'SELENA', 'ANISH'])
def sort(input):
firstLetter = {}
lastLetter = {}
first = None
output = []
for value in input:
firstLetter[value[0]] = value
lastLetter[value[-1]] = value
for value in input:
if value[0] in lastLetter:
continue
else:
first = value
break;
if not first:
first = input[0]
output.append(first)
del firstLetter[first[0]]
next = first[-1]
for value in firstLetter:
output.append(firstLetter[next])
next = firstLetter[next][-1]
return output
print sort(['RAHUK', 'KALLI', 'LUIS', 'HECTOR', 'SELENA', 'EMMANUEL', 'ANISH'])
print sort(['RAHUK', 'KALLI', 'LUIS', 'HECTOR', 'SELENA', 'ANISH'])
List<String> names = new ArrayList<>();
names.add("Luis");
names.add("Hector");
names.add("Selena");
names.add("Emmanuel");
names.add("Amish");
System.out.println();
List<String> namesOrdered = new LinkedList<>();
for (String name : names) {
String nameFirstChar = name.substring(0, 1).toLowerCase();
boolean added = false;
for (int i = 0; i < namesOrdered.size(); i++) {
String ordered = namesOrdered.get(i);
String orderedFirstChar = ordered.substring(0,1).toLowerCase();
if (name.toLowerCase().endsWith(orderedFirstChar)) {
namesOrdered.add(i, name);
added = true;
break;
} else if (ordered.toLowerCase().endsWith(nameFirstChar)) {
namesOrdered.add(i + 1, name);
added = true;
break;
}
}
if (!added) {
namesOrdered.add(name);
}
}
System.out.println();
System.out.println();
for (String name : namesOrdered) {
System.out.print(name + " ");
}
System.out.println();
1) Introduce a HashMap with (char, count). For each word, add last char to the Hashmap.
2) Now, again loop through the given words, and find the starting letter that is not present in Hashmap. This is the word we are going to start from.
3) Form another HashMap with (Starting word, list of words).
4) Now, start printing the words from 2). Then take the last word and search in HashMap in 3) and get the word from the list and print it. Follow the same for the rest.
bool preorder(vector<unordered_multiset<string>> starts_with, vector<unordered_multiset<string>> ends_with, list<string>& answer, size_t goal_size)
{
const auto& first_name = answer.front();
const auto& last_name = answer.back();
auto start_char = first_name[0];
auto end_char = last_name[last_name.size() - 1];
if (!starts_with[end_char - 'a'].empty())
{
for (auto next_name : starts_with[end_char - 'a'])
{
auto starts_with_copy = starts_with;
auto ends_with_copy = ends_with;
answer.push_back(next_name);
if (answer.size() == goal_size)
return true;
starts_with_copy[next_name[0] - 'a'].erase(next_name);
ends_with_copy[next_name[next_name.size() - 1] - 'a'].erase(next_name);
if (preorder(starts_with_copy, ends_with_copy, answer, goal_size))
return true;
answer.pop_back();
}
}
else
{
if (!ends_with[start_char - 'a'].empty())
for (auto next_name : ends_with[start_char - 'a'])
{
auto starts_with_copy = starts_with;
auto ends_with_copy = ends_with;
answer.push_front(next_name);
if (answer.size() == goal_size)
return true;
starts_with_copy[next_name[0] - 'a'].erase(next_name);
ends_with_copy[next_name[next_name.size() - 1] - 'a'].erase(next_name);
if (preorder(starts_with_copy, ends_with_copy, answer, goal_size))
return true;
answer.pop_front();
}
else
return false;
}
return false;
}
void sort_names()
{
size_t count; cin >> count;
vector<string> names(count); for (size_t i = 0; i < count; ++i) cin >> names[i];
names.erase(
remove_if(begin(names), end(names), [](const string& name) { return name.empty(); }),
cend(names)
);
for_each(begin(names), end(names), [](string& name) { transform(cbegin(name), cend(name), begin(name), tolower); });
vector<unordered_multiset<string>> starts_with(26);
vector<unordered_multiset<string>> ends_with(26);
for (const auto& name : names)
{
auto start_char = name[0];
auto end_char = name[name.size() - 1];
starts_with[start_char - 'a'].insert(name);
ends_with[end_char - 'a'].insert(name);
}
for (const auto& name : names)
{
list<string> answer{ name };
auto starts_with_copy = starts_with;
auto ends_with_copy = ends_with;
starts_with_copy[name[0] - 'a'].erase(name);
ends_with_copy[name[name.size() - 1] - 'a'].erase(name);
if (preorder(starts_with_copy, ends_with_copy, answer, names.size()))
{
for (const auto& item : answer)
cout << item << ' ';
cout << endl;
}
}
}
bool preorder(vector<unordered_multiset<string>> starts_with, vector<unordered_multiset<string>> ends_with, list<string>& answer, size_t goal_size)
{
const auto& first_name = answer.front();
const auto& last_name = answer.back();
auto start_char = first_name[0];
auto end_char = last_name[last_name.size() - 1];
if (!starts_with[end_char - 'a'].empty())
{
for (auto next_name : starts_with[end_char - 'a'])
{
auto starts_with_copy = starts_with;
auto ends_with_copy = ends_with;
answer.push_back(next_name);
if (answer.size() == goal_size)
return true;
starts_with_copy[next_name[0] - 'a'].erase(next_name);
ends_with_copy[next_name[next_name.size() - 1] - 'a'].erase(next_name);
if (preorder(starts_with_copy, ends_with_copy, answer, goal_size))
return true;
answer.pop_back();
}
}
else
{
if (!ends_with[start_char - 'a'].empty())
for (auto next_name : ends_with[start_char - 'a'])
{
auto starts_with_copy = starts_with;
auto ends_with_copy = ends_with;
answer.push_front(next_name);
if (answer.size() == goal_size)
return true;
starts_with_copy[next_name[0] - 'a'].erase(next_name);
ends_with_copy[next_name[next_name.size() - 1] - 'a'].erase(next_name);
if (preorder(starts_with_copy, ends_with_copy, answer, goal_size))
return true;
answer.pop_front();
}
else
return false;
}
return false;
}
void sort_names()
{
size_t count; cin >> count;
vector<string> names(count); for (size_t i = 0; i < count; ++i) cin >> names[i];
names.erase(
remove_if(begin(names), end(names), [](const string& name) { return name.empty(); }),
cend(names)
);
for_each(begin(names), end(names), [](string& name) { transform(cbegin(name), cend(name), begin(name), tolower); });
vector<unordered_multiset<string>> starts_with(26);
vector<unordered_multiset<string>> ends_with(26);
for (const auto& name : names)
{
auto start_char = name[0];
auto end_char = name[name.size() - 1];
starts_with[start_char - 'a'].insert(name);
ends_with[end_char - 'a'].insert(name);
}
for (const auto& name : names)
{
list<string> answer{ name };
auto starts_with_copy = starts_with;
auto ends_with_copy = ends_with;
starts_with_copy[name[0] - 'a'].erase(name);
ends_with_copy[name[name.size() - 1] - 'a'].erase(name);
if (preorder(starts_with_copy, ends_with_copy, answer, names.size()))
{
for (const auto& item : answer)
cout << item << ' ';
cout << endl;
}
}
}
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Main {
public static void main(String[] args) {
String input[] = new String[] { "Dave" , "Evan" , "Nash" , "Bernad"};
List<String> output = new ArrayList<>(input.length);
Map<Character, String> startMap = Stream.of(input)
.collect(Collectors.toMap(e -> e.toLowerCase().charAt(0), e -> e));
Map<Character, String> endMap = Stream.of(input)
.collect(Collectors.toMap(e -> e.toLowerCase().charAt(e.length()-1), e -> e));
output.add(startMap.entrySet().stream()
.filter(x -> endMap.keySet().contains(x.getKey()) == false)
.findFirst().get().getValue());
int i = 1;
for(i=1; i< input.length; i++) {
output.add(startMap.get(output.get(i-1).charAt(output.get(i-1).length()-1)));
}
System.out.println(output);
}
}
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Main {
public static void main(String[] args) {
String input[] = new String[] { "Dave" , "Evan" , "Nash" , "Bernad"};
List<String> output = new ArrayList<>(input.length);
Map<Character, String> startMap = Stream.of(input)
.collect(Collectors.toMap(e -> e.toLowerCase().charAt(0), e -> e));
Map<Character, String> endMap = Stream.of(input)
.collect(Collectors.toMap(e -> e.toLowerCase().charAt(e.length()-1), e -> e));
output.add(startMap.entrySet().stream()
.filter(x -> endMap.keySet().contains(x.getKey()) == false)
.findFirst().get().getValue());
int i = 1;
for(i=1; i< input.length; i++) {
output.add(startMap.get(output.get(i-1).charAt(output.get(i-1).length()-1)));
}
System.out.println(output);
}
}
/**
* @author Omid Ghiasi Tarzi
*/
public static List<String> chainList(List<String> list){
Set<Character> starts=new HashSet<>();
Set<Character> ends=new HashSet<>();
Map<Character,String> map=new HashMap<>();
for(String str:list){
starts.add(str.charAt(0));
ends.add(str.charAt(str.length()-1));
map.put(str.charAt(0),str);
}
starts.removeAll(ends);
char c=starts.toArray(new Character[0])[0];
List<String> result=new ArrayList<>();
while(map.get(c)!=null){
String str=map.get(c);
result.add(str);
c=str.charAt(str.length()-1);
}
return result;
}
input = [
"Luis",
"Hector",
"Selena",
"Emmanuel",
"Amish",
]
from collections import defaultdict
start_with = defaultdict(list)
end_with = defaultdict(list)
for word in input:
start_with[word[0].lower()].append(word)
end_with[word[-1]].append(word)
res = []
cycle = set()
visited= set()
def dfs(word):
if word in cycle:
return False
if word in visited:
return True
cycle.add(word)
last_char = word[-1]
for nei in start_with[last_char]:
if not dfs(nei):
return False
cycle.remove(word)
visited.add(word)
res.append(word)
return True
for word in input:
if word not in visited:
dfs(word)
print(res[::-1])
# # output:
# [
# Emmanuel
# Luis
# Selena
# Amish
# Hector
# ]
Java solution using DFS (Depth First Search). In graph node is an index in initial array. One node is connected to some other one if the last letter equals to first letter of the second word. First we build a graph, and then run DFS starting from each node. If at some point we visit all nodes while traversing the graph, it means we found the solution.
- megido December 08, 2015