kn
BAN USERpublic String substring(String str) {
int start=0, end=0; //current window
int maxStart=0, maxEnd = 0; //max
Map<Character, Integer> charIndex = new LinkedHashMap<>();
charIndex.put(str.charAt(0), 0);
for(int i=1; i<str.length(); i++) {
char c = str.charAt(i);
if(charIndex.containsKey(c)) {
if((end-start) > (maxEnd-maxStart)) {
maxStart = start;
maxEnd = end;
}
Iterator<Entry<Character, Integer>> iterator = charIndex.entrySet().iterator();
while(iterator.hasNext()) {
Entry<Character, Integer> entry = iterator.next();
if(!entry.getKey().equals(c)) {
iterator.remove();
} else {
start = entry.getValue() + 1;
iterator.remove();
break;
}
}
}
charIndex.put(str.charAt(i), i);
end++;
}
if((end-start) > (maxEnd-maxStart)) {
maxStart = start;
maxEnd = end;
}
return str.substring(maxStart, maxEnd+1);
}
Seems like your heap is updated based on the movie occurrence count ( Movie [] moviesHeap ).
This does not solve the problem of "last 24 hours".
One way to solve this problem is to use addtional heap that stores tweets of last 24hours (Tweet [] tweetHeap).
when scanning for new tweet, insert method updates 2 heaps:
movieHeap
tweetHeap
while querying for movie which is tweeted max times in last 24hours:
remove all items from tweetHeap which are older than 24hours (and corresponding updates to moviesHeap) and return the root of moviesHeap.
public static List<String> getWordLadder(String one, String two, Set<String> words){
List<String> ladder = new ArrayList<>();
if(one == null || two == null || one.length()!=two.length())
return ladder;
ladder.add(one);
if(one.equals(two))
return ladder;
Set<Integer> visited = new HashSet<>();
boolean flag = true;
char [] temp = one.toCharArray();
while(flag){
flag = false;
for(int i=0; i<one.length(); i++){
if(!visited.contains(i)){
temp[i] = two.charAt(i);
String str = new String(temp);
if(words.contains(str)){
flag=true;
visited.add(i);
ladder.add(str);
} else {
//last element - restore what was there before we tried out two.charAt(i);
temp = ladder.get(ladder.size()-1).toCharArray();
}
}
}
}
if(!flag && visited.size()==one.length())
return ladder;
return new ArrayList<String>();
}
This one does not use sorting but finds the min length string. then compares each string upto that length with temp char array.
public static String getPrefix(List<String> phrases){
if(phrases == null || phrases.size() == 0)
return "";
if(phrases.size() == 1)
return phrases.get(0);
int minCounter = Integer.MAX_VALUE;
int length = Integer.MAX_VALUE, i=0, counter=0;
for(String str : phrases){
if(length > str.length()){
length = str.length();
counter=i;
}
i++;
}
char [] chars = phrases.get(counter).toCharArray();
for(i=0;i<phrases.size();i++){
String str = phrases.get(i);
int len = str.length();
int j;
for(j=0; j<len && j<chars.length && chars[j]==str.charAt(j); j++);
if(j < minCounter)
minCounter = j;
}
return phrases.get(0).substring(0, minCounter);
}
/*
One way to implement this is using asynchronous thread communications.
Poller (thread) keeps polling Guests on regular interval to see if they have any empty plate.
On each run, it lists the Guests which have empty plate. and notifies the Host using appropriate Event object.
I havent tried below code.. just wrote it on Notepad and pasting it here. Just a sample code..
more complex code can be created using Locking APIs..
*/
public class Guest {
boolean isPlateFull = true;
int id;
Guest() {
//or pass Poller instance to each Guest so guests can register them selfs
Poller.register(this);
}
public void eat() {
isPlateFull = false;
}
public void serve() {
isPlateFull = true;
}
public boolean checkPlate() {
return isPlateFull;
}
@PreDestroy
public void myFinalize() {
Poller.unregister(this);
}
//equals and hashCode
//evil getters and setters
}
class Poller implements Runnable {
private Thread t;
private static List<Guest> guestsToPoll = new ArrayList<>();
public static final int pollIntervalSeconds = 5;
public static volatile boolean keepRunning = true;
public Host host;
public static final int maxGuestWaiting = 5;
public static final Poller instance;
private Poller(){}
//making an assumption only 1 poller thread needs to be creted.
//you may need to crete multiple Pollers for each Host.
//or single Poller can handle multiple hosts using a map of Host and Guests
public static final Poller getInstance(Host host){
if(instance == null) {
synchronized(Poller.class) {
if(instance == null) {
instance = new Poller();
instance.host = host;
instance.t = new Thread(this);
instance.t.start();
}
}
}
return instance;
}
@Override
public void run() {
while(keepRunning) {
synchronized(guestsToPoll) {
List<Guest> guestsWaiting = new ArrayList<>();
for(Guest guest : guestsToPoll) {
if(!guest.checkPlate()) { //plate is not full
guestsWaiting.add(guest);
host.notify(new GuestWaitingEvent(guest));
}
}
if(hosts.size()>=maxGuestWaiting) {
host.notify(new MaxHostWaitingEvent(hosts.size()/*, hosts*/));
}
guestsToPoll.wait(pollIntervalSeconds * 1000); //release the lock for a while and wait.
}
}
}
public static void register(Guest g) {
guestsToPoll.add(g);
}
public static void unregister(Guest g) {
guestsToPoll.remove(g); //uses equals
}
public static void stopPoller() {
keepRunning = false;
}
}
public enum EventType{
MAX_GUEST_WAITING,
GUEST_WAITING;
}
public abstract class Event {
EventType type;
Event(EventType type) {
this.type = type;
}
}
public class GuestWaitingEvent extends Event {
private Guest guest;
public HostWaitingEvent(Guest guest) {
super(EventType.GUEST_WAITING);
this.guest = guest;
}
//accessor methods
}
public class MaxGuestWaitingEvent extends Event {
private int num;
//private List<Guest> guestsWaiting; //you can notify who is waiting as well
public MaxGuestWaiting(int n/*, List<Guest> guests*/) {
super(EventType.MAX_GUEST_WAITING);
num = n;
//guestsWaiting = guests;
}
//accessor methods
}
//for truly asynchronous behavior
public class Host implements Runnable {
int servingsRemaining = 5;
Set<Guest> guestsToServe = new HashSet<>();
private Thread t;
private static final instance;
private static final int sleepTime = 200; //millis
private volatile boolean keepRunning = true;
private Host(){}
public static final Host getInstance() {
if(instance == null) {
synchronized(Host.class) {
if(instance == null) {
instance = new Host();
instance.t = new Thread(instance);
instance.t.start();
}
}
}
}
public void stop() {
keepRunning = false;
}
@Override
public void run() {
while(keepRunning) {
synchronized(guestsToServe) {
if(guestsToServe.size()==0) {
try {
guestsToServe.wait(sleepTime); //release the locks for a while
} catch (IllegalMonitorStateException | InterruptedException e) {
e.printStackTrace(System.out);
throw e;
}
} else {
for(Guest guest : guestsToServe) {
while(servingsRemaining==0) {
cook(); //imagine this is asynchronous as well!
guestsToServe.wait(sleepTime*5);
}
serve(guest);
}
}
}
}
}
public void cook() {
//get items from pantry and cook!!
servingsRemaining = 5;
}
public void serve(Guest guest) {
guest.serve();
servingsRemaining--;
}
public void notify(Event event) {
if(GuestWaitingEvent.class.equals(event.getClass())) {
synchronized(guestsToServe) {
guestsToServe.add(((GuestWaitingEvent)event).getGuest());
}
} else (MaxGuestWaitingEvent.class.equals(event.getClass())) {
//do some other thing..
}
}
}
Recursive solution::
Apologize for method and variable names
public class DiscontMatches {
public static void main(String[] args) {
Set<String> ans = findDiscMatches("cat", "catapult");
for(String str : ans)
System.out.println(str);
}
public static Set<String> findDiscMatches(String str1, String str2){
Set<String> set = new TreeSet<>();
Map<Character, List<Integer>> map = new LinkedHashMap<>();
char [] arr = str2.toCharArray();
char [] arr2 = str1.toCharArray();
for(char c: arr2){
int i = 0;
for(char c2 : arr){
if(c==c2){
if(!map.containsKey(c))
map.put(c, new ArrayList<Integer>());
map.get(c).add(i);
}
i++;
}
}
createSet(arr2, arr, set, map, 0, -1);
return set;
}
private static void createSet(char [] str1, char [] str2, Set<String> set,
Map<Character, List<Integer>> map, int str1Pos, int prevCharPos) {
if(str1Pos == str1.length-1) {
List<Integer> locations = map.get(str1[str1Pos]);
for(int i : locations){
if(i<=prevCharPos)
continue;
char [] clone = str2.clone();
clone[i]-=32;
set.add(new String(clone));
}
} else if(str1Pos < str1.length-1) {
List<Integer> locations = map.get(str1[str1Pos]);
for(int i : locations){
if(i<=prevCharPos)
continue;
char [] clone = str2.clone();
clone[i]-=32;
createSet(str1, clone, set, map, str1Pos+1, i);
}
}
}
}
Construct a map and find roots
Use BFS to traverse
public class EmployeeHierarchy {
public static void main(String[] args) throws IOException, URISyntaxException {
List<String> lines = Files.readAllLines(Paths.get(new URI("file:/home/ketav/Workspaces/careercup/Test/src/careercup/coding/EmployeeList.txt")));
Map<String, Set<String>> tree = new HashMap<>();
Set<String> employees = new HashSet<>();
Set<String> roots = new HashSet<>();
for(int i=1;i<lines.size();i++){
String arr[] = lines.get(i).split(" ");
if(!tree.containsKey(arr[0])){
tree.put(arr[0], new HashSet<>());
}
tree.get(arr[0]).add(arr[1]);
if(!employees.contains(arr[1])) {
employees.add(arr[1]);
}
if(!employees.contains(arr[0])){
roots.add(arr[0]);
} else {
roots.remove(arr[0]);
}
}
//thus roots contain root elements .. now you can use BFS (using queue to) to print employees at each level.
printBFS(tree, roots);
}
public static void printBFS(Map<String, Set<String>> graph, Set<String> roots){
Queue<String> queue = new LinkedList<>(roots);
Set<String> visitedNodes = new HashSet<>();
printBFS(graph, queue, visitedNodes);
}
private static void printBFS(Map<String, Set<String>> graph, Queue<String> queue,
Set<String> visitedNodes){
int size = queue.size();
if(size==0)
return;
for(int i=0; i<size; i++){
String name = queue.poll();
if(!visitedNodes.contains(name)){
System.out.print(name+" ");
if(graph.get(name)!=null)
queue.addAll(graph.get(name));
visitedNodes.add(name);
}
}
System.out.println("");
printBFS(graph, queue, visitedNodes);
}
}
following may be updated to meet ur requirements..
public class PatternMatcher {
public static void main(String[] args) {
String str = "This is a sample string";
String pattern = "Th*is +";
System.out.println(isMatchFound(str,pattern));
pattern = "a*This";
System.out.println(isMatchFound(str,pattern));
pattern = "*This"; //valid pattern
System.out.println(isMatchFound(str,pattern));
pattern = "+This"; //invalid pattern
System.out.println(isMatchFound(str,pattern));
}
public static boolean isMatchFound(String str, String pattern){
return isMatchFound(str, pattern, 0, 0);
}
private static boolean isMatchFound(String str, String pattern, int strInd, int patInd){
if(strInd < str.length()){
if(patInd==pattern.length()){
return true;
} else {
if(pattern.charAt(patInd)=='*'){
int i=patInd-1;
for(;i>=0;i--)
if(pattern.charAt(i)!='*' && pattern.charAt(i)!='+')
break;
if(i<0){
//return false;
return isMatchFound(str, pattern, strInd, patInd+1);
} else if(pattern.charAt(i)==str.charAt(strInd)){
return isMatchFound(str, pattern, strInd+1, patInd);
} else {
return isMatchFound(str, pattern, strInd, patInd+1); //match may have been found before, don't worry if its not found as well
}
} else if (pattern.charAt(patInd)=='+') {
int i=patInd-1;
for(;i>=0;i--)
if(pattern.charAt(i)!='*' && pattern.charAt(i)!='+')
break;
if(i<0){
return false;
//return isMatchFound(str, pattern, strInd, patInd+1);
}else if(pattern.charAt(i)==str.charAt(strInd)){
return isMatchFound(str, pattern, strInd+1, patInd);
} else if(pattern.charAt(i)==str.charAt(strInd-1)){
return isMatchFound(str, pattern, strInd, patInd+1); //cur str char still needs to match so not doing strInd+1
} else {
return isMatchFound(str, pattern, strInd, 0); //match not found, start pattern from 0
}
} else { //current pattern char not + nor *
if(pattern.charAt(patInd)==str.charAt(strInd)){
return isMatchFound(str, pattern, strInd+1, patInd+1);
} else {
if(patInd+1<pattern.length() && pattern.charAt(patInd+1)=='*'){
return isMatchFound(str, pattern, strInd, patInd+1); //match not found
} else {
return isMatchFound(str, pattern, strInd+1, 0); //match not found
}
}
}
}
} else {
if(patInd<pattern.length())
return false;
else
return true;
}
}
}
how about using quickSort's partition logic to find correct indexes?
/**
* 1> Find
* index where discrepancy starts - dStartIndex
* index where discrepancy ends - dEndIndex
*
* 2> From i=dStartEnd till dEndIndex (inclusive)
* find min element and its index
* find max element and its index
*
* 3> Find the true index where min element should be kept - using "partition" logic of quickSort - dRealStartIndex
* 4> Find the true index where max should be kept - dRealEndIndex
*
* 5> SubArray that needs to be sorted ranges from dRealStartIndex till dRealEndIndex (inclusive)
*
*/
public class MinSubArrayWithUnsortedValues {
public static void main(String[] args) {
//int a[] = {-1, 0, 4, 3, 2, 1, 7, 8, 9}; //[4,3,2,1]
//int a[] = {10, 15, 20, 30, 25, 40, 35, 45, 50, 60}; //[30, 25, 40, 35]
int a[] = {-1, 0, 4, 3, 2, 1, 7, 8, 9, -2}; //[-1,0,4,3,2,1,7,8,9,-2]
int dStartIndex=-1;
int dEndIndex=-1;
for(int i=0;i<a.length;i++){
if(i+1<a.length && a[i]>a[i+1]){
if(dStartIndex < 0){
dStartIndex=i;
} else {
dEndIndex = i+1;
}
}
}
int dMinValue = Integer.MAX_VALUE;
int dMinValueIndex=-1;
int dMaxValue = Integer.MIN_VALUE;
int dMaxValueIndex=-1;
for(int i=dStartIndex;i<=dEndIndex;i++){
if(dMinValue > a[i]){
dMinValue = a[i];
dMinValueIndex = i;
}
if(dMaxValue < a[i]){
dMaxValue = a[i];
dMaxValueIndex = i;
}
}
if(dMinValueIndex<0 || dMaxValueIndex<0)
return;
int dRealStartIndex = partition(a, dMinValueIndex);
int dRealEndIndex = partition(a, dMaxValueIndex);
for(int i=dRealStartIndex;i<=dRealEndIndex;i++){
System.out.print(a[i]+" ");
}
}
/**
* QuickSort partition without any real swapping
* @param arr
* @param randomIndex
* @return
*/
public static int partition(int []arr, int randomIndex){
int pivotValue = arr[randomIndex];
//swap(arr, randomIndex, arr.length-1);
int pivotRealIndex = 0;
for(int i=0;i<=arr.length-1;i++){ //quicksort condition - i<arr.length-1 - but we are not doing any swap so need to check till the end of the array
if(arr[i] < pivotValue && i!=randomIndex){ //shift less values on left hand side
//swap(arr, pivotRealIndex, i); //pivotRealIndex <= i
pivotRealIndex++;
}
}
//swap(arr, pivotRealIndex, arr.length-1);
return pivotRealIndex; //must return real start|end index
}
}
equals is little ambiguous when it comes to StringBuffer.. see the example
public static void main(String[] args) {
String s = new String("hello");
String s2 = s;
System.out.println("1>" + s.equals("hello") + " 2>" + s.equals(s2)
+ " 3>" + (s == s2) + " 4>" + (s == "hello"));
StringBuffer sb = new StringBuffer("hello");
StringBuffer sb2 = sb;
System.out.println("1>" + sb.equals("hello") + " 2>" + sb.equals(sb2)
+ " 3>" + (sb == sb2));
}
o/p:: 1>true 2>true 3>true 4>false
1>false 2>true 3>true
nice... binary search makes it faster than other linear(backward) search of exact position and stack pop out versions... just little modification.. your algo still needs to store array A before discarding few elements.. lets say arrayList<int[]>.. store into index 0 only if previous content length is less than current.. (like what swathi mentioned in her algo.. )
- kn January 12, 2012
- kn September 17, 2015