dheeraj2311
BAN USER- 0of 0 votes
AnswersThere is a 2d matrix and in each point there are some gold coins.
- dheeraj2311
Then starting from the bottom left point you have to collect the maximum number of points. The constraint is that you can only move in right and up direction.
Then asked me to optimize it
After that do it using recursion
Compare the two methods
Give a mathematical formula for this problem.| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Data Structures - 0of 0 votes
AnswersThis round was focused on DS only
- dheeraj2311
Reverse a link list
Gave me a link list in which loop is there. What will happen if we reverse such a kind of LL.
Detect loop in LL
Starting node at which loop is starting| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Linked Lists
package uber;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class StringAndDictionary {
Set<String> d = new HashSet<String>();
static int count = 0;
Node node = new Node();
public static void main(String[] args) {
// TODO Auto-generated method stub
StringAndDictionary sd = new StringAndDictionary();
String s = "appletablet";
sd.get(s);
System.out.println(count);
}
private void get(String s) {
d.add("apple");
d.add("tablet");
d.add("applet");
d.add("able");
d.add("t");
d.add("app");
d.add("let");
d.add("t");
Iterator<String> dr = d.iterator();
while (dr.hasNext()) {
insert(dr.next());
}
int i = 0;
int n = s.length();
find(s, i, n - 1);
}
private void find(String s, int l, int h) {
if (l == h+1) {
count++;
return;
}
Node temp = node;
int i = l;
while (i <= h && temp != null) {
temp = temp.nodes[s.charAt(i) - 'a'];
i++;
if(temp != null && temp.end){
find(s,i,h);
}
}
}
private void insert(String s) {
int i = 0;
int n = s.length();
Node temp = node;
while (i < n) {
if (temp.nodes[s.charAt(i) - 'a'] == null) {
temp.nodes[s.charAt(i) - 'a'] = new Node();
}
temp = temp.nodes[s.charAt(i) - 'a'];
i++;
}
temp.end = true;
}
}
class Node {
Node nodes[];
boolean end;
public Node() {
nodes = new Node[26];
for (int i = 0; i < 26; i++) {
nodes[i] = null;
end = false;
}
}
}
package com.test.coding;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Stack;
public class LookUp<T> {
Map<T, Integer> m;
List<T> list;
Stack<Node<T>> s;
int currIndex;
public LookUp() {
m = new LinkedHashMap<T, Integer>();
list = new ArrayList<T>();
s = new Stack<Node<T>>();
currIndex = 0;
}
void add(T val) {
if (list.size() > currIndex) {
list.set(currIndex, val);
} else {
list.add(currIndex, val);
}
Node<T> node = new Node<T>(val, currIndex);
s.push(node);
m.put(val, currIndex);
currIndex++;
System.out.println("add: " + list.toString());
}
void delete(T val) {
if (m.containsKey(val)) {
int elementIndex = m.get(val);
System.out.println("Index: " + val + " " + elementIndex);
m.remove(val);
list.set(elementIndex, list.get(currIndex - 1));
currIndex--;
Node<T> topNode = s.peek();
if (topNode.getIndex().equals(elementIndex)) {
s.pop();
}
}
System.out.println("delete: " + list.toString() + " curr index"
+ currIndex);
}
boolean contains(T val) {
if (m.containsKey(val)) {
return true;
}
return false;
}
T getRecent() {
if (!s.isEmpty()) {
return s.peek().getVal();
}
return null;
}
T getRandom() {
Random rand = new Random();
int randomIndex = rand.nextInt((currIndex - 0) ) + 0;
System.out.println("random index: " + randomIndex);
return list.get(randomIndex);
}
}
package com.test.coding;
public class Node<T> {
private T val;
private Integer index;
public Integer getIndex() {
return index;
}
public T getVal() {
return val;
}
public Node(T val2, int lastIndex) {
val = val2;
index = lastIndex;
}
}
public List<Integer> incrementNumber(List<Integer> list) {
List<Integer> ans = new ArrayList<Integer>();
int num = 0;
for (Integer i : list) {
num = (num + i) * 10;
}
num /= 10;
System.out.println(num);
num++;
String s = Integer.toString(num);
for (int i = 0; i < s.length(); i++) {
ans.add((s.charAt(i) - '0') % 10);
num /= 10;
}
return ans;
}
public String computeRelativePath(String path) {
String res = "";
StringTokenizer st = new StringTokenizer(path, "\\");
Stack<String> s = new Stack<String>();
while (st.hasMoreTokens()) {
String item = st.nextToken();
if (item.equals("..")) {
if (!s.isEmpty()) {
s.pop();
}
} else {
s.push(item);
}
}
Stack<String> s1 = new Stack<String>();
while(!s.empty()){
s1.push(s.pop());
}
while(!s1.empty()){
res += "\\" + s1.pop();
}
return res;
}
<pre lang="" line="1" title="CodeMonkey84234" class="run-this">#include<iostream.h>
using namespace std;
void make(string ans,int l,int a,int b){
if(a+b == l){
cout<<ans<<endl;
}
else if(a==b){
make(ans+'a'+'b',l,a+1,b+1);
if(a+b+2 < l)
make(ans+'a'+'a',l,a+2,b);
}
else {
make(ans+'b',l,a,b+1);
}
}
main(){
string ans = "";
int n;
cin>>n;
make(ans,n,0,0);
system("pause");
}
</pre><pre title="CodeMonkey84234" input="yes">4
abab
aabb
</pre>
This approach will not be correct. Using the approach of binary search, you will be able to find greater element than a[i], but that would not mean that it is the nearest maximum element for a[i].
- dheeraj2311 December 08, 2015