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
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)
Labels:Data
Binary Search
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
Wednesday, October 16, 2013
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
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.
Labels:Data
Quora
Subscribe to:
Posts
(
Atom
)