## Amazon Interview Question

Country: India

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

Partition the string into m(could be 2) parts find starting and ending value of each partition say a and b. b-a gives the transition points within each partition.

If b - a == 0 ignore partition

else if b-a>0 and partition size > 1
further partition into m new partitons and make a recursive call.
else
add current index to the resultant array

return

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

Can you pls explain it with an example ?

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

would this still work if the numbers are not consecutive?

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

Please refer to my code for an example. It works even if the numbers are not consecutive.

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

void PrintPoint(const char *str, int low, int high)
{
if (str[low] != str[high])
{
if (low + 1 == high)
{
printf("at [%d] is %c\n", high, str[high]);
}
else
{
int mid = (low + high) / 2;
if (str[low] != str[mid])
{
PrintPoint(str, low, mid);
}
if (str[high] != str[mid])
{
PrintPoint(str, mid, high);
}
}
}
}

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

Can you elaborate your question more?

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

There can be any number of 0's than any number of 1's etc. You have to find all the transition points ie. from 0 to 1 and from 1 to 2...etc.

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

what does it mean transition point?

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

String is 00000000000000000000000000000000000111111111122222222222223333333333333333333333333333344444444444444455555555555555555555....find the index of the string where, 0 changes to 1, 1 changes to 2 and so on....it is infinite string...so no length is given...Please compute in less than O(n)

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

Given the above description the answer should be n. since there would be n transitions.

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

Divide it in n parts of equal length , then if some points are equals unioun them . Finally on need to have n points with different values, Than do binary search in each of interval.

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

Optimal value of m could be a dynamic value starting with n and within each recursive call it could be b-a.

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

Optimal value of m could be a dynamic value starting with n and within each recursive call it could be b-a.

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

This is working solution and tested with diff set of input string

``````package com.learn;

import java.util.HashSet;
import java.util.Iterator;

public class FindTransitions {

public void findPoints(String inputString){
int i = 0,len = inputString.length()-1;
HashSet<Integer> output = new HashSet<Integer>();
while(i <= len){
if(i != 0 && inputString.charAt(i-1) != inputString.charAt(i)){
}
if(i < len && inputString.charAt(i+1) != inputString.charAt(i)){
}
i = i + 2;
}
Iterator<Integer> itr = output.iterator();
while(itr.hasNext()){
System.out.println(" "+itr.next());
}
}

public static void main(String[] args){
String inputString = "000111122455";
new FindTransitions().findPoints(inputString);
}
}``````

O/p : 0 3 7 9 10
Time: O(n/2)

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

Hi Sabarish,I think the interviewer would expect a faster way to solve this problem. Your solution is O(n/2) which is no difference from O(n). If you don't use the information that the array is sorted, you can also get an O(n) solution.

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

``````public void findPoints2(int low,int high){

if(low + 1 == high && ipString.charAt(low + 1) == ipString.charAt(high)){
return;
}
int mid = (low + high) / 2;
if(ipString.charAt(mid) != ipString.charAt(mid+1)){
}
if(ipString.charAt(low) != ipString.charAt(mid)){
findPoints2(low,mid);
}
if(ipString.charAt(mid+1) != ipString.charAt(high) && (mid+1) != high){
findPoints2(mid+1,high);
}
}``````

Gives same o/p with divide and conquer method

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

The code is not at all tested.
1. The above code doesn't work (try another input string)
2. The problem statement is to find all the transition points and your function returns int.

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

Thanks for your comment. My code returns the number of transition points. I will modify it later. Can you provide some test cases where my code doesn't work? Thanks.

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

Hi,

I have written a recursive program for it. But this program works on an assumption that if we have a shift from single digit to double digit. It treats it as two transition, say for example,

012345678910.

It assumes the transition from 9 to 1 as 1 and transition from 1 to 0 as another one.

``````package com.amaze.searching;

import java.io.IOException;

import com.amaze.io.Input;

public class SearchConsecutiveString {

/**
* @param args
* @throws IOException
*/

static int index = 0;

public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub

char[] str = "0000122223345".toCharArray();

int[] arr = new int[str.length];

getTransitionPoints(str,arr,0,str.length-1);

System.out.println();

for(int i=0; i<index; i++){
System.out.print("\t"+arr[i]);
}

System.out.println();

}

private static void getTransitionPoints(char[] str, int[] arr, int start, int end) {

System.out.println("Start "+start+" end "+end+" index "+index);

if(start == end || arr[start] == arr[end])
return;

int mid = (start+end)/2;

getTransitionPoints(str,arr,start,mid);
getTransitionPoints(str, arr, mid+1, end);

if(str[mid]!=str[mid+1]){
arr[index] = mid+1;
index++;
}

}

}``````

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

Yeah, I think we probably need do some trick based on binary search. Here is my way:
implied tips: the data in the array is sorted.
1. start from the first index value, find the end index(say i) of this value using binary search
2. jump to the index of the second value(say i+1) and repeat the step using binary search
until i reach the end of the array
-------------------
But I'm not very sure if this algorithm runs in O(logN), since I'm not sure if the distinct values of this array is relevant to O(N) or not. Can somebody explain it? Thx

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

I think the worst case of your solution might be O(nlgn).
If the input don't have duplicates, like"0123456789". You have to do so many binary search.

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

This is Basically refined binary search algo with the wrapper function of loop will work.

I mean ..

int [] findAll(){
for all number from 0 to n
BinarySearch(currentIndex, topIndex,givenArray[],array[CurrentIndex]);
}

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

print "Hello World!\n";
str1="""00000000000000000011111111111111111111555555555555555555577777777777777777777888888888888888888889999999999999"""
def bsearch(str1,i,l):
str2=""
if i==l:
return str2
else:
while i<=l-2:
if str1[0]==str1[len(str1)-1]:
break
else:
j=(i+l)/2
if str1[i]==str1[j]:
i=j
else:
l=j
if l==(len(str1)-1):
return
else:
str2+=str(l)
print str2,
bsearch(str1,l,len(str1)-1)
i=0
l=len(str1)-1
print bsearch(str1,i,l)
print str1[18],str1[38],str1[57],str1[77],str1[97]
print str1[17],str1[37],str1[56],str1[76],str1[96]

#complexity a log n {n chars in str, a different chars in str}

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

static int d = 0;
int countnumber(char * a, int l, int h)
{
int mid;
if((l == h) || (a[l] == a[h]) )
{
cout<<"l="<<l<<"h="<<h<<endl;
return 0;
}
mid = (l + h)/2;
countnumber(a, l, mid);
countnumber(a, mid+1, h);
if(a[mid] != a[mid+1])
{
d++;
}

}

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

``````public class StringProblems {
public static void main(String[] args) {
String inputString = "0001111224551";
new StringProblems().findTransitionPoints(inputString);
}

public void findTransitionPoints(String str) {
int i=0;
while (i < str.length() - 1) {
if (str.charAt(i) != str.charAt(++i)) {
System.out.print(i + " ");
}
}
}
}
O/p: 3 7 9 10 12``````

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

``````public class TransitionPoints {
//private int count;
//private int mid;
private ArrayList<Integer> al = new ArrayList<Integer>();

public static void main(String[] args) {
String s ="001112233444567";
TransitionPoints tp = new TransitionPoints();
tp.getPoints(s);
}

public void getPoints(String n) {

char [] arr = n.toCharArray();
getTransPoints(arr,0,arr.length-1);
for(Integer i:al)
System.out.println(i);
}
public void getTransPoints(char[] arr,int low, int high)
{
if(low == high)
return;
if(arr[low] == arr[high])
return;

int mid = (low+high)/2;
/* if(arr[low] < arr[high] & low+1 == high){
}*/
getTransPoints(arr,low,mid);
getTransPoints(arr,mid+1,high);
if(arr[mid] != arr[mid+1])

}

}``````

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

Time complexity is O(lg n) for n inputs...

o/p of above code is
1
4
6
8
12
13
11

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

If we have an infinte stream of numbers,we probably could not apply binary search
so we could use search in terms of power of 2 . such as checking at a gap of 2,4,8,16......
so overall complexity would boil down to logarithmic complexity

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

If we have an infinte stream of numbers,we probably could not apply binary search
so we could use search in terms of power of 2 . such as checking at a gap of 2,4,8,16......
so overall complexity would boil down to logarithmic complexity

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

``````public class infinitestream
{
private static char cbufg[] = null;
private static int pos = 0;

public static void transitionpoint(BufferedReader br) throws IOException
{
char input[] =
{ '0', '1', '2', '3', '4' };
int i = 1;
boolean flag = false;
while (i < input.length)
{
pos = printtransiton(br, input[i - 1], input[i], pos);
System.out.println("Transition Position = " + pos);
i++;
}
}

public static int printtransiton(BufferedReader br, char d, char c, int pos)
throws IOException
{
char cbuf[] = new char[2];
int len = 2;
while (true)
{
int k = 0;
if (cbufg != null)
{
for (int i = 0; i < cbufg.length; i++)
{
if (cbufg[i] == c)
{
if (i == cbufg.length - 1)
{
cbufg = null;
return pos + 1;
}
else if (i < cbufg.length - 1)
{
char[] cbuftmp = new char[cbufg.length - i - 1];
System.arraycopy(cbufg, i + 1, cbuftmp, 0,
cbufg.length - i - 1);
cbufg = cbuftmp;
}
return pos + i + 1;
}
}
pos = pos + cbufg.length;
cbufg = null;
}
else
{
while (k < cbuf.length)
{
cbuf[k] = ch;
k++;
if ((int) ch == 13) break;
}
if (cbuf[k - 1] != d)
{
for (int i = 0; i < k; i++)
if (cbuf[i] == c)
{
if (i < cbuf.length - 1)
{
cbufg = new char[k - i - 1];
System.arraycopy(cbuf, i + 1, cbufg, 0, k - i
- 1);
}
return pos + i + 1;
}
}
else
{
pos = pos + len;
len = len * 2;
cbuf = new char[len];
}
}
}
}

public static void main(String[] args) throws IOException
{
transitionpoint(br);
}
}``````

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

It is a good idea to do it like binary search. Here is the code and I have tested it.

``````public class Solution{
public int findTransitionPoints(String s, int start, int end){
if(start > end){
return 0;
}
if(s.charAt(start) == s.charAt(end)){
return 1;
}
int mid = start + (end - start) / 2;
int left = findTransitionPoints(s, start, mid);
int right = findTransitionPoints(s, mid + 1, end);
//if mid + 1 > end , it means that start = end;
if(mid + 1 <= end){
if(s.charAt(mid) == s.charAt(mid + 1)){
return left + right - 1;
}
}
return left + right;
}

public static void main(String[] args){
String inputString = "0000011112222222222";
System.out.println(new Solution().findTransitionPoints(inputString, 0, inputString.length() - 1));
}
}``````

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.