## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 8 vote

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.
Assume 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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Comment hidden because of low score. Click to expand.
0

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

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

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. :)

Comment hidden because of low score. Click to expand.
0

How are you making use of first part of data being sorted?

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

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

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

I think it doesn't work.

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

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

}

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

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.

Comment hidden because of low score. Click to expand.
0

I have this crazy feelng that no perculation may be even neccessary because odd is greater than its even brother so if even's parent is good - it will be good for odd child

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

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

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

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

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

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

Comment hidden because of low score. Click to expand.
0

actually, for (c, 7, 8), (c, 7) and (c, 8) are sorted

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

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

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

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

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.InOrderTravel(tree.root);
}

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

The best strategy is to use the insertion sort.
input: (a, 1, 5), (b, 2, 4), (c, 7, 8)
enter first: (a,1),(a,5)
enter second: (a,1),(a,5),(b,2),(b,4) -> (a,1),(b,2),(a,5),(b,4) -> (a,1),(b,2),(b,4),(a,5)
enter third: (a,1),(b,2),(b,4),(a,5),(c,7),(c,8)

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

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:

Comment hidden because of low score. Click to expand.
0

public static void findPairSorted(Triplet[] triplets)
{

Stack<Pair> s = new Stack<>();

List<Pair> result = new ArrayList<>();
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)
{
}

s.push(first);

while (!s.isEmpty() && s.peek().data <= second.data)
{
}

s.push(second);
i++;

}

while (!s.isEmpty())
{
}

System.out.println(result);
}

Comment hidden because of low score. Click to expand.
0

Whats the complexity of your program?

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Doesn't work for

{{
print sortTuples([('a', 2, 8), ('b', 1, 7)])
}}

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

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);
while (pq.size() > 0 && pq.peek().compareTo(cur) <= 0) {
}
}
while (pq.size() > 0) {
}
return res;
}

public static void main(String [] args) {
ArrayList<Triple> arr = new ArrayList<Triple>();
for (Tuple e: solve(arr)){
System.out.println(e.id + " " + e.a);
}
}
}

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

Merge Sort is the solution

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

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

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

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

for (int i=1;i<input.length;i++) {
// merge tuple3
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;
}

Comment hidden because of low score. Click to expand.
0

Don't think it works with
[(a, 1, 9), (b, 2, 10), (c, 3, 11), (d, 4, 12)]

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

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

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

test

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

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.

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

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

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

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

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

/**
*
*/
package Amazon;

import java.io.ObjectInputStream.GetField;
import java.util.ArrayList;
import java.util.Collections;

/**
* @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) {
// ArrayList<Tuple> p = new ArrayList<Tuple>();
for (int i = 0; i < a.length; i++) {
// 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) {
cnt2++;
if (cnt2 >= a.length)
break;
} else {
cnt3++;
if (cnt3 >= a.length)
break;

}
}
while (cnt2 < a.length) {
cnt2++;
}
while (cnt3 < a.length) {
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;
}

/*
*
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
@Override
public int compareTo(Tuple o) {
return this.val.compareTo(o.val);
}

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

}

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

//============================================================================
// Name        : tuple3.cpp
// Author      :
// Version     :
// 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;
}

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

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

}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;

}

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

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

}

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

def f(A):
B = [] # the returned tuple sequence
for c, i, j in A:
B.append((c, i))
B.append((c, j))
B.sort(key=lambda t: t[1])
return B

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

You can use a merge sort. Put the second-element-tuples in a list A, this is already a sorted one. Put the third-element-tuples in another list B. This process should take O(n). Then sort B using merge sort. And call the merge function on A and B at last. This should take O(nlogn).

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

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

if(!map.containsKey(t3.v3))
map.put(t3.v3, new ArrayList<Tuple2>());
}
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);
}

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

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

if(!map.containsKey(t3.v3))
map.put(t3.v3, new ArrayList<Tuple2>());
}
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);
}

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

Here is a Python implementation:

def getlastelement(atuple):
return atuple[-1]

def twotuple(listoftuples):
result=[]
for atuple in listoftuples:
for element in [(atuple[0],x) for x in atuple[1:]]:
result.append(element)
print sorted(result, key=getlastelement)

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

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

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

I think it is n-way merge sort

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

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

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

This is wrong you get (a,1), (a,5), (b,2) on your first three items

Comment hidden because of low score. Click to expand.
0

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

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?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Well the first set of tuples after the split will be sorted, the second set could be in any order:

(a, 1, 5), (b, 2, 4), (c, 7, 8)

1 -- (a, 1), (b, 2), (c, 7)
2 -- (a, 5), (b, 4), (c, 8) (not sorted)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

So overall it should give us nlog(n).

Comment hidden because of low score. Click to expand.
0

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.

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

You need to sort the second list and then merge first and second list using mergesort.

Comment hidden because of low score. Click to expand.
0

Why not just use binary search to find a position to insert?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

}

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

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

Fails for:

(a,1,11),(b,2,9),(c,7,8), you'd end up with: (a,1),(b,2),(b,9),(c,7),(c,8),(a,11), which is ofcourse not sorted.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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.

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