inadram
BAN USER- 2 Answers Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
why FastRunner is LOOP_SIZE - K steps behind SlowRunner ?
- inadram September 30, 2014
why if we assign head to the slow runner ,then after k step head and fast runner meet each other at the beginning of the loop?| Flag | PURGE
how many possible number your can get where each digit of the possible number is four bigger/smaller than the next digit
if n =3
then 159 is one possible number because the second digit i.e 5 is bigger than 1 by four and also 9 is bigger than second digit i.e 5 by 4.
other possible numbers could be 151,161,171,181,191,162,173 etc
package main.Questions.ID5191526374178816;
import java.util.*;
public class Members {
Map<String, MyGroup> groupList = new HashMap<String, MyGroup>();
public Map<String, MyGroup> getMyGroupsList(Map<String, HashSet<String>> groupMembers) {
for (Map.Entry<String, HashSet<String>> groupMember : groupMembers.entrySet()) {
MyGroup myGroup = createMyGroup(groupMember.getKey());
findMyGroupMembers(groupMembers, groupMember, myGroup);
}
return groupList;
}
private void findMyGroupMembers(Map<String, HashSet<String>> groupMembers, Map.Entry<String, HashSet<String>> groupMember, MyGroup myGroup) {
Queue<HashSet<String>> subGroupMembersQueue = new LinkedList<HashSet<String>>();
HashSet<String> visited = new HashSet<String>();
subGroupMembersQueue.add(groupMember.getValue());
while (subGroupMembersQueue.size() > 0) {
HashSet<String> subGroupMembers = subGroupMembersQueue.remove();
for (String subGroupMember : subGroupMembers) {
if (isaGroup(groupMembers, subGroupMember)) {
if (!visited.contains(subGroupMember)) {
visited.add(subGroupMember);
subGroupMembersQueue.add(groupMembers.get(subGroupMember));
}
MyGroup subMyGroup = createMyGroup(subGroupMember);
subMyGroup.MemberOf.put(myGroup.Identity, myGroup);
groupList.put(subMyGroup.Identity, subMyGroup);
myGroup.Members.put(subMyGroup.Identity, subMyGroup);
} else {
myGroup.Users.add(subGroupMember);
}
}
}
groupList.put(myGroup.Identity, myGroup);
}
private boolean isaGroup(Map<String, HashSet<String>> groupMembers, String subGroupMember) {
return groupMembers.containsKey(subGroupMember);
}
private MyGroup createMyGroup(String key) {
if (!groupList.containsKey(key)) {
MyGroup myGroup = new MyGroup(key);
groupList.put(key, myGroup);
}
return groupList.get(key);
}
}
git.io/vOnjm -- source
git.io/vOnj8 -- test
public class ArrayAsInteger {
public int[] increment(int[] array) {
int[] incrementedArray = incrementByOne(array, array.length - 1);
return (array[0] < 10) ? incrementedArray : extendedBoundary(array.length + 1);
}
private int[] extendedBoundary(int length) {
int[] array = new int[length];
array[0] = 1;
return array;
}
private int[] incrementByOne(int[] array, int i) {
array[i] = array[i] + 1;
if (array[i] >= 10 && i > 0) array[i] = array[i] % 10;
else return array;
return incrementByOne(array, i - 1);
}
}
git.io/vYLy8 -- source
git.io/vYLyL -- test
it use O(K) where k is the number of ".."
public class RelativePath {
public String normalise(String path) {
path = removeCurrentDirectorySign(path);
return removeParentDirectorySign(path);
}
private String removeParentDirectorySign(String path) {
String[] pathArray =path.split("\\\\.\\.");
StringBuilder pathBuilder = new StringBuilder();
for (String aPathArray : pathArray) {
if (pathBuilder.length()>0) pathBuilder.delete(pathBuilder.lastIndexOf("\\"), pathBuilder.length());
pathBuilder.append(aPathArray);
}
return pathBuilder.toString();
}
private String removeCurrentDirectorySign(String path) {
return path.replace("\\.\\", "\\");
}
}
http://git.io/vYvmv - source
http://git.io/vYvqW - test
Thanks for your response, I can understand that when the slow runner is k step behind fast runner and when they finally meet the slow runner is k steps away from home.
But I am still struggling to understand why "If you go counterclockwise from SlowRunner to FastRunner, it would be LOOPSIZE-K."
and why they always meet at exactly "LOOPSIZE-K"
using recursion
source - git.io/vOArQ
- inadram August 07, 2015test - git.io/vOAom