Snapdeal Interview Question
Senior Software Development EngineersCountry: India
Interview Type: In-Person
it cannot be O(N).
It is O(N*logN), because when you get "an unsorted list", you should apply some sorting algorithm. The fastest sorting algorithms (merge sort, etc.) have complexity O(N*logN) in average and worst cases.
Of course, N is the number of cities in the database.
This is assuming that all the dates are in order like the example and all dates are there (no gaps).
Read the first and last lines of each file. There are you have a range of all dates. Take the total number of days in divide the total file size by the total number of days this will give you the position to set the pointer at for a particular date.
Also assuming that we have the same number of cities for each date, take that particular date block with each city's name and store it in a we array.
To get a temperature for particular city do a binary search found the city name and get the temperature.
To get the the average of the top five cities do up merge sort sort by temperature lowest to highest get the top five indexes and take the average of that.
O (log n) solution
c# implementation.
using System;
using System.Collections.Generic;
using System.Linq;
namespace Hash3Columns {
using CustomHashTable = Dictionary<System.DateTime, Dictionary<string, int>>;
class Program {
static CustomHashTable _database = new CustomHashTable();
private static string GetTemperature( string city, DateTime date ) {
try {
return _database[ date ][ city ].ToString();
}
catch (KeyNotFoundException) {
return "No data in database";
}
}
private static string[] GetHottestCities( DateTime date, int n ) {
return _database[ date ]
.OrderByDescending( x => x.Value )
.Take( n )
.Select( y => y.Key )
.ToArray();
}
private static string[] GetColdestCities( DateTime date, int n ) {
return _database[ date ]
.OrderBy( x => x.Value )
.Take( n )
.Select( y => y.Key )
.ToArray();
}
static void Main(string[] args)
{
// code for testing here
}
}
}
Create a City implementing Comparable interface
public class City implements Comparable<City>{
String name;
String date;
String temp;
public City(String name, String date, String temp) {
// TODO Auto-generated constructor stub
this.name = name;
this.date = date;
this.temp = temp;
}
@Override
public int compareTo(City o) {
if(Integer.parseInt(this.temp)<Integer.parseInt(o.temp))
return 1;
else if(Integer.parseInt(this.temp)>Integer.parseInt(o.temp))
return -1;
else
return 0;
}
}
Then Create a City Map Builder Class as given below and write methods:::
public class CityBuilder {
List<City> cities;
Map<String, List<City>> map = new HashMap<String, List<City>>();
public CityBuilder(List<City> cities) {
// TODO Auto-generated constructor stub
this.cities = cities;
map = cityTemperatureMap(cities);
}
public List<City> listCities(BufferedReader br) throws IOException{
List<City> result = new ArrayList<City>();
while(br.readLine()!=null){
StringTokenizer str = new StringTokenizer(br.readLine());
City city = new City(str.nextToken(), str.nextToken(), str.nextToken());
result.add(city);
}
return result;
}
public Map<String, List<City>> cityTemperatureMap(List<City> list){
for(City city:list){
boolean b = map.containsKey(city.date);
if(b==true){
List<City> result = map.get(city.date);
result.add(city);
map.put(city.date, result);
}else{
List<City> resul = new ArrayList<City>();
resul.add(city);
map.put(city.date, resul);
}
}
return map;
}
public List<City> listForADate(String date){
return map.get(date);
}
public int getTemperature(String name, String date){
List<City> list = map.get(date);
for(City c:list){
if(c.name.equals(name)){
return Integer.parseInt(c.temp);
}
}
return -1;
}
}
Create a City implementing Comparable interface
public class City implements Comparable<City>{
String name;
String date;
String temp;
public City(String name, String date, String temp) {
// TODO Auto-generated constructor stub
this.name = name;
this.date = date;
this.temp = temp;
}
@Override
public int compareTo(City o) {
if(Integer.parseInt(this.temp)<Integer.parseInt(o.temp))
return 1;
else if(Integer.parseInt(this.temp)>Integer.parseInt(o.temp))
return -1;
else
return 0;
}
}
Then Create a City Map Builder Class as given below and write methods:::
public class CityBuilder {
List<City> cities;
Map<String, List<City>> map = new HashMap<String, List<City>>();
public CityBuilder(List<City> cities) {
// TODO Auto-generated constructor stub
this.cities = cities;
map = cityTemperatureMap(cities);
}
public List<City> listCities(BufferedReader br) throws IOException{
List<City> result = new ArrayList<City>();
while(br.readLine()!=null){
StringTokenizer str = new StringTokenizer(br.readLine());
City city = new City(str.nextToken(), str.nextToken(), str.nextToken());
result.add(city);
}
return result;
}
public Map<String, List<City>> cityTemperatureMap(List<City> list){
for(City city:list){
boolean b = map.containsKey(city.date);
if(b==true){
List<City> result = map.get(city.date);
result.add(city);
map.put(city.date, result);
}else{
List<City> resul = new ArrayList<City>();
resul.add(city);
map.put(city.date, resul);
}
}
return map;
}
public List<City> listForADate(String date){
return map.get(date);
}
public int getTemperature(String name, String date){
List<City> list = map.get(date);
for(City c:list){
if(c.name.equals(name)){
return Integer.parseInt(c.temp);
}
}
return -1;
}
}
If the cities are set list for example of Darla only 50 cities. You you could read the first line of the fall and the last line of the file it will give you a range of dates. Take this range and get a number of days and you can take you take the total file size divided by the number of days. These calculations you could get each date group by block.
Place the block into an array and do a merge sort on the array this will give you an index of each cities position for future searches. Get date block plus cities index to get each cities temperature for that day if cities appear in same order in each date block. If not search for city name using binary search on each block.
For each temperature you that the date block, merge sort by lowest temperature and then get the top five indexes and then get an average of that.
O (log n) running time.
Since the data query is by date, my first instinct is to keep the data as a hash table keyed by date, and then keyed by city.
hash = {date: {city: temp}}
Getting the temp for a city on a particular date is in the avg case a O(1) hash lookup and another O(1) hash lookup in the city.
For finding the top 5, we would first get the data by date first. This will give us a unsorted list of {city: temp} value pairs. As we process the list, we can keep a list of top 5 values (min or max). If the new value is <//> of the min value, then we swap out fhe min value. This can be optimized by keeping this 5 array in sorted order.
Instead of doing any sorting on this array, since this is just a consta number, we can do a bubble of the value up until it is in the right place. e.g. the new number ifs first swapped with top_five[0] and then bubbled up until is it between top_filve[i], top_five[i+2] where top_five[i] < new_val < top_five[i+2]
So every new value can potentially result in a reordering of the top five list.
The complexity will be O(N * 1) where N is the number of cities. Worst case is
that the numbers are read in sorted order so that each data swaps out the old so it will process the top five. Best case is it will again O(N) where only the first 5 cities cause a swap out and after that no swap happens.
$ python city_temp.py
- haroud December 02, 2015Adding Delhi:45 to 09-11-2015
Adding Guwahati:51 to 09-11-2015
Adding Kolkata:42 to 09-11-2015
Adding Bombay:35 to 09-11-2015
Adding Ahmedabad:35 to 09-11-2015
Adding Chandigarh:41 to 09-11-2015
Adding NewYork:25 to 09-11-2015
Adding SanFrancisco:40 to 09-11-2015
Adding Shanghai:23 to 09-11-2015
Adding Junea:20 to 09-11-2015
Adding Toronto:21 to 09-11-2015
Adding Delhi:45 to 10-11-2015
Adding Guwahati:51 to 10-11-2015
Adding Kolkata:42 to 10-11-2015
Adding Bombay:35 to 10-11-2015
Adding Ahmedabad:35 to 10-11-2015
Adding Chandigarh:40 to 10-11-2015
Adding NewYork:25 to 10-11-2015
Adding SanFrancisco:40 to 10-11-2015
Adding Shanghai:23 to 10-11-2015
Adding Junea:20 to 10-11-2015
Adding Toronto:21 to 11-11-2015
Adding Delhi:45 to 11-11-2015
Adding Guwahati:51 to 11-11-2015
Adding Kolkata:42 to 11-11-2015
Adding Bombay:35 to 11-11-2015
Adding Ahmedabad:35 to 11-11-2015
Adding Chandigarh:40 to 11-11-2015
Adding NewYork:25 to 11-11-2015
Adding SanFrancisco:40 to 11-11-2015
Adding Shanghai:23 to 11-11-2015
Adding Junea:20 to 11-11-2015
Adding Toronto:21 to 11-11-2015
[('40', 'SanFrancisco'), ('41', 'Chandigarh'), ('42', 'Kolkata'), ('45', 'Delhi'), ('51', 'Guwahati')]
(51, Guwahati)
(45, Delhi)
(42, Kolkata)
(41, Chandigarh)
(40, SanFrancisco)