Prateek
BAN USERTime Complexity: O(n)
When some node is visted then compute net danger rank(NDR) and also add current node individual rank in the friend node net danger rank(NDR) then remove current node from the friendslist of friend .
for eg: if A has friends B and C
then acc to transitivity B also has friend A......
When you visit A then compute NDR of A with the help of its friends and also add A's IDR in B's NDR and remove A node from B's Friend List. So need of visiting A again while computing NDR for B.
public class PrisionerVO {
private int idr;
private int ndr;
private List<Character> friendList;
public int getNdr() {
return ndr;
}
public void setNdr(int ndr) {
this.ndr = ndr;
}
public int getIdr() {
return idr;
}
public void setIdr(int idr) {
this.idr = idr;
}
public List<Character> getFriendList() {
return friendList;
}
public void setFriendList(List<Character> friendList) {
this.friendList = friendList;
}
@Override
public String toString() {
return "\tIndividual Danger Rank:"+ idr +"\nNet Danger Rank:" + ndr+ "\nFriend List:"+ friendList+"\n---------------\n\n";
}
}
public Character computerMaxDangerRank(Map<Character,PrisionerVO> prisionerMap){
Set<Character> keySet = prisionerMap.keySet();
int maxDR = 0;
Character maxDRPrisioner = null;
//key is prisionerName
for(Character key:keySet){
PrisionerVO currPrisioner = prisionerMap.get(key);
List<Character> friendList = currPrisioner.getFriendList();
//idr is individual danger rank
int idr = currPrisioner.getIdr();
//ndr is net danger rank of a prisioner
int ndr = idr;
if(friendList!=null && friendList.size()!=0)
{
for(Character friend:friendList){
PrisionerVO friendPrisioner = prisionerMap.get(friend);
friendPrisioner.setNdr(friendPrisioner.getNdr()+idr);
//adding friend idr current ndr
ndr= ndr + friendPrisioner.getIdr();
//removing the current node from the friends list
friendPrisioner.getFriendList().remove(key);
//i++;
}
}
ndr = ndr + currPrisioner.getNdr();
currPrisioner.setNdr(ndr);
if(ndr>maxDR){
maxDR=ndr;
maxDRPrisioner = key;
}
}
return maxDRPrisioner;
}
Java
Complexity: O(n)
public class SumOfLeftEqualsSumofRight {
public static void main(String[] args) {
int arr[] = {-1, 100, 1, 98, 1};
SumOfLeftEqualsSumofRight sumOfLeftEqualsSumofRight = new SumOfLeftEqualsSumofRight();
int totalSum = getSum(arr);
System.out.println(sumOfLeftEqualsSumofRight.getElementWithEqualSum(arr,totalSum));
}
public static int getSum (int []arr){
int sum=0;
for(int curr:arr){
sum=sum+curr;
}
return sum;
}
public int getElementWithEqualSum(int arr[], int sum){
if (arr == null || arr.length == 0)
return -1;
int leftTotal = 0;//arr[0];
int rightTotal = sum-arr[0];
for(int i=1;i<arr.length;i++){
leftTotal = leftTotal + arr[i-1];
rightTotal = rightTotal - arr[i];
if(leftTotal==rightTotal){
return i;
}
}
return -1;
}
}
Java Code
Complexity: O(mlogn)
public class ZerosOnesIn2DArray {
public static void main(String[] args) {
int arr[][] = {{0,0,0,1},{0,1,1,1},{1,1,1,1},{0,0,1,1}};
System.out.println(new ZerosOnesIn2DArray().getMaxOnesRow(arr));
}
public int getMaxOnesRow(int[][] arr){
int row = arr.length;
int col = arr[0].length;
int temp[]=arr[0];
int maxOnesLoc = binarySearch(arr[0], 0, col, 1);
int maxOnesRow = 0;
for(int i=1;i<row;i++){
if(arr[i][maxOnesLoc]==1){
int currOnesLoc = binarySearch(arr[i], 0, maxOnesLoc, 1);
if(currOnesLoc<maxOnesLoc){
maxOnesLoc = currOnesLoc;
maxOnesRow = i;
}
}
}
return maxOnesRow;
}
public int binarySearch(int []arr, int low, int high, int val)
{
if(high<low){
return -1;
}
int mid =(low+high)/2;
int output = 0;
if(arr[mid]<val){
low = mid+1;
output =binarySearch(arr, low, high, val);
}
else if(arr[mid]>val){
high = mid-1;
output =binarySearch(arr, low, high, val);
}
else{
if(mid!=0 && arr[mid-1]==val){
high = mid-1;
output =binarySearch(arr, low, high, val);
}
else{
output = mid;
}
}
return output;
}
}
Java Code
Verified
import java.util.ArrayList;
import java.util.List;
public class Dummy2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
//For eg. "Today is the day" -> "Today ishe ". Also give test cases.
String string = "Today is the day";
alterString(string);
}
private static void alterString(String string) {
int length = string.length(),i=0;
List<Character> list = new ArrayList<Character>();
char c,orig;
while(i<length){
c = string.toLowerCase().charAt(i);
orig = string.charAt(i);
if(!list.contains(c)){
list.add(c);
System.out.print(orig);
}
else
list.remove(Object.class.cast(c));
i++;
}
}
}
Java Code
Complexity O(n)
public class Dummy1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
List<Integer> list = null;
list = createList();
System.out.println("Input Data: "+list);
applyPattern(list);
System.out.println("Output Data: "+list);
}
public static List<Integer> createList(){
List<Integer> list = new ArrayList<Integer>();
int limit = 100;
int i =0;
while(i<limit){
list.add((int) (Math.random()*10000));
i++;
}
return list;
}
private static void applyPattern(List<Integer> list) {
int i = 0;
int limit = list.size();
int var1=0,var2=0;
while(i<limit-1){
int j=i+1;
if(i%2==0){
var1 = list.get(i);
var2 = list.get(j);
if(var1>var2)
{
list.set(i, var2);
list.set(j, var1);
}
}
else{
var1 = list.get(i);
var2 = list.get(j);
if(var1<var2)
{
list.set(j, var1);
list.set(i, var2);
}
}
i++;
}
}
}
Time Complexity: O(n)
When some node is visted then compute net danger rank(NDR) and also add current node individual rank in the friend node net danger rank(NDR) then remove current node from the friendslist of friend .
for eg: if A has friends B and C
then acc to transitivity B also has friend A......
When you visit A then compute NDR of A with the help of its friends and also add A's IDR in B's NDR and remove A node from B's Friend List. So need of visiting A again while computing NDR for B.
- Prateek February 04, 2015