singhSahab
BAN USER- 0of 0 votes
AnswersFor a given array size is know but elements using index is not accessible. 2 given functions are below:
- singhSahab in United States
1. getIndexOfNthLargest(int n) // returns the index of nth largest number. Like for n=1 the index of largest element will be returned, for n=2 the index of 2nd largest number will be returned.
2. reverseArray(int i) // reverse the elements of the array from index 0 to i
How to sort the array in place?| Report Duplicate | Flag | PURGE
Goldman Sachs Developer Program Engineer Algorithm - 0of 0 votes
AnswersIn Excel sheet rows are marked using integer numbers like 1,2,3 but the columns are marked using characters. Like A, B and C.
- singhSahab in India
so here column 0 = A (assuming column starting with 0)
column 1 = B
column 25 = Z
column 26 = AA
column 100 = CW
Q. Write a program to give the string representation of column for given integer.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
I have given the logic, but they wanted complete working code.
Logic:
* For both node find all ancestors up to root. (ancestor = node's parent or parent's parent)
* Add ancestors in a 2 separate queues then find the first common node from both queue.
* OR we can add into 2 separate stacks and start popping nodes from both stack until we get different nodes.The last common node will be the answer.
My code initially failed for large number when more that 2 characters required for column name. Adding some test data to check the code.
A - Z will be represented by 0-25
AA - ZZ will create 26*26 = 676 more numbers.
so AA-ZZ will be from 26 - 701
Number - Column name
701 - ZZ
702 - AAA
703 - AAB
* Order of complexity was also asked for the code.
Assuming that question is about binary search tree, because there can't be a fixed strategy to add an element in a normal binary tree.
Basic Java implementation (wwithout delete operation):
public class BST {
private class Node {
private int value;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
private Node root; // root of BST
public void insert(int item) {
root = insert(root, item);
}
private Node insert(Node x, int item) {
if (x == null) {
return new Node(item);
}
if (item < x.value) {
x.left = insert(x.left, item);
} else if (item > x.value) {
x.right = insert(x.right, item);
}
return x;
}
public void inOrder() {
inOrder(root);
System.out.println();
}
private void inOrder(Node x) {
if (x == null) {
return;
}
inOrder(x.left);
System.out.print(x.value + " ");
inOrder(x.right);
}
public static void main(String[] args) {
BST t = new BST();
t.insert(5);
t.insert(2);
t.insert(1);
t.insert(3);
t.insert(6);
t.insert(7);
t.insert(4);
t.inOrder();
}
}
Java implementation of Queue using Linked List:
public class Queue {
// inner class for Node
private class Node {
private int item;
private Node next;
}
private int N; // number of elements in queue
private Node first;
private Node last;
public Queue() {
first = null;
last = null;
N = 0;
}
// check if queue is empty
public boolean isEmpty() {
return first == null;
}
// return the number of elements in queue
public int size() {
return N;
}
// return the first element of queue without removing it from queue
public int peek() {
if (isEmpty())
throw new RuntimeException("Queue underflow");
return first.item;
}
// add an element to queue
public void enqueue(int item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty())
first = last;
else
oldlast.next = last;
N++;
}
// remove the first element
public int dequeue() {
if (isEmpty())
throw new RuntimeException("Queue underflow");
int item = first.item;
first = first.next;
N--;
if (isEmpty())
last = null; // to avoid loitering
return item;
}
// string representation of Queue
public String toString() {
StringBuilder s = new StringBuilder();
Node n = first;
while (n != null) {
s.append(n.item + " ");
n = n.next;
}
return s.toString();
}
/**
* A test client.
*/
public static void main(String[] args) {
Queue q = new Queue();
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);
System.out.println(q);
q.dequeue();
q.dequeue();
System.out.println(q);
}
}
Thanks, corrected the question.
- singhSahab October 30, 2012