varun.me15
BAN USERI think there is no need of graph or tree. The question is asking minimum no of steps which is in worst case will be 3(three letter words: three bits to flip). Simple loop should work.
Suggestion and corrections welcomed :)
public class ChangeWord {
public static void main(String[] args) {
// TODO Auto-generated method stub
// cat -> dog : dat -> dot -> dog;
int steps = findMinimumStepsToChange("cat", "dog");
System.out.println(steps);
// pic -> cat : pic -> cic -> cac -> cat
int steps2 = findMinimumStepsToChange("pic", "cat");
System.out.println(steps2);
}
public static int findMinimumStepsToChange(String word1, String word2){
if("".equals(word1)||"".equals(word2))
return -1;
if(word1.equals(word2))return 0;
int steps = 0;
int charCount = 0;
for(int i=0;i<word1.length();i++){
if(word1.charAt(i) != word2.charAt(i)){
steps++;
}
}
return steps;
}
}
The minimum no of steps to reach cat to dog is three
cat -> dat -> dot -> dog
Can please someone explain why my answer was downvoted?
- varun.me15 March 30, 2015I think making a n-ary tree should work. Start by any node and Do BFS. If you encounter any node that already in the tree except its parent, that means that node is not critical.
- varun.me15 March 30, 2015public static String getCanonicalPath(String input){
if(input==null||input.trim().length()==0){
return null;
}
String[] path = input.split("/");
Stack<String> canonicalForm = new Stack<String>();
StringBuilder sb = new StringBuilder();
for(String token:path){
if(token.equals("..")){
if(!(canonicalForm.isEmpty())&&canonicalForm.peek()!=".."){
sb.append(canonicalForm.pop()+"/");
}
}else if(token.equals(".")){
System.out.println("Skipping .");
}else{
canonicalForm.push(token);
}
}
for(String token:canonicalForm){
sb.append(token+"/");
}
return sb.toString();
}
Please add more details about the question...the question is not clear....
- varun.me15 March 30, 2015It should be O(mn)
- varun.me15 March 30, 201527
- varun.me15 March 27, 201526
- varun.me15 March 27, 2015Using Hashmap to Save all the timeslots. Complexity should O(nlogn).
Assumptions: TimeSlots are always of same size.
package careerCup;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
public class CommanTimeSlot {
static HashMap<String,List<TimeSlot>> timeslots = new HashMap<String,List<TimeSlot>>();
public static void main(String[] args) {
// TODO Auto-generated method stub
//HashMap<String,List<TimeSlot>> timeslots = new HashMap<String,List<TimeSlot>>();
// friend 1
List<TimeSlot> timeSlotList = new ArrayList<TimeSlot>();
timeSlotList.add(new TimeSlot(8, 9));
timeSlotList.add(new TimeSlot(10, 11));
timeSlotList.add(new TimeSlot(16, 17));
timeSlotList.add(new TimeSlot(19, 20));
timeSlotList.add(new TimeSlot(21, 22));
timeslots.put("friend1",timeSlotList);
// friend 2
ArrayList<TimeSlot> timeSlotList2 = new ArrayList<TimeSlot>();
timeSlotList2.add(new TimeSlot(7, 8));
timeSlotList2.add(new TimeSlot(13, 14));
timeSlotList2.add(new TimeSlot(19, 20));
timeSlotList2.add(new TimeSlot(21, 22));
timeslots.put("friend2",timeSlotList2);
// friend 3
ArrayList<TimeSlot> timeSlotList3 = new ArrayList<TimeSlot>();
timeSlotList3.add(new TimeSlot(5, 6));
timeSlotList3.add(new TimeSlot(13, 14));
timeSlotList3.add(new TimeSlot(19, 20));
timeSlotList3.add(new TimeSlot(21, 22));
timeslots.put("friend3",timeSlotList3);
// friend 4
ArrayList<TimeSlot> timeSlotList4 = new ArrayList<TimeSlot>();
timeSlotList4.add(new TimeSlot(6, 7));
timeSlotList4.add(new TimeSlot(13, 14));
timeSlotList4.add(new TimeSlot(19, 20));
timeSlotList4.add(new TimeSlot(21, 22));
timeslots.put("friend4",timeSlotList4);
List<String> friendList = new ArrayList<String>();
friendList.add("friend1");
friendList.add("friend2");
friendList.add("friend3");
System.out.println(new TimeSlot(19,20).equals(new TimeSlot(19,20)));
List<TimeSlot> output = printFirstNCommonTimeslots(friendList , 1);
System.out.println(output.toString());
}
private static List<TimeSlot> getTimeSlots(String friend){
return timeslots.get(friend);
}
private static List<TimeSlot> printFirstNCommonTimeslots(
List<String> friends, int i) {
HashMap<TimeSlot, Integer> timeSlotMap = new HashMap<TimeSlot, Integer>();
List<TimeSlot> commanTimeSlot = new ArrayList<TimeSlot>();
int length = friends.size();
for(String friend:friends){
List<TimeSlot> timeSlotsforFriend = getTimeSlots(friend);
System.out.println(timeSlotsforFriend.toString());
for(TimeSlot ts: timeSlotsforFriend){
System.out.println(timeSlotMap.containsKey(ts));
if(!timeSlotMap.containsKey(ts)){
System.out.println(ts.toString());
System.out.println("Not Equals");
timeSlotMap.put(ts,1);
System.out.println("HS"+timeSlotMap.toString());
}else{
timeSlotMap.put(ts,timeSlotMap.get(ts)+1);
System.out.println(timeSlotMap.toString());
System.out.println("Equals");
if(timeSlotMap.get(ts)==length){
System.out.println("HS"+timeSlotMap.toString());
commanTimeSlot.add(ts);
System.out.println(ts.toString());
}
}
}
}
if(commanTimeSlot.size() > i){
Collections.sort(commanTimeSlot);
return commanTimeSlot.subList(0,i);
}else
return null;
}
}
private class TimeSlot implements Comparable {
int init;
int end;
public TimeSlot(int init, int end) {
super();
this.init = init;
this.end = end;
}
@Override
public String toString() {
return init + " " + end;
}
@Override
public int hashCode(){
return this.init;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
TimeSlot other = (TimeSlot) obj;
if (this.end != other.end)
return false;
if (this.init != other.init)
return false;
return true;
}
@Override
public int compareTo(Object arg0) {
TimeSlot ts = (TimeSlot) arg0;
if(this.init > ts.init){
return 1;
}else if(this.init < ts.init){
return -1;
}
return 0;
}
}
package careercup;
public class CC5716548811489280 {
public static int findZeros(int[] input,int count,int start,int end){
//System.out.println("Start"+ start);
//System.out.println("End"+ end);
if(start>end){
return count+1;
}
int mid = (end + start)/2;
//System.out.println("mid" + mid);
if(input[mid] == 0){
count = mid;
return findZeros(input,count, mid+1, end);
}else{
return findZeros(input, count,start, mid-1);
}
}
public static void main(String[] args){
int[] array = {0,0,0,0,0,0,1,1,1,1,1};
System.out.println(findZeros(array, 0,0, array.length - 1));
}
}
It should be either {1,2,3} and {5,6} if we are not considering the second occurance. else it should {1,2,3,9} and {5,6} ..??
- varun.me15 January 17, 2015package careercup;
public class CC5707979286380544 {
public static int getMaxGold(int[] gold,int maxGold,int turn,int startIndex,int endIndex){
if(startIndex >endIndex||startIndex < 0||endIndex > gold.length){
return maxGold;
}
if(turn == 0){
if(gold[startIndex] > gold[endIndex]){
maxGold+= gold[startIndex];
return getMaxGold(gold, maxGold, 1, ++startIndex, endIndex);
}else{
maxGold+= gold[endIndex];
return getMaxGold(gold, maxGold, 1, startIndex, --endIndex);
}
}else{
if(gold[startIndex] > gold[endIndex]){
return getMaxGold(gold, maxGold, 0, startIndex, --endIndex);
}else{
return getMaxGold(gold, maxGold, 0, ++startIndex, endIndex);
}
}
}
public static void main(String[] args){
int[] gold = {5,3,1,2,4};
System.out.println(getMaxGold(gold, 0, 0, 0, gold.length-1));
}
}
Using Multimap
package careercup;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import org.apache.commons.collections4.map.MultiValueMap;
public class CC6241017174949888 {
public static HashMap<String, Integer> finalScore(ArrayList<testResult> scores){
MultiValueMap<String, Integer> scoresList = new MultiValueMap<String,Integer>();
for(testResult score:scores){
scoresList.put(score.studentId,score.score);
}
System.out.println(scoresList.toString());
HashMap<String,Integer> finalScores = new HashMap<String,Integer>();
for(Entry result:scoresList.entrySet()){
ArrayList<Integer> mark = (ArrayList<Integer>) result.getValue();
Collections.sort(mark, Collections.reverseOrder());;
int finalSc = 0;
for(int i=0;i<5;i++){
finalSc += mark.get(i);
}
finalScores.put((String) result.getKey(), (finalSc/5));
}
return finalScores;
}
public static void main(String[] args){
ArrayList<testResult> testResults = new ArrayList<testResult>();
testResults.add(new testResult(45, "varun", "1"));
testResults.add(new testResult(40, "vikas", "1"));
testResults.add(new testResult(35, "sachin", "1"));
testResults.add(new testResult(20, "praveen", "1"));
testResults.add(new testResult(15, "nitish", "1"));
testResults.add(new testResult(56, "varun", "1"));
testResults.add(new testResult(68, "varun", "1"));
testResults.add(new testResult(44, "vikas", "1"));
testResults.add(new testResult(36, "sachin", "1"));
testResults.add(new testResult(25, "praveen", "1"));
testResults.add(new testResult(17, "nitish", "1"));
testResults.add(new testResult(43, "varun", "1"));
testResults.add(new testResult(42, "varun", "1"));
testResults.add(new testResult(48, "vikas", "1"));
testResults.add(new testResult(45, "sachin", "1"));
testResults.add(new testResult(70, "praveen", "1"));
testResults.add(new testResult(55, "nitish", "1"));
testResults.add(new testResult(75, "varun", "1"));
testResults.add(new testResult(85, "varun", "1"));
testResults.add(new testResult(30, "vikas", "1"));
testResults.add(new testResult(35, "sachin", "1"));
testResults.add(new testResult(10, "praveen", "1"));
testResults.add(new testResult(65, "nitish", "1"));
testResults.add(new testResult(75, "varun", "1"));
testResults.add(new testResult(45, "varun", "1"));
testResults.add(new testResult(46, "vikas", "1"));
testResults.add(new testResult(32, "sachin", "1"));
testResults.add(new testResult(78, "praveen", "1"));
testResults.add(new testResult(88, "nitish", "1"));
testResults.add(new testResult(90, "varun", "1"));
System.out.println(finalScore(testResults).toString());
}
}
package careercup;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
public class CC6241017174949888 {
public static HashMap<String, Integer> finalScore(ArrayList<testResult> scores){
HashMap<String,ArrayList<Integer>> scoresList = new HashMap<String,ArrayList<Integer>>();
for(testResult score:scores){
if(scoresList.containsKey(score.studentId)){
scoresList.get(score.studentId).add(score.score);
}else{
ArrayList<Integer> marks = new ArrayList<Integer>();
marks.add(score.score);
scoresList.put(score.studentId, marks);
}
}
HashMap<String,Integer> finalScores = new HashMap<String,Integer>();
for(Entry result:scoresList.entrySet()){
ArrayList<Integer> mark = (ArrayList<Integer>) result.getValue();
Collections.sort(mark);
int finalSc = 0;
for(int i=mark.size()-1;i>mark.size()-6;i--){
finalSc += mark.get(i);
}
finalScores.put((String) result.getKey(), (finalSc/5));
}
return finalScores;
}
public static void main(String[] args){
ArrayList<testResult> testResults = new ArrayList<testResult>();
testResults.add(new testResult(45, "varun", "1"));
testResults.add(new testResult(40, "vikas", "1"));
testResults.add(new testResult(35, "sachin", "1"));
testResults.add(new testResult(20, "praveen", "1"));
testResults.add(new testResult(15, "nitish", "1"));
testResults.add(new testResult(56, "varun", "1"));
testResults.add(new testResult(68, "varun", "1"));
testResults.add(new testResult(44, "vikas", "1"));
testResults.add(new testResult(36, "sachin", "1"));
testResults.add(new testResult(25, "praveen", "1"));
testResults.add(new testResult(17, "nitish", "1"));
testResults.add(new testResult(43, "varun", "1"));
testResults.add(new testResult(42, "varun", "1"));
testResults.add(new testResult(48, "vikas", "1"));
testResults.add(new testResult(45, "sachin", "1"));
testResults.add(new testResult(70, "praveen", "1"));
testResults.add(new testResult(55, "nitish", "1"));
testResults.add(new testResult(75, "varun", "1"));
testResults.add(new testResult(85, "varun", "1"));
testResults.add(new testResult(30, "vikas", "1"));
testResults.add(new testResult(35, "sachin", "1"));
testResults.add(new testResult(10, "praveen", "1"));
testResults.add(new testResult(65, "nitish", "1"));
testResults.add(new testResult(75, "varun", "1"));
testResults.add(new testResult(45, "varun", "1"));
testResults.add(new testResult(46, "vikas", "1"));
testResults.add(new testResult(32, "sachin", "1"));
testResults.add(new testResult(78, "praveen", "1"));
testResults.add(new testResult(88, "nitish", "1"));
testResults.add(new testResult(90, "varun", "1"));
System.out.println(finalScore(testResults).toString());
}
}
public static int tossDice(){
int bit1 = toss();
int bit2 = toss();
int bit3 = toss();
if(bit1==0&&bit2 == 0&&bit3==0){
return 1;
}else if(bit1 == 0&&bit2 == 0&&bit3==1){
return 2;
}else if(bit1 == 0&&bit2 == 1&&bit3==0){
return 3;
}
else if(bit1 == 0&&bit2 == 1&&bit3==1){
return 4;
}else if(bit1 == 1&&bit2 == 0&&bit3==0){
return 5;
}else if(bit1 == 1&&bit2 == 0&&bit3==1){
return 6;
}else{
return tossDice();
}
};
whats the effect of making mid.previous.next null?
- varun.me15 January 15, 2015
Choosing random pivot makes the probability of choosing a bad pivot(i.e O(n2)) less
- varun.me15 March 30, 2015