## Snapdeal Interview Question for Senior Software Development Engineers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

``````def preprocess(file, data):
with open(file, 'r') as datafile:
(date, city, temp) = line.split()
print 'Adding %s:%s to %s' % (city, temp, date)
if date in data.keys():
data[date][city] = temp
else:
data[date] = {city: temp}

def find_temp_city_date(date, city, data):
try:
return data[date][city]
except KeyError:
raise Exception("Date or City not in database")

def find_hottest_five(date, data):
top_five = [(0, "") , (0, ""), (0, ""), (0, ""), (0, "")]
for city, temp in data[date].items():
if temp > top_five[0][0]:
top_five[0] = (temp, city)
for t in range(len(top_five) - 1):
if top_five[t][0]  > top_five[t+1][0]:
(top_five[t], top_five[t+1]) = (top_five[t+1], top_five[t])
print "%s" % top_five
for d in reversed(top_five):
print "(%s, %s)" % (d[0], d[1])

data = ('09-11-2015 Delhi 45\n'
'09-11-2015 Guwahati 51\n'
'09-11-2015 Kolkata 42\n'
'09-11-2015 Bombay 35\n'
'09-11-2015 Chandigarh 41\n'
'09-11-2015 NewYork 25\n'
'09-11-2015 SanFrancisco 40\n'
'09-11-2015 Shanghai 23\n'
'09-11-2015 Junea 20\n'
'09-11-2015 Toronto 21\n'
'10-11-2015 Delhi 45\n'
'10-11-2015 Guwahati 51\n'
'10-11-2015 Kolkata 42\n'
'10-11-2015 Bombay 35\n'
'10-11-2015 Chandigarh 40\n'
'10-11-2015 NewYork 25\n'
'10-11-2015 SanFrancisco 40\n'
'10-11-2015 Shanghai 23\n'
'10-11-2015 Junea 20\n'
'11-11-2015 Toronto 21\n'
'11-11-2015 Delhi 45\n'
'11-11-2015 Guwahati 51\n'
'11-11-2015 Kolkata 42\n'
'11-11-2015 Bombay 35\n'
'11-11-2015 Chandigarh 40\n'
'11-11-2015 NewYork 25\n'
'11-11-2015 SanFrancisco 40\n'
'11-11-2015 Shanghai 23\n'
'11-11-2015 Junea 20\n'
'11-11-2015 Toronto 21\n')

with open("a.data", 'w') as f:
f.write(data)``````

\$ python city_temp.py
[('40', 'SanFrancisco'), ('41', 'Chandigarh'), ('42', 'Kolkata'), ('45', 'Delhi'), ('51', 'Guwahati')]
(51, Guwahati)
(45, Delhi)
(42, Kolkata)
(41, Chandigarh)
(40, SanFrancisco)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

I stated O(N) because I am considering 5 to a constant. I do not sort the whole list but for every city, I will do at most 5 operations to place it in the sorted list of top 5.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

use map reduce

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();

City city = new City(str.nextToken(), str.nextToken(), str.nextToken());
}

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);
map.put(city.date, result);

}else{

List<City> resul = new ArrayList<City>();
map.put(city.date, resul);

}

}

return map;

}

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;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();

City city = new City(str.nextToken(), str.nextToken(), str.nextToken());
}

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);
map.put(city.date, result);

}else{

List<City> resul = new ArrayList<City>();
map.put(city.date, resul);

}

}

return map;

}

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;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use HashMap to store date.toString as key, So we can have fast lookup based on date.
instead of storing (city,temp) pair in hashmap use treesort / double end dequeue / priority queue. Now insert will be done in O(c + nlogn), both queries will be address in O(c + n)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.