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];
}
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;
}
}
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;
//top-left
if(i>0 && j>0 && matrix[i-1][j-1]==(c+1))
max = getMax(max, findlen(i-1, j-1, c+1, matrix));
//top
if(j>0 && matrix[i][j-1]==(c+1))
max = getMax(max, findlen(i, j-1, c+1, matrix));
//top-right
if(i<(width-1) && j>0 && matrix[i+1][j-1]==(c+1))
max = getMax(max, findlen(i+1, j-1, c+1, matrix));
//right
if(i<(width-1) && matrix[i+1][j]==(c+1))
max = getMax(max, findlen(i+1, j, c+1, matrix));
//bottom-right
if(i<(width-1) && j<(height-1) && matrix[i+1][j+1]==(c+1))
max = getMax(max, findlen(i+1, j+1, c+1, matrix));
//bottom
if(i<(height-1) && matrix[i][j+1]==(c+1))
max = getMax(max, findlen(i, j+1, c+1, matrix));
//bottom-left
if(i<(width-1) && j<(height-1) && matrix[i-1][j+1]==(c+1))
max = getMax(max, findlen(i-1, j+1, c+1, matrix));
//left
if(i>0 && matrix[i-1][j]==(c+1))
max = getMax(max, findlen(i-1, 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));
}
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.