Amazon Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
My input is (0,1,3)
Output is
0-1
3-1
Input is {0}
output is
0-0
Program is not working as expected
For input {0, 1, 3}
Output is
0-1
3-1
For Input {0}
Output is
0-0
It does not work as expected.
Am I off track here?
private static void runPairs(int[] list) {
int len = list.length;
for (int i=0;i<len;i++) {
if (Arrays.binarySearch(list,list[i]+1) >0 && list[i] != 1) {
System.out.print(list[i]+"-");
} else if (list[i] > 1) {
System.out.print(list[i]);
if (i<len-1) System.out.print(",");
}
}
}
runPairs(new int[] {0,1,2,7,21,22,1098,1099});
If the order in which the ranges are given in output doesn't matter, we can do this with a lookup table in a relatively short time (ideally, O(n) time). It works by having each entry seen check the table for its predecessor (i.e. for value x, check if table has value x-1) and then removes that key from the table, replacing it with the current one. The val assigned to that key is the val of the first entry in the range.
I'm bad at describing this so let's see how it looks implemented in python:
def find_in_unsorted(vals):
output = ""
val_counts = {}
for x in vals:
if not val_counts.get(x-1, None):
val_counts[x] = x
else:
start = val_counts.pop(x-1)
val_counts[x] = start
for end, start in val_counts.iteritems():
if output != "":
output += ", "
output += "{}".format(end) if end == start else "{}-{}".format(start,end)
return output
However, this solution isn't always ideal, tables with lots of collisions are going to have worse lookup times. If you are willing to run it through a heapsort for O(n log n) time, you can accomplish this in, worst case, O(n log n). The python code for the post-sort processing looks like :
def find_ranges(vals):
output = ""
curr_start = 0
curr_end = 0
for i in range(1,len(vals)):
curr_val = vals[i]
if curr_val == (vals[i-1] + 1):
curr_end = i
continue
else:
output += append_vals(curr_start, curr_end, vals)
curr_start = i
curr_end = i
output += append_vals(curr_start,curr_end,vals)
return output
def append_vals(start,end, vals):
output = "{}".format(vals[start]) if start == end else "{}-{}".format(vals[start],vals[end])
return output + (", " if end < len(vals) - 1 else "")
This also prints the ranges in proper order.
The first method, if my memory serves me right, has a worst-case runtime (with lots of collisions and slow lookups) of O(n^2), so while the first solution is faster in ideal cases (O(n)) the second is stable and is not affected by such issues.
Have two runners. If the array is not sorted. Sort the array. As long as difference is not greater than one for 2 consecutive values, keep tail going but do not increment head.
public class AmazonQuestions{
public static void main(String[] args) {
int a[] = {0,1,2,7,8,9,10,21,22,23,24,25,27,1098,1099,2000};
System.out.println(ranges(a));
}
private static String ranges(int []a){
String answer ="";
int head=0;
for(int tail=1; tail<a.length; tail++){
// they are consecutive
if(a[tail] - a[tail-1] != 1){
// put in a check to see if they are the same number
// if they are then print just once
answer += a[head] +" - " + a[tail-1]+"\n";
head= tail;
}
}
// put in a check to see if they are the same number
// if they are then print just once
answer += a[head]+ "-"+ a[a.length-1];
return answer;
}
}
private static StringBuilder buildRangeString(int[] arr) {
if(arr.length==0)
return null;
StringBuilder outputString=new StringBuilder();
int head=0;
for(int tail=1;tail<arr.length;tail++) {
if(arr[tail]!=arr[tail-1]+1) {
if(head==tail-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[tail-1]+",");
}
head=tail;
}
}
if(head==arr.length-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[arr.length-1]+",");
}
return outputString;
}
private static StringBuilder buildRangeString(int[] arr) {
if(arr.length==0)
return null;
StringBuilder outputString=new StringBuilder();
int head=0;
for(int tail=1;tail<arr.length;tail++) {
if(arr[tail]!=arr[tail-1]+1) {
if(head==tail-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[tail-1]+",");
}
head=tail;
}
}
if(head==arr.length-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[arr.length-1]+",");
}
return outputString;
}
private static StringBuilder buildRangeString(int[] arr) {
if(arr.length==0)
return null;
StringBuilder outputString=new StringBuilder();
int head=0;
for(int tail=1;tail<arr.length;tail++) {
if(arr[tail]!=arr[tail-1]+1) {
if(head==tail-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[tail-1]+",");
}
head=tail;
}
}
if(head==arr.length-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[arr.length-1]+",");
}
return outputString;
}
private static StringBuilder buildRangeString(int[] arr) {
if(arr.length==0)
return null;
StringBuilder outputString=new StringBuilder();
int head=0;
for(int tail=1;tail<arr.length;tail++) {
if(arr[tail]!=arr[tail-1]+1) {
if(head==tail-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[tail-1]+",");
}
head=tail;
}
}
if(head==arr.length-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[arr.length-1]+",");
}
return outputString;
}
private static StringBuilder buildRangeString(int[] arr) {
if(arr.length==0)
return null;
StringBuilder outputString=new StringBuilder();
int head=0;
for(int tail=1;tail<arr.length;tail++) {
if(arr[tail]!=arr[tail-1]+1) {
if(head==tail-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[tail-1]+",");
}
head=tail;
}
}
if(head==arr.length-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[arr.length-1]+",");
}
return outputString;
}
private static StringBuilder buildRangeString(int[] arr) {
if(arr.length==0)
return null;
StringBuilder outputString=new StringBuilder();
int head=0;
for(int tail=1;tail<arr.length;tail++) {
if(arr[tail]!=arr[tail-1]+1) {
if(head==tail-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[tail-1]+",");
}
head=tail;
}
}
if(head==arr.length-1) {
outputString.append(arr[head]+",");
}
else {
outputString.append(arr[head]+"-"+arr[arr.length-1]+",");
}
return outputString;
}
public void printRange(int[] n) {
int begIndex = 0;
String toPrint = "":
if (n.length == 1) {
System.out.prinlnt(n[0]);
return;
}
for (int i = 1; i < n; i++) {
while (i < n.length && n[i] - n[i - 1] == 1) {
i++;
}
if (i-1 == begIndex) {
toPrint += ", " + n[begIndex];//handle first parenthesis
}
else {
toPrint += ", " + n[begIndex] +" - " + n[i-1];
}
begIndex = i;
}
System.out.prinlnt(toPrint);
}
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
using namespace std;
int main()
{
int a[]={0,1,2,7,21,22,1080,1081,1082};
int l1=sizeof(a)/sizeof(int);
int i=0;
int min,max;
min=max=a[0];
string s;
while(l1--)
{
stringstream ss,ss1;
if(a[i+1]-a[i]==1)
{
max=a[i+1];
i++;
continue;
}
else
{
if(min!=max)
{
ss << min;
ss1 << max;
s=s+ss.str()+"-"+ss1.str()+" ";
}
max=min=a[i+1];
}
i++;
}
cout<<s<<endl;
return 0;
}
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
using namespace std;
int main()
{
int a[]={0,1,2,7,21,22,1080,1081,1082};
int l1=sizeof(a)/sizeof(int);
int i=0;
int min,max;
min=max=a[0];
string s;
while(l1--)
{
stringstream ss,ss1;
if(a[i+1]-a[i]==1)
{
max=a[i+1];
i++;
continue;
}
else
{
if(min!=max)
{
ss << min;
ss1 << max;
s=s+ss.str()+"-"+ss1.str()+" ";
}
max=min=a[i+1];
}
i++;
}
cout<<s<<endl;
return 0;
}
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
using namespace std;
int main()
{
int a[]={0,1,2,7,21,22,1080,1081,1082};
int l1=sizeof(a)/sizeof(int);
int i=0;
int min,max;
min=max=a[0];
string s;
while(l1--)
{
stringstream ss,ss1;
if(a[i+1]-a[i]==1)
{
max=a[i+1];
i++;
continue;
}
else
{
if(min!=max)
{
ss << min;
ss1 << max;
s=s+ss.str()+"-"+ss1.str()+" ";
}
max=min=a[i+1];
}
i++;
}
cout<<s<<endl;
return 0;
}
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
using namespace std;
int main()
{
int a[]={0,1,2,7,21,22,1080,1081,1082};
int l1=sizeof(a)/sizeof(int);
int i=0;
int min,max;
min=max=a[0];
string s;
while(l1--)
{
stringstream ss,ss1;
if(a[i+1]-a[i]==1)
{
max=a[i+1];
i++;
continue;
}
else
{
if(min!=max)
{
ss << min;
ss1 << max;
s=s+ss.str()+"-"+ss1.str()+" ";
}
max=min=a[i+1];
}
i++;
}
cout<<s<<endl;
return 0;
}
{
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
using namespace std;
int main()
{
int a[]={0,1,2,7,21,22,1080,1081,1082};
int l1=sizeof(a)/sizeof(int);
int i=0;
int min,max;
min=max=a[0];
string s;
while(l1--)
{
stringstream ss,ss1;
if(a[i+1]-a[i]==1)
{
max=a[i+1];
i++;
continue;
}
else
{
if(min!=max)
{
ss << min;
ss1 << max;
s=s+ss.str()+"-"+ss1.str()+" ";
}
max=min=a[i+1];
}
i++;
}
cout<<s<<endl;
return 0;
}
}
First sort it then from beginging look for ranges.
public String getRanges(Integer[] numbers){
Arrays.sort(numbers);
Integers begin= numbers[0];
StringBuilder buffer= new StringBuilder();
for(int i=1;i<number.length;i++){
if(numbers[i]!=numbers[i-1]+1){
if(begin==numbers[i-1]){
buffer.append(begin).append(“,”);
}else{
buffer.appebd(begin).append(“-”).append(number[i-1]).append(“,”);
}
begin=numbers[i];
}
}
int len=buffer.length();
buffer.delete(len-1,len);
return buffer.toStrong();
}
string GetRange(vector<long>& input)
{
ostringstream oss;
vector<long> numbers(input);
sort(numbers.begin(), numbers.end());
if (!numbers.empty())
{
size_t first = 0;
for (size_t i = 1; i < numbers.size(); i++)
{
if ((numbers[i] - numbers[i - 1]) > 1)
{
oss << numbers[first];
if (first != i - 1)
oss << " - " << numbers[i - 1] << ", ";
else
oss << ", ";
first = i;
}
}
oss << numbers[first];
if (first != numbers.size() - 1)
oss << " - " << numbers[numbers.size() - 1];
}
return oss.str();
}
void findRange(int iArr[])
{
//if the array is not sorted then sort it in descending order.
int strtRnge = -1,endRnge=0;
for(int i=0;i<n;i++)
{
if(iArr[i+1]-iArr[i] ==1)
{
if(strtRnge == -1)
strtRnge = iArr[i];
continue;
}
endRnge = iArr[i];
if(strtRnge==-1)
cout << endRnge << ",";
else
cout << strtRnge << "-" << endRnge << ",";
strtRnge =-1;
}
}
In the previous submission of code there is a mistake in the comment stating
that the array, if not sorted sort it in descending instead of ascending order.
void findRange(int iArr[])
{
//if the array is not sorted then sort it in ascending order.
int strtRnge = -1,endRnge=0;
for(int i=0;i<n;i++)
{
if(iArr[i+1]-iArr[i] ==1)
{
if(strtRnge == -1)
strtRnge = iArr[i];
continue;
}
endRnge = iArr[i];
if(strtRnge==-1)
cout << endRnge << ",";
else
cout << strtRnge << "-" << endRnge << ",";
strtRnge =-1;
}
}
public String arrayToRange(int[] array){
if(array.length == 0)
return null;
int prev = array[0];
StringBuilder sb = new StringBuilder();
List<Integer> list = new ArrayList<Integer>();
list.add(prev);
for(int i = 1; i<array.length; ++i){
if(array[i] == ++prev || list.size()==0){
list.add(array[i]);
prev = array[i];
}
else if(list.size()>1){
sb.append(list.get(0));
sb.append('-');
sb.append(list.get(list.size()-1));
sb.append(',');
prev= array[i];
list.clear();
list.add(prev);
}
else{
prev= array[i];
list.clear();
list.add(prev);
}
}
if(list.size()>1){
sb.append(list.get(0));
sb.append('-');
sb.append(list.get(list.size()-1));
}
return sb.toString();
}
string rangeOfNumbers(int A[], int n)
{
assert(A != NULL && n > 0);
set<int> st(A, A + n); string ans;
while (!st.empty())
{
int s = *st.begin(), t = s;
while (st.count(t + 1) > 0) st.erase(++t);
st.erase(s);
if (!ans.empty()) ans.push_back(',');
ans += to_string(s);
if (t != s)
{
ans += "-"; ans += to_string(t);
}
}
return move(ans);
}
- Vir Pratap Uttam April 12, 2015package com.algorithm.amazon; public class RunPairs { public static void main(String[] args) { // TODO Auto-generated method stub runPairs(new int[] { 0, 1, 2, 7, 21, 22, 1098, 1099 }); } private static void runPairs(int[] arr) { // TODO Auto-generated method stub int start = arr[0], end = 0; int count = 0; for (int i = 1; i < arr.length; i++) { if (arr[i - 1] == arr[i] - 1) { end = arr[i]; count++; } else { end = arr[i - 1]; if (count > 0) System.out.println(start + "-" + end); else System.out.println(end); start = arr[i]; count = 0; } } System.out.println(start + "-" + end); } }