Amazon Interview Question
Country: India
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);
}
}
}
}
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)
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>();
output.add(0);
while(i <= len){
if(i != 0 && inputString.charAt(i-1) != inputString.charAt(i)){
output.add(i);
}
if(i < len && inputString.charAt(i+1) != inputString.charAt(i)){
output.add(i+1);
}
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)
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.
public void findPoints2(int low,int high){
if(low + 1 == high && ipString.charAt(low + 1) == ipString.charAt(high)){
outputset.add(high);
return;
}
int mid = (low + high) / 2;
if(ipString.charAt(mid) != ipString.charAt(mid+1)){
outputset.add(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
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.
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++;
}
}
}
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
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}
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
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){
al.add(low);
}*/
getTransPoints(arr,low,mid);
getTransPoints(arr,mid+1,high);
if(arr[mid] != arr[mid+1])
al.add(mid);
}
}
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)
{
char ch = (char) br.read();
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
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
transitionpoint(br);
}
}
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));
}
}
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.
- Anonymous June 07, 2014If 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