ramprasad85
BAN USERUsing an array will make space complexity O(n)
Unless specified by the interviewer, we should try to give O(1) space complexity solution I think...
Hi,
I think usually in an interview when they say list, they usually mean singly linked list, not doubly linked list. There are very few interview question around doubly linked list, in which case they would explicitly mention it as doubly linked list.
Now a days we also see multiple lifts in a building. Lift A stops only at G,2,4,6,8...
while B stops at G, 1, 3, 5, 7..... to reduce the time taken to reach.
visual studio>edit>advanced>format selection
public int min2(int[] mouse, int[] holes) {
if (mouse == null  holes == null)
return 1;
int lenM = mouse.length;
int lenH = holes.length;
if (lenM > lenH)
return 1;
Arrays.sort(mouse);
Arrays.sort(holes);
int[][] DP = new int[lenM][lenH];
DP[0][0] = Math.abs(mouse[0]  holes[0]);
int min = DP[0][0];
for (int i = 0; i < lenH; i++) {
DP[0][i] = min = Math.min(min, Math.abs(mouse[0]  holes[i]));
}
for (int i = 1; i < lenM; i++) {
DP[i][i] = Math.max(DP[i  1][i  1], Math.abs(mouse[i]  holes[i]));
}
for (int i = 1; i < lenM; i++) {
for (int j = i + 1; j < lenH; j++) {
DP[i][j] = Math.min(DP[i][j  1],
Math.max(DP[i  1][j  1], Math.abs(mouse[i]  holes[j])));
}
}
return DP[lenM  1][lenH  1];
}

ramprasad85
February 08, 2015 Thanks but its impossible to go through your unformatted code!!!!!
I'll format it for you :)
import java.util.Scanner;
public class Mice {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int T = Integer.parseInt(input.nextLine());
String[] nm;
int n;
int m;
int[] mices;
int[] holes;
int[] distances;
int[] differences;
String[] miceStr;
String[] holesStr;
for(int i = 0; i < T; i++) {
nm = input.nextLine().split(" ");
n = Integer.parseInt(nm[0]);
m = Integer.parseInt(nm[1]);
mices = new int[n];
holes = new int[m];
distances = new int[n];
differences = new int[m];
miceStr = input.nextLine().split(" ");
for(int j = 0; j < miceStr.length; j++) {
mices[j] = Integer.parseInt(miceStr[j]);
}
holesStr = input.nextLine().split(" ");
for(int j = 0; j < holesStr.length; j++) {
holes[j] = Integer.parseInt(holesStr[j]);
}
for(int mice = 0; mice < mices.length; mice++) {
for(int hole = 0; hole < holes.length; hole++) {
differences[hole] = getDifference(mices[mice], holes[hole]);
}
distances[mice] = getMin(differences);
}
System.out.println(getMax(distances));
}
}
private static int getDifference(int i, int j) {
if(i < j)
return j  i;
else
return i  j;
}
private static int getMin(int[] num) {
int min = 0;
if(num.length > 0)
min = num[0];
if(num.length > 1){
for(int i = 1; i < num.length; i++) {
if(num[i] < min)
min = num[i];
}
}
return min;
}
private static int getMax(int[] num) {
int max = 0;
if(num.length > 0)
max = num[0];
if(num.length > 1){
for(int i = 1; i < num.length; i++) {
if(num[i] > max)
max = num[i];
}
}
return max;
}
}

ramprasad85
February 08, 2015 Thanks
But going through the code to find the logic is always painful
It will save time if the logic is put in a comment...
I think this is more of a design question than a coding one.
We can think about
 reducing the response time of the server
 by using a distributed system to share the load based on geography
 by using a central server but many caching servers at various geographical locations
 what would be the right database design
 reducing the storage space
 database design
 backup and failover
 security issues
 prevent people from creating links to whatever
 handling old/obsolete urls
 may be, while creating the url we can say to the user that it will be deleted if the url is never used for more than say 3 years
 may be allow the user to login and delete unused ones
 how a company like bit.ly is going to make profit out of this service! how can that be improved
 user friendly things
 browser plugins to speed up creating links (youtube sharing has an option to create short urls)
 giving report to user about the usage statistics
 mobile app to create urls quickly
.....
Can you explain some more.
Possibly with a simple example?
Here is a piece of code which finds all the sequences for the given character. it should be easy to extend this to print the longest sequence.
#include <iostream>
using namespace std;
static const int width=4;
static const int height=4;
char getMax(char max, char ret)
{
return max>ret?max:ret;
}
char findlen(int i, int j, char c, char matrix[width][height])
{
//The following can be also be put in a for loop.
char max = c;
//topleft
if(i>0 && j>0 && matrix[i1][j1]==(c+1))
max = getMax(max, findlen(i1, j1, c+1, matrix));
//top
if(j>0 && matrix[i][j1]==(c+1))
max = getMax(max, findlen(i, j1, c+1, matrix));
//topright
if(i<(width1) && j>0 && matrix[i+1][j1]==(c+1))
max = getMax(max, findlen(i+1, j1, c+1, matrix));
//right
if(i<(width1) && matrix[i+1][j]==(c+1))
max = getMax(max, findlen(i+1, j, c+1, matrix));
//bottomright
if(i<(width1) && j<(height1) && matrix[i+1][j+1]==(c+1))
max = getMax(max, findlen(i+1, j+1, c+1, matrix));
//bottom
if(i<(height1) && matrix[i][j+1]==(c+1))
max = getMax(max, findlen(i, j+1, c+1, matrix));
//bottomleft
if(i<(width1) && j<(height1) && matrix[i1][j+1]==(c+1))
max = getMax(max, findlen(i1, j+1, c+1, matrix));
//left
if(i>0 && matrix[i1][j]==(c+1))
max = getMax(max, findlen(i1, j, c+1, matrix));
return max;
}
enum {a='a',b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z};
int main()
{
char matrix[width][height]=
{
{a,b,c,d},
{l,m,n,e},
{k,p,o,f},
{j,i,h,g}
};
char tofind = a;//specify the required character here
for(int I=0;I<width;I++)
{
for(int J=0;J<height;J++)
{
if(matrix[I][J] == tofind)
cout<<(findlen(I, J, tofind, matrix)  tofind + 1)<<endl;
}
}
return 0;
}
Will print 16
 ramprasad85 December 23, 2014I think while dealing with linked lists the 'next' should be of pointer type. In this version, just have a temporary pointer and a dummy node and splice the data.
#include <stdio.h>
#include <stdlib.h>
typedef struct _node
{
int data;
struct _node *next;
}Node;
Node* newnode(int value)
{
Node *n = (Node*)malloc(sizeof(Node));
if(n == NULL)
return NULL;
n>data = value;
n>next = NULL;
return n;
}
void printSL(Node* node)
{
while(node != NULL)
{
printf("%d ", node>data);
node= node>next;
}
printf("\n");
}
Node* mergeSL(Node *f, Node *s)
{
Node dummy, *tail;
dummy.next = NULL;
tail= &dummy;
while(1)
{
if(f == NULL){
tail>next = s;
break;
}
if(s == NULL){
tail>next = f;
break;
}
if(f>data <= s>data)
{
tail>next = f;
f = f>next;
}
else
{
tail>next=s;
s = s>next;
}
tail=tail>next;
}
return dummy.next;
}
int main()
{
Node *first = newnode(0);
Node *temp = first;
for(int i=1; i<10; i++)
{
temp = temp>next = newnode(i*2);
}
Node *second = newnode(1);
temp = second;
for(int i=1; i<15; i++)
{
temp = temp>next = newnode(i*2 + 1);
}
printSL(first);
printSL(second);
printSL(mergeSL(first, second));
}

ramprasad85
December 22, 2014 Open Chat in New Window
For showing the places and routes, weighted directed graph may be the algorithm. Also for finding the shortest path in reasonable amount of time, they will also need to store an approximate angle between the nodes or directly the latitudes and altitudes in the nodes.
 ramprasad85 February 08, 2015For showing the satellite image (Google Earth) I think they will use JPEG2000 kind of a file format to store the actual satellite image. JPEG2000 allows storing a huge image as tiles and each tile will have images at increasing quality levels (known as streaming). Only if the user zooms in, the next level of the image will be downloaded, this will save time and bandwidth for user and server.