Nish
BAN USER- 0of 0 votes
Answerswrite a function which takes two parameter as numerator and denominator and returns the string form of (numerator/denominator)..if the fraction is repeating then the repeating no. should be in bracket.
- Nish
For ex- input: num=13, den=11
output: 1.[18]| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersAssume always the input will be between integer value 1-1000. Implement a data structure in which
- Nish
void Insert(int), void Delete(int), boolean IsTher(int), int FindAny()(returns any no. from previous input)..all are of O(1)..may use extra space if required.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThere is a linked list whose node has 3 fields, val, next pointer & random pointer...next pointer points to next node in the list and random pointer can point to any node in the list.Write an efficient function which takes such list and returns the copy/clone of that list.
- Nish| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Linked Lists - 0of 0 votes
AnswersThere are 'n' sorted linked list with avg. 'k' length, write an efficient function which return the head pointer of a single list which is the combination of all 'n' list and in sorted order.(Avoid using extra space)
- Nish| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Linked Lists
public class Pattern {
public static void main(String[] args){
int[] input={1,2,3,4,7,6,5,2,3,4,1,2}; //N
int startIndex=0;
int runs=10; //M
int no = 10; //K
int diff = 10; //L
while(startIndex+1<input.length){
if(input[startIndex]<no || input[startIndex+1]<no || Math.abs(input[startIndex]-input[startIndex+1])>diff )
continue;
Mode mode=getMode(input[startIndex],input[startIndex+1]);
System.out.print("{"+input[startIndex]+",");
++startIndex;
while(startIndex+1<input.length){
if(input[startIndex]>no || input[startIndex+1]>no || Math.abs(input[startIndex]-input[startIndex+1])>diff )
break;
if(mode==getMode(input[startIndex],input[startIndex+1])){
System.out.print(input[startIndex]+",");
++startIndex;
}
else
{
break;
}
}
System.out.println(input[startIndex]+"}");
--runs;
if(runs<=0)
return;
}
//System.out.println("Hi");
}
private static Mode getMode(int num1,int num2){
if(num1>num2)
return Mode.Decreasing;
else
return Mode.Increasing;
// return null;
}
}
enum Mode{Increasing,Decreasing}
<pre lang="" line="1" title="CodeMonkey79477" class="run-this">//Working java code to solve this problem
package com.arrayRotation;
class RotationOfArray {
public RotationOfArray(){
//Do nothing
}
private static void initialize(char arr[]){
char start= 'A';
for(int i=0;i<arr.length;i++){
arr[i] = start;
++start;
}
}
public static void main(String[] args){
char[] initArray = new char[5];
int rotationIndex=2;
initialize(initArray);
rotate(initArray,rotationIndex);
for(int i=0;i<initArray.length;i++){
System.out.print(initArray[i]+ " ");
}
}
public static void rotate(char arr[],int rotationIndex){
//First reverse the array completely
reverse(0,arr.length-1,arr);
//reverse the last rotation index length of the array
reverse(arr.length-rotationIndex,arr.length-1,arr);
//finally reverse first array length - rotation index
reverse(0,arr.length-rotationIndex-1,arr);
}
private static void reverse(int start, int end,char arr[]){
char temp;
while(start<end)
{
temp = arr[start];
arr[start]= arr[end];
arr[end]=temp;
++start;
--end;
}
}
}
</pre><pre title="CodeMonkey79477" input="yes">
</pre>
here the program traverse whole 2D array in clockwise manner starting from outer square or rectangle
time complexity: O(mxn) where m and n are rows and column respectively
//program to print a 2-D array spirally
package com.printspirally;
public class PrintSpirally {
private static int MAXROW=3;
private static int MAXCOL =3;
public static void main(String[]args)
{
int[][] arr =new int[MAXROW][MAXCOL];
int start=0;
for(int i=0;i<MAXROW;i++)
{
for(int j=0;j<MAXCOL;j++)
arr[i][j]=++start;
}
print(arr,0,MAXROW-1,0,MAXCOL-1);
}
private static void print(int[][] arr, int startRow, int endRow, int startCol,
int endCol) {
if((startRow<=endRow)&&(startCol<=endCol))
{
for(int p=startCol;p<=endCol;p++)
{
System.out.print(arr[startRow][p] + " ");
}
for(int p=startRow;p<=endRow;p++)
{
System.out.print(arr[p][endCol] + " ");
}
for(int p=endCol;p>=startCol;p--)
{
System.out.print(arr[endRow][p] + " ");
}
for(int p=endRow;p>=startRow;p--)
{
System.out.print(arr[p][startCol] + " ");
}
System.out.println("\n");
print(arr,startRow+1,endRow-1,startCol+1,endCol-1);
}
}
}
public class InorderIteration {
- Nish May 08, 2013private static Stack<Node> nodeStack= new Stack<Node>();
private static Set<Node> visited= new HashSet<Node>();
public static void main(String[] args){
Node head = createBST();
System.out.println("Inorder from recursion");
printInorder(head);
nodeStack.add(head);
System.out.println("\nInorder from iteration");
inorder();
}
private static void inorder() {
while(!nodeStack.empty()){
Node curr=nodeStack.pop();
if(visited.contains(curr)){ //to check if its backtracking
System.out.print(curr.getValue()+" ");
visited.remove(curr);
}else{
if(curr.getLeft()==null){
System.out.print(curr.getValue()+" ");
if(curr.getRight()!=null)
nodeStack.push(curr.getRight());
}
else{
if(curr.getRight()!=null)
nodeStack.push(curr.getRight()); //right first
nodeStack.push(curr); //parent
visited.add(curr); // to mark its visited
nodeStack.push(curr.getLeft());//left at last
}
}
}
}
public static Node addToBST(Node node, int value){
if(node==null){
node =new Node();
node.setValue(value);
return node;
}
if(node.getValue()>=value)
node.setLeft(addToBST(node.getLeft(),value));
else
node.setRight(addToBST(node.getRight(),value));
return node;
}
public static void printInorder(Node node){
if(node!=null){
printInorder(node.getLeft());
System.out.print(node.getValue()+" ");
printInorder(node.getRight());
}
}
public static Node createBST(){
Node head=addToBST(null,4);
head=addToBST(head,2);
head=addToBST(head,1);
head=addToBST(head,3);
head=addToBST(head,6);
head=addToBST(head,5);
head=addToBST(head,7);
head=addToBST(head,3);
head=addToBST(head,6);
head=addToBST(head,5);
return head;
}
public static class Node{
private Node left=null;
private Node right=null;
private int value;
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
}