.·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º>
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
1) "abcabc"
2) "abcABC"
3) "abc"
4) ""
5) NULL
6) "aaaaaaaaaa"
7) "aAaAaAaAaAaA"
8) "A very big string which length is bigger than INTEGER.MAX_VALUE ( If possible )"
9) "123123"
10) "!"#$#%&/()?=)(/&%$#"!°¡ "
11) " " (spaces)
12) Is it thread safe? HashMap is not thread Safe, so we can do something to break it maybe
13) different encoding perhabs?
you can optimized your code if you use char [] or StringBuilder but It works.
Here are some test cases:
Base case:
1) "abcabc"
2) "abcABC"
3) "abc"
4) ""
5) NULL
6) "aaaaaaaaaa"
7) "aAaAaAaAaAaA"
8) "A very big string which length is bigger than INTEGER.MAX_VALUE ( If possible )"
9) "123123"
10) "!"#$#%&/()?=)(/&%$#"!°¡ "
11) " " (spaces)
12) Is it thread safe? HashMap is not thread Safe, so we can do something to break it maybe
13)
This will not work. The question is asking about removing alternate duplicates not just all the duplicates.
Watch out !
You can take a look at the Hashtable class in the JDK source code.
The implementation is huge.
but basically,
1) you need to syncronized any operation that alters the table, because Hashtable are syncronized.
2) get, put and contains should run in avg O(1)
3) you need to provide a way to deal with collitions
4) you need to implement an efficient hashcode method for the keys
5) care need to be taken when modifying the load factor and initial capacity of the hashTable
In short:
Mergesort is a sorting algorithm that follows the paradigm of: divide and conquer:
1) recursivly split the array in 2
2) until the array length is 1 ( or the pointers start and end are equal)
3) merge the sorted array an return the array sorted
public static char[] mersort(char str[], int start, int end){
if(str.length <= 1 ){
return str;
}else{
int middle = (end-start)/2;
char[] first_half = getArray(str,start,middle);
char[] second_half = getArray(str,middle,end);
char [] l1 = mersort(first_half,0,first_half.length);
char [] l2 = mersort(second_half,0,second_half.length);
return mergeArrays(l1,l2);
}
}
HashTable: Is an implementation of a Dictionary where you MAP Key and Values.
You need the Key's hashcode to located the bucket where the value is going to be store.
The hashcode must be well implemented shuch that It will always return the same value for the same key.
equals method should also be implemented in case of collision, so we can iterate over the list of values at the same bucket.
There are many implementation of MAP, one of them are hashtable which are thread safe. HashMap is similar but is not thread save.
There are other implementations where the key as store in oreder, so implemented the MapSorted such as treeMap.
hashtable operation runs on constant time O(1) (AVG), such as get, put, and contains.
There are many other things you can talk about hashing, like hashing functions, hashCode for Object class, and some others.
We can write a complete book about how to test a website like Amazon.com
But in short,
We can make a list of all the features and test each one seperatly and at the end do an integration testing.
For exmple:
Your Amazon Community
Your Site Preferences
Shopping Features
Notifications & E-mail Subscriptions
Business Opportunities
Accessibility
And for each feature we can test:
If you don't know the detail of each feature you can start by an exploratory testing.
If you knnow the detail of each feature, you can start testing
base case scenarios
worse case scenarios
boundary testing
.....
If you have access to the code, then you can look for pitfalls or critical parts.
You can create an automated testing framework to test funcational testing for every module.
You can stress the website using any request tool or create your own one.
You can test accesability, usability, etc
There are tons of things you can test, I think the thing is to split the system in many peaces as possible an test them individually and then integreate all of them an test it all together.
If this was asked on a phone interview, I think the interviewer wants to see if you have an structure methodology to face this problem. Of course he/she will not expect you to tell you all the possible ways to test this out. The key is keep talking till he/she stop you ;)
public static void arrange(int array[]){
char int[] = Programming.mersort(array,0,array.length);
int i = 0;
int e = sorted.length -1;
boolean flag = false;
while(i<=e){
if(flag){
System.out.print( sorted[e--] + (i<=e?" >= ":"") );
}else{
System.out.print( sorted[i++] + (i<=e?" <= ":"") );
}
flag = !flag;
}
System.out.println("");
}
int []{3,4,5,7,8,9};
output
3 <= 9 >= 4 <= 8 >= 5 <= 7
Then the question would be: Implement a LinkedList or a doubleLinkedList or just a anything from the List Interface.
We need to clarify this. I dont think is that simple
that would means a LinkedList which is not an array[]
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 16, 2013INPUT:
max_subsequence(new Item[]{
new Item(1,-2),
new Item(2,1),
new Item(3,-3),
new Item(4,4),
new Item(5,-1),
new Item(6,2),
new Item(7,1),
new Item(8,-5),
new Item(9,4)
});
OUTPUT:
[0]<1,-2> , = -2
[1]<2,1> , = 1
[2]<2,1> ,<3,-3> , = -2
[3]<4,4> , = 4
[4]<4,4> ,<5,-1> , = 3
[5]<4,4> ,<5,-1> ,<6,2> , = 5
[6] MAX: <4,4> ,<5,-1> ,<6,2> ,<7,1> , = 6
[7]<4,4> ,<5,-1> ,<6,2> ,<7,1> ,<8,-5> , = 1
[8]<4,4> ,<5,-1> ,<6,2> ,<7,1> ,<8,-5> ,<9,4> , = 5
INPUT:
max_subsequence(new int[] {-2,1,-3,4,-1,2,1,-5,4});
OUTPUT
[0]-2, = -2
[1]1, = 1
[2]1,-3, = -2
[3]4, = 4
[4]4,-1, = 3
[5]4,-1,2, = 5
[6] MAX: 4,-1,2,1, = 6
[7]4,-1,2,1,-5, = 1
[8]4,-1,2,1,-5,4, = 5
I am sorry. I just test it out my code and YES! I HAD a very BAD Bug:
I wrote: sum[i] = array[i-1].b + array[i].b;
when I should use the sum[] values ( which is actually the most importan part of my code:
sum[i] = sum[i-1] + sum[i];
Sorry about that. I've fixed it.
Please send me the bill or the bet I've lost lol
This is a variation of the Kadane's Algorithm
public static void max_subsequence(int sequence[]){
int MAX = Integer.MIN_VALUE;
String paths[] = new String[sequence.length];
int sum[] = new int[sequence.length];
for(int i = 0; i <sequence.length; i++){
paths[i] = sequence[i] + ",";
sum[i] = sequence[i];
if(sum[i]>MAX){
MAX = sum[i];
}
}
for(int i = 1; i < sequence.length; i++){
if((sum[i-1] + sum[i]) > sum[i]){
paths[i] = paths[i-1] + paths[i];
sum[i] = sum[i-1]+sum[i];
if(MAX < sum[i]){
MAX = sum[i];
}
}
}
for(int i = 0; i < sum.length; i++){
if(MAX == sum[i]){
System.out.println("MAX: "+paths[i] + " = " + sum[i]);
}else{
System.out.println(paths[i] + " = " + sum[i]);
}
}
}
explain why not.
give some test cases.
I bet, It works
Assuming that this is store on a RDBMS:
Select top 1 * from restaurants where distance < 1k
If the result is empty, then try distance*2 till you get something back.
Else:
We can hash by country, state, town, zipcode and get the set of restaurants from the zipcodes around my location ( not only my current zipcode) and then reduce the search and get the nearest restaurant.
how?
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 16, 2013In Java:
public static int getNOnes(int n)
{
int result = 0;
while(n>0)
{
n = n&(n-1);
result++;
}
return result;
}
What do you suggest?
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 16, 2013If you cannot use a simple array like
String[] or Object[] or E[]
then the question would be more like create an array implementation on the JVM an not in JAVA.
In Java there is a class called Arrays, which is a utility class to deal with regular arrays ( sorting, copying, etc etc etc)
The only thing you can do ( as far as I can think ) is to implement any Data Structure such as Vector, ArrayList, Stack, Queue even a tree using a regular array ( Object[] )
Another thing to point out is that, in java we cannot extends from Object[] even if arrays are treat like Objects. This is not allow. so that is not the way to go.
The last resource we have instead would be using native methods and try to implement something in C on a DDL or something. But I am running out of ideas.
Anybody?
You break the bar so that you get 1 peace, 2 peaces and 4 peaces.
**** | ** | *
first day you give 1 peace
2dn you give the one with 2 and get back the other with only 1
3rd you give the 2 and 1
4.- you give the one with 4
5.- 4 & 1
6.- 4 & 2
7.- All
O(n) Complexity
public static void max_subsequence(Item[] array){
String paths[] = new String[array.length];
int sum[] = new int[array.length];
int max = Integer.MIN_VALUE;
for(int i = 0; i < array.length; i++){
sum[i] = array[i].b;
paths[i] = "<" + array[i].a + "," + array[i].b +"> ,";
if(sum[i] > max){
max = sum[i];
}
}
for(int i = 1; i < array.length; i++){
if( array[i-1].a <= array[i].a && (sum[i-1]+ sum[i])> sum[i]){
paths[i] = paths[i-1] + paths[i];
sum[i] = sum[i-1] + sum[i];
if(max < sum[i]){
max = sum[i];
}
}
}
for(int i = 0; i < paths.length; i++){
if(max == sum[i]){
System.out.println("["+i+"]"+ " MAX: " + paths[i] + " = " + sum[i]);
}else{
System.out.println("["+i+"]"+paths[i] + " = " + sum[i]);
}
}
}
Thread support is not allow, I think this question is what it is about.
I think, designing a distribute system, does not required thread support, but you somehow are doing things async.
what do you guys think?
///
max_subsequence(new int[] {-2,1,-3,4,-1,2,1,-5,4});
///
public static void max_subsequence(int sequence[]){
int MAX = Integer.MIN_VALUE;
String paths[] = new String[sequence.length];
int sum[] = new int[sequence.length];
for(int i = 0; i <sequence.length; i++){
paths[i] = sequence[i] + ",";
sum[i] = sequence[i];
if(sum[i]>MAX){
MAX = sum[i];
}
}
for(int i = 1; i < sequence.length; i++){
if((sum[i-1] + sum[i]) > sum[i]){
paths[i] = paths[i-1] + paths[i];
sum[i] = sum[i-1]+sum[i];
if(MAX < sum[i]){
MAX = sum[i];
}
}
}
for(int i = 0; i < paths.length; i++){
if(MAX == sum[i]){
System.out.println("["+i+"]"+ " MAX: " + paths[i] + " = " + sum[i]);
}else{
System.out.println("["+i+"]"+paths[i] + " = " + sum[i]);
}
}
}
Output:
[0]-2, = -2
[1]1, = 1
[2]1,-3, = -2
[3]4, = 4
[4]4,-1, = 3
[5]4,-1,2, = 5
[6] MAX: 4,-1,2,1, = 6
[7]4,-1,2,1,-5, = 1
[8]4,-1,2,1,-5,4, = 5
This is a generic Class for N Stacks Using a Single Array.
I also added some special cases to test. but somehow It just work fine. If you find any issue just let me know.
cheers,
Axel
import java.lang.Exception;
public class NStackArray{
public int array[];
public int capacity;
public StackMetaData stacks[];
public int numberStacks;
public NStackArray(int nStacks){
this.capacity = nStacks; // by the fault the capacity will only hold 1 element for each stack.
this.array = new int[this.capacity];
this.numberStacks = nStacks;
this.initStacks();
}
public NStackArray(int initCapacity,int nStacks){
if((initCapacity%nStacks)==0){
this.capacity = initCapacity;
}else{
this.capacity = initCapacity + (nStacks - (initCapacity%nStacks));
}
this.array = new int[this.capacity];
this.numberStacks = nStacks;
this.initStacks();
}
private void initStacks(){
int stackSize = this.capacity/this.numberStacks;
this.stacks = new StackMetaData[this.numberStacks];
this.array = new int[this.capacity];
int initStartIndex = stackSize/-1;
int initTopIndex = (stackSize/-1) -1;
int initEndIndex =0;
for(int i = 0; i<this.stacks.length; i++){
initStartIndex+= stackSize;
initTopIndex += stackSize; // is TopIndex < startIndex Then Stack is empty
initEndIndex += stackSize;
this.stacks[i] = new StackMetaData();
this.stacks[i].startIndex = initStartIndex;
this.stacks[i].topIndex = initTopIndex;
this.stacks[i].endIndex = initEndIndex;
}
}
public void resizeStack(){
this.capacity *=this.numberStacks; // grows by the number stacks
//System.out.println("Seziing to " + this.capacity + " for No Stacks: " + this.numberStacks);
StackMetaData tmp[] = new StackMetaData[this.numberStacks];
int tmpStacks[] = new int[this.capacity];
int stackSize = this.capacity/this.numberStacks;
int initStartIndex = stackSize/-1;
int initEndIndex = 0;
for(int i = 0; i< tmp.length; i++)
{
initStartIndex+= stackSize;
initEndIndex += stackSize;
tmp[i] = new StackMetaData();
tmp[i].startIndex = initStartIndex;
tmp[i].endIndex = initEndIndex;
int temporalIndex = tmp[i].startIndex;
for(int index = this.stacks[i].startIndex; index <= this.stacks[i].topIndex; index++){
tmpStacks[temporalIndex++] = this.array[index];
}
tmp[i].topIndex = --temporalIndex; // if topIndex < start Index then Stack is empty
}
this.stacks = tmp;
this.array = tmpStacks;
}
public void push(int stackIndex, int value)throws Exception{
if(stackIndex < 0 || stackIndex >= this.numberStacks){
throw new Exception("Stack Out of Bounds Exception");
}
if(this.stacks[stackIndex].topIndex >= this.stacks[stackIndex].endIndex -1)
{
this.resizeStack();
}
this.array[++this.stacks[stackIndex].topIndex] = value;
}
public int pop(int stackIndex)throws Exception{
if(stackIndex < 0 || stackIndex >= this.numberStacks){
throw new Exception("Stack Out of Bounds Exception");
}
if(this.stacks[stackIndex].topIndex >= this.stacks[stackIndex].startIndex){
int index = this.stacks[stackIndex].topIndex--;
int value = this.array[index];
this.array[index] = 0;
return value;
}else{
return -666; // or maybe return just null or an Exception
}
}
public int peek(int stackIndex)throws Exception{
if(stackIndex < 0 || stackIndex > this.numberStacks){
throw new Exception("Stack Out of Bounds Exception");
}
if(this.stacks[stackIndex].topIndex >= this.stacks[stackIndex].startIndex){
return this.array[this.stacks[stackIndex].topIndex];
}else{
return -666; // or maybe return just null or an Exception
}
}
public boolean isEmpty(int stackIndex)throws Exception{
if(stackIndex < 0 || stackIndex >= this.numberStacks){
throw new Exception("Stack Out of Bounds Exception");
}
return this.stacks[stackIndex].topIndex < this.stacks[stackIndex].startIndex;
}
public int size(int stackIndex)throws Exception{
if(stackIndex < 0 || stackIndex >= this.numberStacks){
throw new Exception("Stack Out of Bounds Exception");
}
if(this.isEmpty(stackIndex))return 0;
else{
return this.stacks[stackIndex].topIndex - this.stacks[stackIndex].startIndex + 1;
}
}
public void printInfo() throws Exception
{
System.out.println("Number Stacks: " + this.numberStacks);
for(int i =0; i < this.stacks.length; i++){
System.out.println("STACK ID: " + (i+1));
System.out.println("Size: " + this.size(i));
for(int index = this.stacks[i].startIndex; index <= this.stacks[i].topIndex; index++){
System.out.print(this.array[index] + " -> " );
}
System.out.println("");
}
for(int i = 0; i<this.array.length; i++){
System.out.print(this.array[i] + " -> " );
}
System.out.println("");
}
class StackMetaData
{
public int startIndex;
public int topIndex;
public int endIndex;
//public int size; // topIndex -startIndex;
}
public static void main(String [] args){
try{
NStackArray stack = new NStackArray(3);
stack.printInfo();
for(int i = 1; i< 5; i++){
stack.push(0,i*1);
stack.push(1,i*2);
stack.push(2,i*3);
stack.printInfo();
}
stack.printInfo();
for(int i = 1; i< 5; i++){
System.out.println("peek(0)" + stack.peek(0));
System.out.println("peek(1)" + stack.peek(1));
System.out.println("peek(2)" + stack.peek(2));
//stack.printInfo();
}
stack.printInfo();
for(int i = 1; i< 5; i++){
System.out.println("POP(0)" + stack.pop(0));
System.out.println("POP(1)" + stack.pop(1));
System.out.println("POP(2)" + stack.pop(2));
stack.printInfo();
}
System.out.println("End**");
}catch(Exception ex){
ex.printStackTrace();
}
}
}
Output:
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 16, 2013mafafito@mafafito-Aspire-4752:~/programming$ gcc microsoft.c -o micro
mafafito@mafafito-Aspire-4752:~/programming$ ./micro
aaBBccdefgZzO