Booking.com Interview Question for Developer Program Engineers


Country: Netherlands
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
4
of 4 vote

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.

import java.util.*;
import java.io.*;

public class Solution {
    int num;
    int total; // total number of words
    boolean found;
    boolean[] used; // used[i] - if we used i-th word
    List<Integer> result = new ArrayList<>(); // list of resulted strings
    Map<Integer, List<Integer>> g = new HashMap<>(); // n -> list of connected nodes

    public static void main(String[] args) {
        new Solution().solve();
    }

    public void solve() {
        PrintWriter out = new PrintWriter(System.out);
        String[] words = {"Luis", "Hector", "Selena", "Emmanuel", "Amish"};
        buildTailedStrings(words);

        if (found)
            for (int i : result)
                out.println(words[i]);
        else
            out.println("No solution found");

        out.close();
    }

    public void connectWordNodes(int ind1, int ind2, String w1, String w2) {
        // w2 can continue w1 (w1 --> w2)
        if (w1.toUpperCase().charAt(w1.length() - 1) == w2.toUpperCase().charAt(0)) {
            if (!g.containsKey(ind1))
                g.put(ind1, new ArrayList<>());
            g.get(ind1).add(ind2);
        }

        // w1 can continue w2 (w2 --> w1)
        if (w2.toUpperCase().charAt(w2.length() - 1) == w1.toUpperCase().charAt(0)) {
            if (!g.containsKey(ind2))
                g.put(ind2, new ArrayList<>());
            g.get(ind2).add(ind1);
        }
    }

    public void buildTailedStrings(String[] words) {
        // Build graph
        for (int i = 0; i < words.length - 1; i++)
            for (int j = i + 1; j < words.length; j++) {
                String w1 = words[i];
                String w2 = words[j];

                connectWordNodes(i, j, w1, w2);
            }

        found = false;
        total = words.length;
        used = new boolean[words.length];

        // Run dfs from each node
        for (int i = 0; i < words.length; i++) {
            num = 0;
            dfs(i);
            if (found)
                break;
        }
    }

    public void dfs(int node) {
        num++;
        used[node] = true;
        result.add(node);

        // if we reach to the point where we have all nodes, return result
        if (num == total) {
            found = true;
            return;
        }

        if (g.containsKey(node)) {
            List<Integer> nodesList = g.get(node);
            for (int curNode : nodesList) {
                if (!used[curNode])
                    dfs(curNode);
            }
        }

        if (found)
            return;

        num--;
        used[node] = false;
        result.remove(result.size() - 1);
    }
}

- megido December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

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

- halmeida September 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

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);
		}

	}
}

- cpeeyush December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How would you decide the parent if there are more than one strings starting same char.
Ex: [luis, sat, sam, mos]
Expected answer: luis -> sam -> mos -> sat.

But your code will print luis ->sat.

- kbrajesh176 February 03, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();

- koray January 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}

}

- Anonymous January 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
}

- Anonymous January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution above is mine. Forgot to loggin before posting.

- Felipe Cerqueira January 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/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);

- kotak86 January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
    }

- Christopher Nassar January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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("]");
    }
}

- Md Rakib Shahriar March 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/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;

- PT May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Yao Yicheng January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/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";
}

- Disha April 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Anonymous July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- harry July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- harry July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
}}}

- harry July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ 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) - harry July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- harry July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- harry July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- harryy000 July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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'])

- Deepak September 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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'])

- Deepak September 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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'])

- Deepak September 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();

- Luiz Santana November 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Aravind Prasad October 30, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question need to be solved by backtracking/dfs, because if there are more than one names starting with same character, we have to explore both paths.

Ex: [luis, sat, sam, mos]
Expected answer: luis -> sam -> mos -> sat.

- kbrajesh176 February 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }
    }
}

- shayan.eftekhari April 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }
    }
}

- shayan.eftekhari April 09, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	  }
}

- dexter August 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	  }
}

- dexter August 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
     * @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;
    }

- omid095 October 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
# ]

- Anonymous February 18, 2024 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

You can refer to this question: id=5932349506191360

- thelineofcode January 07, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More