import java.util.LinkedHashMap; public class FirstNonRepeated { public static void main(String[] args) { LinkedHashMap<Character, Integer> linkedHashMap = new LinkedHashMap<>(); String str = "allergicToBitches"; for (int i = 0; i < str.length(); i++) { char key = str.charAt(i); if (linkedHashMap.containsKey(key)) { linkedHashMap.remove(key); } else { Integer val = linkedHashMap.get(key); linkedHashMap.put(key, null == val ? 1 : val + new Integer(1)); } } System.out.print(linkedHashMap.entrySet().iterator().next().getKey()); } }

## Thursday, July 14, 2016

### Find firstNon repeating character in string in one pass

## Monday, November 24, 2014

### Given: an array x of N elements, sorted in ascending order and an integer a Try to find a in x. 1. if a is in x: return its position 2. if a is not in x: return the position, where to insert a in x, such that x remains sorted

Note: Question is pretty simple but there are lots of test cases to cover if you find any test case is not working , feel free to comment.

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

int x[]=new int[]{2, 6, 8, 10,13};

int a=11;

System.out.println(search(x,a));

}

public static int search(int x[], int a)

{

if(x==null || x.length==0) return 0;

int pos=-1;

int l=0;

int length=x.length;

int r=length-1;

if(a<x[0])

return 0;

if(a>x[length-1])

return length;

if(r<=0)

return 0;

if(1==length){

if(a>x[0])

return 1;

else if(a<=x[0])

return 0;

}

// [2, 6, 8, 10] values 0 , 7 , 5 , 9 , 11

if(l<=r)

{

while(l<=r)

{

int mid=l+((r-l)/2);

System.out.println("l= " + l + " mid = " + mid + " r= " + r);

if(x[mid]==a)

return mid;

else if(x[mid] > a && x[mid-1]<a)

return mid;

else if(x[mid] < a && x[mid+1]> a)

return mid+1;

else if(a<=x[mid-1])

r=mid-1;

else if(a>=x[mid+1])

l=mid+1;

}

}

return pos;

}

}

Run Here http://ideone.com/YuA70F

TC O(logn)

SC O(1)

Labels:Data
Binary Search
,
imo

Reactions: |

## Tuesday, April 1, 2014

### Given a element, find the strictly greater element in sorted array - 1st post for 2k14

E.g. if array is // [ a, c, d, h, k, l, l, l, o, u, x, z ]

//if given m -> o

// if given k -> l

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

// your code goes here

System.out.println(search(new char[]{'b', 'c', 'd', 'h', 'k', 'l', 'l', 'l', 'o', 'u', 'x', 'z'},'b')) ;

}

static char search(char a[],char find)

{

if(a==null || a.length==0)

return ' ';// if nothing found

int start=0;

int end=a.length-1;

if(start>end) return ' ' ; //|| find>=a[end]) return ' ';

if(find <a[start]) return a[start];

if(start==end && a[start]>find)

return a[start];

while(start<end)

{

int mid=start+(end-start+1)/2; //to minimize over flow

if(mid+1<=end && find>=a[mid] && find <a[mid+1])

return a[mid+1];

else if(mid-1>=0 && find < a[mid] && find >= a[mid-1])

return a[mid];

else if(find >=a[mid])

start=mid;

else if( find <a[mid])

end=mid;

else

return ' ';

System.out.println("start= " + start + ":::" + " End= " + end);

}

return ' ';//if nothing found , return special character

}

}

Time Complexity O(logn)

Space Complexity O(1)

//if given m -> o

// if given k -> l

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

// your code goes here

System.out.println(search(new char[]{'b', 'c', 'd', 'h', 'k', 'l', 'l', 'l', 'o', 'u', 'x', 'z'},'b')) ;

}

static char search(char a[],char find)

{

if(a==null || a.length==0)

return ' ';// if nothing found

int start=0;

int end=a.length-1;

if(start>end) return ' ' ; //|| find>=a[end]) return ' ';

if(find <a[start]) return a[start];

if(start==end && a[start]>find)

return a[start];

while(start<end)

{

int mid=start+(end-start+1)/2; //to minimize over flow

if(mid+1<=end && find>=a[mid] && find <a[mid+1])

return a[mid+1];

else if(mid-1>=0 && find < a[mid] && find >= a[mid-1])

return a[mid];

else if(find >=a[mid])

start=mid;

else if( find <a[mid])

end=mid;

else

return ' ';

System.out.println("start= " + start + ":::" + " End= " + end);

}

return ' ';//if nothing found , return special character

}

}

Time Complexity O(logn)

Space Complexity O(1)

## Monday, December 9, 2013

## Sunday, December 1, 2013

## Saturday, November 16, 2013

### Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order.

Example if nCards=9 and ICut=6 then for N=123456789 , you need 3 shuffle to get the original positions , wondering how , try it now and feel free to post comment here .

Labels:Data
FaceBook Engineering Team

Reactions: |

## Wednesday, October 16, 2013

### Find all 10 digit numbers which are perfect squares efficiently

Labels:Data
Twitter Interview

Reactions: |

## Sunday, October 13, 2013

### Two players play the following game: they pick a random number N (less than 2 billion) then, starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice). Whoever reaches N first wins. The candidate should write a function that given N decides who wins (first or second player)?

Labels:Data
Facebook Interview

Reactions: |

### Design a function f, such that: f(f(n)) == -n Where n is a 32 bit signed integer; you can't use complex numbers arithmetic. If you can't design such a function for the whole range of numbers, design it for the largest range possible.

## Thursday, October 3, 2013

### Two strings can be chained if the first one ends with the same character second one starts with. Given set of 'n' strings, how can we verify efficiently, whether they can be chained or not?

e.g. cat, dog, toad answer is YES.

for tape ate ass answer is NO.

for tape ate ass answer is NO.

Subscribe to:
Posts
(
Atom
)