Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
"This means we can sort any N integers in O(N) time, which is impossible based on normal comparison"
I'm not sure I agree. The problem states that the *first* tuple's first number is guaranteed to be the smallest (or tied for the smallest.) This is why we can perform swaps as we traverse the list 1 time (swapping as we go.) If we didn't have that guarantee I don't think you could sort in O(n).
e.g. this *can't* be done in O(n)
(a, 8, 12)
(b, 7, 9)
(c, 11, 12)
I am naive in the algorithm space...but this is the solution i came up with...
How about building a binary search tree and inserting each tuple as node?
every insert would take avg o(log n) time and in order traversal would take o(n) time...so it would give max o(n log n) time...
Love to hear comments and criticism..since this is my first answer to career cup. :)
//.h
class comparator{
public:
int operator() (const pair<string, int>&a, const pair<string, int>&b)
{
if(a.second < b.second)
return true;
return false;
}
};
typedef vector<tuple<string,int,int>> in_tuple;
typedef set< pair<string, int>, comparator> out_pair;
void SortTuple( in_tuple in, out_pair &out);
//.cpp
void SortTuple( in_tuple in, out_pair &out)
{
for_each(in.begin(), in.end(),[&out](tuple<string,int,int> elem)
{
string id; int a, b;
tie(id,a,b) = elem;
out.insert(make_pair(id,a));
out.insert(make_pair(id,b));
});
}
BOOST_AUTO_TEST_CASE(TestSortTuple)
{
in_tuple in;
in.push_back(make_tuple("a",1,3));
in.push_back(make_tuple("b",2,11));
in.push_back(make_tuple("c",4,7));
in.push_back(make_tuple("d",9,13));
in.push_back(make_tuple("e",12,33));
out_pair out;
SortTuple(in,out);
}
My solution in Java. We have to compare with value2 all the time and insert properly. Suppose we have classes TwoTuple(id, value) and ThreeTuple(id, value1, value2)
public static TwoTuple[] (ThreeTuple[] origin) {
if (!origin) return null;
int len = origin.length;
TwoTuple result[] = new TwoTuple[2*len];
if (len<1) return result;
//put fisrt two elements
result[0] = new TwoTuple(origin[0].id,origin[0].value1);
result[1] = new TwoTuple(origin[0].id,origin[0].value2);
for (int i=1; i<len; i++) {
ThreeTuple current = origin[i];
//compare with last element of result
if (current.value1 < result[2*i].value) {
//insert before last
result[2*i+1] = result[2*i];
result[2*i] = new TwoTuple(current.id, current.value1);
} else {
//add to end
result[2*i+1] = new TwoTuple(current.id, current.value1);
}
//append second value
result[2*i+2] = new TwoTuple(current.id, current.value2);
}
return result;
}
public static void main(String[] args){
Object[][] a={{'a',1,5},{'b',2,4},{'c',7,8}};
solve(a);
}
static void solve(Object[][] a){
int len=a.length*2;
Object[][] o=new Object[len][2];
char tmpc=' ';
int tmpi=0;
int count=0;
for(int i=0;i<a.length;i++){
for(int j=0;j<a[i].length;j++){
if(j==0){
tmpc=(char)a[i][j];
o[count][0]=tmpc;
}
else if (j==1){
tmpi=(int)a[i][j];
o[count][1]=(int)tmpi;
count++;
}else {
tmpc=(char)a[i][0];
tmpi=(int)a[i][j];
o[count][0]=tmpc;
o[count][1]=(int)tmpi;
count++;
}
}
}
for(int i=0;i<o.length;i++){
System.out.println(o[i][0] + " ," + o[i][1]);
}
}
Consider 2nd and 3rd as even and odd element of array. Consider this is array representation of min heap.
Perculate up every odd number that was not passed throug - from the bottom up.
# for each item in array : extract the id,integer pairs
# store them in a list
# sort the newlist based on the integer,optionally use id to break ties
input_array = [("a", 1, 5), ("b", 2, 4), ("c", 7, 8)]
def break_and_sort_tuple(input_array):
newlist = []
for element in input_array:
for index in range(1,3):
newlist.append((element[0],element[index]))
#result = sorted(newlist,key= (lambda x:(x[1],x[0]))) # if you want to use id as well
result = sorted(newlist,key=lambda x:x[1])
print result
return result
break_and_sort_tuple(input_array)
In this solution I do an insertion sort by looping back over the list and finding the place to insert the next tuple.
void Main()
{
var data = new object[][] {new object[]{'a',1,5},new object[]{'b',2,4},new object[]{'c',7,8}};
var result = new object[data.Length*2][];
// No data, nothing to do
if(data.Length < 1) return;
// Insert first tuple
result[0] = new object[]{data[0][0], data[0][1]};
result[1] = new object[]{data[0][0], data[0][2]};
for(int i = 1; i < data.Length; i++)
{
var current = data[i];
var new1 = new object[]{current[0], current[1]};
var new2 = new object[]{current[0], current[2]};
Insert(result, new1, i*2);
Insert(result, new2, (i*2)+1);
}
}
void Insert(object[][] arr, object[] val, int current)
{
var previous = current-1;
arr[current] = val;
while(previous >= 0 && ((int)arr[current][1]) < ((int)arr[previous][1]))
{
Swap(arr, current,previous);
current = previous;
previous = current - 1;
}
}
void Swap(object[][] arr, int i, int j)
{
var t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
You can do this in O(n * log n) time without sorting. Given the problem statement,
the interviewer probably doesn't want you to sort anyway since half of the 2-tuples will
already be sorted. What you *can* do instead is use binary search to find the correct
index to insert the unsorted 2-tuples into the list of sorted 2-tuples.
ex:
(a, 1, 5), (b, 2, 4), (c, 7, 8)
(a, 1), (b, 2), (c, 7) (sorted)
(a, 5), (b, 4), (c, 8) (not sorted)
You might be thinking to yourself O(n*log n) is no different from just using mergesort
in the first place, and you would be right, but half of the 2-tuples are already sorted.
If you sorted again you would be doing repeat work, likely what the interviewer doesn't
want you to do.
#!/usr/bin/perl
use strict;
use warnings;
use feature qw(say);
sub split_tuples {
my @tuples = @_;
my (@left, @right);
foreach my $tuple (@tuples) {
push @left, [$tuple->[0], $tuple->[1]];
push @right,[$tuple->[0], $tuple->[2]];
}
return (\@left, \@right);
}
# Precondition : $left is sorted
# Postcondition: $left is sorted and now contains all elements of $right
sub merge {
my ($left, $right) = @_;
foreach my $elem ( @$right ) {
my $index = binary_search($left, $elem);
if ( $index == -1 ) {
push @$left, $elem;
}
else {
splice(@$left, $index, 0, $elem);
}
}
return @$left;
}
sub binary_search {
my ($tuples, $elem) = @_;
return _binary_search($tuples, $elem, 0, scalar @$tuples - 1);
}
sub _binary_search {
my ($tuples, $elem, $left, $right) = @_;
return $left
if $elem->[1] <= $tuples->[$left]->[1];
return -1
if $elem->[1] > $tuples->[$right]->[1];
my $mid = int( ($right - $left) / 2 ) + $left;
my $key = $elem->[1];
my $m = $tuples->[$mid]->[1];
if ( $m == $key ) {
return $mid;
}
elsif ( $m < $key ) {
return $mid + 1
if $mid + 1 <= $right && $key <= $tuples->[$mid+1]->[1];
return _binary_search($tuples, $elem, $mid + 1, $right);
}
else {
return $mid
if ($mid - 1) >= $left && $key > $tuples->[$mid-1]->[1];
return _binary_search($tuples, $elem, $left, $mid - 1);
}
}
my @tuples = (['a', 1, 5], ['b', 2, 4], ['c', 7, 8]);
say 'Original: ', join ',', map { "($_->[0], $_->[1], $_->[2])" } @tuples;
say 'Unsorted: ', join ',', map { "($_->[0], $_->[1])" } map { @$_ } split_tuples(@tuples);
say 'Sorted : ', join ',', map { "($_->[0], $_->[1])" } merge split_tuples(@tuples);
The following solution first separates the sorted values from unsorted ones.
We know that for every 3tuple (a, 1, 5) the (a, 1) is in sorted order for each element.
After separation, we iterate over the unsorted array and insert each element into the sorted array at the proper position. Position is found using binary search.
static TwoTuple[] solveProblem(ThreeTuple[] array) {
if (array == null || array.length == 0) {
return null;
}
int length = array.length * 2;
// each 3tuple becomes two 2tuples
// separate the sorted and unsorted elements
TwoTuple[] sorted = new TwoTuple[length];
List<TwoTuple> unsorted = new ArrayList<TwoTuple>();
int index = 0;
for (int i = 0; i < array.length; i++) {
ThreeTuple curr = array[i];
sorted[index++] = new TwoTuple(curr.id, curr.a);
unsorted.add(new TwoTuple(curr.id, curr.b));
}
// insert unsorted elements into sorted array at proper position
// using binary search
binaryInsertionSort(sorted, unsorted, (length - unsorted.size()));
return sorted;
}
static void binaryInsertionSort(TwoTuple[] result, List<TwoTuple> unsorted,
int sortedCount) {
for (TwoTuple t : unsorted) {
int insertionPoint = Arrays.binarySearch(result, 0, sortedCount, t);
if (insertionPoint < 0) {
insertionPoint = (-(insertionPoint) - 1);
}
// shift
for (int i = result.length - 1; i > insertionPoint; i--) {
result[i] = result[i - 1];
}
// insert
result[insertionPoint] = t;
// update sortedCount
sortedCount++;
}
}
trick of this question is: you don't have to consider first char. If you create a tree node with 2 Values. you will easily do this in nlogn (worst case n(2) [n square]) code as:
//Redfine tree node and be sure, int data use for tree insertion
public class TreeNode
{
public int data;
public string data2;
public TreeNode left;
public TreeNode right;
public TreeNode(int data, string data2)
{
this.data = data;
this.data2 = data2;
left = null;
right = null;
}
}
//Add as tree node and traverse
public static void AnswerToQuestion(List<Tuple<string, int, int>> inputs)
{
TreeClass tree = new TreeClass();
foreach(Tuple<string, int,int> input in inputs)
{
tree.Add(input.Item2, input.Item1);
tree.Add(input.Item3, input.Item1);
}
tree.InOrderTravel(tree.root);
}
1) For every truplet we will have two pair. Lets call them first and second.
Example: (a,1,5) --> first = (a,1) and second = (a,5)
2) Create one stack
2) push first entry add first pair in output and push second pair in stack
4) Then for every truplet, do the following steps for first and second pair
4.1) if s.peek().data less than equal to pair then pop from stack and add in output
Java implementation of following algo:
Forgot to add code:
public static void findPairSorted(Triplet[] triplets)
{
Stack<Pair> s = new Stack<>();
List<Pair> result = new ArrayList<>();
result.add(new Pair(triplets[0].c, triplets[0].first));
Pair p = new Pair(triplets[0].c, triplets[0].second);
s.push(p);
int i = 1;
while (!s.isEmpty() && i < triplets.length)
{
Pair first = new Pair(triplets[i].c, triplets[i].first);
Pair second = new Pair(triplets[i].c, triplets[i].second);
while (!s.isEmpty() && s.peek().data <= first.data)
{
result.add(s.pop());
}
s.push(first);
while (!s.isEmpty() && s.peek().data <= second.data)
{
result.add(s.pop());
}
s.push(second);
i++;
}
while (!s.isEmpty())
{
result.add(s.pop());
}
System.out.println(result);
}
Here is some python code that uses a heap to keep a sorted queue of the second part of the tuple, and insert them appropriately as you go.
In the worst case where the first element is identical and the second element is different, this will be O(n log n), but on average it should be a lot quicker than that, for example the best case is O(n) (when both lists are sorted)
from heapq import heappush, heappop
def sortTuples(alist):
slist = [(alist[0][1], alist[0][0])]
start = (alist[0][2], alist[0][0])
queue = []
queue.append(start)
for t in alist[1:]:
x = (t[1],t[0])
y = (t[2], t[0])
heappush(queue, y)
while (not queue ==[]) and queue[0][0] < x[0]:
z = heappop(queue)
print z,x
slist.append(z)
slist.append(x)
while not queue == []:
z = heappop(queue)
slist.append(z)
return slist
print sortTuples([('a',1, 8), ('b',2, 7),('d',4, 6), ('c', 7 , 5) ])
Put 3rd values to min heap, and pop when root is less the current element.
import java.util.*;
public class Solution {
static class Triple {
public final String id;
public final Integer a, b;
public Triple(String id, Integer a, Integer b){
this.id = id;
this.a = a;
this.b = b;
}
}
static class Tuple implements Comparable {
public final String id;
public final Integer a;
public Tuple(String id, Integer a){
this.id = id;
this.a = a;
}
public int compareTo(Object other) {
return this.a - ((Tuple)other).a;
}
}
public static ArrayList<Tuple> solve(ArrayList<Triple> in){
PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
ArrayList<Tuple> res = new ArrayList<Tuple>();
for(Triple e : in){
Tuple cur = new Tuple(e.id, e.a);
pq.add(new Tuple(e.id, e.b));
while (pq.size() > 0 && pq.peek().compareTo(cur) <= 0) {
res.add(pq.poll());
}
res.add(cur);
}
while (pq.size() > 0) {
res.add(pq.poll());
}
return res;
}
public static void main(String [] args) {
ArrayList<Triple> arr = new ArrayList<Triple>();
arr.add(new Triple("a", 1, 2));
arr.add(new Triple("b", 1, 5));
arr.add(new Triple("c", 2, 3));
arr.add(new Triple("d", 4, 4));
for (Tuple e: solve(arr)){
System.out.println(e.id + " " + e.a);
}
}
}
We can push firsts tuples immediately to result array and for seconds tuples use min_heap. For each step compare current value with top of min_heap.
1. Split tuple3 into two tuple2: 'first' and 'second'
2. While top of min_heap less than 'first' tuple2, push the top to result array.
3. Push the 'first' tuple to result array.
4. Push 'second' tuple2 to min_hep
5. Repeat it for each tuple3
But I don't use here "id". Why interviewer give that field? Probably there is any reason.
vector<tuple2> split(const vector<tuple3>& arr) {
priority_queue<tuple2, vector<tuple2>, comp_fn> min_heap;
vector<tuple2> result;
result.reserve(2 * arr.size())
for (const tuple3& it : arr) {
tuple2 tuple(it.id, it.val1);
while (!min_heap.empty() && min_heap.top().val < tuple.val) {
result.push_back(min_heap.top());
min_heap.pop();
}
rs.push_back(tuple);
min_heap.push(tuple2(it.id, it.val2));
}
while (!min_heap.empty() ) {
rs.push_back(min_heap.top());
min_heap.pop();
}
return rs;
}
It can be solve by one-pass and 4log4*n time complexity (O(8n)).
Treat it as intervals, and try to merge them.
class Tuple3 {
String id;
int left;
int right;
public Tuple3(String id,int left,int right) {
this.id = id;
this.left = left;
this.right = right;
}
}
class Tuple2 {
String id;
int val;
public Tuple2(String id,int val) {
this.id = id;
this.val = val;
}
}
public class Solution{
static Tuple2[] dissembleTuple(Tuple3[] input) {
Tuple2[] result = new Tuple2[input.length*2];
Comparator c1 = new Comparator<Tuple2>(){
@Override
public int compare(Tuple2 t1, Tuple2 t2){
return t1.val-t2.val;
}
};
PriorityQueue<Tuple2> q = new PriorityQueue(4,c1);
q.add(new Tuple2(input[0].id,input[0].left));
q.add(new Tuple2(input[0].id,input[0].right));
for (int i=1;i<input.length;i++) {
// merge tuple3
q.add(new Tuple2(input[i].id,input[i].left));
q.add(new Tuple2(input[i].id,input[i].right));
result[(i-1)*2]=q.poll();
result[(i-1)*2+1]=q.poll();
}
result[input.length*2-2] = q.poll();
result[input.length*2-1] = q.poll();
return result;
}
this is one pass sort - just keeps appending to an output list
def myfunc(s):
out = list()
scndout = list()
for v in s :
if out == []:
out.append((v[0],v[1]))
scndout.append((v[0],v[2]))
else :
for i in range(1,3):
if v[i] > scndout[0][1]:
scndout.append((v[0],v[i]))
elif v[i] == scndout[0][1]:
scndount.insert((v[0],v[i]))
else:
out.append((v[0],v[i]))
out+=scndout
return out
Reading the problem, I can assume that I only need to compare the 3rd element against the succeeding third element (since its sorted based on 2nd, and 3rd is greater than or equal to 2nd.)
Here's my attempt in JavaScript (with test case.)
module.exports = function(tuples) {
var result = [];
var i, n;
for (i = 0, n = tuples.length; i < n; i += 2) {
result.push([tuples[i][0], tuples[i][1]]);
if (i+1 < n) {
result.push([tuples[i+1][0], tuples[i+1][1]]);
if (tuples[i][2] > tuples[i+1][2]) {
result.push([tuples[i+1][0], tuples[i+1][2]]);
result.push([tuples[i][0], tuples[i][2]]);
} else {
result.push([tuples[i][0], tuples[i][2]]);
result.push([tuples[i+1][0], tuples[i+1][2]]);
}
} else {
result.push([tuples[i][0], tuples[i][2]]);
}
}
return result;
};
// Test case:
var assert = require('assert');
var sortTuples = require('../tuples.js');
describe('sortTuples', function () {
it('should return sorted tuples', function () {
var input = [['a', 1, 5], ['b', 2, 4], ['c', 7, 8]];
var expected = [['a', 1], ['b', 2], ['b', 4], ['a', 5], ['c', 7], ['c', 8]];
assert.deepEqual(expected, sortTuples(input));
});
});
I assume it is this simple, but would love to hear other's thoughts.
What do you guys think about the code below? It uses a red and black tree using the integers as keys. I believe the space complexity is O (n * log n) while the time complexity is the same. I'm not sure... Feed back please!!!
import java.util.TreeMap;
import java.util.Collection;
public class SortTuple {
public void createSingleTuple (String [] arrayTuple){
String [] finalArray = new String [arrayTuple.length*2 ];
TreeMap <Integer,String> redBlackTree = new TreeMap<Integer,String>();
for ( int i =0; i <arrayTuple.length;i++){
String [] tokens = arrayTuple[i].split("[,]");
StringBuffer first = new StringBuffer ();
StringBuffer second = new StringBuffer ();
first.append(tokens[0]).append(tokens[1]);
second.append(tokens[0]).append(tokens[2]);
redBlackTree.put(Integer.parseInt(tokens[1]), first.toString());
redBlackTree.put(Integer.parseInt(tokens[2]), second.toString());
}
Collection <String> coll= redBlackTree.values();
coll.toArray(finalArray);
System.out.println("Print out of array");
for ( int i = 0; i < finalArray.length; i ++ ){
System.out.print(finalArray[i] + " ");
}} }
I think this problem is quite like the merge intersects problem on LeetCode, each tuple can be regarded as an intersects, and during the merge process, we first split the two integer and hold the large one, then sweep to the next one, compare the second integer first then the third integer, update the largest value till now, and I think the time complexity would be O(n).
/**
*
*/
package Amazon;
import java.io.ObjectInputStream.GetField;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
/**
* @author mangesh
*
*/
public class SortTwoTuples {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Object[][] a = { { 'a', 1, 5 }, { 'b', 2, 4 }, { 'c', 7, 8 } };
FindSorted(a);
}
public static void FindSorted(Object[][] a) {
LinkedList<Tuple> p = new LinkedList<Tuple>();
LinkedList<Tuple> finalL = new LinkedList<Tuple>();
// ArrayList<Tuple> p = new ArrayList<Tuple>();
for (int i = 0; i < a.length; i++) {
p.add(new Tuple('2', a[i][2]));
// a[i][0]
}
Collections.sort(p);
//System.out.println(p.toString());
int cnt3 = 0;// for tuple 3
int cnt2 = 0;// for tuple 2
while (true) {
if ((Integer) (a[cnt2][1]) <= p.get(cnt3).val) {
finalL.add(new Tuple(a[cnt2][0], a[cnt2][1]));
cnt2++;
if (cnt2 >= a.length)
break;
} else {
finalL.add(p.get(cnt3));
cnt3++;
if (cnt3 >= a.length)
break;
}
}
while (cnt2 < a.length) {
finalL.add(new Tuple(a[cnt2][0], a[cnt2][2]));
cnt2++;
}
while (cnt3 < a.length) {
finalL.add(p.get(cnt3));
cnt3++;
}
System.out.println(finalL.toString());
}
}
class Tuple implements Comparable<Tuple> {
char name;
Integer val;
public Tuple() {
}
public Tuple(Object a, Object a2) {
name = (char) a;
val = (int) a2;
}
/*
* (non-Javadoc)
*
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
@Override
public int compareTo(Tuple o) {
return this.val.compareTo(o.val);
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
// TODO Auto-generated method stub
return "[" + name + "," + val + "]";
}
// public boolean equals(Object o) {
// if (o instanceof Tuple) {
// // id comparison
// Tuple mo = (Tuple) o;
// return mo.val.equals(val);
// }
// return false;
// }
}
//============================================================================
// Name : tuple3.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;
typedef std::tuple<char, int, int> tripLet;
typedef std::pair<char, int> doublet;
struct DoubletComparator
{
bool operator () ( doublet a,doublet b)
{
return (std::get<1>(a) < std::get<1> (b));
}
} doubletcomparatorObject;
int main()
{
std::vector<tripLet> data;
data.push_back(std::make_tuple('a', 1, 5));
data.push_back(std::make_tuple('b', 2, 4));
data.push_back(std::make_tuple('c', 7, 8));
std::vector<std::pair<char, int> > list1;
for (size_t i = 0; i < data.size(); i++)
{
tripLet tmp = data.at(i);
list1.push_back(make_pair(std::get < 0 > (tmp), std::get < 1 > (tmp)));
list1.push_back(make_pair(std::get < 0 > (tmp), std::get < 2 > (tmp)));
}
std::sort(list1.begin(),list1.end(),doubletcomparatorObject);
for (std::vector<doublet>::iterator it=list1.begin(); it!=list1.end(); ++it)
std::cout << " (" << std::get<0>(*it) << " , "<< std::get<1>(*it) << " )" << endl;
return 0;
}
#include<iostream>
using namespace std;
#define ROWMAX 3
#define COLMAX 3
struct Node{
char name;
int data;
Node *next;
};
struct Node *sortTuple(int a[ROWMAX][COLMAX]){
struct Node *output = new Node;
output = NULL;
Node *startPtr = new Node;
for(int i=0; i<ROWMAX;i++){
Node * temp1 = new Node;
Node * temp2 = new Node;
for(int j=0;j<COLMAX;j++){
if(j == 0){
temp1->name = (char)a[i][j];
temp2->name = (char)a[i][j];
}
else if(j == 1){
temp1->data = a[i][j];
temp1->next = NULL;
}
else if(j == 2){
temp2->data = a[i][j];
temp2->next = NULL;
}
}
if(output == NULL){
startPtr = temp1;
output = temp1;
temp1->next = temp2;
output = temp2;
}
else{
output->next = temp1;
temp1->next = temp2;
output = temp2;
}
}
cout<<"Unsorted List"<<endl;
Node *ou = startPtr;
while(ou!=NULL){
cout<<ou->name<<" , "<< ou->data<<endl;
ou = ou->next;
}
//Sorting
Node *sortPtr = startPtr;
for(int i=0; i<(ROWMAX*2); i++){
while(sortPtr->next != NULL){
if(sortPtr->data > sortPtr->next->data){
int data = sortPtr->data;
sortPtr->data = sortPtr->next->data;
sortPtr->next->data = data;
char name = sortPtr->name;
sortPtr->name = sortPtr->next->name;
sortPtr->next->name = name;
}
else
sortPtr = sortPtr->next;
}
}
return startPtr;
}
int main(){
int a[ROWMAX][COLMAX]={{'a',1,5},{'b',2,4},{'c',7,8}};
int rowlength = ROWMAX*2;
int collength = COLMAX;
int **outa = new int *[rowlength];
for (int i = 0; i< rowlength; i++)
outa[i] = new int [2];
struct Node *output;
output = sortTuple(a);
cout<<"Sorted List"<<endl;
struct Node *temp = output;
while(temp!=NULL){
cout<<temp->name<<" , "<< temp->data<<endl;
temp = temp->next;
}
return 0;
}
#include<iostream>
using namespace std;
#define ROWMAX 3
#define COLMAX 3
struct Node{
char name;
int data;
Node *next;
};
struct Node *sortTuple(int a[ROWMAX][COLMAX]){
struct Node *output = new Node;
output = NULL;
Node *startPtr = new Node;
for(int i=0; i<ROWMAX;i++){
Node * temp1 = new Node;
Node * temp2 = new Node;
for(int j=0;j<COLMAX;j++){
if(j == 0){
temp1->name = (char)a[i][j];
temp2->name = (char)a[i][j];
}
else if(j == 1){
temp1->data = a[i][j];
temp1->next = NULL;
}
else if(j == 2){
temp2->data = a[i][j];
temp2->next = NULL;
}
}
if(output == NULL){
startPtr = temp1;
output = temp1;
temp1->next = temp2;
output = temp2;
}
else{
output->next = temp1;
temp1->next = temp2;
output = temp2;
}
}
cout<<"Unsorted List"<<endl;
Node *ou = startPtr;
while(ou!=NULL){
cout<<ou->name<<" , "<< ou->data<<endl;
ou = ou->next;
}
//Sorting
Node *sortPtr = startPtr;
for(int i=0; i<(ROWMAX*2); i++){
while(sortPtr->next != NULL){
if(sortPtr->data > sortPtr->next->data){
int data = sortPtr->data;
sortPtr->data = sortPtr->next->data;
sortPtr->next->data = data;
char name = sortPtr->name;
sortPtr->name = sortPtr->next->name;
sortPtr->next->name = name;
}
else
sortPtr = sortPtr->next;
}
}
return startPtr;
}
int main(){
int a[ROWMAX][COLMAX]={{'a',1,5},{'b',2,4},{'c',7,8}};
int rowlength = ROWMAX*2;
int collength = COLMAX;
int **outa = new int *[rowlength];
for (int i = 0; i< rowlength; i++)
outa[i] = new int [2];
struct Node *output;
output = sortTuple(a);
cout<<"Sorted List"<<endl;
struct Node *temp = output;
while(temp!=NULL){
cout<<temp->name<<" , "<< temp->data<<endl;
temp = temp->next;
}
return 0;
}
#include<iostream>
using namespace std;
#define ROWMAX 3
#define COLMAX 3
struct Node{
char name;
int data;
Node *next;
};
struct Node *sortTuple(int a[ROWMAX][COLMAX]){
struct Node *output = new Node;
output = NULL;
Node *startPtr = new Node;
for(int i=0; i<ROWMAX;i++){
Node * temp1 = new Node;
Node * temp2 = new Node;
for(int j=0;j<COLMAX;j++){
if(j == 0){
temp1->name = (char)a[i][j];
temp2->name = (char)a[i][j];
}
else if(j == 1){
temp1->data = a[i][j];
temp1->next = NULL;
}
else if(j == 2){
temp2->data = a[i][j];
temp2->next = NULL;
}
}
if(output == NULL){
startPtr = temp1;
output = temp1;
temp1->next = temp2;
output = temp2;
}
else{
output->next = temp1;
temp1->next = temp2;
output = temp2;
}
}
cout<<"Unsorted List"<<endl;
Node *ou = startPtr;
while(ou!=NULL){
cout<<ou->name<<" , "<< ou->data<<endl;
ou = ou->next;
}
//Sorting
Node *sortPtr = startPtr;
for(int i=0; i<(ROWMAX*2); i++){
while(sortPtr->next != NULL){
if(sortPtr->data > sortPtr->next->data){
int data = sortPtr->data;
sortPtr->data = sortPtr->next->data;
sortPtr->next->data = data;
char name = sortPtr->name;
sortPtr->name = sortPtr->next->name;
sortPtr->next->name = name;
}
else
sortPtr = sortPtr->next;
}
}
return startPtr;
}
int main(){
int a[ROWMAX][COLMAX]={{'a',1,5},{'b',2,4},{'c',7,8}};
int rowlength = ROWMAX*2;
int collength = COLMAX;
int **outa = new int *[rowlength];
for (int i = 0; i< rowlength; i++)
outa[i] = new int [2];
struct Node *output;
output = sortTuple(a);
cout<<"Sorted List"<<endl;
struct Node *temp = output;
while(temp!=NULL){
cout<<temp->name<<" , "<< temp->data<<endl;
temp = temp->next;
}
return 0;
}
#include<iostream>
using namespace std;
#define ROWMAX 3
#define COLMAX 3
struct Node{
char name;
int data;
Node *next;
};
struct Node *sortTuple(int a[ROWMAX][COLMAX]){
struct Node *output = new Node;
output = NULL;
Node *startPtr = new Node;
for(int i=0; i<ROWMAX;i++){
Node * temp1 = new Node;
Node * temp2 = new Node;
for(int j=0;j<COLMAX;j++){
if(j == 0){
temp1->name = (char)a[i][j];
temp2->name = (char)a[i][j];
}
else if(j == 1){
temp1->data = a[i][j];
temp1->next = NULL;
}
else if(j == 2){
temp2->data = a[i][j];
temp2->next = NULL;
}
}
if(output == NULL){
startPtr = temp1;
output = temp1;
temp1->next = temp2;
output = temp2;
}
else{
output->next = temp1;
temp1->next = temp2;
output = temp2;
}
}
cout<<"Unsorted List"<<endl;
Node *ou = startPtr;
while(ou!=NULL){
cout<<ou->name<<" , "<< ou->data<<endl;
ou = ou->next;
}
//Sorting
Node *sortPtr = startPtr;
for(int i=0; i<(ROWMAX*2); i++){
while(sortPtr->next != NULL){
if(sortPtr->data > sortPtr->next->data){
int data = sortPtr->data;
sortPtr->data = sortPtr->next->data;
sortPtr->next->data = data;
char name = sortPtr->name;
sortPtr->name = sortPtr->next->name;
sortPtr->next->name = name;
}
else
sortPtr = sortPtr->next;
}
}
return startPtr;
}
int main(){
int a[ROWMAX][COLMAX]={{'a',1,5},{'b',2,4},{'c',7,8}};
int rowlength = ROWMAX*2;
int collength = COLMAX;
int **outa = new int *[rowlength];
for (int i = 0; i< rowlength; i++)
outa[i] = new int [2];
struct Node *output;
output = sortTuple(a);
cout<<"Sorted List"<<endl;
struct Node *temp = output;
while(temp!=NULL){
cout<<temp->name<<" , "<< temp->data<<endl;
temp = temp->next;
}
return 0;
}
My code in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Test_Application
{
public class Node
{
public Tuple<char, int> Value { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
public class Program
{
private static List<Tuple<char, int, int>> list3 = new List<Tuple<char, int, int>>();
private static List<Tuple<char, int>> list2 = new List<Tuple<char, int>>();
static void Main(string[] args)
{
list3.Add(Tuple.Create<char, int, int>('a', 1, 7));
list3.Add(Tuple.Create<char, int, int>('b', 5, 12));
list3.Add(Tuple.Create<char, int, int>('c', 10, 11));
list3.Add(Tuple.Create<char, int, int>('d', 12, 16));
list3.Add(Tuple.Create<char, int, int>('e', 15, 24));
list3.Add(Tuple.Create<char, int, int>('f', 18, 19));
Node root = null;
foreach (Tuple<char, int, int> t3 in list3)
{
List<Tuple<char, int>> l = ConvertFrom2TupleTo3(t3);
foreach (Tuple<char, int> temp in l)
{
AddToBinaryTree(ref root, temp);
}
}
// Perform a in order traversal and print the tuples
TraverseAndPrint(root);
}
private static void TraverseAndPrint(Node root)
{
if (root == null)
{
return;
}
TraverseAndPrint(root.Left);
System.Console.Out.Write("{ " + root.Value.Item1 + ", " + root.Value.Item2 + " }");
TraverseAndPrint(root.Right);
}
private static List<Tuple<char, int>> ConvertFrom2TupleTo3(Tuple<char, int, int> t3)
{
if (t3 == null)
{
throw new ArgumentNullException("t3");
}
List<Tuple<char, int>> list = new List<Tuple<char, int>>();
list.Add(Tuple.Create<char, int>(t3.Item1, t3.Item2));
list.Add(Tuple.Create<char, int>(t3.Item1, t3.Item3));
return list;
}
public static void AddToBinaryTree(ref Node root, Tuple<char, int> element)
{
if (element == null)
{
throw new ArgumentNullException("element");
}
if (root == null)
{
root = new Node();
root.Value = element;
return;
}
Node temp = root;
Node current = root;
while (true)
{
bool isLeft = true;
if (element.Item2 < current.Value.Item2)
{
// Move to left
current = current.Left;
isLeft = true;
}
else
{
// Move to right
current = current.Right;
isLeft = false;
}
if (current == null)
{
// We need to add here
if (isLeft)
{
temp.Left = new Node();
temp.Left.Value = element;
}
else
{
temp.Right = new Node();
temp.Right.Value = element;
}
break;
}
temp = current;
}
}
}
}
Use a min_heap to store the second number, the first number is added into results if it is larger than the top element of the min_heap.
#include <iostream>
#include <queue>
using namespace std;
class three_entry {//entry of a 3-tuple
public:
string id;
int first;
int second;
three_entry(string name, int f, int s) : id(name), first(f), second(s) {}
};
class two_entry {//entry for output
public:
string id;
int val;
two_entry(string name, int v) : id(name), val(v) {}
};
class comparator {//comparator for min-heap
public:
bool operator()(const two_entry& a, const two_entry& b){
return a.val > b.val;
}
};
void sortThreeEntry(vector<three_entry> input){
priority_queue<two_entry, vector<two_entry>, comparator> min_heap;
vector<two_entry> result;
for (int i = 0; i < input.size(); i ++) {
//push the first number of each entry only when the heap is empty or
//the top element of the heap is larger than the first number
while (min_heap.size() && input[i].first >= min_heap.top().val) {
//pop out the top entry from the heap
result.push_back(min_heap.top());
min_heap.pop();
}
//add the first number into results
result.push_back(two_entry(input[i].id, input[i].first));
//push the second number into min_heap
min_heap.push(two_entry(input[i].id, input[i].second));
}
//pop out the rest of the heap
while (min_heap.size()) {
result.push_back(min_heap.top());
min_heap.pop();
}
//print results
for (auto v : result) {
cout << v.id << v.val << endl;
}
}
int main(int argc, const char * argv[])
{
// insert code here...
vector<three_entry> input;
input.push_back(three_entry("a", 1, 5));
input.push_back(three_entry("b", 2, 4));
input.push_back(three_entry("c", 7, 8));
sortThreeEntry(input);
return 0;
}
The idea is similar to merge sort, which is to merge the 2 sorted arrays into one big array. The first subarray is all the elements merged thus far. The second subarray is the 2 2-tuples obtained by the 3-tuple. It will always be a subarray of two elements.
The sorting algorithm would first construct a temp array that holds the two halves. It will then compare the first element of the two halves and picks the smaller of the two halves into the first position of the resulting sorted array. It then advances the pointer of the half A from which the first element is drawn and compares the next element of A with the first element of the other half. It continues this until the pointer passes the length of either two halves. The remaining elements in the first half will then be placed at the end one after another. Since they are already sorted, they need not be sorted.
Following is the code:
def sort_three_tuples(three_tuples):
first_three_tuple = three_tuples[0]
# put the first 2 tuples from first_three_tuples into the result array
# first
result = [(first_three_tuple[0], first_three_tuple[1]), (first_three_tuple[0], first_three_tuple[2])]
del three_tuples[0]
for three_tuple in three_tuples:
first_tuple = (three_tuple[0], three_tuple[1])
second_tuple = (three_tuple[0], three_tuple[2])
# left will iterate up to, not including, middle
middle = len(result)
left = 0
# right will iterate from middle
right = middle
# + 2 because there is always two tuples added to the existing sorted
# tuples
tot = middle + 2
# store result temporarily in temp first
temp = result + [first_tuple, second_tuple]
# this makes sure result has the same size as temp
result = temp
cur = 0
# now compare the first half with the second half
while left < middle and right < tot:
if temp[left][1] > temp[right][1]:
#print cur, right
result[cur] = temp[right]
cur = cur + 1
right = right + 1
else:
result[cur] = temp[left]
cur = cur + 1
left = left + 1
# remaining will keep track of how many of remaining elements in the
# left half that need to be copied into the result array
# if remaining = 0, there is nothing to copy and we are done sorting
remaining = middle - left
for i in xrange(0, remaining):
result[cur] = temp[left]
cur = cur + 1
left = left + 1
return result
print sort_three_tuples([('a', 1, 5), ('b', 2, 4), ('c', 7, 8)])
Assuming there are N 3-tuples. First time, it will take O(4) because we will have to move at most 4 elements (2 elements from the right and 2 from the left). Second, it will take at most 6 elements (2 elements from the right and 4 from the left). Third, it will take at most 8 elements (2 elements from the right and 6 from the left). The pattern is 2 + 4 + 6 + 8 + N*2 = 2(1+2+3+…(N-1)+N) = O(N^2).
HeapSort
struct ThreeTuple {
char leter;
int n1;
int n2;
ThreeTuple();
ThreeTuple(char l, int i, int j){
leter = l;
n1 = i;
n2 = j;
}
};
struct TwoTuple {
char leter;
int n1;
TwoTuple();
TwoTuple(char l, int n){
leter = l;
n1 = n;
}
bool operator <(const TwoTuple &other) const{
if(n1 == other.n1)
return leter > other.leter;
return n1 > other.n1;
}
};
int main(int argc, const char * argv[]) {
vector<ThreeTuple>initialVector;
initialVector.push_back(ThreeTuple('c', 5, 6));
initialVector.push_back(ThreeTuple('a', 1, 2));
initialVector.push_back(ThreeTuple('d', 1, 2));
initialVector.push_back(ThreeTuple('b', 3, 4));
priority_queue<TwoTuple> pq;
for (int i = 0; i < initialVector.size(); i++) {
ThreeTuple tt = initialVector[i];
pq.push(TwoTuple(tt.leter, tt.n1));
pq.push(TwoTuple(tt.leter, tt.n2));
}
while (!pq.empty()) {
TwoTuple two = pq.top();
pq.pop();
cout << "(" << two.leter << "," << two.n1 << ")" << " , ";
}
return 0;
}
private void sort(OrginalTuple[] originalTuple) {
// TODO Auto-generated method stub
resultTuple []rt1 = new resultTuple[originalTuple.length];
resultTuple []rt2 = new resultTuple[originalTuple.length];
resultTuple []finalResult = new resultTuple[originalTuple.length*2];
for(int i = 0;i< originalTuple.length; i++ ){
//make two arrays of original tuple
rt1[i] = new resultTuple(originalTuple[i].id, originalTuple[i].left );
rt2[i] = new resultTuple(originalTuple[i].id, originalTuple[i].right );
}
//sort second array
Arrays.sort(rt2);
//merge first and second.
int counter1 = 0;
int counter2 = 0;
int i = 0;
for(i=0;i< originalTuple.length; i++ ){
if(rt1[counter1].data<rt2[counter2].data){
finalResult[i] = rt1[counter1];
counter1++;
}else{
finalResult[i] = rt2[counter2];
counter2++;
}
}
while(counter1<originalTuple.length){
finalResult[i] = rt1[counter1];
i++;
counter1++;
}
while(counter2<originalTuple.length){
finalResult[i] = rt2[counter2];
i++;
counter2++;
}
//print final output
for(int z = 0; z<finalResult.length; z++){
System.out.println(finalResult[z].id + " " + finalResult[z].data );
}
}
Why no body uses HashMap ??
I think it can solve this O(n).
here is my Code
class Tuple3 {
String v1;
int v2,v3;
public Tuple3(String v1,int v2, int v3){
this.v1 = v1;
this.v2 = v2;
this.v3 = v3;
}
}
class Tuple2 {
String v1;
int v2;
public Tuple2(String v1,int v2){
this.v1 = v1;
this.v2 = v2;
}
}
public Tuple2[] convert(Tuple3[] arr){
HashMap<Integer, ArrayList<Tuple2>> map =
new HashMap<Integer, ArrayList<Tuple2>>();
for(Tuple3 t3 : arr){
if(!map.containsKey(t3.v2))
map.put(t3.v2, new ArrayList<Tuple2>());
map.get(t3.v2).add(new Tuple2(t3.v1, t3.v2));
if(!map.containsKey(t3.v3))
map.put(t3.v3, new ArrayList<Tuple2>());
map.get(t3.v3).add(new Tuple2(t3.v1, t3.v3));
}
Tuple2[] narr = new Tuple2[arr.length*2];
int pos = 0;
for(int k : map.keySet())
for(Tuple2 t:map.get(k))
narr[pos++] = t;
return narr;
}
public void testConvert(){
Tuple3[] arr = new Tuple3[]{new Tuple3("a", 1, 5),
new Tuple3("b", 2, 4),
new Tuple3("c", 7, 8)};
Tuple2[] narr = convert(arr);
}
Why no body uses HashMap ??
I think it can solve this O(n).
here is my Code
class Tuple3 {
String v1;
int v2,v3;
public Tuple3(String v1,int v2, int v3){
this.v1 = v1;
this.v2 = v2;
this.v3 = v3;
}
}
class Tuple2 {
String v1;
int v2;
public Tuple2(String v1,int v2){
this.v1 = v1;
this.v2 = v2;
}
}
public Tuple2[] convert(Tuple3[] arr){
HashMap<Integer, ArrayList<Tuple2>> map =
new HashMap<Integer, ArrayList<Tuple2>>();
for(Tuple3 t3 : arr){
if(!map.containsKey(t3.v2))
map.put(t3.v2, new ArrayList<Tuple2>());
map.get(t3.v2).add(new Tuple2(t3.v1, t3.v2));
if(!map.containsKey(t3.v3))
map.put(t3.v3, new ArrayList<Tuple2>());
map.get(t3.v3).add(new Tuple2(t3.v1, t3.v3));
}
Tuple2[] narr = new Tuple2[arr.length*2];
int pos = 0;
for(int k : map.keySet())
for(Tuple2 t:map.get(k))
narr[pos++] = t;
return narr;
}
public void testConvert(){
Tuple3[] arr = new Tuple3[]{new Tuple3("a", 1, 5),
new Tuple3("b", 2, 4),
new Tuple3("c", 7, 8)};
Tuple2[] narr = convert(arr);
}
Just Merge sort 2 lists, in which one of them has been sorted.
Below is verified C++ implementation:
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
struct Triple {
char id;
int x;
int y;
Triple(char aid, int ax, int ay) {
id = aid; x = ax; y = ay;
}
};
void Merge(vector< pair<char,int> > &v, int l_start, int l_end, int r_start, int r_end){
if (l_start >= r_start) return;
vector< pair<char,int> > v1;
int i,j;
i=l_start;
j=r_start;
while(i <= l_end && j <= r_end ) {
if ( v[i].second < v[j].second ) {
v1.push_back(v[i++]);
} else {
v1.push_back(v[j++]);
}
}
while(i <= l_end) {
v1.push_back(v[i++]);
}
while(j <= r_end) {
v1.push_back(v[j++]);
}
v = v1;
}
void MergeSort( vector< pair<char,int> > &v, int start, int end ){
if ( start >= end ) {
return ;
}
int middle = (start+end) >> 1;
MergeSort(v, start, middle);
MergeSort(v, middle+1, end);
Merge(v, start, middle, middle+1, end);
}
void sortTriple( vector<Triple> &input, vector< pair<char,int> > &v ){
vector< pair<char,int> > v1, v2;
// store the sorted tuple firstly
for(int i=0; i<input.size(); i++) {
pair<char,int> temp(input[i].id,input[i].x);
v1.push_back(temp);
}
// store and sort the second tuple
for(int i=0; i<input.size(); i++) {
pair<char,int> temp(input[i].id,input[i].y);
v2.push_back(temp);
}
MergeSort(v2, 0, v2.size()-1);
v.insert(v.end(), v1.begin(), v1.end());
v.insert(v.end(), v2.begin(), v2.end());
Merge(v, 0, v1.size()-1, v1.size(), v.size()-1);
}
int main() {
Triple A('a', 1, 5);
Triple B('b', 2, 4);
Triple C('c', 7, 8);
vector<Triple> input;
input.push_back(A); input.push_back(B); input.push_back(C);
vector< pair<char, int> > v;
sortTriple( input, v );
for(int i=0; i< v.size();i++) {
cout << "(" << v[i].first << "," << v[i].second << "),";
}
}
public static void sortThreeTuple(ThreeTuple input[]) {
int n = input.length;
TwoTuple result[] = new TwoTuple[n*n];
int index = 0;
for(int i = 0; i < n; i++) {
//Split three tuple to two tuples
TwoTuple one = new TwoTuple(input[i].c, input[i].start);
TwoTuple two = new TwoTuple(input[i].c, input[i].end);
if(index == 0) {
result[index++] = one;
result[index++] = two;
} else {
TwoTuple x = result[index-1];
if(x.start > one.start) {
result[index-1] = one;
if(x.start > two.start) {
result[index++] = two;
result[index++] = x;
} else {
result[index++] = x;
result[index++] = two;
}
} else {
result[index++] = one;
result[index++] = two;
}
}
}
for(int i = 0; i < index; i++) {
System.out.print("(" + result[i].c + ", " + result[i].start + ") ");
}
System.out.println();
}
public static void main(String[] args) {
ThreeTuple input[] = {new ThreeTuple('a', 1, 5), new ThreeTuple('b', 2, 4), new ThreeTuple('c', 7, 8)};
sortThreeTuple(input);
}
public static void sortThreeTuple(ThreeTuple input[]) {
int n = input.length;
TwoTuple result[] = new TwoTuple[n*n];
int index = 0;
for(int i = 0; i < n; i++) {
//Split three tuple to two tuples
TwoTuple one = new TwoTuple(input[i].c, input[i].start);
TwoTuple two = new TwoTuple(input[i].c, input[i].end);
if(index == 0) {
result[index++] = one;
result[index++] = two;
} else {
TwoTuple x = result[index-1];
if(x.start > one.start) {
result[index-1] = one;
if(x.start > two.start) {
result[index++] = two;
result[index++] = x;
} else {
result[index++] = x;
result[index++] = two;
}
} else {
result[index++] = one;
result[index++] = two;
}
}
}
for(int i = 0; i < index; i++) {
System.out.print("(" + result[i].c + ", " + result[i].start + ") ");
}
System.out.println();
}
public static void main(String[] args) {
ThreeTuple input[] = {new ThreeTuple('a', 1, 5), new ThreeTuple('b', 2, 4), new ThreeTuple('c', 7, 8)};
sortThreeTuple(input);
}
I doubt that this question is from a Google interview for software development position.
My python solution :
arrayofTuples = [('a',1,5),('b',2,4),('c',7,8)]
def breakTuples(t):
newList = list()
for item in t:
x = item[0]
y = item[1]
z = item[2]
a = tuple([x,y])
b = tuple([x,z])
newList.append(a)
newList.append(b)
newList.sorted(key=lambda x:x[1])
return newList
print(breakTuples(arrayofTuples))
import java.util.*;
import java.util.Map.Entry;
public class ArrayOfTuples {
public static void SortArrayOfTupple()
{
ArrayList<Integer> secondTupple = new ArrayList<Integer>();
ArrayList<Integer> thirdTupple = new ArrayList<Integer>();
ArrayList<Integer> fourthTupple = new ArrayList<Integer>();
int [] array = {1,2,4,5,7,8};
secondTupple.add(1);
secondTupple.add(5);
thirdTupple.add(2);
thirdTupple.add(4);
fourthTupple.add(7);
fourthTupple.add(8);
HashMap<Character, ArrayList<Integer>> tuppleMap = new HashMap<Character, ArrayList<Integer>>();
tuppleMap.put('a', secondTupple);
tuppleMap.put('b', thirdTupple);
tuppleMap.put('c', fourthTupple);
for (int i=0; i<array.length; i++)
{
for (Entry<Character, ArrayList<Integer>> entry : tuppleMap.entrySet())
{
for(int j=0; j<entry.getValue().size(); j++)
if(array[i] == entry.getValue().get(j))
{
System.out.println(entry.getKey() + " " + entry.getValue().get(j));
}
}
}
}
public static void main (String [] args)
{
SortArrayOfTupple();
}
}
//What do you think of this solution?
1. Store it in a HashMap with <field1,field2>,<field1,field3> and so on. Eg: (a,1),(a,5),(b,2),(b,4),(c,7),(c,8)
2. Sort it by value by overriding comparator.
I think they do not want you to use sort, it would be not a good performance. Your data are already almost sorted. You can just swap elements when inserting.
I don't have the energy to write the full functioning code.
But my pseudo-code
Make two lists:
First one is (id, #firstNum)
Second one is (id, #secondNum)
Merge sort both of them:
It should take nlog(n).
Merge the two sorted array into final one:
Should be O(n).
Love to hear your comments. All constructive criticisms welcome :)
You do not need to sort your lists, they are already sorted... At least first one, by definition of the problem. The second is not necessarily fully sorted but close to that. You just need to merge properly.
import java.util.ArrayList;
// Time complexity : O(n)
// Space complexity: O(n)
public class Main {
public static void main(String[] args) {
ArrayList<Triplet> input = new ArrayList<Triplet>();
input.add(new Triplet('a', 1, 5));
input.add(new Triplet('b', 2, 4));
input.add(new Triplet('c', 7, 8));
ArrayList<Pair> result = sortTuples(input);
for(Pair item : result)
{
System.out.println(item.toString());
}
}
static ArrayList<Pair> sortTuples(ArrayList<Triplet> triplets)
{
ArrayList<Pair> unsortedPairs = getUnsortedPairs(triplets);
for(int i = 0; i < unsortedPairs.size() - 1; i++)
{
if (unsortedPairs.get(i).getValue() > unsortedPairs.get(i + 1).getValue())
{
Swap(unsortedPairs, i, i + 1);
}
}
return unsortedPairs;
}
static ArrayList<Pair> getUnsortedPairs(ArrayList<Triplet> triplets)
{
ArrayList<Pair> result = new ArrayList<Pair>();
for(Triplet triplet : triplets)
{
result.add(new Pair(triplet.getId(), triplet.getValue1()));
result.add(new Pair(triplet.getId(), triplet.getValue2()));
}
return result;
}
static void Swap(ArrayList<Pair> input, int left, int right)
{
Pair temp = input.get(left);
input.set(left, input.get(right));
input.set(right, temp);
}
}
// Pair and Triplet are classes representing the 2-tuple and 3-tuple items
O(N) solution:
For simple, we assume that the length of the list is more than 1.
We split first item [a,x,y] to [a,x] and [a,y], then take [a, y] as the cur item
pair<char, int> cur = [a, y]
for (int i = 1; i < inputlist.size(); ++i) {
item1, item2 = inputlist[i].split(); // get [b, x] and [b, y]
if (item1 > cur) {
swap(item1, cur);
}
output(item1);
if (item2 > cur) {
swap(item1, cur);
}
output(item2);
}
output(cur);
The O(nlogn) Solution is pretty straight forward. The interesting part is: whether can we find O(n) solution. The answer is NO. I can prove this by contradiction.
- yuyi September 14, 2014Assume such algorithm exists. Then for any N integers x1,x2,....xn. I construct the N three tuples (a, -infinity, x1), (b, -infinity, x2)...... clearly -infinity < xk, so it satisfies the condition. Now, with the algorithm, we can get (a,-infinity), (b, -infinity) .......(a, x1), (b, x3)..... This means we can sort any N integers in O(N) time, which is impossible based on normal comparison. Of course, if you do it by using bucket sort, you can do it but it needs more assumptions about the numbers.