krupen.ghetiya
BAN USERSolution using recursion and iteration both:
class Main {
static Node head;
public static void main(String[] args) {
Node root = new Node(1);
Node n1 = new Node(2);
Node n2 = new Node(3);
Node n3 = new Node(4);
Node n4 = new Node(5);
Node n5 = new Node(6);
root.next=n1;n1.next=n2;n2.next=n3;n3.next=n4;n4.next=n5;
printll(root);
head=root;
//iterative
Node currnode = root,prevnode=null,nextnode=null;
while(currnode!=null){
nextnode=currnode.next;
currnode.next=prevnode;
prevnode=currnode;
currnode=nextnode;
head =prevnode;
}
printll(head);
//recursive
reverse(head);
printll(head);
}
public static void printll(Node root){
System.out.println("");
while(root!=null){
System.out.print(" "+root.data);
root=root.next;
}
}
public static void reverse(Node root){
if(root.next==null) {
head=root;
return;}
reverse(root.next);
Node n = root.next;
n.next=root;
root.next=null;
}
}
class Node{
int data;
Node next;
public Node(int d){
data=d;
}
}
Time complexity O(n2) i.e. n square
Space complexity O(n)
Solution using simple recursion to find distance from each house to target:
import java.util.*;
class Main {
static char[][] arr = {{'h','_','_','_'},{'_','t','_','t'},{'_','h','t','h'},{'t','h','_','t'}};
static int[][] trav = new int[arr.length][arr.length];
static int[][] distances = new int[arr.length][arr.length];
static int finali=1,finalj=2; //position to find paths from
public static void main(String[] args) {
for(int i=0;i<arr.length;i++){
//init traversed and distances arrays
for(int k=0;k<distances.length;k++){
Arrays.fill(distances[k],Integer.MAX_VALUE);
Arrays.fill(trav[k],0);
}
for(int j=0;j<arr.length;j++){
if(arr[i][j]=='h'){
trav[i][j]=1;
System.out.println("i:"+i+"|j:"+j+"|dist:"+finddistance(i,j,0));
}
}
}
}
public static int finddistance(int r, int c, int sum){
//reached point
if(r==finali && c==finalj)return sum;
//right
int rightsum=Integer.MAX_VALUE;
if((c+1)<arr.length && arr[r][c+1]!='t' && trav[r][c+1]!=1){
trav[r][c+1]=1;
rightsum=finddistance(r,c+1,sum+1);
}
//bottom
int bottomsum=Integer.MAX_VALUE;
if((r+1)<arr.length && arr[r+1][c]!='t'&& trav[r+1][c]!=1){
trav[r+1][c]=1;
bottomsum=finddistance(r+1,c,sum+1);
}
//left
int leftsum=Integer.MAX_VALUE;
if((c-1)>=0 && arr[r][c-1]!='t'&& trav[r][c-1]!=1){
trav[r][c-1]=1;
leftsum=finddistance(r,c-1,sum+1);
}
//top
int topsum=Integer.MAX_VALUE;
if((r-1)>=0 && arr[r-1][c]!='t'&& trav[r-1][c]!=1){
trav[r-1][c]=1;
topsum=finddistance(r-1,c,sum+1);
}
// System.out.println("r"+r+"|c:"+c+"| rightsum:"+rightsum+"|bottomsum:"+bottomsum+"|leftsum:"+leftsum+"|topsum:"+topsum);
return Math.min(Math.min(rightsum,bottomsum),Math.min(leftsum,topsum));
}
}
Input:
H _ _ _
_ T X T
_ H T H
T H _ T
X -> target
Output:
i:0|j:0|dist:3
i:2|j:1|dist:6
i:2|j:3|dist:2147483647
i:3|j:1|dist:7
Time complexity O(n2) i.e. n square
Space complexity O(n) - to store which nodes are traversed.
Solution using simple recursion:
import java.util.*;
class Main {
static int[][] arr = {{1,2,0},{2,-1,2},{1,-2,2}};
static int[][] trav = new int[arr.length][arr.length];
public static void main(String[] args) {
int sumtofind = 5;
boolean found =false;
for(int i=0;i<arr.length;i++){
found = false;
for(int j=0;j<arr.length;j++){
//refill for traversal
for(int k=0;k<arr.length;k++){
Arrays.fill(trav[k],0);
}
found = findsum(i,j,arr[i][j],sumtofind);
if(found){
//System.out.println("ans:"+found);
break;
}
}
if(found)break;
}
System.out.println("ans:"+found);
}
public static boolean findsum(int r,int c,int currsum,int sum){
//right
if((c+1)<arr.length && trav[r][c+1]!=1){
int newcurrsum=currsum+arr[r][c+1];
trav[r][c+1]=1;
if(newcurrsum==sum)return true;
return findsum(r,c+1,newcurrsum,sum);
}
//bottom
if((r+1)<arr.length && trav[r+1][c]!=1){
int newcurrsum=currsum+arr[r+1][c];
trav[r+1][c]=1;
if(newcurrsum==sum)return true;
return findsum(r+1,c,newcurrsum,sum);
}
return false;
}
}
Input:
1 2 0
2 -1 4
1 -2 2
sum=5
output:
ans:true
Time complexity O(n);
Space complexity O(n);
Solution using Trie data structure:
import java.util.*;
class Main {
public static void main(String[] args) {
TrieNode root = new TrieNode('*');
String[] dictionary = {"i","like","face","book","facebook"} ;
String input = "ilikefacebook";
for(String s:dictionary){
root.addString(s);
}
findans(root,input);
}
public static void findans(TrieNode root,String inp){
int counter=0;
TrieNode itr = root;
int i=0;
while(i<inp.length()-1){
if((itr.children).get(inp.charAt(i))!=null){
itr=(itr.children).get(inp.charAt(i));
i++;
}else{
counter++;
itr=root;
}
}
System.out.println("ans:"+counter);
}
}
class TrieNode {
HashMap<Character,TrieNode> children = new HashMap<>();
Character c;
boolean terminates;
public TrieNode(Character cc){
c=cc;
}
public void addString(String s){
if(s==null || s.length()==0)return;
Character nextchar = s.charAt(0);
if(children.get(nextchar)==null){
TrieNode n = new TrieNode(nextchar);
children.put(nextchar,n);
}
(children.get(nextchar)).addString(s.substring(1));
}
}
Output:
ans:2
For diameter:
class Main {
public static void main(String[] args) {
Node root = new Node(1);
Node l1 = new Node(2);
Node r1 = new Node(3);
Node l2 = new Node(4);
Node r2 = new Node(5);
Node l3 = new Node(6);
Node l4 = new Node(7);
Node l5 = new Node(8);
root.left=l1;
root.right=r1;
l1.left=l2;
l1.right=r2;
l2.left=l3;
r1.left=l4;
l3.right=l5;
System.out.println("ans: "+finddia(root));
}
public static int finddia(Node n){
int leftmax = maxheight(n.left);
int rightmax = maxheight(n.right);
return leftmax+rightmax+1;
}
public static int maxheight(Node n){
if(n==null)return 0;
int max = Math.max(maxheight(n.left),maxheight(n.right));
return max+1;
}
}
class Node {
int data;
Node left,right;
public Node(int d){
data=d;
}
}
A simple BFS using queue should do the job. If a node has no children to be added to the queue, we have reached the solution.
- krupen.ghetiya July 26, 2017Calculate distance from each of the 'g' to each of the 'o' (avoiding 'w' and 'g') and store the minimum distance in the result matrix. Update result matrix point if new distance is lower than stored one. Result matrix is initialised with Integer.MAX_VALUE
Below is the working code:
import java.util.*;
class Main {
static char[][] matrix = { { 'o', 'o', 'o', 'g', 'o' }, { 'o', 'o', 'w', 'o', 'o' }, { 'o', 'g', 'o', 'o', 'w' },
{ 'o', 'w', 'g', 'o', 'o' }, { 'w', 'o', 'o', 'o', 'g' } };
static int[][] result = new int[matrix.length][matrix.length];
public static void main(String[] args) {
for(int i=0;i< matrix.length;i++){
Arrays.fill(result[i],Integer.MAX_VALUE);
}
for(int i=0;i< matrix.length;i++){
for(int j=0;j< matrix.length;j++){
if(matrix[i][j]=='g'){
//calc distances
calcdistances(i,j,0);
}
}
}
//to replace Integer.MAX_VALUE with 'g' and 'w'
String[][] display = new String[matrix.length][matrix.length];
for(int i=0;i< matrix.length;i++){
for(int j=0;j< matrix.length;j++){
if(matrix[i][j]=='g'){
display[i][j]="g";
}else if(matrix[i][j]=='w'){
display[i][j]="w";
}else{
display[i][j]=result[i][j]+"";
}
}
}
for(int i=0;i< display.length;i++){
System.out.println(Arrays.toString(display[i]));
}
}
public static void calcdistances(int r, int c, int currDist){
int cleft = c-1;
if(cleft>=0 && matrix[r][cleft]!='w'&& matrix[r][cleft]!='g') {
if(result[r][cleft]>(currDist+1)){
result[r][cleft] = currDist+1;
calcdistances(r,cleft,result[r][cleft]);
}
}
int cright = c+1;
if(cright<result.length && matrix[r][cright]!='w'&& matrix[r][cright]!='g' ){
if(result[r][cright]>(currDist+1)){
result[r][cright] = currDist+1;
calcdistances(r,cright,result[r][cright]);
}
}
int rtop = r-1;
if(rtop>=0 && matrix[rtop][c]!='w'&& matrix[rtop][c]!='g') {
if(result[rtop][c]>(currDist+1)){
result[rtop][c] = currDist+1;
calcdistances(rtop,c,result[rtop][c]);
}
}
int rbottom = r+1;
if(rbottom<result.length && matrix[rbottom][c]!='w'&& matrix[rbottom][c]!='g') {
if(result[rbottom][c]>(currDist+1)){
result[rbottom][c] = currDist+1;
calcdistances(rbottom,c,result[rbottom][c]);
}
}
}
}
Output:
[3, 2, 1, g, 1]
[2, 1, w, 1, 2]
[1, g, 1, 2, w]
[2, w, g, 1, 1]
[w, 2, 1, 1, g]
To show friends or friends, build Graph with edges between relations.
Get the node with the id to be searched and traverse children. Mark nodes as 'traversed' once printed to prevent infinite loop.
Here is the code:
import java.util.*;
class Main {
public static void main(String[] args) {
List<List<Integer>> relations = new ArrayList<>();
relations.add(Arrays.asList(1, 2));
relations.add(Arrays.asList(2, 3));
relations.add(Arrays.asList(5, 6));
relations.add(Arrays.asList(1, 3));
relations.add(Arrays.asList(2, 4));
relations.add(Arrays.asList(4, 12));
printFriendCircle(relations.iterator(), 1);
}
public static void printFriendCircle(Iterator<List<Integer>> itr,int id){
Graph graph = new Graph();
while(itr.hasNext()){
List<Integer> edge = itr.next();
graph.addEdge(edge.get(0),edge.get(1));
}
Node root=graph.nodes.get(id);
printfriends(root);
}
public static void printfriends(Node n){
if(n==null)return;
for(Node child: n.children){
if(!child.traversed){
System.out.println(child.data+ " ");
child.traversed=true;
printfriends(child);
}
}
}
}
class Graph{
HashMap<Integer,Node> nodes = new HashMap<>();
public void addNode(int d){
Node n = new Node(d);
nodes.put(d,n);
}
public void addEdge(int a,int b){
if(nodes.get(a)==null)addNode(a);
if(nodes.get(b)==null)addNode(b);
(nodes.get(a).children).add(nodes.get(b));
(nodes.get(b).children).add(nodes.get(a));
}
}
class Node{
boolean traversed = false;
int data;
List<Node> children = new ArrayList<>();
public Node(int d){
data=d;
}
}
inp1 divided by inp2:
int inp1 = 32;
int inp2 = -8;
int a = Math.abs(inp1);
int b = Math.abs(inp2);
int rem = a;
int ans =0;
if(b>0 && a>0){
while(rem>=b){
rem-=b;
ans++;
}
}
if((inp1<0 && inp2>0) ||(inp1>0 && inp2<0) ){
ans=-ans;
}
System.out.println("ans:"+ans);
a divided by b:
// a/b
int a = 41;
int b = 5;
int rem = a;
int ans =0;
while(rem>=b){
rem-=b;
ans++;
}
System.out.println("ans:"+ans+"|rem="+rem);
Working solution in Java. Array elements are added one after the other so can be fed from other machines as well.
import java.util.*;
class Main {
static PriorityQueue<Integer> minHeap = new PriorityQueue<>();
static PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a,Integer b){
return b.compareTo(a);
}
});
public static void main(String[] args) {
System.out.println("Hello, world!");
int[] arr = {4,3,1,8,4,7,6};
for(int i: arr){
findmedian(i);
}
}
public static void findmedian(int x){
if(maxHeap.isEmpty() || x<maxHeap.peek()){
maxHeap.add(x);
}else{
minHeap.add(x);
}
rebalance();
printmedian();
}
public static void rebalance(){
if(Math.abs(minHeap.size()-maxHeap.size())>1){
PriorityQueue<Integer> biggerHeap = (minHeap.size()>maxHeap.size())?minHeap:maxHeap;
PriorityQueue<Integer> smallerHeap = (minHeap.size()>maxHeap.size())?maxHeap:minHeap;
int element = biggerHeap.remove();
smallerHeap.add(element);
}
}
public static void printmedian(){
PriorityQueue<Integer> biggerHeap = (minHeap.size()>maxHeap.size())?minHeap:maxHeap;
PriorityQueue<Integer> smallerHeap = (minHeap.size()>maxHeap.size())?maxHeap:minHeap;
if(biggerHeap.size()==smallerHeap.size()){
float median = (float)(biggerHeap.peek()+smallerHeap.peek())/2;
System.out.println("ans:"+median);
}else{
System.out.println("ans:"+biggerHeap.peek());
}
}
}
This problem is almost same as "Running Median" problem. It can be found in book "Cracking the coding interview 6th ed: - Gayle Laakmann". You will need 1 max heap and 1 min heap. When inserting, keep both of them balanced. The median will be the average of top element of both the heaps if they both have same number of elements, otherwise it will be the top element of the heap with more elements.
- krupen.ghetiya July 22, 2017Assuming it has no zero, if it has zero, remove zeroes in O(n). Should be simple to implement.
int[] arr = {-4, -3, -2, -1, 1, 1, 2, 3};
int[] newarr = new int[arr.length];
int j = 0, i = 0;
for (i = 0; i < arr.length - 2; i++) {
if (arr[i] < 0 && arr[i + 1] < 0) {
newarr[j++] = arr[i] * arr[i + 1];
i++;
} else {
newarr[j++] = arr[i];
}
}
while (i < arr.length) {
newarr[j++] = arr[i++];
}
System.out.println("ans: new: " + Arrays.toString(newarr));
Arrays.sort(newarr);
int leftover = 0, startIndex = 0,count_ones=0;
int k = 0;
for (int q = 0; q < newarr.length; q++) {
if (newarr[q] <= 0) {
startIndex++;
leftover += newarr[q];
}
if (newarr[q]==1){
count_ones++;
}
}
System.out.println("ans: startIndex: " + startIndex+" |left="+leftover+" |count_ones="+count_ones);
int[] input = new int[newarr.length - startIndex-count_ones];
System.arraycopy(newarr, startIndex+count_ones, input, 0, newarr.length - startIndex-count_ones);
System.out.println("ans: input: " + Arrays.toString(input));
//int maxsum= findsum(arr,0,arr[0]);
while(count_ones!=0){
input[0]+=1;
Arrays.sort(input);
count_ones--;
}
System.out.println("ans: new input: " + Arrays.toString(input));
int ans=input[0];
for(int m = 1;m<input.length;m++){
ans*=input[m];
}
ans-=leftover;
System.out.println("ans:"+ans);
RepEshikaLopez, general assistant at MMSS
Dedicated and reliable general assistant with background in and strong knowledge of secretarial and administrative principles. Capable of providing direct ...
Same solution as given by Florent but in Java:
- krupen.ghetiya July 27, 2017