.·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º>
BAN USERI can accept failure, everyone fails at something. But I can't accept not trying
¡Viva Mexico Cabrones !
- 0of 0 votes
AnswersDesign a musical jukebox using object-oriented principles
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - -6of 6 votes
AnswersModify the following code to add a row number for each line is printed
public class Test { public static void main(String [] args){ printParenthesis(3); } public static void printParenthesis(int n){ char buffer[] = new char[n*2]; printP(buffer,0,n,0,0); } public static void printP(char buffer[], int index, int n, int open, int close){ if(close == n){ System.out.println(new String(buffer)); }else{ if(open > close){ buffer[index] = ']'; printP(buffer, index+1, n, open, close+1); } if(open < n ){ buffer[index] = '['; printP(buffer,index+1,n,open+1,close); } } } }
Expected Output:
1.[][][] 2.[][[]] 3.[[]][] 4.[[][]] 5.[[[]]]
What changes needs to be done to accomplish the output expected?
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a BST, replace each node with the sum of the values of all the nodes that are greater than that node. Only constraint being that I was not allowed to use any global or static variable.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in United States| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiving a number T, print out all possible ways to get to T.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in United States
For example
T= 5
1 + 1 + 1 +1 +1
2 + 1 + 1 + 1
3 + 1 +1
2 + 2 + 1
4 + 1
3 + 3
Note that, 3 + 2 is equal than 2 + 3, so you don´t have to print both cases.
What is the time complexity? ( VERY IMPORTANT TO ELABORATE ) Brute force is not allow.| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 1of 1 vote
AnswersSuppose that you been offered the opportunity to invest in the Volatile Chemical
Corporation. Like the chemicals the company produces, the stock price of the
Volatile Chemical Corporation is rather volatile. You are allowed to buy one unit
of stock only one time and then sell it at a later date, buying and selling after the
close of trading for the day. To compensate for this restriction, you are allowed to
learn what the price of the stock will be in the future. Your goal is to maximize
your profit.Day 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Price 100 113 110 85 105 102 86 63 81 101 94 106 101 79 94 90 97 Change 0 13 -3 - 25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7
find the subset of days where the profit is the highest.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in United States
What is the time complexity?| Report Duplicate | Flag | PURGE
Algorithm - 1of 1 vote
AnswersSerling Enterprises buys long steel roads and cuts them into shorter rods, which it then sells. Each cut is free. The management of Serling Enterprises charges for a road of length i inches. Road lengths are always an integral number of inches.
The rod-cutting problem is the following: Given a rod of length n and a table of prices V for {1,2...n} determine the maximum revenue Rn obtain by cutting up the road and selling the pieces.
Table:
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in United Stateslength i 1, 2, 3 ,4 ,5 , 6 , 7 , 8 , 9, 10 price Pi 1, 5, 8, 9, 10,17,17,20,24,30
| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 1of 1 vote
AnswersImplement a sudoku solution verifier function. The rules for sudoku is this:
You have a 9 by 9 board. This board is divided into nine rows, nine columns, and nine 3x3 blocks. In a solved puzzle, every row, every column, and every 0 block has to contain each of the digits from 1 to 9. This is an example of a solved puzzle:
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in United States248|395|716 571|628|349 936|741|582 ---+---+--- 682|539|174 359|174|628 714|862|953 ---+---+--- 863|417|295 195|286|437 427|953|861
| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersDesign an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º>| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 0of 0 votes
AnswersAssume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º>| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists).
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º>| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a directed graph, design an algorithm to find out whether there is a route be-
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in United States for Oracle
tween two nodes.
What is the complexity of the algorithm?| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 0of 0 votes
AnswersSuppose you have all the info of all the restaurants on the world.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in United States
1) How would you store all the information ?
2) Get the top 10 recommendation near me. ( using your current position)
explain design and algorithm complexity analysis| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 1of 1 vote
AnswersImagine you have the information of all the people from the beginning of the world. How would you know who is the first common ancestor of 2 people.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in United States
Let say, You have a reference to yourself and I give you a reference to Albert Einstein, I want to know who is your common ancestor| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow would you return/get/print/know the longest Unique word from a text (book, newspaper, lot of data) efficiently ?
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> in Mexico for Oracle Data Miner
In other words, find the word that only occurs 1 time from a big text.| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm
//Assume you have a method isSubstring which checks if one word is a substring of another.
// Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring i.e., waterbottle is a rotation of erbottlewat
// COMPLEXITY O ( n^2 ) + O (n + m) = O ( n^2 )
public static boolean isRotation(char str1 [], char str2[] )
{
return isSubstring(append(str2,str2),str1);
}
// COMPLEXITY O ( n + m )
public static char[] append(char str1[], char str2[]){
char result[] = new char[str1.length + str2.length];
int index = 0;
int len1 = str1.length;
while(index < str1.length)
result[index] = str1[index++];
index = 0;
while(index < str2.length)
result[len1 + index] = str2[index++];
return result;
}
// COMPLEXITY O ( N^2 )
public static boolean isSubstring(char str1[], char str2[]){
int counter = 0;
for(int i = 0; i < str2.length; i++){
int start = i;
while(counter < str2.length && start < str1.length && str1[start++] == str2[counter++]){
if(counter == str2.length)return true;
}
counter = 0;
}
return false;
}
// Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
// COMPLEXCITY O (NM)
public static void setZero(int M[][]){
boolean rows [] = new boolean[M.length];
boolean columns[] = new boolean[M[0].length];
for(int i = 0; i < M.length; i++){
for(int j = 0; j < M[i].length; j++){
if(M[i][j] == 0 ){
rows[i] = true;
columns[j] = true;
}
}
}
for(int i = 0; i < M.length; i++){
for(int j = 0; j < M[i].length ; j++){
if(rows[i] || columns[j]){
M[i][j] = 0;
}
}
}
}
// Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place
// COMPLEXITY O (N^2)
public static void rotateM(int M[][],int N){
for( int layer = 0; layer <= N/2; layer++){
int last = N - 1 - layer;
for(int i = layer; i < last; i++){
int offset = i - layer;
// top
int temp = M[layer][i];
// top = left
M[layer][i] = M[last - offset][layer];
// left = buttom
M[last - offset][layer] = M[last][last-offset];
// bottom = right
M[last][last - offset] = M[layer + offset][last];
// right = top
M[layer + offset][last] = temp;
}
}
}
// Write a method to replace all spaces in a string with '%20'.
// COMPLEXITY O (N + 2 * #SPACES ) O (N) AVG
public static char[] replaceSpaces(char str[]){
int spaces = 0;
for(int i = 0; i < str.length; i++){
if(str[i] == ' '){
spaces++;
}
}
int length = str.length + (2*spaces);
char result [] = new char[length];
int index = 0;
for(int i = 0; i < str.length; i++){
if(str[i] == ' '){
result[index++] = '%';
result[index++] = '2';
result[index++] = '0';
}else{
result[index++] = str[i];
}
}
return result;
}
// Write a method to decide if two strings are anagrams or not.
// Complexity O ( 2n + k) avg, since s1 and s2 should contains the same length otherwise It will return false immediate
public static boolean isAnagram(char s1[], char s2[]){
if(s1.length != s2.length) return false;
int letters [] = new int[256];
for( int i = 0; i < s1.length; i++){
letters[toUpperCase(s1[i])]++;
}
for( int j = 0; j < s2.length; j++){
letters[toUpperCase(s2[j])]--;
if(letters[toUpperCase(s2[j])] < 0) return false;
}
for(int x = 0; x < letters.length; x++){
if(letters[x] != 0 ) return false;
}
return true;
}
// Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine.
//An extra copy of the array is not.
// Complexity O ( n )
public static void removeDuplicates(char str[]){
boolean letters [] = new boolean[256];
int index = 0 ;
for(int i = 0; i < str.length ; i++ ){
char current = str[i];
if(!letters[current] || current == ' '){
str[index++] = str[i];
letters[current] = true;
}
}
for(int i = index; i < str.length; i ++)
{
str[i] = ' ';
}
}
// Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
// Complexity = O( n ) and space complexity O ( k ) where k is the length of the charset for ASCII = 256
public static boolean hasUniqueChars(char str []){
boolean letters [] = new boolean[256];
for(int i = 0; i < str.length ; i ++){
if(str[i] == ' ') continue;
char current = toUpperCase(str[i]);
if(letters[current]){
return false;
}else{
letters[current] = true;
}
}
return true;
}
public static char toUpperCase(char c){
if( c >= 'a' && c <= 'z'){
c -= ('a' - 'A');
}
return c;
}
public static char toLowerCase(char c){
if( c >= 'A' && c <= 'Z'){
c += ('a'-'A');
}
return c;
}
Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages' libraries.
Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered.
Binary Tries - Used in almost every high-bandwidth router for storing router-tables.
Hash Trees - used in p2p programs and specialized image-signatures in which a hash needs to be verified, but the whole file is not available.
Heaps - Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including robotics and video games). Also used in heap-sort.
Huffman Coding Tree (Chip Uni) - used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats.
GGM Trees - Used in cryptographic applications to generate a tree of pseudo-random numbers.
Syntax Tree - Constructed by compilers and (implicitly) calculators to parse expressions.
Treap - Randomized data structure used in wireless networking and memory allocation.
T-tree - Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.
Are you guys sure the complexity is the worse case is still O (m +n ) Think about the case almost every node in T1 match T2.root, so you have to look for T2 in T1 many many times. Imagine that It only differ on one Node ( on the T1 subtree )
then you have to look the whole T1 ( O (n ) ) times T2 ( O (m - x ) where x is the number of nodes that did not match. then It ends up like O (n*(m-x)) ~ O(n*m) which is much more thatn O (n +m )
What do you think? If you don't agree elaborate more no the complexity please.
Never mind. Both approches can work perfectly.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> January 24, 2014I liked your answer more than mine. But I was thinking that my approach can work on a Garph as well.
What do you think Eugene?
If it was not a Binary Search Tree then we can just change the folowing lines
if(t1.value > t2.value){
return isSubTree(t1.left,t2);
}else{
return isSubTree(t1.right,t2);
}
TO:
return isSubTree(t1.left,t2) || isSubTree(t1.right,t2);
Complexity O (m*n) worse case scenario
public static boolean isSubTree(TNode t1, TNode t2)
{
if( t1 == null && t2 == null) return true;
if( t1 == null) return false;
if(t2 == null || (t1.value == t2.value && containsTree(t1,t2))){
return true;
}else{
if(t1.value > t2.value){
return isSubTree(t1.left,t2);
}else{
return isSubTree(t1.right,t2);
}
}
}
public static boolean containsTree(TNode t1, TNode t2)
{
if( t2 == null ) return true;
if( t1 == null ) return false; // t2 not found
if( t1.value == t2.value ){
return containsTree(t1.right,t2.right) && containsTree(t1.left,t2.left);
}else{
return false;
}
}
Test case:
TNode root = null;
root = insert(root,100);
insert(root,200);
insert(root,50);
insert(root,25);
insert(root,75);
insert(root,250);
insert(root,150);
insert(root,10);
insert(root,8);
insert(root,6);
insert(root,4);
insert(root,300);
insert(root,400);
insert(root,500);
List<List<TNode>> result = treeToLinkList(root);
for(List<TNode> l : result){
for(TNode n: l){
System.out.print("->" + n.value);
}
System.out.println();
}
Output:
->100
->50->200
->25->75->150->250
->10->300
->8->400
->6->500
->4
Breadth-first search algorithm using a dummy Node to divide each level (may not be necessary if we keep track of each level in a different way )
But this works just fine.
public static List<List<TNode>> treeToLinkList(TNode node){
List<List<TNode>> result = new LinkedList<List<TNode>>();
List<TNode> level = new LinkedList<TNode>();
Queue<TNode> queue = new LinkedList<TNode>();
TNode dummy = new TNode(-1); // this is a dummy node that will divide each level on the tree
// Special case for Root
level.add(node);
result.add(level);
level = new LinkedList<TNode>();
queue.add(node);
queue.add(dummy);
while(queue.size() > 1){ // The last element will be the dummy node
TNode current = queue.poll();
if(current == dummy){ // at this point we have reach the end of a level.
if(level != null){
result.add(level);
}
level = new LinkedList<TNode>();
queue.add(dummy); // add a dummy to divide the level
}else{
if(current.left != null){
queue.add(current.left);
level.add(current.left);
}
if(current.right != null){
queue.add(current.right);
level.add(current.right);
}
}
}
return result;
}
static class TNode{
public TNode left;
public TNode right;
public int value;
public TNode(int val){
this.value = val;
}
}
Complexity:
Tree Insert O(n log n) + Iterate array O (n ) = O( 2n log n) ~ O (n log n )
public static TNode insert(TNode node, int value){
if(node == null){
node = new TNode(value);
}else{
if(value > node.value)
node.right = insert(node.right,value);
else
node.left = insert(node.left,value);
}
return node;
}
public static TNode createTree2(int array[], int start, int end, TNode root){
if(start < 0 || end >= array.length || start > end){
return root;
}else{
int middle = ((end - start)/2)+start; // middle Index
root =insert(root,array[middle]);
createTree2(array,start,middle-1,root);
createTree2(array,middle+1,end,root);
}
return root;
}
please ignore the searchBFS, I'm still working on it. the one that does the actual work is called:
searchDFS(startPoint,target);
Note: Sorry about the mess I did on the main method, I was just trying to create a random Graph. Not the best way to do it, but It works for testing proposes.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> January 21, 2014You make a node visited only when you have visited all Its childrens. when you are pushing to the stack It is on a state like "exploring" or "visiting" but not visited at all.
try it yourself here is the complete code:
//Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
import java.util.*;
public class Graph{
public static void main(String [] args){
GNode startPoint = new GNode(100);
Random random = new Random();
for(int w = 0; w < 5; w ++){
startPoint.addGNode(random.nextInt(100));
}
List<GNode> secondLevel = startPoint.getNodes();
for(int i = 0; i < secondLevel.size(); i++){
GNode node = secondLevel.get(i);
for(int z = 0; z < 5; z ++){
GNode n = new GNode(random.nextInt(100),node.value);
node.getNodes().add(n);
for(int c = 0; c< 5; c++)
n.getNodes().add(new GNode(random.nextInt(100),n.value));
}
}
printBFSGraph(startPoint);
int target = random.nextInt(100);
System.out.println("target: " + target );
searchDFS(startPoint,target);
}
public static void printBFSGraph(GNode node){
Queue<GNode> q = new LinkedList<GNode>();
q.add(node);
while(q.peek() != null){
GNode current = q.poll();
System.out.println("[ {"+current.parent+"},"+ current.value +" ] ");
List<GNode> childrens = current.getNodes();
for(GNode ne : childrens){
q.add(ne);
}
}
}
public static void searchDFS(GNode node, int value)
{
Stack<GNode> stack = new Stack<GNode>();
stack.push(node);
boolean found = false;
while(!stack.empty()){
GNode current = stack.peek();
if(current.value == value){
found =true;
break;
}else{
GNode next = current.getNextNotVisited();
if(next == null){
current.visited =true;
stack.pop();
}else{
stack.push(next);
}
}
}
if(found){
while(!stack.empty())
System.out.print(stack.pop().value + " <- ");
}else{
System.out.println("No found");
}
}
public static void searchBFS(GNode node, int value){
Queue<GNode> queue = new LinkedList<GNode>();
queue.add(node);
while(queue.peek() != null)
{
}
}
static class GNode{
public int value;
public int parent;
public boolean visited;
public List<GNode> nodes;
public GNode(int val){
this.value = val;
this.parent = -666;
}
public GNode(int val,int parent){
this.value =val;
this.parent = parent;
}
public void addGNode(int value){
if(nodes == null){
nodes = new ArrayList<GNode>();
}
nodes.add(new GNode(value,this.value));
}
public List<GNode> getNodes(){
if(nodes == null){
nodes = new ArrayList<GNode>();
}
return nodes;
}
public GNode getNextNotVisited(){
for(GNode node:nodes){
if(!node.visited)return node;
}
return null;
}
}
}
Depending on how the getNextNotVisited() method. The Complexity should be worse case O(n)
What about the avg? O(n) ??
public static void searchDFS(GNode node, int value)
{
Stack<GNode> stack = new Stack<GNode>();
stack.push(node);
boolean found = false;
while(!stack.empty()){
GNode current = stack.peek();
if(current.value == value){
found =true;
break;
}else{
GNode next = current.getNextNotVisited();
if(next == null){
current.visited =true;
stack.pop();
}else{
stack.push(next);
}
}
}
if(found){
while(!stack.empty())
System.out.print(stack.pop().value + " <- ");
}else{
System.out.println("No found");
}
}
This is about creating a Singlenton class that holds a cache of connections so that the connections can be reused when future requests to the database are required.
When you say that "When the user is done, returns them back to the pool" means that you just freed one of your N connection hold in your cache, wich means It can be use by another user/request/process/thread/etc
There is a creational design pattern called object pool pattern if you want to get into details.
Additionally, there are a lot open source software that are in charged of such task. In real life, It is hard that someones needs to rebuild the wheel, but It is a good idea to knoew in details such open source software to disscuss it during the interview and why not came up with your own implentation.
hope It works.
cheers
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
//Base Case for Equilateral
System.out.println(Test.getTringleType(1,1,1));
System.out.println(Test.getTringleType(10, 10, 10));
System.out.println(Test.getTringleType(100, 100, 100));
//Base Case for Isosceles
System.out.println(Test.getTringleType(2,2,3));
System.out.println(Test.getTringleType(50,50,1));
System.out.println(Test.getTringleType(10,2,10));
// Base Case for Scalen
System.out.println(Test.getTringleType(5,6,7));
System.out.println(Test.getTringleType(10, 20, 15));
System.out.println(Test.getTringleType(511, 522, 533));
// Expected Errors
System.out.println(Test.getTringleType(0,1,2));
System.out.println(Test.getTringleType(0,0,0));
System.out.println(Test.getTringleType(Integer.MAX_VALUE,1,1));
System.out.println(Test.getTringleType(Integer.MAX_VALUE,Integer.MAX_VALUE + 1,Integer.MAX_VALUE + 2));
}
/**
* returns one of four values to determine the triangle type
* @author axel
* @param a
* @param b
* @param c
* @return 1=scalene, 2=isosceles, 3=equilateral, 4=error
*/
public static int getTringleType(int a,int b,int c){
if( a <= 0 || b <= 0 || c <= 0 || b+c<=a || a+c<=b || a+b<=c)
{
return 4; // Error
}else if(a == b && b == c ){
return 3; // Equilateral
}else if(a == b || b == c || a == c){
return 2; // Isosceles
}else{
return 1; // Scalen
}
}
}
public class CircularQueue {
private int size;
private int head;
private int tail;
private int array[];
public CircularQueue(int initialCapacity) {
size = initialCapacity;
array = new int[initialCapacity];
initialize();
}
public synchronized void initialize() {
head = 0;
tail = 0;
}
public synchronized void enqueue(int v) throws Exception {
int tmp = (tail+1) % size;
if (tmp == head) {
resizeQueue();
array[tail] = v;
}else{
array[tail] = v;
tail = tmp;
}
}
public synchronized int dequeue() throws Exception{
if (head == tail) throw new Exception("Empty Queue!");
int tmp = array[head];
array[head] = 0; // Zero is just an arbitrary value, Just to simulate a clean up of the current slot
head = (head + 1) % size;
return tmp;
}
public void resizeQueue()throws Exception{
size = size*2;
int tmp []= new int[size];
int index = 0;
while(head != tail){
tmp[index++] = dequeue();
}
head = 0;
tail = index;
array = tmp;
}
public void printQueue(){
if( tail == head){
System.out.println("Empty Queue!");
}
for(int i = 0 ; i < array.length ; i++){
if(i == tail)
System.out.print("Tail->[" +array[i] +"],");
else if(i == head)
System.out.print("head->[" +array[i] +"],");
else
System.out.print("["+array[i]+"],");
}
}
public static void main(String [] args) throws Exception{
CircularQueue myQueue = new CircularQueue(5);
myQueue.enqueue(1);
myQueue.enqueue(2);
myQueue.enqueue(3);
myQueue.enqueue(4);
myQueue.enqueue(5);
myQueue.enqueue(6);
myQueue.dequeue();
myQueue.dequeue();
myQueue.dequeue();
myQueue.dequeue();
myQueue.printQueue();
}
}
SUM = m * n * l
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> January 04, 2014hi Roxanne.
There is not problem at all.
The way the snake data structure (double linked list) is being updated is as follow:
The head moves: then the previus node will be equals to the old head. and the previus of the previus will be updated to the old value of the previus node and so on.
So por example:
N1 - N2 - N3 - N4
|
|
<=Head- N5
In the following example, the head is going left but the tail is going right and N4 should go down.
In this case, If the user press down key, then the following will happen:
1) Head will go down Y++
2) N5 will be update to the old head ( previus to be updated in step 1)
3) N4 = N5, N3= N4, N2 = N3, N1 = N2 and so on.
since each node represent a Point ( X, Y ) then It will simulate the movement of the snake.
Each move or each frame or each update will cost O(n) to repaint + The complexity to validate the integrity of the game ( crashiong, feeding, wining, lowing, pointing, etc etc etc)
What about that?
moveUp()
{
head.y++;
}
move down()
{
head.y--;
}
moveR()
{
head.x++;
}
moveL()
{
head.x--;
}
validateForCrashes()
{
// check if head does not overlaps with the rest of the snake or any of the walls or any of the obstacules
Node tmp = head.previus;
while(tmp != null)
{
if(head.x ==tmp.x && head.y==tmp.y) return FALSE; // CRASHED
// check for walls
/ check for obstacules
}
}
I'll go for a double linked list.
public class Snake{
Node head;
moveR();
moveL();
moveUp();
moveDown();
updateSnake()
{
// for each node from tail to head, update nodes.
Node tmp = tail;
while(tmp != null){
node = node.next;
}
}
}
public class Node{
Node previus;
Node next;
int x;
int y;
}
O(n!)
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> December 28, 2013I prefer using char[] than String so I little change
public static void print anagrams(char str[], int start, int n)
public static void swap(char str[],int i, int j){
char tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
anagrams("Hello",0,5);
public static void print anagrams(String str, int start, int n)
{
if(start == n)
{
System.out.println(str);
}else{
for(int i = start; i < n ; i++)
{
swap(str,start,i);
anagrams(str,start+1,n)
swap(str,start,i);
}
}
}
Well, we need to make sure we are just dealing with letters, if so, then I agree. but not big harm to use 256 at all. In case we are dealing with unicode, then we just need to change the size of the array and the rest should be ok.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 29, 2013Thanks for sharing guys.
@Alex: Correct, You got it. I meant using || instead of &&. that's correct. Thx
@Navi: Initial values should be: Integer.MIN_VALUE and Integer.MAX_VALUE ( in case we are dealing with integers.
@Alex, can you elaborate more on your improvement please.
I didn't test it. hope It works
public static void isValidBST(Node node,int minValue, int maxValue)
{
if(node == null)
{
return true;
}else
{ if(node.value < minValue && node.value > maxValue)
{
return false;
}
return isValidBST(node.left,minValue,node.value) && isValidBST(node.right,node.value,maxValue);
}
}
It is not about memorize, It is about understand the root of the problem. If you want to only memorized the solution, then good luck in your future work.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 29, 2013good approach, but do you really have to visit all the nodes up to Adan and Eve? I think It will be only if you fall in the worse case scenario.
What about alternately visit parents for You and Einstein until you get a visited node ?
What could be the special cases ( weirdo relationship in history) ?
you havent break my ego anyway. But lets go back to bussiness:
What do you think about my program?
What about print the wining path inside the recursive call, do you think It could be interesting?
Oh. you are not taking about my code.
about the upvoting thing, of course I know it does not work. ( or at least it shouldn't work) But I wonder, how do you know that I did try anyway?
why it doesnt work?
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 19, 2013HERE ARE A SIMULATION:
public static void main(String [] args){
System.out.println();
int coins[] = new int[]{100,1,20,30,40,10,20,30,90};
for(int i = 0 ; i < coins.length; i++)
System.out.print(coins[i] + " , ");
System.out.println();
playGame(coins);
System.out.println("Recursive call result: : " + max_coin(coins,0,coins.length-1));
}
public static void playGame(int array[])
{
// taking the first one.
int sum = array[0];
int sumB = 0;
int i = 1;
int j = array.length-1;
String paths = "" + array[0] + " + ";
String pathsB ="";
while(i<j){
// Time for Player B
if(array[i] > array[j])
{
pathsB += array[i] + " + ";
sumB += array[i];
i++;
}else{
pathsB += array[j] + " + ";
sumB += array[j];
j--;
}
// Time for player A
if(i>j)break;
if(array[i] > array[j])
{
paths += "" + array[i] + " + ";
sum += array[i];
i++;
}else{
paths += "" + array[j] + " + ";
sum += array[j];
j--;
}
}
System.out.println("Taking the first one:");
if(sumB>sum){
System.out.println("B WINS ");
}else{
System.out.println("A WINS " );
}
System.out.println("PLAYER A " + paths + " = " + sum);
System.out.println("PLAYER B " + pathsB + " = " +sumB);
// Start by taking the last one
sum = array[array.length-1];
i = 0;
j = array.length-2;
paths = "" + array[array.length-1] + " + ";
while(i<j){
// Time for Player B
if(array[i] > array[j])
{
pathsB += array[i] + " + ";
sumB += array[i];
i++;
}else{
pathsB += array[j] + " + ";
sumB += array[j];
j--;
}
// Time for player A
if(i>j)break;
if(array[i] > array[j])
{
paths += "" + array[i] + " + ";
sum += array[i];
i++;
}else{
paths += "" + array[j] + " + ";
sum += array[j];
j--;
}
}
System.out.println("Taking the Last one:");
if(sumB>sum){
System.out.println("B WINS");
}else{
System.out.println("A WINS");
}
System.out.println("PLAYER A " + paths + " = " + sum);
System.out.println("PLAYER B " + pathsB + " = " + sumB);
}
public static int max_coin( int coin[], int start, int end ){
if (start > end)
return 0;
int a = coin[start] + Math.min( max_coin( coin, start+2,end ), max_coin( coin, start+1,end-1 ) );
int b = coin[end] + Math.min( max_coin( coin, start+1,end-1 ), max_coin( coin, start,end-2 ) );
return Math.max(a,b);
}
mafafito@mafafito-Aspire-4752:~/programming$ java Amazon
100 , 1 , 20 , 30 , 40 , 10 , 20 , 30 , 90 ,
Taking the first one:
A WINS
PLAYER A 100 + 30 + 10 + 30 + 1 + = 171
PLAYER B 90 + 20 + 40 + 20 + = 170
Taking the Last one:
B WINS
PLAYER A 90 + 30 + 10 + 30 + 1 + = 161
PLAYER B 90 + 20 + 40 + 20 + 100 + 20 + 40 + 20 + = 350
Recursive call result: : 171
public static char[] getPalindromo(char str[], int start, int end)
{
// The only Exception I have found is with letters with acent like ába will not be a palindrome
while( start >= 0 && end < str.length &&
(toLowerCase(str[start]) == toLowerCase(str[end]) ||
!isLetter(str[start]) ||
!isLetter(str[end])))
{
if(!isLetter(str[start]) && isLetter(str[end]))
start--;
else if(isLetter(str[start]) && !isLetter(str[end]))
end++;
else{
start--;
end++;
}
}
start++;
end--;
return subString(str,start, (end-start)+1);
}
public static boolean isLetter(char c)
{
return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}
public static char toLowerCase(char c){
if(c >= 'a' && c <= 'z')
return c;
else return (char)(c + ('a'-'A'));
}
public static char[] subString(char str[],int from, int length){
char result [] = new char[length];
for(int index = 0; index < length; index++)
{
result[index] = str[from + index];
}
return result;
}
public static char[] getLongestPalindromo(char str[]){
if(str == null) return new char[0];
if(str.length < 2) return str;
char longestSoFar [] = new char[1];
longestSoFar[0] = str[0]; // default
char result[] = longestSoFar;
for(int i = 0; i < str.length; i++){
char palindromo[] = getPalindromo(str,i,i);
if(longestSoFar.length < palindromo.length)
longestSoFar = palindromo;
palindromo = getPalindromo(str,i,i+1);
if(longestSoFar.length < palindromo.length)
longestSoFar = palindromo;
if(result.length < longestSoFar.length)
result = longestSoFar;
}
return result;
}
public static void main(String [] args){
System.out.println(Amazon.getLongestPalindromo("123 Are we not drawn onward to new era? XXX".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("A car, a man, a maraca.".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("A dog, a plan, a canal: pagoda.".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal-Panama!".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("A Santa dog lived as a devil God at NASA.".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("A Toyota! Race fast, safe car! A Toyota!".toCharArray()));
System.out.println(Amazon.getLongestPalindromo("Are we not pure? “No sir!” Panama’s moody Noriega brags. “It is garbage!” Irony dooms a man; a prisoner up to new era.".toCharArray()));
}
Output:
mafafito@mafafito-Aspire-4752:~/programming$ java Amazon
123 Are we not drawn onward to new era?
A car, a man, a maraca
A dog, a plan, a canal: pagoda
A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal-Panama
A Santa dog lived as a devil God at NASA
A Toyota! Race fast, safe car! A Toyota
Are we not pure? “No sir!” Panama’s moody Noriega brags. “It is garbage!” Irony dooms a man; a prisoner up to new era
mafafito@mafafito-Aspire-4752:~/programming$
but It is till has a code.
I fix it on my post. Vote for it!
Not getting the question. Need more Context please
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 17, 2013I'm assuming that upper are different than lower cases. But It would be a good thing to point out to the interviewer.
Here is my algorithm:
public static void removeCommon(char str1[], char str2[]){
int letters[] = new int[256];
for(int i = 0; i < str1.length; i++)
letters[str1[i]]++;
for(int i = 0; i < str2.length; i++)
if(letters[str2[i]]>0)
letters[str2[i]]= -1;
int index = 0;
for(int i = 0; i < str1.length; i++)
{
if(letters[str1[i]] != -1){
str1[index++] = str1[i];
}
}
while(index < str1.length)
str1[index++] = 0;
index = 0;
for(int i = 0; i < str2.length; i++)
{
if(letters[str2[i]] != -1){
str2[index++] = str2[i];
}
}
while(index < str2.length)
str2[index++] = 0;
System.out.println(str1);
System.out.println(str2);
System.out.println("Common");
for(int i = 0; i < letters.length; i ++){
if(letters[i] == -1){
char c = (char)i;
System.out.print(c);
}
}
System.out.println();
}
public static void main(String [] args){
removeCommon("abcdefghijklmnopqrstuvwxyz".toCharArray(),"AEIOUaeiou123".toCharArray());
}
mafafito@mafafito-Aspire-4752:~/programming$ javac Amazon.java
mafafito@mafafito-Aspire-4752:~/programming$ java Amazon
bcdfghjklmnpqrstvwxyz
AEIOU123
Common
aeiou
void removeALTERNATEDuplicates(char str[],int n){
int letters [256];
int i = 0;
int index=0;
for(i=0;i<256;i++)
letters[i]=0;
for(i=0; i<n;i++){
char lowerCase = str[i];
if(str[i] >= 65 && str[i] <= 90){
lowerCase +=('a' - 'A');
}
if(letters[lowerCase] == 0){
letters[lowerCase]++;
str[index++]=str[i];
}else{
letters[lowerCase]--; // We want to Alternate
}
}
while(index < i){
str[index++]= 0;
}
}
BY THE WAY! You implementation is wrong!
This is about deleting ALTERNATE duplicates, not all the duplicates.
So for Example:
Input: "aaAaaAAA"
Output: "aAaA"
Check my code:
void removeDuplicates(char str[],int n){
int letters [256];
int i = 0;
int index=0;
for(i=0;i<256;i++)
letters[i]=0;
for(i=0; i<n;i++){
char lowerCase = str[i];
if(str[i] >= 65 && str[i] <= 90){
lowerCase +=('a' - 'A');
}
if(letters[lowerCase] == 0){
letters[lowerCase]++;
str[index++]=str[i];
}else{
letters[lowerCase]--; // We want to Alternate
}
}
while(index < i){
str[index++]= 0;
}
}
void removeAlternateDuplicates(char str[],int n){
int letters [256];
int i = 0;
int index=0;
for(i=0;i<256;i++)
letters[i]=0;
for(i=0; i<n;i++){
char lowerCase = str[i];
if(str[i] >= 65 && str[i] <= 90){
lowerCase +=('a' - 'A');
}
if(letters[lowerCase] == 0){
letters[lowerCase]++;
str[index++]=str[i];
}else{
letters[lowerCase]--; // We want to Alternate
}
}
while(index < i){
str[index++]= 0;
}
}
int main(){
char str[]="aAaBbBcCcdefgFGZzzzO";
removeAlternateDuplicates(str,20);
printf("%s\n",str );
return 0;
}
Output:
mafafito@mafafito-Aspire-4752:~/programming$ gcc microsoft.c -o micro
mafafito@mafafito-Aspire-4752:~/programming$ ./micro
aaBBccdefgZzO
What about a merge sort in O (n log n) from index 25 to 75. so that Min = a[25] and Max = a[75].
In case we cannot modify the array, we can iterate from a[25] to a[75] and keep track of min and max
Complexity O (n) where n = 75 - 25 ;
Another option will be:
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> January 25, 2014A min heap and a max heap out of the range of the array. in O (n/2) each
There are many solutions to the problem. I wonder why they were asked an specific range, 100 elements is still a small size for that range.
Any more ideas?